基于碼頭集卡共享的運輸任務分配優化模型

曾慶成 于婷

摘要：為提高港口集疏運效率，減少集卡空駛，提出一種基于集卡共享的任務分配方法。以最大化承運人的總利潤為目標，引入補償機制激勵承運人合作，考慮進出口任務的截止時間、承運人車隊大小，建立基于碼頭集卡共享的任務分配模型。通過優化進出口任務分配，減少集卡空駛，并設計啟發式算法求解模型。分析不同情景下承運人的利潤變化，并通過算例分析驗證算法的有效性。結果表明：基于集卡共享的任務分配模型能夠有效地對任務分配過程進行優化和控制，進而提高集卡作業效率。

關鍵詞： 集裝箱碼頭; 集疏運系統; 遺傳算法; 集卡共享; 任務分配

中圖分類號： U169.71 ? ?文獻標志碼： A

Abstract： In order to improve the efficiency of port collecting and distributing system and decrease the unloaded distance of trucks， a task allocation method based on truck sharing is proposed. With the objective of maximizing carriers total profit， a compensation mechanism is introduced to motivate carriers to cooperate together. Considering the deadline of import and export tasks and the size of carriers fleet， a task allocation model based on truck sharing is developed. The unloaded distance of trucks is decreased by optimizing the allocation of import and export tasks. A heuristic algorithm is designed to solve the model. The carriers profit change under different conditions is analyzed， and the validity of the algorithm is verified by example analysis. Results indicate that the task allocation model based on truck sharing can effectively control and optimize the process of task allocation， and then improve the operation efficiency of trucks.

Key words： container terminal; collecting and distributing system; genetic algorithm; truck sharing; task allocation

我國港口集裝箱有80%以上通過公路集疏運，由外集卡完成進港-出港的拖運作業。大量的拖運作業導致高峰時段碼頭擁堵，這不僅會嚴重影響集疏運效率，降低碼頭運營效率，而且會加劇港區污染。此外，由于進出口運輸任務不平衡，大量的集卡都是單程運輸，所以集卡運輸成本高，集疏運效率低。

國內外學者針對集卡調度和任務分配問題開展了大量研究。集卡的路徑優化方面：曹慶奎等[1]探討了成本對路徑選擇的影響，并建立了面向作業面的集卡路徑成本優化模型;李廣儒等[2]分析了整個碼頭水平作業的動態調度方案，提出一種求解集卡動態調度路徑的自適應蟻群算法，進而提高集卡利用率;ZHANG等[3]研究了多個倉庫和碼頭的集卡路徑規劃問題，并考慮入站滿箱、入站空箱、出站滿箱、出站空箱等4種集裝箱運輸方式以及港口的時間窗，獲得了作業時間最短的集卡運輸路徑;STERZIK等[4]同時考慮了車輛路徑和空箱使用率，并設計禁忌搜索算法得出車輛行駛時間最短的運輸路徑;CORDEAU等[5]在研究集卡路徑優化時綜合考慮了集卡的運行時間和等待時間，并通過仿真來模擬不同時刻集卡的運輸路徑，設計局部搜索算法進行求解;楊靜蕾[6]建立了基于總行駛距離最短的集裝箱碼頭路徑規劃模型，獲得集卡的最優路徑。集卡任務分配方面：LAI等[7]將進出口任務結合起來，假設集裝箱和集卡不是分開服務的，并設計了Clarke-and-Wright算法，最大限度地降低集卡的運營成本;周林等[8]以運輸成本最小為目標，分別考慮物流成本和延遲成本，建立多任務優化模型，設計了基于優先權的遺傳算法;趙金樓等[9]綜合研究燃料成本和作業時間對集卡運輸的影響，構建基于集卡作業時間最短、燃料成本最低的任務分配模型，并用算例驗證了模型的有效性;曾慶成等[10]從碼頭整體作業效率角度出發，建立集卡動態調度模型，并設計了Q學習算法對每輛集卡的裝卸任務進行分配;NOSSACK等[11]對承運人的運輸任務安排以及空箱調度進行分析，建立了集卡任務分配模型;YU等[12]研究了基于越庫作業的集卡任務分配問題，以最小化作業時間為目標，求得集卡的最優任務分配方案和作業位置。為提高集卡利用率，承運人聯盟與集卡聯合調度得到越來越多的關注：KRAJEWSKA等[13]運用合作博弈理論研究橫向合作所產生的節約成本的分配，并以最大化總節約成本為研究目標，提出一種用于多個承運人之間協作的規劃方法;LI等[14]提出部分信息共享機制，解決兩個承運人協作過程中的任務選擇和交換問題，以最大化承運人的總利潤為目標構建了兩階段混合整數規劃模型;VERDONCK等[15]提出了共享配送倉庫機制，該問題可以歸類為選址問題，為確保合作的可持續性，需要將協作成本公平地分配給不同的參與者，通過合作博弈來分析共享倉庫的好處以及不同的成本分配方式可能帶來的影響;STERZIK等[16]的研究表明，在承運人之間共享空箱能夠極大地節約成本，推動兩家公司繼續合作的機制至關重要;ZENER等[17]提出在一個物流網絡下的托運人形成一個聯盟，將所有貨運需求整合優化分配給承運人可以大大降低運輸成本，并通過合作博弈論驗證了該方案的可行性;CABALLINI等[18]以節約的運輸成本最多為目標，探討了在多承運人聯盟的情況下，運輸任務的整合與分配，并通過啟發式算法證明任務的整合與再分配能夠減少集卡的空駛。

