基于屬性分類的出港集裝箱箱位分配問題研究

姜 偉，毛詩敏

（浙江師范大學(xué) 工學(xué)院，浙江 金華 321004）

基于屬性分類的出港集裝箱箱位分配問題研究

姜 偉，毛詩敏

（浙江師范大學(xué) 工學(xué)院，浙江 金華 321004）

在對(duì)出港箱按屬性分類并定義組、簇、批的基礎(chǔ)上研究出港集裝箱的箱位分配問題，從優(yōu)化物流輸入環(huán)節(jié)來減少裝船時(shí)的倒垛數(shù)。通過引進(jìn)批的位置變量、組與垛關(guān)系變量和每個(gè)位置的倒垛變量，并以組與垛的關(guān)系、箱位使用原則和狀態(tài)、批的箱量守恒以及不同批間倒垛關(guān)系為約束對(duì)該問題建立非線性整數(shù)規(guī)劃模型，目標(biāo)是實(shí)現(xiàn)裝船時(shí)各街區(qū)箱量均衡、集卡運(yùn)輸距離最短和裝船時(shí)一定發(fā)生倒垛的集裝箱數(shù)最少。利用等價(jià)變換將該模型轉(zhuǎn)化為優(yōu)化軟件可直接求解的線性模型，并實(shí)例驗(yàn)證模型的有效性。

出港集裝箱；屬性分類；箱位分配；集成模型

1 引言

近年來隨著全球化和經(jīng)濟(jì)一體化的快速發(fā)展，國內(nèi)和國際貨物的運(yùn)輸量不斷增長，這種增長趨勢對(duì)為貨物的運(yùn)輸、裝卸、包裝、倉儲(chǔ)、配送及信息管理提供相應(yīng)服務(wù)并保證貨物安全準(zhǔn)時(shí)到達(dá)的物流業(yè)提出了更高的要求。港口作為貨物海陸聯(lián)運(yùn)的樞紐，是物流體系中一個(gè)不可替代的重要節(jié)點(diǎn)。在港口中堆場空間是一種稀缺資源，在集裝箱的貨流量不斷增加的環(huán)境下，如何管理碼頭堆場系統(tǒng)，為每個(gè)集裝箱分配合理的箱位進(jìn)而提高裝卸效率和碼頭服務(wù)水平，成為碼頭管理者和學(xué)術(shù)界關(guān)注的熱點(diǎn)問題。

合理分配出港箱在存入堆場時(shí)的箱位可以提高堆場中集裝箱的裝船效率，從而縮短船的在港時(shí)間。集裝箱堆場箱位分配問題包括兩個(gè)階段，第一階段(宏觀層面)是空間分配階段，用來決策分配到每個(gè)街區(qū)的箱量；第二階段(微觀層面)是具體位置分配階段，用來決策每個(gè)箱的具體箱位(由街區(qū)號(hào)、貝號(hào)、行號(hào)和層號(hào)確定)，使得在提取過程中總倒垛數(shù)最少，所以也將第二階段問題稱為倒垛問題。

