考慮燃料成本的集裝箱碼頭集卡路徑優化

趙金樓， 黃金虎， 劉馨， 高宏玉

(1.哈爾濱工程大學 經濟管理學院，黑龍江 哈爾濱 150001； 2.工業和信息化部電子第五研究所，廣東 廣州 510610)

在實現既定目標下，有效對資源進行調度優化近年來引起了學者們的重視。周林等[1]基于以物流成本和延遲懲罰成本之和為目標函數，構建了多任務集成調度模型，采用基于優先權的遺傳算法，對多起始地-多目的地的多任務集成調度問題進行研究。Bookbinder等[2]通過構建概率模型來選擇最大持有時間和期望的發貨量，結合已有的卡車運輸時間合并的實際決策規則，從而減少給定的起點和目的地之間的總運輸成本。XU等[3]通過構建雙層規劃模型，以減小或者消除供應不確定性在協同物流網絡中的不利影響，該模型降低了資源規劃變化的規律和成本，從而增加了協同物流網絡模型的穩定性。并在此基礎上，提出通用兩階段量化框架，使決策者能夠在不確定的情況下為協同物流網絡模型選擇最優的網絡設計方案，對協同物流網絡模型的穩定性和低成本進行進一步研究[4]。

在集卡研究中集卡路徑問題是學者們關注的焦點。Jean-Fran?ois Cordeau等[5]以集卡運輸和等待時間之和最小為目標，構建了集卡路徑優化模型，采用局部搜索算法和仿真手段對不同時刻下的集卡運行情況進行了模擬。Kim等[6-7]構建了集卡多目標路徑優化模型，以時間和行駛距離最短為目標，并運用整數規劃的方法進行求解。Bish等[8]以集卡行駛距離最短為目標，研究了集卡路徑問題與進口箱的堆場位置問題。Berghman等[9]將碼頭集卡作業劃分為三個階段，以時間最短為目標，參考柔性流水車間問題構建了調度模型，并引入枚舉搜索樹設計了拉格朗日啟發式算法來求解。楊靜蕾[10]以集卡行駛距離最小為目標提出了集裝箱碼頭物流路徑優化模型，獲得了集卡最優路徑。計明軍等[11]以集卡和岸橋作業時間之和最小為優化目標，構建了集卡線路優化模型，并利用改進的進化規劃來求解。曾慶成等[12]以總作業時間最小為目標，建立了集卡調度動態模型，并設計了Q學習算法對裝卸任務進行分配。曹慶奎等[13]將集卡成本劃分為固定成本、可變成本、懲罰成本，分別直接給定單位成本，以最小化作業成本為目標，建立了面向“作業面”的港口集卡路徑成本優化模型，并采用遺傳蟻群算法求解。

綜上，集卡路徑相關研究雖然較多，但多以集卡行駛距離或運輸時間最小為優化目標。然而，在規定時間內能夠完成任務的前提下，碼頭經營者更為關注運輸成本。集卡運輸成本由固定成本和可變成本構成，可變成本中很重要一部分就是燃料成本。然而，目前對集卡路徑問題的研究中尚未有人從燃料消耗的角度來考慮集卡成本。隨著低碳理念和碳稅相關制度的逐步確立，減少集卡燃料消耗從而降低碳排放兼具環保和經濟意義。

基于上述背景，本文在考慮燃料成本的基礎上分兩步進行集卡路徑優化。基于集卡運輸成本對路徑進行優化，運輸成本中重點分析燃料成本。此部分不考慮集卡數量，主要考慮如何規劃路徑使集卡運輸成本最低。在此基礎上，考慮集卡數量的影響，基于集卡作業時間對路徑進行優化，主要考慮如何分配任務使所有集卡完成作業的時間最短。對應地分別構建了兩個模型，即考慮燃料成本的集卡路徑優化模型和考慮集卡作業時間的路徑任務分配模型，結合算例分別采用了Lingo和粒子群算法來求解。

由于粒子群算法參數較少，操作較簡單；不存在交叉和變異運算，搜索速度快，且具有記憶性，可以保持歷史最優解等優點，是解決組合優化問題的一種很好的方法，所以本文中采用粒子群算法對問題進行求解。