本文在已有研究基礎上提出一種基于外集卡共享的任務分配方法，以最大化承運人的總利潤為目標，引入補償機制激勵承運人合作，同時考慮進出口任務的截止時間和承運人車隊大小，建立任務分配模型，將進口任務與出口任務進行最優組合后分配給承運人，進而提高集卡利用率，降低運輸成本。

1 問題描述與建模

1.1 基于集卡共享的任務分配問題

集裝箱碼頭集卡拖運問題可以歸結為“星型”網絡問題，如圖1所示。圖1中：中心節點1代表港口，對于進口任務節點1為起點，對于出口任務節點1則為終點;其他節點代表物流中心;實線代表進口，虛線代表出口。

傳統的進出口運輸過程如圖2a所示。進口過程：承運人R1的集卡在港口1提一個滿箱→運載滿箱至物流中心2并交付→空駛返回港口1。出口過程：承運人R2的集卡在港口1提一個空箱→運載空箱至物流中心3并裝貨→運載滿箱至港口1并交付。這種進出口策略不僅造成了大量的空駛和較高的成本，同時也加重了交通擁堵和環境問題。

共享經濟背景下的進出口運輸過程如圖2b所示：集卡在港口1提一個滿箱→運載滿箱至物流中心2并交付→繼續行駛至物流中心3，提一個滿箱→運載滿箱至港口1并交付。

與傳統的進出口運輸過程相比，外集卡共享運輸不僅減少了集卡的空載行駛距離，而且改變了很多碼頭集卡單程運輸的作業狀態，有利于提高集卡的作業效率，進而提高集疏運效率。為此，本文構建基于集卡共享的運輸任務分配優化模型，通過將進口任務與出口任務進行最優組合，減少集卡空駛，提高碼頭作業效率。

1.2 模型構建

構建模型的假設條件如下：（1）港口有多個承運人在此承運貨物，每個承運人有一定數量同質的集卡和一些進出口運輸任務，每個任務的運輸距離已知;（2）所有承運人的運輸任務可以共享;（3）每個承運人有統一的管理成本;（4）所有的集裝箱尺寸均為20 TEU;（5）每個運輸任務有一個起點、一個終點和一個截止時間;（6）每個托運人的需求均能得到滿足，且有時間窗限制;（7）只有進口與出口任務可以進行組合。