對(duì)于第一階段的空間分配問題，Bazzazi等[1]{Bazza-zi,2009#7}使用遺傳算法求解具有不同類型的進(jìn)港箱的空間分配問題，目標(biāo)是街區(qū)間的工作量平衡。徐亞等[2]對(duì)出口箱空間分配問題提出以集卡運(yùn)輸距離最短和工作量平衡為目標(biāo)的多目標(biāo)規(guī)劃模型，并采用改進(jìn)的線性功效系數(shù)法將模型轉(zhuǎn)化為單目標(biāo)整數(shù)規(guī)劃模型進(jìn)行求解。嚴(yán)南南和崔景云[3]以箱區(qū)貝位間作業(yè)量的平衡和龍門吊的使用數(shù)量最小為目標(biāo)建立兩層數(shù)學(xué)模型，確定不同尺寸集裝箱分配到各箱區(qū)貝位中的具體數(shù)量。檀財(cái)茂等[4]從考慮碼頭資源緊缺的角度將堆場空間分配問題分解成兩個(gè)連續(xù)的問題：第一個(gè)問題模型以最大化箱區(qū)的空間利用率來確定箱區(qū)航線配對(duì)組合情況；第二個(gè)問題模型將第一階段已經(jīng)配對(duì)好的航線組合指派到堆場中的具體箱區(qū)。

對(duì)于第二階段的具體位置分配問題，Wan等[5]對(duì)靜態(tài)倒垛問題（當(dāng)一個(gè)貝位的初始堆垛狀態(tài)及集裝箱的提取順序給定時(shí)，如何決策倒垛箱在該貝位中的位置使得提取過程中總倒垛數(shù)最少）首次建立整數(shù)規(guī)劃模型，然后提出多種啟發(fā)式算法驗(yàn)證算法的有效性。徐亞等[6]對(duì)同樣的問題提出啟發(fā)式算法及其改進(jìn)算法，并通過仿真實(shí)驗(yàn)驗(yàn)證算法的有效性。Caserta等[7]首次證明了靜態(tài)倒垛問題是NP難問題。Zehendner和Feillet[8]首次使用基于數(shù)學(xué)規(guī)劃的branch and price方法來解決靜態(tài)倒垛問題。Tang等[9]對(duì)Wan等[5]提出的整數(shù)規(guī)劃模型進(jìn)行改進(jìn)，并提出有效的啟發(fā)式規(guī)則。

本文的主要貢獻(xiàn)在于通過對(duì)出港集裝箱按屬性分類并引入組、簇、批的定義，從一個(gè)新的角度將空間分配問題和具體箱位分配問題這兩個(gè)階段集成起來解決堆場箱位分配問題，從而在物流輸入環(huán)節(jié)控制影響裝船效率的因素。針對(duì)出港集裝箱的箱位分配問題，引進(jìn)與組和批相關(guān)的決策變量，建立非線性0-1整數(shù)規(guī)劃模型來達(dá)到提高裝船效率的目標(biāo)。通過等價(jià)變換，將其轉(zhuǎn)化為線性規(guī)劃模型并利用優(yōu)化軟件CPLEX進(jìn)行有效求解。

2 出港集裝箱的分類及問題描述

集裝箱碼頭為了有效地提高堆場空間利用率，通常采取將多個(gè)集裝箱按垂直方向向上堆垛的方式進(jìn)行堆存。集裝箱的這種堆放方式雖然具有高密度和高空間利用率的特點(diǎn)，但在提箱的過程中有可能產(chǎn)生不必要的倒垛而影響提箱的效率。如果待提取的目標(biāo)箱上面放有其他箱，那么就產(chǎn)生了壓箱。為了要提出該目標(biāo)箱，必須先將壓在其上面的箱暫時(shí)移到其他箱位，這種臨時(shí)的集裝箱移動(dòng)稱為倒垛。堆場中無論任何時(shí)段任何操作都不希望有倒垛發(fā)生，因?yàn)榈苟獠僮鞔蟠蠼档土斯ぷ餍?，增加了操作成本，因此有效減少倒垛數(shù)是集裝箱碼頭操作中另一個(gè)研究熱點(diǎn)。

由于出港集裝箱可以根據(jù)所屬船舶、箱型、到港站、重量級(jí)別等屬性進(jìn)行分類，且所有屬性均相同的出港箱在裝船時(shí)可以相互替換，因此根據(jù)配載計(jì)劃進(jìn)行裝船時(shí)，通過提取屬性相同的箱中壓箱數(shù)最少的箱可以減少倒垛的發(fā)生，提高裝船效率。因此當(dāng)出港箱由外部集卡運(yùn)進(jìn)堆場時(shí)，采用按屬性歸類后再分配其在堆場中箱位的方法可以從物流輸入的源頭上控制裝船的倒垛量。假設(shè)所有出港箱的箱型都相同，圖1為出港箱根據(jù)所屬船舶、到港站、重量級(jí)別分類的示意圖。將要裝上同一條船的出港箱定義為一組(group)。為了操作方便和避免倒垛，在實(shí)際的堆場操作中，不同船的箱不會(huì)混放到同一垛中，因此不同組的箱不能放在同一垛中；然后對(duì)同一組中的箱根據(jù)到港站的不同進(jìn)行分類，將同組且到港站相同的箱定義為一簇(family)；最后對(duì)同一簇中的箱根據(jù)重量級(jí)別的不同進(jìn)行分類，將同簇中重量級(jí)別相同的箱定義為一批(batch)。根據(jù)上述定義，同批中的箱由于屬性完全相同，即使放在同一垛中也不會(huì)發(fā)生倒垛，因此倒垛操作只能發(fā)生在同組但不同批的箱之間。對(duì)出港集裝箱引入批的概念后，不需要決策某個(gè)具體箱是否放在某個(gè)箱位，而只需決策某一批中的箱是否放在某個(gè)箱位。因此，通過引入與批相關(guān)的決策變量后，堆場箱位分配問題中用來決策每個(gè)箱位置的位置變量就會(huì)明顯減少，便于建模求解。

