基于吸引度搜索的汽車滾裝碼頭堆場車位分配優化

陳 曉 靜， 胡 志 華*， 李 功 君

( 1.上海海事大學 物流研究中心， 上海 201306；2.上海海通國際汽車碼頭有限公司， 上海 200137 )

?

基于吸引度搜索的汽車滾裝碼頭堆場車位分配優化

陳 曉 靜1， 胡 志 華*1， 李 功 君2

( 1.上海海事大學 物流研究中心， 上海 201306；2.上海海通國際汽車碼頭有限公司， 上海 200137 )

為加快滾裝運輸過程中汽車裝卸滾裝船舶的周轉率，促進滾裝碼頭堆場車位資源的高效利用，研究了滾裝碼頭堆場車位分配問題．按照成組集中分配原則，以提高成組汽車停放集中度為目標，建立了衡量成組汽車停放集中度的混合整數規劃模型．進而設計吸引度搜索算法對模型進行了求解．與分支定界法相比，吸引度搜索算法在高效求解規模化算例的同時可實現解的質量較優．以上海海通汽車滾裝碼頭堆場的車位實際布局及作業情況為背景，驗證了所提模型與算法的合理性及有效性，拓展了汽車滾裝碼頭堆場車位分配管理的理論研究．

滾裝碼頭堆場；車位分配；集中度；混合整數規劃；吸引度搜索算法

0 引 言

汽車滾裝碼頭堆場車位分配作業是影響滾裝運輸作業過程中汽車裝卸船舶周轉率及堆場車位資源利用率的關鍵環節．在實際滾裝運輸過程中，部分水道和港灣因受潮汐影響，使得滾裝船舶必須在高潮前后才能航行和進出碼頭，這就對汽車裝卸滾裝船舶的時效性具有較高的要求．此外，隨著汽車滾裝碼頭年吞吐量的增長，加之汽車無法在堆場內堆垛存儲的特性，使得堆場車位資源趨緊的現象也日益凸顯．研究滾裝碼頭堆場車位分配作業對加快汽車裝卸過程的周轉速度，提高堆場車位資源利用率具有重要意義．

滾裝運輸業務量的增長促使堆場車位分配作業的工作量加大，采用合理的算法可實現對數學模型規模化算例的高效求解．與集裝箱作業相比，目前國內外關于汽車滾裝作業的研究仍相對較少，且多數屬于早期文獻．Mattfeld等[1]參考不來梅港的汽車調度機制，針對庫存控制及人力計劃建立決策模型，并將其分層處理，設計啟發式算法加以求解；Fischer等[2]詳細描述了汽車轉運港口的多Agent系統，探究了堆場車位的分配及調度計劃，并通過算例設計對隨機生成的汽車儲位問題加以檢驗；Mattfeld等[3]提出了基于啟發式算法的堆場容量利用策略來平衡計劃期內堆場車位的分配，指出與遺傳算法相比，啟發式算法能夠在較短的時間內找到更好的解決方案；Cordeau等[4]從管理層、戰略層的角度出發，分析了汽車堆場中存在的管理問題，采用自適應大規模鄰域搜索算法對所建立的數學模型加以求解．

本文針對滾裝碼頭堆場車位分配問題，按照成組集中分配原則，以提高堆場內成組汽車停放集中度為目標，建立混合整數規劃模型．設計吸引度搜索算法，分別采用分支定界法與吸引度搜索算法對多組實驗場景進行求解，驗證其合理性及有效性．

1 問題描述

滾裝碼頭作為汽車供銷渠道，為整車運輸提供中轉節點，能夠對車輛流通過程中的時間和空間加以壓縮，減少汽車物流中的阻礙[5]．其堆場作為汽車運輸物流鏈中的重要節點，具有庫存緩沖作用[6]，可吸收或緩解牛鞭效應，大幅度降低汽車物流成本，促進汽車物流利潤實現最大化[7]．隨著汽車滾裝業務的發展，模塊化布置方式的滾裝碼頭堆場車位布局逐漸成為主流．圖1給出了上海海通汽車滾裝碼頭外四堆場的部分車位布局圖，各模塊的周邊都設有通道，每個模塊內的車位呈矩形集中布置．

經同一滾裝船卸載的相同類型的汽車一般具備相同的出港時間要求，將其按型號劃分成不同的組別，分別停放于一個輻射范圍盡可能小，集中度盡可能大的停車區域內，可滿足汽車堆存量及提取、停放便捷的雙重要求，從而加快汽車裝卸過程的周轉速度，提高堆場車位資源利用率．基于此，按照成組集中分配原則，建立數學規劃模型，在使同一組別的汽車在堆場內集中停放的基礎上，達到各組汽車同時集中停放的效果，優化堆場車位分配作業．