模型參數定義如下：NI為進口任務的集合，ni∈NI;NE為出口任務集合，ne∈NE;N為所有進口與出口任務集合，N=NI∪NE，n∈N;R為承運人集合，r∈R;dn（n∈N）為任務n起點與終點之間的距離，km;tne為服務任務ne所需的時間，tne=dne/v+βne，其中v為集卡的行駛速度，km/h，βne為在節點拆箱和裝箱的時間;δni為與任務ni相關的補償費用;δne為與任務ne相關的補償費用;bne為任務ne的開始時間;fni為任務ni的完成時間;hne為任務ne的截止期限;tnine為服務任務對（ni，ne）所需的總時間;fnine為任務對（ni，ne）的結束時間;[Pone，Po′ne]為任務ne在開始節點的時間窗;[Pdne，Pd′ne]為任務ne在結束節點的時間窗;εnine為把任務ni與ne組合起來時，需要行駛的距離;Cdnine為延遲成本，如果任務ne在截止期限后結束則計算延遲成本，Cdnine=cd（fnine-hne），其中cd為單位延遲成本;Nr為承運人r所擁有的任務的集合;cr為承運人r執行任務的單位成本，元/km;znr，若任務n由承運人r執行，則znr=1，否則znr=0;Sr0為承運人r獨立執行其任務所獲得的利潤;Sr為承運人r的最終利潤;Vr為承運人r可用的集卡的數量;g為承運人執行一次任務的單位收入;M為一個很大的數。

步驟6 交換變異算子。首先從1、2、3三個數中隨機選擇一個，1代表第一行進行變異，以此類推;接著隨機產生兩個變異點的位置，將對應位置的任務序列進行交換，即可生成新的染色體。

步驟7 修復算子。通過交叉和變異操作會產生很多不可行解，對不可行解的修復對提高算法的運行效率十分重要，因此構造修復步驟如下：①將初始化種群過程中生成的優質解存儲到一個元胞數組G{i}中;②對交叉變異后的每個個體進行約束檢驗;③當檢測出不可行解時，首先按照初始化種群的步驟重新生成個體，進行再檢測，并設置此迭代的最大次數為3，當運行3次后依舊是不可行解時，用存儲的優質解G{i}代替不可行解，進而保證種群規模不變。

步驟8 終止準則。當進化代數達到設定的最大迭代次數時，計算結束，得到最優分配方案，否則執行步驟3。

3 模擬計算與結果分析

3.1 基于集卡共享的任務分配問題

港口A有3家承運人負責30個運輸任務。假設3家承運人均服務于由1個港口節點和8個物流節點構成的相同區域。表1設置了10種不同的情景，每個情景之間均存在差異。表1中：I/E表示進/出口任務數;集卡的平均行駛速度為50 km/h。

3.2 算法有效性驗證

為選擇合適的遺傳參數，先進行多次實驗，在保證解的精確性和算法運行時間最短的情況下，設定種群規模為100，最大迭代次數為200，交叉概率為0.8，變異概率為0.1。

為驗證本文設計的改進的遺傳算法的有效性，小規模算例采用Cplex進行求解，大規模算例采用啟發式算法求解，每個算例運行5次，取平均值。表2和3分別展現了不同規模算例的求解結果。

由表2可以發現，當進出口任務數達到30個時，Cplex已經無法在短時間內求出精確解，而本文設計的遺傳算法能夠在很大程度上提高計算效率，并且可以在較短時間內求得高質量的解，平均Gap值只有3.31%。表3展示了本文提出的算法在求解大規模算例時的計算時間和目標函數值。由表3可以發現，程序的計算時間差別不大，即使任務數達到100個，本文提出的算法仍然可以在較短時間內求出結果，計算時間只有15.72 s。由此可見，本文設計的求解算法是有效的。

3.3 Digkstra算法初始化種群有效性分析