根據(jù)集裝箱船的基本配載原則可以確定不同批的出港集裝箱裝船時(shí)的先后順序。首先，為了避免在集裝箱船上發(fā)生倒垛，要求集裝箱船上到港站遠(yuǎn)的箱不能壓在到港站近的箱上面，因此裝船時(shí)要先裝到港站遠(yuǎn)的箱再裝到港站近的箱；其次，為了保證集裝箱船的穩(wěn)定性，配載時(shí)要將重量級(jí)別高(重)的箱放在船的下面，因此裝船時(shí)要先裝重量級(jí)別高的箱再裝重量級(jí)別低的箱。

根據(jù)上面出港集裝箱的分類及不同類別集裝箱的裝船順序，基于屬性分類的出港集裝箱箱位分配問題描述如下：在某一給定的時(shí)段，堆場的初始堆垛狀態(tài)非空且已知，該時(shí)段內(nèi)外部集卡向堆場運(yùn)進(jìn)出港箱的數(shù)量已知，這些出港箱在運(yùn)進(jìn)堆場時(shí)其所屬船舶、到港站和重量級(jí)別等信息便可以獲得。該時(shí)段內(nèi)到港的船泊數(shù)量及?？康牟次灰阎⑶颐織l船的?？坎次慌c堆場中每個(gè)街區(qū)的距離給定。根據(jù)每個(gè)箱的屬性可以按照上面的分類原則將其分批。我們的問題就是要決策分批后的集裝箱在堆場中的具體箱位，目標(biāo)是各街區(qū)的工作量均衡、裝船時(shí)集卡在街區(qū)和船間運(yùn)輸?shù)目偩嚯x最短和發(fā)生倒垛的集裝箱數(shù)最少，從而保證裝船效率。

圖1 出港集裝箱按屬性分類示意圖

3 數(shù)學(xué)模型

根據(jù)出港箱的分類及組、簇和批的概念可知，倒垛只能發(fā)生在放入同一垛中的同組但不同批的箱之間，因此在箱位分配問題的模型中決策變量只需考慮到批而無需再具體到每個(gè)箱，這樣會(huì)使決策變量的數(shù)量大幅減少而容易求解。首先引進(jìn)與組和批相關(guān)的決策變量，對(duì)基于屬性分類的出港集裝箱箱位分配問題建立非線性0-1整數(shù)規(guī)劃模型，然后通過等價(jià)變換將該模型轉(zhuǎn)化為優(yōu)化軟件CPLEX可直接求解的線性規(guī)劃模型。

3.1 模型參數(shù)

為了建模方便以及便于比較對(duì)應(yīng)于同一條船的兩個(gè)到港站的遠(yuǎn)近及兩個(gè)重量級(jí)別的高低，首先將所考慮的集裝箱船從1開始順次編號(hào)，然后分別順次對(duì)每條船的所有到港站按從近到遠(yuǎn)的順序從1開始編號(hào)，最后分別順次對(duì)每條船每個(gè)到港站的所有重量級(jí)別按從低到高的順序從1開始編號(hào)，并給出如下模型參數(shù)：

j：船的編號(hào)；

J：船的集合；

|J|：船的總數(shù)；

b：堆場中街區(qū)的編號(hào)；

B：堆場中街區(qū)的集合；

|B|：堆場中街區(qū)的總數(shù)；

s：堆場中垛的編號(hào)；

S：堆場中垛的集合；

|S|：堆場中垛的總數(shù)；

Nb：街區(qū)b中垛的集合；

p：堆場中層的編號(hào)；

P：堆場中層的集合；

