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

姜 偉，毛詩敏

（浙江師范大學 工學院，浙江 金華 321004）

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

姜 偉，毛詩敏

（浙江師范大學 工學院，浙江 金華 321004）

在對出港箱按屬性分類并定義組、簇、批的基礎上研究出港集裝箱的箱位分配問題，從優化物流輸入環節來減少裝船時的倒垛數。通過引進批的位置變量、組與垛關系變量和每個位置的倒垛變量，并以組與垛的關系、箱位使用原則和狀態、批的箱量守恒以及不同批間倒垛關系為約束對該問題建立非線性整數規劃模型，目標是實現裝船時各街區箱量均衡、集卡運輸距離最短和裝船時一定發生倒垛的集裝箱數最少。利用等價變換將該模型轉化為優化軟件可直接求解的線性模型，并實例驗證模型的有效性。

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

1 引言

近年來隨著全球化和經濟一體化的快速發展，國內和國際貨物的運輸量不斷增長，這種增長趨勢對為貨物的運輸、裝卸、包裝、倉儲、配送及信息管理提供相應服務并保證貨物安全準時到達的物流業提出了更高的要求。港口作為貨物海陸聯運的樞紐，是物流體系中一個不可替代的重要節點。在港口中堆場空間是一種稀缺資源，在集裝箱的貨流量不斷增加的環境下，如何管理碼頭堆場系統，為每個集裝箱分配合理的箱位進而提高裝卸效率和碼頭服務水平，成為碼頭管理者和學術界關注的熱點問題。

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

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

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

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

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

集裝箱碼頭為了有效地提高堆場空間利用率，通常采取將多個集裝箱按垂直方向向上堆垛的方式進行堆存。集裝箱的這種堆放方式雖然具有高密度和高空間利用率的特點，但在提箱的過程中有可能產生不必要的倒垛而影響提箱的效率。如果待提取的目標箱上面放有其他箱，那么就產生了壓箱。為了要提出該目標箱，必須先將壓在其上面的箱暫時移到其他箱位，這種臨時的集裝箱移動稱為倒垛。堆場中無論任何時段任何操作都不希望有倒垛發生，因為倒垛操作大大降低了工作效率，增加了操作成本，因此有效減少倒垛數是集裝箱碼頭操作中另一個研究熱點。

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

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

根據上面出港集裝箱的分類及不同類別集裝箱的裝船順序，基于屬性分類的出港集裝箱箱位分配問題描述如下：在某一給定的時段，堆場的初始堆垛狀態非空且已知，該時段內外部集卡向堆場運進出港箱的數量已知，這些出港箱在運進堆場時其所屬船舶、到港站和重量級別等信息便可以獲得。該時段內到港的船泊數量及停靠的泊位已知，并且每條船的?？坎次慌c堆場中每個街區的距離給定。根據每個箱的屬性可以按照上面的分類原則將其分批。我們的問題就是要決策分批后的集裝箱在堆場中的具體箱位，目標是各街區的工作量均衡、裝船時集卡在街區和船間運輸的總距離最短和發生倒垛的集裝箱數最少，從而保證裝船效率。

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

3 數學模型

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

3.1 模型參數

為了建模方便以及便于比較對應于同一條船的兩個到港站的遠近及兩個重量級別的高低，首先將所考慮的集裝箱船從1開始順次編號，然后分別順次對每條船的所有到港站按從近到遠的順序從1開始編號，最后分別順次對每條船每個到港站的所有重量級別按從低到高的順序從1開始編號，并給出如下模型參數：

j：船的編號；

J：船的集合；

|J|：船的總數；

b：堆場中街區的編號；

B：堆場中街區的集合；

|B|：堆場中街區的總數；

s：堆場中垛的編號；

S：堆場中垛的集合；

|S|：堆場中垛的總數；

Nb：街區b中垛的集合；

p：堆場中層的編號；

P：堆場中層的集合；

|P|：堆場中允許的最高層數；

w：重量級別的編號；

Wj：船j的箱對應的所有重量級別的集合；

d：到港站的編號；

Dj：船j的箱對應的所有到港站的集合；

|Dj|：船j的箱對應的所有到港站的總數；

Cwd：由外部卡車運到堆場重量級別為w，到港站為d的出港箱數量；

Iwd：初始狀態時，堆場中重量級別為w，到港站為d的出港箱數量；

Ajb：船j與街區b之間的距離；

M：無限大的數；

δ1：目標中與各街區的工作量均衡相關的權重；

δ2：目標中與集卡的運輸距離最短相關的權重；

δ3：目標中與倒垛數最少相關的權重。

3.2 決策變量

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

3.3 模型

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

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

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

由于模型中使用街區間最大工作量與最小工作量的差最小化這種非線性表達來實現街區間工作量平衡的目標，因此無法直接利用優化軟件CPLEX進行求解。下面利用等價變換將目標中非線性部分轉化為線性的。首先引入新變量E和F：

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

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

4 實例

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

表2 Iwd的值

表3 Ajb的值

出港箱在堆場中的初始堆垛狀態由圖4中黑色的數字和字母組合給出，圖中jWwDd表示某個批中的箱，其中該批的箱重量級別為w到港站為d且要裝上船j。根據圖4中給出的初始堆垛狀態可以很容易地得出的值。按照上面給出的基本配載要求可知，在初始的堆垛狀態下，有2個箱在裝船時需要倒垛。其中一個需要倒垛的集裝箱(2W3D5)的位置在16垛2層，因為在它正下方與其到港站相同但重量級別比它高的箱(2W4D5)要先裝上船；另一個需要倒垛的集裝箱(1W2D2)的位置在26垛2層，因為下面的箱(1W2D3)的到港站比它遠。

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

圖2 對應約束（9）的堆垛狀態

圖3 對應約束（10）的堆垛狀態

圖4 模型對實例的決策結果

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

5 結語

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

[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]徐亞,陳秋雙,龍磊,劉麗蕓.基于多目標規劃的堆場空間分配問題研究[J].系統工程學報,2009,24(3)：365-369.

[3]嚴南南,崔景云.集裝箱碼頭堆場出口箱箱區空間分配動態模型[J].重慶交通大學學報(自然科學版),2016,35(2)：163-168.

[4]檀財茂,黃有方,何軍良,嚴偉.集裝箱港口出口箱堆場空間優化分配研究[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]徐亞,陳秋雙,龍磊,楊立志,劉麗蕓.集裝箱倒箱問題的啟發式算法研究[J].系統仿真學報,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

浙江省自然科學基金資助項目（LQ13G020010）

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