基于碼頭集卡共享的運輸任務(wù)分配優(yōu)化模型

曾慶成 于婷

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

關(guān)鍵詞： 集裝箱碼頭; 集疏運系統(tǒng); 遺傳算法; 集卡共享; 任務(wù)分配

中圖分類號： 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%以上通過公路集疏運，由外集卡完成進港-出港的拖運作業(yè)。大量的拖運作業(yè)導(dǎo)致高峰時段碼頭擁堵，這不僅會嚴重影響集疏運效率，降低碼頭運營效率，而且會加劇港區(qū)污染。此外，由于進出口運輸任務(wù)不平衡，大量的集卡都是單程運輸，所以集卡運輸成本高，集疏運效率低。

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

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

1 問題描述與建模

1.1 基于集卡共享的任務(wù)分配問題

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

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

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

與傳統(tǒng)的進出口運輸過程相比，外集卡共享運輸不僅減少了集卡的空載行駛距離，而且改變了很多碼頭集卡單程運輸?shù)淖鳂I(yè)狀態(tài)，有利于提高集卡的作業(yè)效率，進而提高集疏運效率。為此，本文構(gòu)建基于集卡共享的運輸任務(wù)分配優(yōu)化模型，通過將進口任務(wù)與出口任務(wù)進行最優(yōu)組合，減少集卡空駛，提高碼頭作業(yè)效率。

1.2 模型構(gòu)建

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

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

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

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

步驟8 終止準則。當進化代數(shù)達到設(shè)定的最大迭代次數(shù)時，計算結(jié)束，得到最優(yōu)分配方案，否則執(zhí)行步驟3。

3 模擬計算與結(jié)果分析

3.1 基于集卡共享的任務(wù)分配問題

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

3.2 算法有效性驗證

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

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

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

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

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

3.4 承運人利潤對比分析

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

3.5 δ值分析

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

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

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

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

參考文獻：

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

[2] 李廣儒， 楊大奔， 任大偉. 集卡動態(tài)調(diào)度路徑優(yōu)化算法[J]. 交通運輸工程學(xué)報， 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] 楊靜蕾. 集裝箱碼頭物流路徑優(yōu)化研究[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] 周林， 王旭， 林云， 等. 面向空間分布式小批量物流供需的多任務(wù)集成調(diào)度[J]. 計算機集成制造系統(tǒng)， 2016， 22（3）： 822-832. DOI： 10.13196/j.cims.2016.03.027.

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

[10] 曾慶成， 楊忠振. 集裝箱碼頭集卡調(diào)度模型與Q學(xué)習算法[J]. 哈爾濱工程大學(xué)學(xué)報， 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] 劉志宏， 胡永明， 施工. 特征統(tǒng)計算法及其在NP組合優(yōu)化問題上的應(yīng)用[J]. 科技導(dǎo)報， 2006， 24（11）： 28-30. DOI： 10.3321/j.issn：1000-7857.2006.11.009.

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

（編輯 賈裙平）