|P|：堆場中允許的最高層數(shù)；

w：重量級(jí)別的編號(hào)；

Wj：船j的箱對(duì)應(yīng)的所有重量級(jí)別的集合；

d：到港站的編號(hào)；

Dj：船j的箱對(duì)應(yīng)的所有到港站的集合；

|Dj|：船j的箱對(duì)應(yīng)的所有到港站的總數(shù)；

Cwd：由外部卡車運(yùn)到堆場重量級(jí)別為w，到港站為d的出港箱數(shù)量；

Iwd：初始狀態(tài)時(shí)，堆場中重量級(jí)別為w，到港站為d的出港箱數(shù)量；

Ajb：船j與街區(qū)b之間的距離；

M：無限大的數(shù)；

δ1：目標(biāo)中與各街區(qū)的工作量均衡相關(guān)的權(quán)重；

δ2：目標(biāo)中與集卡的運(yùn)輸距離最短相關(guān)的權(quán)重；

δ3：目標(biāo)中與倒垛數(shù)最少相關(guān)的權(quán)重。

3.2 決策變量

基于屬性分類的出港集裝箱的箱位分配問題中的決策變量定義如下：

3.3 模型

根據(jù)上述定義的模型參數(shù)和決策變量，建立基于屬性分類的出港集裝箱箱位分配問題的模型(IP)如下：