1 集裝箱碼頭集卡路徑問題描述

假設每輛集卡一次只能運輸一個40英尺集裝箱(FEU)。集卡作業過程和路徑見圖1。待卸船舶和待裝船舶分別停靠于集裝箱碼頭的泊位1和泊位2，同時進行兩船的裝卸作業。集卡從泊位1出發，將卸下的進口集裝箱運至進口箱區，然后空載到出口箱區提取一個出口集裝箱運至泊位2。此作業方式也稱為作業面模式。在此過程中集卡主要作業路徑為：泊位1→進口箱區→出口箱區→泊位2。由于可能存在裝卸不平衡的情況，即待卸集裝箱的總量與待裝集裝箱的總量不相等，除上述路線外，還存在：泊位1→進口箱區，泊位2→出口箱區兩種往返路徑，分別實現多余進口箱和出口箱的運輸任務。三種路徑中，集卡的裝載情況已在圖上標明，其中虛線表示空載。因一次最多只能裝載一個集裝箱，故集卡只存在滿載和空載這兩種裝載情況。

圖1 集裝箱碼頭集卡作業的三種路徑Fig.1 The three ways of the packing yard trailers

本文中，集卡的路徑問題實際上有兩層含義，一是在一次作業過程中集卡需要經過哪個進口箱區和哪個出口箱區，二是對于每條相同的路徑集卡需要走多少次。把這兩個問題歸為集卡的初步路徑規劃問題。在此基礎上，對于既定數量的集卡和路徑任務，還需在此基礎上進一步研究如何給每輛集卡分配任務。本文構建的兩個模型分別解決了集卡的初步路徑規劃問題和進一步的路徑任務分配問題。

2 燃料成本計算

燃料成本是車輛運輸中可變成本的主要組成部分，研究顯示車輛燃料成本受到距離、載重量、速度、路況、燃料消耗率(fuel consumption rate，FCR)等多個因素的影響，Xiao等[14]對車輛燃料消耗研究情況進行了歸納和應用，參考相關文獻[14]，本文采用如下燃料成本計算方法：

(1)

本文燃料消耗率是指單位距離的燃料消耗體積。研究表明，燃料消耗率受到車輛載重量和速度的影響，與車輛載重量和速度大致呈正相關關系[14-15]。在集卡作業過程中，假設集卡行駛速度不變。一般來說，運輸過程中貨物的集散會導致載重量的變化，因此集卡在運輸過程中燃料消耗率是變化的。由于集卡運輸過程只存在滿載和空載兩種裝載狀態，故只對應存在滿載燃料消耗率和空載燃料消耗率兩種狀況。這兩項參數參考相關標準和經驗值給出。

3 集裝箱碼頭集卡路徑優化的兩階段模型

3.1 考慮燃料成本的集卡路徑優化模型

3.1.1 參數與變量

決策變量如下：

Xij為集卡沿路徑“泊位1→進口箱區i→出口箱區j→泊位2”的運行次數；Yoi為集卡沿路徑“泊位1→進口箱區i”之間往返的運行次數；Zrj為集卡沿路徑“泊位2→出口箱區j”之間往返的運行次數。

3.1.2 數學模型

假設集卡運輸中可變成本僅考慮燃料成本，燃料成本通過式(1)來計算。以包括可變成本和固定成本的集卡運輸成本最小為目標函數，構建集裝箱碼頭集卡路徑優化模型如下

(2)

s.t.

(3)

(4)

(5)

(6)

Xij≥0,i∈I,j∈E

(7)

Yoi≥0,i∈I

(8)

Zrj≥0,j∈E

(9)