化種群的程序收斂速度對比 ?當承運人數量為3，進出口任務數為30時，計算目標函數值，驗證Digkstra算法初始化種群的有效性，實驗結果見圖5。從圖5可知：采用隨機組合法生成初始種群時，適應度函數值在收斂過程中有些波動，且最優解不穩定，計算時間長達38.26 s;使用Digkstra算法的收斂速度較快，迭代次數少，適應度函數值變化范圍小，且能夠保持在最優解中，計算時間7.45 s，算法有效。

3.4 承運人利潤對比分析

圖6給出了不同情景下承運人最終利潤和初始利潤的對比情況，其中實線柱代表最終利潤，虛線柱代表初始利潤。由圖6可知，承運人1所獲得的利潤最高，一方面是因為承運人1擁有的初始任務數最多，共享后獲得的補償多，另一方面是因為承運人1擁有較低的單位成本。對于整個聯盟而言，最終利潤高于初始利潤，也證明共享集卡有利。

3.5 δ值分析

承運人利潤的影響 ?為進一步分析補償值δ對承運人利潤的影響，假設每個承運人的經營成本相同，δ取值范圍200～500。圖7顯示了δ值變化對承運人最終利潤的影響。當δ>450時，至少有一個承運人的最終利潤低于其初始利潤，出現這種情況就表明共享集卡對該承運人是不利的，從而應該終止合作，因此δ的取值對于整個聯盟至關重要。

對于一個承運人而言，在執行一次組合的任務后，所獲得的收益為2gdni+dne-crdni+dne+εnine-Cdnine。如果這兩個任務均是與其他承運人共享的，那么該承運人就要給任務對（ni，ne）的承運人一定的補償，且收益2gdni+dne-crdni+dne+εnine-Cdnine一定大于或等于補償值δni+δne。因此，各承運人可以通過上述關系得出補償值δ大概的取值范圍，并與其他承運人協商出一個恰當的值，進而保證合作的可持續性。4 結 論

本文針對拖車運輸作業環節，提出一種基于外集卡共享的任務分配方法。以最大化承運人的總利潤為目標，引入補償機制激勵承運人合作，同時考慮進出口任務的截止時間、承運人車隊大小，建立了基于集卡共享的運輸任務分配優化模型，通過將進口任務與出口任務進行最優組合，減少集卡空駛。設計了改進的遺傳算法求解模型，并用實際數據對不同情景下承運人的利潤進行對比分析。實驗結果表明，在共享背景下每個承運人的最終利潤都不低于其初始利潤，表明此合作機制有效。本文構建的基于集卡共享的運輸任務分配優化模型不僅能夠為合作承運人帶來經濟優勢，還可以減少擁堵和環境污染，提高集卡的作業效率。

本文沒有考慮工作量均衡以及卡車司機最長的工作時間等因素，進一步研究可以考慮此類約束，進一步完善集卡調度優化模型，設計更精確的算法，使其更接近集卡運輸的實際情況，具有更強的實用性。

參考文獻：

[1] 曹慶奎， 趙斐. 基于遺傳蟻群算法的港口集卡路徑優化[J]. 系統工程理論與實踐， 2013， 33（7）： 1820-1828. DOI： 10.3969/j.issn.1000-6788.2013.07.023.

[2] 李廣儒， 楊大奔， 任大偉. 集卡動態調度路徑優化算法[J]. 交通運輸工程學報， 2012， 12（3）： 86-91.

[3] ZHANG Ruiyou， YUN Won Young， KOPFER H. Heuristic-based truck scheduling for inland container transportation[J]. OR Spectrum， 2010， 32： 787-808. DOI： 10.1007/s00291-010-0193-4.

[4] STERZIK S， KOPFER H. A tabu search heuristic for the inland container transportation problem[J]. Computers & Operations Research， 2013， 40（4）： 953-962. DOI： 10.1016/j.cor. 2012.11.015.