在上述數(shù)學(xué)模型中，目標(biāo)函數(shù)（1）包含三部分：第一項(xiàng)表示堆場中具有最大工作量的街區(qū)與具有最小工作量的街區(qū)間的工作量之差，最小化這個(gè)差值來實(shí)現(xiàn)街區(qū)間的工作量均衡，這里街區(qū)的工作量對(duì)應(yīng)該街區(qū)的總箱量；第二項(xiàng)表示將所有出港箱裝上船時(shí)集卡的運(yùn)輸距離之和；第三項(xiàng)表示在裝船時(shí)一定發(fā)生倒垛的集裝箱總數(shù)。因此目標(biāo)函數(shù)（1）實(shí)現(xiàn)在裝船時(shí)作業(yè)分布均勻、內(nèi)部集卡運(yùn)行距離最短和發(fā)生倒垛的集裝箱數(shù)最少。約束（2）-（4）給出組與垛的關(guān)系。約束（2）表示任意兩個(gè)組（船）的箱不混放在同一垛位中。約束（3）保證若s垛中放組（船）j的箱則zjs=1。約束（4）保證若zjs=0則s垛上一定不放組(船)j的箱。約束（5）-（7）為箱位使用原則和堆垛狀態(tài)約束。約束（5）表示將堆場的初始狀態(tài)賦給變量 xwdsp，即若=1必有 xwdsp=1。約束（6）確保一個(gè)箱位至多只能放一個(gè)集裝箱。約束（7）表示堆場中集裝箱不能懸空，即若s垛p層有箱則s垛p-1層必有箱。約束（8）表示批的箱量守恒約束。即堆場中某一批的集裝箱總數(shù)等于初始狀態(tài)時(shí)該批的集裝箱數(shù)加上由外部卡車運(yùn)到堆場中的相同批的集裝箱總數(shù)。約束（9）和（10）為不同批間倒垛關(guān)系約束。約束（9）根據(jù)船的基本配載要求給出同組但不同簇間箱的倒垛關(guān)系。其中表示被放在s垛i層且要裝上船j的集裝箱到港站編號(hào)，而表示被放在s垛p層且要裝上船j的集裝箱的到港站編號(hào)。如果要裝上集裝箱船j且重量級(jí)別為w，到港站為d的集裝箱在到達(dá)堆場時(shí)被存放在了s垛p層（即）且存放在s垛i層箱的到港站比存放在s垛p層箱的到港站遠(yuǎn)（即），此時(shí)約束（9）變成 |Dj|ysp≥1，這迫使ysp=1，即在物流輸入環(huán)節(jié)，當(dāng)為將要裝上同一條船的兩個(gè)集裝箱分配存儲(chǔ)位置時(shí)，如果將到港站遠(yuǎn)的集裝箱放在了到港站近的集裝箱下方，則在裝船時(shí)由于要先裝到港站遠(yuǎn)的箱，這個(gè)到港站近的集裝箱一定會(huì)發(fā)生倒垛；如果要裝上集裝箱船j且重量級(jí)別為w，到港站為d的集裝箱在到達(dá)堆場時(shí)被存放在了s垛p層（即）且存放在s垛i層箱的到港站比被存放在s垛 p 層箱的到港站近（即0），于是約束（9）變成 |Dj|ysp≥Ne（其中 Ne是一個(gè)負(fù)數(shù)），此時(shí)無論ysp取0還是1約束（9）恒成立，目標(biāo)中最小化總倒垛數(shù)會(huì)使ysp=0，即在物流輸入環(huán)節(jié)當(dāng)為將要裝上同一條船的兩個(gè)集裝箱分配存儲(chǔ)位置時(shí)，如果將到港站近的集裝箱放在了到港站遠(yuǎn)的集裝箱的下方，則在裝船時(shí)由于要先裝到港站遠(yuǎn)的箱，這個(gè)到港站遠(yuǎn)的集裝箱不會(huì)發(fā)生倒垛；如果要裝上集裝箱船j且重量級(jí)別為w，到港站為d的集裝箱在到達(dá)堆場時(shí)被存放在了s垛p層（即）且存放在s垛i層箱的到港站與存放在s垛p層箱的到港站相同（即），于是約束（9）變成|Dj|ysp≥0，此時(shí)無論ysp取0還是1約束（9）恒成立，目標(biāo)中最小化總倒垛數(shù)會(huì)使ysp=0，即在物流輸入環(huán)節(jié)，當(dāng)為將要裝上同一條船的兩個(gè)集裝箱分配存儲(chǔ)位置時(shí)，如果將到港站相同的箱放在了同一垛中，則放在較高層的箱不會(huì)發(fā)生倒垛；如果在物流輸入環(huán)節(jié)沒有箱被存放在s垛p層（即）約束（9）變成這里由于，于是 ysp無論取0還是1約束（9）恒成立，目標(biāo)中最小化總倒垛數(shù)會(huì)使ysp=0，此時(shí)約束（9）保證當(dāng)某位置沒有集裝箱時(shí)就沒有倒垛發(fā)生。約束（10）根據(jù)船的基本配載要求給出同簇但不同批間箱的倒垛關(guān)系。由于約束（10）中d∈Dj，對(duì)于集裝箱船j某個(gè)給定的到港站d，表示被放在s垛i層且要裝上船j到港站為d的集裝箱的重量級(jí)別的編號(hào)，而表示被放在s垛p層且要裝上船j到港站為d的集裝箱的重量級(jí)別的編號(hào)。如果要裝上集裝箱船j且重量級(jí)別為w，到港站為d的集裝箱在到達(dá)堆場時(shí)被存放在了s垛p層（即）且存放在s垛i層箱的重量級(jí)別比被存放在s垛p層箱的重量級(jí)別高（即），則約束（10）迫使 ysp=1，即在物流輸入環(huán)節(jié)，當(dāng)為將要裝上同一條船且同一到港站的兩個(gè)集裝箱分配存儲(chǔ)位置時(shí)，如果將重量級(jí)別高的集裝箱放在了重量級(jí)別低的集裝箱的下方，則在裝船時(shí)由于要先裝重量級(jí)別高的箱，這個(gè)重量級(jí)別低的集裝箱一定會(huì)發(fā)生倒垛；如果要裝上集裝箱船j且重量級(jí)別為w，到港站為d的集裝箱在到達(dá)堆場時(shí)被存放在了s垛p層（即）且存放在s垛i層箱的重量級(jí)別比被存放在s垛p層箱的重量級(jí)別低（即），于是約束（10）變成（其中 Ne是一個(gè)負(fù)數(shù)），此時(shí)無論ysp取0還是1約束（10）恒成立，目標(biāo)中最小化總倒垛數(shù)會(huì)使ysp=0，即在物流輸入環(huán)節(jié)，當(dāng)為將要裝上同一條船同一到港站的兩個(gè)集裝箱分配存儲(chǔ)位置時(shí)，如果將重量級(jí)別低的集裝箱放在了重量級(jí)別高的集裝箱的下方，則在裝船時(shí)由于要先裝重量級(jí)別高的箱，這個(gè)重量級(jí)別高的集裝箱不會(huì)發(fā)生倒垛；如果要裝上集裝箱船j且重量級(jí)別為w，到港站為d的集裝箱在到達(dá)堆場時(shí)被存放在了s垛p層(即且存放在s垛i層箱的重量級(jí)別與存放在s垛p層箱的重量級(jí)別相同(即)，于是約束（10）變成，此時(shí)無論 ysp取0還是1約束（10）恒成立，目標(biāo)中最小化總倒垛數(shù)會(huì)使ysp=0，即在物流輸入環(huán)節(jié)，當(dāng)為將要裝上同一條船同一到港站的兩個(gè)集裝箱分配存儲(chǔ)位置時(shí)，如果將重量級(jí)別相同的箱放在了同一垛中，則放在較高層的箱不會(huì)發(fā)生倒垛；如果在物流輸入環(huán)節(jié)沒有箱被存放在s垛p層(即)，約束（10）變成，這里由于，于是ysp無論取0還是1約束（10）恒成立，目標(biāo)中最小化總倒垛數(shù)會(huì)使ysp=0，此時(shí)約束（10）保證當(dāng)某位置沒有集裝箱時(shí)就沒有倒垛發(fā)生。最后，約束（11），（12）和（13）保證決策變量必須為0,1整數(shù)。

模型(IP)的特點(diǎn)在于：一方面該模型將空間分配階段與具體位置分配階段進(jìn)行集成來研究出港集裝箱的箱位分配問題；另一方面這里的集成并不是將兩階段的已有模型直接合并，而是通過將出港箱按屬性分類后定義批的概念，并在模型中引入與批相關(guān)的決策變量來實(shí)現(xiàn)宏觀的空間分配與微觀的倒垛的兼容。引入組、簇、批的概念后，根據(jù)船的基本配載要求，壓箱關(guān)系只存在于同組但不同批的箱之間，從而裝船時(shí)堆場中每個(gè)位置的箱是否需要倒垛更容易快速地判斷。

由于模型中使用街區(qū)間最大工作量與最小工作量的差最小化這種非線性表達(dá)來實(shí)現(xiàn)街區(qū)間工作量平衡的目標(biāo)，因此無法直接利用優(yōu)化軟件CPLEX進(jìn)行求解。下面利用等價(jià)變換將目標(biāo)中非線性部分轉(zhuǎn)化為線性的。首先引入新變量E和F：

于是基于屬性分類的出港集裝箱箱位分配問題的模型(IP)可以等價(jià)地轉(zhuǎn)化為如下的線性規(guī)劃模型(LIP)：

約束（14）和（15）用來反映新變量E和F的定義，通過定義新的變量及引入新的約束，線性模型(LIP)完全等價(jià)于原來的模型(IP)，因此可以使用優(yōu)化軟件CPLEX直接求解。

4 實(shí)例

為了驗(yàn)證上面所討論模型的有效性，給出如下具體實(shí)例。假設(shè)給定某時(shí)段有編號(hào)分別為1,2,3的三條船進(jìn)港，堆場中有4個(gè)街區(qū)，每個(gè)街區(qū)分別為7垛4層。船1的箱有2個(gè)重量級(jí)別和3個(gè)到港站，船2的箱有3個(gè)重量級(jí)別和2個(gè)到港站，船3的箱有2個(gè)重量級(jí)別和3個(gè)到港站。模型中為了便于表示和計(jì)算，首先按街區(qū)編號(hào)從小到大的順序?qū)⒔謪^(qū)中的垛從左至右順次編號(hào)，如圖4所示；然后按船編號(hào)的順序?qū)⒚織l船的重量級(jí)別從低到高順次編號(hào)，即W1={1,2}，W2={3,4,5}，W3={6,7}；類似地將每條船的到港站從近到遠(yuǎn)順次編號(hào)，即D1={1,2,3}，D2={4,5}，D3={6,7,8}。表1給出由外部集卡運(yùn)進(jìn)的各批出港箱的具體數(shù)量Cwd，表2給出初始狀態(tài)時(shí)堆場中各批出港箱的數(shù)量Iwd，而每條船與各街區(qū)之間的距離Ajb見表3。