式中：N1為待卸進口集裝箱總量；N2為待裝出口集裝箱總量；I為進口箱區的集合，共有l個箱區；用i表示進口箱區的序號，i=1,2,…,l；E為出口箱區的集合，共有m個箱區；用j表示出口箱區的序號，j=1,2,…,m；doi為泊位1到進口箱區i的距離；用o表示泊位1；drj為泊位2到出口箱區j的距離，用r表示泊位2；dij為進口箱區i到出口箱區j的距離；Qi為第i個進口箱區所能容納的集裝箱數量；Pj為第j個出口箱區已堆存的集裝箱數量；c0為單位體積燃料成本；n為集卡數量；ρ0為空載燃料消耗率；ρm為滿載燃料消耗率；c′為每輛集卡運輸的固定成本。其中，目標函數(2)表示集卡完成所有裝卸任務的總成本最小。式(2)：等號右側前5項反映由集卡燃料成本構成的運輸可變成本；第1項表示集卡在泊位1與進口箱區之間滿載運輸的燃料成本；第2項表示集卡在泊位1與進口箱區之間空載運輸的燃料成本；第3項表示當沿路徑“泊位1→進口箱區i→出口箱區j→泊位2”運輸時，集卡在進口箱區與出口箱區之間空載運輸的燃料成本；第4項表示集卡在泊位2與出口箱區之間滿載運輸的燃料成本；第5項表示集卡在泊位2與出口箱區之間空載運輸的燃料成本；第6項為運輸固定成本。約束(3)保證所有待卸進口集裝箱都能卸載完畢。約束(4)保證所有待裝出口集裝箱都能裝載完畢。約束(5)保證運送到第i個進口箱區的集裝箱總數不超過該進口箱區的容量。約束(6)保證第j個出口箱區的已堆存集裝箱都能裝船。約束(7)～(9)表示決策變量的取值范圍。

3.2 考慮集卡作業時間的路徑任務分配模型

根據上述模型可以得到集卡的初步路徑規劃，即需要沿哪些路徑來運輸集裝箱，每條路徑需要走多少次。然而實踐中通常有多輛集卡共同完成作業，基于初步路徑規劃的結果，接著需要對每輛集卡進行任務分配。本部分把每條路徑的一次運輸過程當成一項任務，以所有集卡完成作業的時間最小為目標，建立進一步的優化模型。

已知的相關參數及變量如下：

H為任務集合，任務數量為h；用s表示任務的序號，s=1,2,…,h；N為集裝箱卡車的集合，集卡數量為n；用k表示集卡的序號，k=1,2,…,n；Tk為第k輛集卡執行完任務所用的時間；v為集卡行駛速度；Ds為任務s的路程，根據泊位與箱區之間的距離計算得到：

假設所有集卡在作業過程中的行駛速度不變，考慮集卡作業時間構建的路徑任務分配模型如下

minT=max{Tk,k∈N}

(10)

s.t.

(11)

(12)

Gks∈{0,1},s∈H,k∈N

(13)

目標函數(10)表示所有集卡完成任務的總時間最短，取完成任務序列中時間最長的集卡作業時間為總時間。約束(11)表示每個任務有且僅有1輛集卡執行，約束(12)給出了每輛集卡作業時間的計算方法，約束(13)表明了決策變量是0～1的變量。

4 模型求解

4.1 考慮燃料成本的集卡路徑優化模型求解

待卸船舶停靠于泊位1，有480個進口箱需要卸載。待裝船舶停靠于泊位2，有450個出口箱需要裝載。碼頭有5個進口箱區和5個出口箱區，各進口箱區所能容納的集裝箱數量和出口箱區已堆存的集裝箱數量見表1及表2。箱區與泊位、箱區與箱區之間的距離見表3。單位體積燃料成本c0=7元/L，集卡的空載燃料消耗率ρ0=0.15 L/km，滿載燃料消耗率ρm=0.50 L/km，集卡速度v=10 m/s，每輛集卡固定成本c′=4 000元，集卡數量n=10。

使用Lingo軟件對考慮燃料成本的集卡路徑優化模型進行求解，得到最優總成本為46 055元，最優路徑及沿各路徑裝卸量見表4。

表1 進口箱區容量

表2 出口箱區堆存量

表3 堆場各點間距離

表4 集卡運輸路徑及裝卸箱量Table 4 The route and loading or unloading of the container

