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

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

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

?

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

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

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

為加快滾裝運(yùn)輸過程中汽車裝卸滾裝船舶的周轉(zhuǎn)率，促進(jìn)滾裝碼頭堆場車位資源的高效利用，研究了滾裝碼頭堆場車位分配問題．按照成組集中分配原則，以提高成組汽車停放集中度為目標(biāo)，建立了衡量成組汽車停放集中度的混合整數(shù)規(guī)劃模型．進(jìn)而設(shè)計(jì)吸引度搜索算法對模型進(jìn)行了求解．與分支定界法相比，吸引度搜索算法在高效求解規(guī)?；憷耐瑫r(shí)可實(shí)現(xiàn)解的質(zhì)量較優(yōu)．以上海海通汽車滾裝碼頭堆場的車位實(shí)際布局及作業(yè)情況為背景，驗(yàn)證了所提模型與算法的合理性及有效性，拓展了汽車滾裝碼頭堆場車位分配管理的理論研究．

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

0 引 言

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

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

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

1 問題描述

滾裝碼頭作為汽車供銷渠道，為整車運(yùn)輸提供中轉(zhuǎn)節(jié)點(diǎn)，能夠?qū)囕v流通過程中的時(shí)間和空間加以壓縮，減少汽車物流中的阻礙[5]．其堆場作為汽車運(yùn)輸物流鏈中的重要節(jié)點(diǎn)，具有庫存緩沖作用[6]，可吸收或緩解牛鞭效應(yīng)，大幅度降低汽車物流成本，促進(jìn)汽車物流利潤實(shí)現(xiàn)最大化[7]．隨著汽車滾裝業(yè)務(wù)的發(fā)展，模塊化布置方式的滾裝碼頭堆場車位布局逐漸成為主流．圖1給出了上海海通汽車滾裝碼頭外四堆場的部分車位布局圖，各模塊的周邊都設(shè)有通道，每個(gè)模塊內(nèi)的車位呈矩形集中布置．

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

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

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

2 模型建立

(1)集合說明

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

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

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

(2)參數(shù)說明

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

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

④Xr,c∈G：堆場內(nèi)第r行第c列的車位對應(yīng)取值為已停放其內(nèi)的汽車組別．

(3)變量說明

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

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

圖2給出了各變量間的邏輯關(guān)系．

圖2 變量間邏輯關(guān)系

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

(1)

(2)

(3)

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

(4)

約束條件為

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

3 基于吸引度搜索的啟發(fā)式算法設(shè)計(jì)

3.1 堆場車位分配特征分析

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

3.2 吸引度定義

(1)符號說明

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

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

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

(2)吸引度水平

(21)

(22)

(3)總吸引度指標(biāo)

(23)

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

3.3 算法步驟

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

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

圖3 吸引度水平計(jì)算示例

Fig.3Calculatingdemonstrationsofattractiondegreelevel

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

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

4 數(shù)值實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 數(shù)值實(shí)驗(yàn)設(shè)計(jì)

4.2 實(shí)驗(yàn)結(jié)果分析

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

表1 數(shù)值實(shí)驗(yàn)設(shè)計(jì)

圖5 實(shí)驗(yàn)場景1算例3滾裝碼頭堆場車位

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

圖6 實(shí)驗(yàn)場景3算例2滾裝碼頭堆場車位

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

碼頭堆場車位分配方案，與分支定界法計(jì)算結(jié)果(表2)作比，前者獲得了最優(yōu)解，誤差為0，后者誤差為0.03．從計(jì)算結(jié)果及計(jì)算時(shí)間來看，隨著待作業(yè)汽車組數(shù)、待作業(yè)汽車總數(shù)的增加，以及堆場布局規(guī)模的擴(kuò)大，吸引度搜索算法的計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)小于分支定界法．且在堆場規(guī)模依次遞增的實(shí)驗(yàn)場景3中，算例5、6計(jì)算時(shí)間長達(dá)72 h，分支定界法仍未得到最優(yōu)解．實(shí)驗(yàn)結(jié)果證明了吸引度搜索算法在高效求解規(guī)?；憷耐瑫r(shí)可實(shí)現(xiàn)解的質(zhì)量較優(yōu)．

5 實(shí)際應(yīng)用

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

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

表3 實(shí)際應(yīng)用算例設(shè)計(jì)

圖7 計(jì)算結(jié)果統(tǒng)計(jì)

圖8 計(jì)算時(shí)間統(tǒng)計(jì)

6 結(jié) 語

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

[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．

國家自然科學(xué)基金資助項(xiàng)目(71471109)；國家自然科學(xué)基金青年基金資助項(xiàng)目(71101088)；教育部博士點(diǎn)基金資助項(xiàng)目(20113121120002)；上海市教委科研創(chuàng)新項(xiàng)目(14YZ100)；交通部應(yīng)用基礎(chǔ)研究項(xiàng)目(2015329810260)；上海市曙光計(jì)劃項(xiàng)目(13SG48).

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

U651

A

10.7511/dllgxb201602002