表2 Iwd的值

表3 Ajb的值

出港箱在堆場中的初始堆垛狀態(tài)由圖4中黑色的數(shù)字和字母組合給出，圖中jWwDd表示某個(gè)批中的箱，其中該批的箱重量級(jí)別為w到港站為d且要裝上船j。根據(jù)圖4中給出的初始堆垛狀態(tài)可以很容易地得出的值。按照上面給出的基本配載要求可知，在初始的堆垛狀態(tài)下，有2個(gè)箱在裝船時(shí)需要倒垛。其中一個(gè)需要倒垛的集裝箱(2W3D5)的位置在16垛2層，因?yàn)樵谒路脚c其到港站相同但重量級(jí)別比它高的箱(2W4D5)要先裝上船；另一個(gè)需要倒垛的集裝箱(1W2D2)的位置在26垛2層，因?yàn)橄旅娴南?1W2D3)的到港站比它遠(yuǎn)。

將已知數(shù)據(jù)Cwd,Ajb,,Iwd輸入模型(LIP)中，這里目標(biāo)中的權(quán)重分別取δ1=0.3，δ2=0.3，δ3=0.4。由于倒垛對(duì)裝船效率的影響較大，所以取相對(duì)大的權(quán)重。約束（2）-（8）如前所述。對(duì)給定的船和任意的垛，如果p層有箱(即)且該箱的到港站比其下面的i層箱的到港站近(即)，則約束（9）迫使 ysp=1(如圖3中的(a)所示)，即s垛p層的箱要倒垛。而對(duì)于其他不產(chǎn)生倒垛的情況(圖2中的(b)(c)(d))，約束（9）恒成立。對(duì)給定的船和其任一個(gè)到港站，如果p層有箱(即)且該箱的重量級(jí)別比其下面的 i層箱的重量級(jí)別低(即)，則約束（10）迫使 ysp=1(如圖3中的(a)所示)，即s垛p層的箱要倒垛。而對(duì)于其他不產(chǎn)生倒垛的情況(圖3中的(b)(c)(d))，約束(10)恒成立。