在不考慮燃料成本，而以距離最短為目標的傳統模型中，根據最優方案計算得到的總成本為46 819元[16]。顯然，本文構建的考慮燃料消耗的優化模型得到的結果更優。

4.2 考慮集卡作業時間的路徑任務分配模型求解

使用帶慣性權重的粒子群算法對集卡路徑任務分配模型進行求解，具體步驟如下[17]:

1)初始化粒子群。采用整數編碼方式，用長度為h的位置向量Xv來表示各任務的分配情況，Xv中元素的取值代表集卡序號，Xv取值范圍為1～n(集卡數量)。在該算例中，n=10。編碼過程見表5，Xv表示執行各任務的集卡序號。隨機生成位置向量Xv和速度向量Vv，保證Xv每一維取1～n之間的整數，Vv每一維取-(n-1)～(n-1)之間的整數。

表5 編碼示意

2)計算適應值函數。利用式(10)、(12)計算適應值函數，以此作為粒子評價標準。

3)重復以下步驟，直到滿足迭代終止條件。

①對每一個粒子，按位置和速度公式進行更新，超過邊界范圍時按邊界取值。速度及位置更新公式如下：

(14)

(15)

式中:c1和c2是學習因子，r1和r2是隨機數，pbest是當前粒子的歷史最優位置，gbest是所有粒子的歷史最優位置。ω是線性遞減的慣性權重，采用如下公式計算：

(16)

式中：ωmax是初始權重，ωmin是最終權重，itermax是最

大迭代次數，iter是當前迭代次數。

②用適應值函數評價所有粒子。

③若某個粒子的當前適應值優于歷史最優適應值，則記當前適應值為歷史最優適應值。同時記下此時的粒子位置為該粒子歷史最優位置。

④尋找當前各粒子群內的最優解和總群體最優解，若優于歷史最優解則更新pbest和gbest。對于子群內有多個最優值，則隨機取其中一個為子群內當前最優解。

4)設置迭代終止條件。以最大迭代次數為算法停止條件。

基于粒子群算法使用Matlab對考慮集卡作業時間的路徑任務分配模型進行求解，得到各集卡任務分配及作業時間情況見表6。表中列出了各集卡沿各路徑的運輸次數，即相應任務數量。取集卡中完成任務時間最長者為總作業時間，為5.27h。

表6 集卡任務分配及作業時間

5 結論

對于集裝箱碼頭的集卡路徑問題，本文綜合考慮了燃料消耗情況和作業時間兩個因素，構建兩階段模型對集卡路徑優化進行研究。綜合兩個模型，既考慮了燃料成本又考慮了作業時間，與實際碼頭經營者的關注點相一致。通過本文中的研究，主要得出如下結論：

1)通過構建的考慮燃料消耗的優化模型得到的總成本小于傳統模型中以距離最短為目標的根據最優方案計算得到的總成本。

2)通過構建的兩階段集卡路徑優化模型，可以在降低總成本的基礎上，降低集卡的作業時間，對集卡路徑進行進一步優化。

在考慮燃料成本的情況下，從成本和時間兩個角度對集卡路徑進行優化。研究還不夠深入，應在本文研究的基礎上，從等待時間、固定成本、可變成本等多維角度，對集卡路徑優化問題進行進一步研究。

[1] 周林，王旭，林云，景熠. 面向空間分布式小批量物流供需的多任務集成調度[J]. 計算機集成制造系統， 2016， 22(3)： 822-832.

ZHOU Lin, WANG Xu, LIN Yun, et al. Integrated multi-task scheduling for spatially distributed small-batch logistics[J]. Computer integrated manufacturing systems, 2016， 22(3)： 822-832.

[2] BOOKBINDER J H，HIGGINSON J K. Probabilistic modeling of freight consolidation by private carriage [J]. Transportation research part E: logistics and transportation review, 2002, 38(5): 305-318.

[3] XU X F，ZHANG W，LI N，et al. A bi-level programming model of resource matching for collaborative logistics network in supply uncertainty environment [J]. Journal of the Franklin institute, 2015, 352(9): 3873-3884.