目前已有的文獻中尚未發現以成組集中分配為指標的堆場車位分配問題的研究．而在實際堆場操作作業中，堆場車位的分配也大都依賴于調度人員的實際操作經驗．堆場車位分配問題實質上是將不同組別的車輛分配至堆場的各個車位，形成堆場車位分配計劃．就模型建立方面，必然涉及以0-1變量來描述各個車輛在堆場中被分配的位置，從而形成混合整數規劃模型．而在其他領域中大多數此類問題都具有NP-hard性質，因此，如何設計高效的算法對模型進行有效求解也是本文需要解決的難點．

圖1 上海海通汽車滾裝碼頭堆場部分車位布局圖

2 模型建立

(1)集合說明

①{(r,c)}為每個停車位所對應的行列位置集合，r=1,2,…,R，c=1,2,…,C．

②A為待作業的汽車集合，由a∈A索引．

③G為相同型號的汽車組別集合，由g∈G索引．

(2)參數說明

①Bg,a：0-1參數，汽車a屬于g組時取1，否則為0．

③R,C：分別表示汽車堆場的行數、列數．

④Xr,c∈G：堆場內第r行第c列的車位對應取值為已停放其內的汽車組別．

(3)變量說明

①xa,r,c：0-1變量，汽車a停放于堆場內第r行第c列的車位時取1，否則為0．

⑩yg,r1,r2,c1,c2：0-1變量，g組內所有汽車均被停放于堆場內由行[r1,r2]和列[c1,c2]所構成的區域時取1，否則為0．

圖2給出了各變量間的邏輯關系．

圖2 變量間邏輯關系

(4)衡量每組汽車集中度的函數描述

(1)

(2)

(3)

(5)成組集中策略下汽車滾裝碼頭堆場車位分配模型

(4)

約束條件為

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

3 基于吸引度搜索的啟發式算法設計

3.1 堆場車位分配特征分析

根據汽車滾裝碼頭堆場車位布局特點，將堆場車位布置抽象為二維網絡格局，如圖3所示．每個格子代表一個車位，每個車位坐標可由具體的行列數(r,c)表示，并被賦予不同的狀態．其中-1代表作業前初始堆場內已被占據的車位，不再參與分配作業；0代表作業結束后，堆場內未被分配的車位；其余數字則分別代表了待作業的各組汽車組別．根據本文模型中的目標函數，堆場車位分配的目標在于盡可能使同組內的汽車在堆場中集聚放置．因此，對于任何一個可行解，建立堆場車位分配吸引度的概念去表征同組汽車在堆場內存放的局部集聚水平，具體定義與計算方法可見3.2、3.3．同時，基于堆場中各位置的車位對不同組別汽車的吸引度，采用交換的策略以使得局部集聚水平不斷得到提高．通過遍歷搜索，最終使得堆場車位的分配布局達到次最優的狀態．

3.2 吸引度定義

(1)符號說明

③ψ(r,c)：堆場內(r,c)位置車位的鄰域空間．

④ψg,a：0-1參數，g組中第a輛汽車的車位屬于ψ(r,c)時取1，否則為0．

⑤s：0-1參數，堆場內(r,c)位置的車位屬于ψ(r,c)時取1，否則為0．

(2)吸引度水平

(21)

(22)

(3)總吸引度指標

(23)

圖3給出了4行6列的堆場內(1,1)、(2,6)、(3,4)3個位置車位對各組汽車吸引度水平的計算示例．

3.3 算法步驟

Step 1 (初始化)將待作業汽車隨機存放到堆場內未被占據的車位中，得到堆場車位分配方案P．

圖4給出了4行6列的堆場內(3,4)位置車位依據吸引度水平對各組汽車進行搜索交換的示例．

圖3 吸引度水平計算示例

Fig.3Calculatingdemonstrationsofattractiondegreelevel

圖4 基于吸引度水平的滾裝碼頭堆場汽車搜索交換示例

Fig.4 A demonstration of vehicles search and swap in ro-ro yard based on attraction degree level

4 數值實驗設計與分析

4.1 數值實驗設計

4.2 實驗結果分析

采用分支定界法與吸引度搜索算法求解上述數值實驗，其中分支定界法通過CPLEX來實現．圖5、6分別給出了采用吸引度搜索算法求解實驗場景1算例3及實驗場景3算例2所得到的滾裝

表1 數值實驗設計

圖5 實驗場景1算例3滾裝碼頭堆場車位

Fig.5 Distribution scheme of parking space in ro-ro yard based on the third example in the first experiment scene

圖6 實驗場景3算例2滾裝碼頭堆場車位

Fig.6 Distribution scheme of parking space in ro-ro yard based on the second example in the third experiment scene

碼頭堆場車位分配方案，與分支定界法計算結果(表2)作比，前者獲得了最優解，誤差為0，后者誤差為0.03．從計算結果及計算時間來看，隨著待作業汽車組數、待作業汽車總數的增加，以及堆場布局規模的擴大，吸引度搜索算法的計算時間遠遠小于分支定界法．且在堆場規模依次遞增的實驗場景3中，算例5、6計算時間長達72 h，分支定界法仍未得到最優解．實驗結果證明了吸引度搜索算法在高效求解規模化算例的同時可實現解的質量較優．