圖2 對(duì)應(yīng)約束（9）的堆垛狀態(tài)

圖3 對(duì)應(yīng)約束（10）的堆垛狀態(tài)

圖4 模型對(duì)實(shí)例的決策結(jié)果

通過優(yōu)化軟件CPLEX 11.0對(duì)該實(shí)例進(jìn)行最優(yōu)求解，得到出港箱在堆場中的最優(yōu)存儲(chǔ)箱位，圖4中淺色的數(shù)字和字母組合表示將外部集卡運(yùn)進(jìn)的出港箱分配到堆場中的最優(yōu)分配狀態(tài)。該模型的目標(biāo)函數(shù)值為80.9，目標(biāo)中第一部分的值為1.5，即堆場中街區(qū)間最大工作量與最小工作量的差為5；目標(biāo)第二部分的值為78.6，即集卡運(yùn)輸距離為262；目標(biāo)中第三部分的值為0.8，即將堆場中的所有出港箱都裝上船時(shí)一定會(huì)發(fā)生倒垛的集裝箱數(shù)為2，這說明使用我們提出的模型為由外部集卡運(yùn)進(jìn)的出港箱分配堆場中的存儲(chǔ)位置時(shí)沒有產(chǎn)生額外的壓箱。從圖4的最終分配結(jié)果可以看出，距離船近的兩個(gè)街區(qū)1和2分配了較多的箱，但總體上各街區(qū)間的工作量還是比較均衡的，同時(shí)并沒有因?yàn)橛行碌某龈巯溥M(jìn)入堆場而增加裝船時(shí)的倒垛?？梢钥闯鲈诙褕龅某跏级讯鉅顟B(tài)給定的情況下，通過合理地為進(jìn)入堆場中的出港箱分配箱位可以減少裝船時(shí)的倒垛數(shù)，從優(yōu)化物流輸入環(huán)節(jié)的存儲(chǔ)位置分配來提高裝船時(shí)的效率。

5 結(jié)語