[4] XU Xiaofeng, HAO Jun, DENG Yirui, et al. Design optimization of resource combination for collaborative logistics network under uncertainty[J]. Applied soft computing, 2017, 560(7): 684-691.

[5] CORDEAU J F, LEGATO P, MAZZA R M, et al. Simulation-based optimization for housekeeping in a container transshipment terminal[J]. Computers & operations research, 2015, 53: 81-95.

[6] KIM K H, BAE J W. A look-ahead dispatching method for automated guided vehicles in automated port container terminals[J]. Transportation science, 2004, 38(2): 224-234.

[7] KIM K H. A pooled dispatching strategy for automated guided vehicles in port container terminals [J]. International journal of management science, 2000, 6(2): 47-67.

[8] BISH E K, LEONG T Y, Li C L, et al. Analysis of a new vehicle scheduling and location problem[J]. Naval research logistics (NRL), 2001, 48(5): 363-385.

[9] BERGHMAN L, LEUS R. A Lagrangian heuristic for a dock assignment problem with trailer transportation[C]// 2010 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). [S.l.], 2010: 1376-1380.

[10] 楊靜蕾. 集裝箱碼頭物流路徑優化研究[J]. 水運工程, 2006(1): 32-35.

YANG Jinglei. Logistics routing optimization of constainer[J]. Port & waterway engineering, 2006(1): 32-35.

[11] 計明軍, 靳志宏. 集裝箱碼頭集卡與岸橋協調調度優化[J]. 復旦學報: 自然科學版, 2007, 46(4): 459-464.

JI Mingjun, JIN Zhihong. A united optimization of crane scheduling and yard trailer routing in a container terminal[J]. Journal of Fudan University: Natural Science, 2007, 46(4): 459-464.

[12] 曾慶成, 楊忠振. 集裝箱碼頭集卡調度模型與Q學習算法[J]. 哈爾濱工程大學學報, 2008, 29(1): 1-4.

ZENG Qingcheng, YANG Zhongzhen. A scheduling model and Q-learning algorithm for yard trailers at container terminals[J]. Journal of Harbin Engineering University, 2008, 29(1):1-4.

[13] 曹慶奎, 趙斐. 基于遺傳蟻群算法的港口集卡路徑優化[J]. 系統工程理論與實踐, 2013, 33(7): 1820-1828.

CAO Qingkui, ZHAO Fei. Port trucks route optimization based on GA-ACO[J]. Systems engineering-theory & practice, 2013, 33(7): 1820-1828.

[14] XIAO Y, ZHAO Q, KAKU I, et al. Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J]. Computers & operations research, 2012, 39(7): 1419-1431.

[15] 吳麗榮,胡祥培,饒衛振. 考慮燃料消耗率的車輛路徑問題模型與求解[J]. 系統工程學報, 2013, 28(6): 804-811.

WU Lirong, HU Xiangpei, RAO Weizhen. New capacity-vehicle-routing-problem model and algorithm for reducing fuel consumption[J]. Journal of systems engineering, 2013, 28(6): 804-811.

[16] 趙金樓, 黃金虎, 劉馨. 集裝箱碼頭的集卡兩階段路徑優化研究[J]. 中國管理科學, 2017(4): 152-157.

ZHAO Jinlou, HUANG Jinhu, LIU Xin. Two-stage optimization for yard trailers routing in container terminals [J]. Chinese jurnal of management dcience, 2017(4): 152-157.

[17] 紀震, 廖惠連, 吳青華. 粒子群算法及其應用[M]. 北京：科學出版社, 2009.

JI Zhen, LIAO Huilian, WU Qinghua. Particle swarm optimization and application [M]. Beijing：Science Press, 2009.

本文引用格式：

趙金樓， 黃金虎， 劉馨， 等. 考慮燃料成本的集裝箱碼頭集卡路徑優化[J]. 哈爾濱工程大學學報， 2017， 38(12): 1985-1990.

ZHAO Jinlou, HUANG Jinhu, LIU Xin, et al. Optimization for routing yard trailers in container terminals by considering fuel cost[J]. Journal of Harbin Engineering University， 2017， 38(12): 1985-1990.