5 實際應用

根據海通碼頭外四堆場布局及汽車分配作業的實際情況，仿照表1實驗場景1設計應用算例(表3)．如圖1中B4區所示，選取13行10列的堆場布局，通過調整已占車位坐標，控制已占車位率為0.3，已占車位分散度為0.5，運用吸引度搜索算法求解．從計算結果(圖7)可以看出， 在每組實驗中，隨著待作業汽車組數的增加，f值逐漸增大，這與成組集中分配策略下滾裝碼頭堆場車位分配模型表征意義相符．此外，待作業汽車組數的增加導致堆場內每個車位具備的吸引度水平種類增多，堆場內不同組別的汽車搜索交換過程變復雜，從而采用吸引度搜索算法求解所需要的CPU計算時間也依次遞增(圖8)．

表2 分支定界法與吸引度搜索算法結果對比

表3 實際應用算例設計

圖7 計算結果統計

圖8 計算時間統計

6 結 語

本文針對滾裝碼頭堆場車位分配問題，按照成組集中分配原則，建立了衡量成組汽車停放集中度的混合整數規劃模型，并設計吸引度搜索算法求解．與分支定界法對比的數值實驗結果表明，吸引度搜索算法在解的質量上趨近于分支定界法，且運算時間遠小于分支定界法，能夠高效處理大規模算例．根據海通碼頭外四堆場的實際布局及作業情況設計算例，進一步分析了研究成果的應用情況．驗證了堆場車位分配模型的合理性及吸引度搜索算法的有效性，拓展了汽車滾裝碼頭堆場車位分配管理的理論研究，在優化車位分配的基礎上促進了滾裝運輸作業的高效運行．

[1] Mattfeld D C, Kopfer H. Terminal operations management in vehicle transshipment [J]. Transportation Research Part A:Policy and Practice, 2003, 37(5):435-452.

[2] Fischer T, Gehring H. Planning vehicle transshipment in a seaport automobile terminal using a multi-agent system [J]. European Journal of Operational Research, 2005, 166(3):726-740.

[3] Mattfeld D C, Bierwirth C. An efficient genetic algorithm for job shop scheduling with tardiness objectives [J]. European Journal of Operational Research, 2004, 155(3):616-630.

[4] Cordeau J-F, Laporte G, Moccia L,etal. Optimizing yard assignment in an automotive transshipment terminal [J]. European Journal of Operational Research, 2011, 215(1):149-160.

[5] Dias J C Q, Calado J M F, Mendonca M C. The role of Europeanro-roport terminals in the automotive supply chain management [J]. Journal of Transport Geography, 2010, 18(1):116-124.

[6] Mendonca M C, Dias J C Q. ′Postponement′ in the logistical systems of new automobiles marketed in Portugal:the brands and quality [J]. Total Quality Management & Business Excellence, 2007, 18(6):681-696.

[7] Chen I J, Paulraj A. Understanding supply chain management:Critical research and a theoretical framework [J]. International Journal of Production Research, 2004, 42(1):131-163.

Optimization for parking space distribution in automotive ro-ro yard based on attraction degree search

CHEN Xiao-jing1, HU Zhi-hua*1, LI Gong-jun2

( 1.Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China；2.Shanghai Haitong International Automotive Terminal Co., Ltd., Shanghai 200137, China )

In order to speed up the turnover ratio when automobiles roll up and roll down ro-ro ships in the process of ro-ro transportation and promote the utilization of parking space in ro-ro yard efficiently, the problem of parking space distribution in ro-ro yard is explored. According to the principle of centralized allocation of gathered groups,focusing on improving concentration degree of batch automobiles, a mixed-integer programming model is constructed to measure concentration degree of batch automobiles. Then attraction degree search algorithm is designed to solve the model. Compared with branch and bound method,the attraction degree search algorithm can deal with large-scale numerical examples efficiently and get satisfied solutions at the same time. Using the layout of parking space and operation conditions in Shanghai Haitong automotive ro-ro yard as research background, the proposed model and algorithm are proved to be reasonable and valid, which expand the theoretical research of parking space distribution management in automotive ro-ro yard.

ro-ro yard;parking space distribution;concentration degree;mixed-integer programming; attraction degree search algorithm

1000-8608(2016)02-0118-09

2015-09-03；

2016-01-12．

國家自然科學基金資助項目(71471109)；國家自然科學基金青年基金資助項目(71101088)；教育部博士點基金資助項目(20113121120002)；上海市教委科研創新項目(14YZ100)；交通部應用基礎研究項目(2015329810260)；上海市曙光計劃項目(13SG48).

陳曉靜(1990-)，女，碩士生，E-mail:990598065@qq.com；胡志華*(1977-)，男，博士，教授，E-mail:zhhu@shmtu.edu.cn.

U651

A

10.7511/dllgxb201602002