本文從實(shí)際出發(fā)，針對(duì)集裝箱碼頭堆場箱位分配問題，在對(duì)出港箱按其所屬船舶、重量級(jí)別和到港站分類并引入組、簇、批概念的基礎(chǔ)上，將空間分配階段與具體箱位分配階段集成來研究出港箱在堆場中的箱位分配問題。根據(jù)裝船時(shí)的倒垛只可能發(fā)生在同組但不同批的箱之間的這個(gè)特征，通過引入與批相關(guān)的決策變量，以各街區(qū)的箱量均衡、集卡運(yùn)輸距離最短和裝船時(shí)一定發(fā)生倒垛的集裝箱數(shù)最少為目標(biāo)建立非線性0-1整數(shù)規(guī)劃模型，實(shí)現(xiàn)從物流輸入環(huán)節(jié)提高出港箱的裝船效率。利用上確界和下確界的定義，以及引進(jìn)新的變量和約束的方式將所建立的模型轉(zhuǎn)化為與其等價(jià)的線性規(guī)劃模型，并使用標(biāo)準(zhǔn)優(yōu)化軟件CPLEX求解實(shí)例來驗(yàn)證該模型的有效性。

[1]Bazzazi M,Safaei N,Javadian N.A genetic algorithm to solve the storage space allocation problem in a container terminal[J].Computers&Industrial Engineering,2009,56(1)：44-52.

[2]徐亞,陳秋雙,龍磊,劉麗蕓.基于多目標(biāo)規(guī)劃的堆場空間分配問題研究[J].系統(tǒng)工程學(xué)報(bào),2009,24(3)：365-369.

[3]嚴(yán)南南,崔景云.集裝箱碼頭堆場出口箱箱區(qū)空間分配動(dòng)態(tài)模型[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,35(2)：163-168.

[4]檀財(cái)茂,黃有方,何軍良,嚴(yán)偉.集裝箱港口出口箱堆場空間優(yōu)化分配研究[J].計(jì)算機(jī)仿真,2016,(10)：187-191.

[5]Wan Y W,Liu J Y,Tsai P C.The Assignment of Storage Locations to Containers for a Container Stack.Naval Research Logistics,2009,56(8)：699-713.

[6]徐亞,陳秋雙,龍磊,楊立志,劉麗蕓.集裝箱倒箱問題的啟發(fā)式算法研究[J].系統(tǒng)仿真學(xué)報(bào),2008.20(14)：3 666-3 669.

[7]Caserta M,Schwarze S,Voss S.A mathematical formulation and complexity considerations for the blocks relocation problem[J].European Journal of Operational Research,2012,219(1)：96-104.

[8]Zehendner E,Feillet D.A branch and price approach for the container relocation problem[J].International Journal of Production Research,2014,52(24)：7 159-7 176.

[9]Tang L,Jiang W,Liu J,Dong Y.Research into container reshuffling and stacking problems in container terminal yards[J].Iie Transactions,2015,47(7)：751-766.

Study on Slot Allocation Problem of Outgoing Containers Based on Attribute Classification

Jiang Wei,Mao Shimin
(School of Technology,Zhejiang Normal University,Jinhua 321004,China)

In this paper,on the basis of the attribute-based classification of outgoing containers and the definition of group,cluster and batch,we studied the slot allocation problem of the containers so as to reduce the number of stack transfer needed in ship loading by optimizing the logistics input links.Next,through introducing in the location variable of the batch,the relational variable between the group and the stack and the stack transfer variable at every position,and with the relationship between the group and stack,the principle and status of slot utilization,the law of conservation of the container quantity for the same batch and the stack transfer relationship between different batches as the constraint,we built the nonlinear integer programming model for the problem.At the end,through equivalent transformation,we turned the model into a linear model directly solvable by an optimization software and demonstrated its validity through an empiricaltest.

outgoing container;attribute classification;slot allocation;integration model

F224.0;U169.6

A

1005-152X(2017)06-0078-07

10.3969/j.issn.1005-152X.2017.06.020

2017-03-31

浙江省自然科學(xué)基金資助項(xiàng)目（LQ13G020010）

姜偉（1981-），女，遼寧阜新人，博士，講師，主要研究方向：集裝箱碼頭等相關(guān)物流運(yùn)作的建模及優(yōu)化算法設(shè)計(jì)、物流設(shè)施選址設(shè)計(jì)及最優(yōu)化算法。