[5] CORDEAU J F， LEGATO P， MAZZA R M， et al. Simulation-based optimization for housekeeping in a container trans-shipment terminal[J]. Computers & Operations Research， 2015， 53： 81-95. DOI： 10.1016/j.cor.2014.08.001.

[6] 楊靜蕾. 集裝箱碼頭物流路徑優化研究[J]. 水運工程， 2006（1）： 32-35. DOI： 10.3969/j.issn.1002-4972.2006.01.008.

[7] LAI M， CRAINIC T G， FRANCESCO M D， et al. An heuristic search for the routing of heterogeneous trucks with single and double container loads[J]. Transportation Research Part E， 2013， 56： 108-118. DOI： 10.1016/j.tre.2013.06.001.

[8] 周林， 王旭， 林云， 等. 面向空間分布式小批量物流供需的多任務集成調度[J]. 計算機集成制造系統， 2016， 22（3）： 822-832. DOI： 10.13196/j.cims.2016.03.027.

[9] 趙金樓， 黃金虎， 劉馨， 等. 考慮燃料成本的集裝箱碼頭集卡路徑優化[J]. 哈爾濱工程大學學報， 2017， 38（12）： 1985-1990. DOI： 10.11990/jheu.201709060.

[10] 曾慶成， 楊忠振. 集裝箱碼頭集卡調度模型與Q學習算法[J]. 哈爾濱工程大學學報， 2008， 29（1）： 1-4. DOI： 10.3969/j.issn.1006-7043.2008.01.001.

[11] NOSSACK J， PESCH E. A truck scheduling problem arising in intermodal container transportation[J]. European Journal of Operational Research， 2013， 230： 666-680. DOI： 10.1016/j.ejor.2013.04.042.

[12] YU W， EGBELU P J. Scheduling of inbound and outbound trucks in cross docking systems with temporary storage[J]. European Journal of Operational Research， 2008， 184（1）： 377-396. DOI： 10.1016/j.ejor.2006.10.047.

[13] KRAJEWSKA M A， KOPFER H， LAPORTE G， et al. Horizontal cooperation among freight carriers： request allocation and profit sharing[J]. Journal of the Operational Research Society， 2008， 59（11）： 1483-1491. DOI： 10.1057/palgrave.jors.2602489.

[14] LI Junsong， RONG Gang， FENG Yiping. Request selection and exchange approach for carrier collaboration based on auction of a single request[J]. Transportation Research Part E， 2015， 84： 23-39. DOI： 10.1016/j.tre.2015.09.010.

[15] VERDONCK L， BEULLENS P， CARIS A， et al. Analysis of collaborative savings and cost allocation techniques for the cooperative carrier facility location problem[J]. Journal of the Operational Research Society， 2016， 67（6）： 853-871. DOI： 10.1057/jors.2015.106.

[16] STERZIK S， KOPFER H， YUN W Y. Reducing hinterland transportation costs through container sharing[J]. Flexible Services and Manufacturing Journal， 2015， 27： 382-402. DOI： 10.1007/s10696-012-9167-y.

[17] ZENER O ， ERGUN . Allocating costs in a collaborative transportation procurement network[J]. Transportation Science， 2008， 42（2）： 146-165. DOI： 10.1287/trsc.1070.0219.

[18] CABALLINI C， SACONNE S， SAEEDNIA M. Planning truck carriers operations in a cooperative environment[J]. IFAC Proceedings Volumes， 2014， 47（3）： 5121-5126.

[19] 劉志宏， 胡永明， 施工. 特征統計算法及其在NP組合優化問題上的應用[J]. 科技導報， 2006， 24（11）： 28-30. DOI： 10.3321/j.issn：1000-7857.2006.11.009.

[20] 侯運炳， 夏興， 閆旭. 基于礦井地理網絡模型的最短路徑改進算法[J]. 煤炭科學技術， 2011， 39（2）： 103-105. DOI： 10.13199/j.cst.2011.02.108.houyb.030.

（編輯 賈裙平）