集裝箱甩掛運輸車輛調度優(yōu)化模型的三階段啟發(fā)式算法

楊光敏　曹馨湖 楊珍花 靳志宏

摘要：

為完善解決軸輻式網絡下的集裝箱甩掛運輸調度問題，針對軸輻式甩掛運輸網絡中的不同任務類型，考慮掛車中心數量、位置及任務時間窗，構建甩掛運輸車輛調度優(yōu)化數學模型；設計基于任務緊迫度函數、懲罰函數和距離函數的三階段啟發(fā)式算法，分別調度緊急任務、普通任務和超期任務.通過對經典算例求解，分別針對牽引車、掛車、掛車中心和緊急任務等數量的變化等進行敏感性分析，顯示不同因素變化對整體調度方案的影響.該方法可為甩掛運輸企業(yè)調度決策者提供相關的決策支持.

關鍵詞：

甩掛運輸； 軸輻式網絡； 掛車中心； 時間窗； 啟發(fā)式算法

中圖分類號： U169.71；U492.22

文獻標志碼： A

0 引 言

軸輻式網絡是道路運輸的常見形式，胡志華等[1]對該物流網絡進行過樞紐重配置優(yōu)化研究.甩掛運輸集汽車列車運輸與裝卸甩掛作業(yè)技術于一體，是一種集約、高效的運輸組織模式.常見的甩掛模式有：一線兩點，兩端甩掛；循環(huán)甩掛；一線多點，沿途甩掛；多線一點，輪流拖帶[2].

現有文獻中有關帶有掛車的車輛路徑問題（Vehicle Routing Problem， VRP）的研究主要分為兩類.一類問題可以被描述為：一輛貨車配備一輛或者若干輛可以與之接掛或分離的掛車組成汽車列車.針對這類問題展開的研究主要有：SEMET等[3]首次討論了“公路列車”（拖帶一輛或多輛掛車的貨車）的VRP；GERDESSEN[4]提出了VRPT（Vehicle Routing Problem with Trailers）的兩種現實情境；CHAO[5]將帶有掛車的VRP定義為TTRP（Truck and Trailer Routing Problem），并首次為該問題建立數學模型而不是描述性模型；SCHEUERER[6]、LIN等[79]和VILLEGAS等[1011]分別設計啟發(fā)式算法、模擬退火算法和超啟發(fā)式算法求解TTRP；DERIGS等[12]對TTRP的變形問題進行研究；胡志華[13]為該問題建立子回路分割模型.

另一類問題則是對目前國內所推廣的“甩掛運輸”的研究.該類問題與前述問題的區(qū)別在于：（1）甩掛運輸問題中牽引車僅提供動力部分，沒有裝貨的空間，而前述問題中的貨車車頭既是動力引擎又提供裝貨空間；（2）與前述問題拖掛分離的目的不同，甩掛運輸中拖掛分離的目的是為了提高牽引車的利用率.雖然兩類問題都存在其現實意義與研究價值，但是本文的研究內容主要集中在對第二類問題即甩掛運輸問題的研究.

在甩掛運輸相關文獻中，HALL等[14]運用基于預測路徑生產率的控制規(guī)則判斷在循環(huán)甩掛中何時釋放牽引車.SMILOWITZ[15]運用嵌入列生成的分支定界法對帶有柔性任務的多資源路徑規(guī)劃問題進行求解.FRANCIS等[16]對SMILOWITZ[15]的模型及算法進行了改進，得到了更好的解.ZHANG等[17]對同一問題[1516]進行動態(tài)調度研究，運用兩階段算法對問題進行求解，目標是使運輸成本最小.TAN等[18]在LEE等[19]模型的基礎上加入掛車約束，首次建立了甩掛運輸問題的數學模型，運用混合多目標進化算法得到問題的帕累托最優(yōu)解.胡志華等[20]研究集裝箱集散環(huán)境下空重箱循環(huán)甩掛的調度問題，建立混合整數規(guī)劃模型，運用兩階段優(yōu)化方法求解該問題.繼而，胡志華[21]將該方法應用于集裝箱碼頭間互拖的集卡甩掛運輸調度問題.LI等[22]研究單車場牽引車與半掛車路徑問題（tractor and semitrailer routing problem），運用啟發(fā)式算法得到牽引車數量和每輛牽引車的路徑，但文章缺乏對該問題的數學建模.袁野等[23]對單一客戶點甩掛運輸的建模進行了分析.

分析文獻可以看出，現有文獻集中在對循環(huán)甩掛和多線一點、輪流拖帶這兩種甩掛模式的研究上.在問題描述方面，對多線一點、輪流拖帶的軸輻式網絡結構缺乏明確的定義.在建模方面，對甩掛運輸問題的數學建模，尤其是針對不同甩掛運輸模式的特色建模，還處于研究初期，需要進一步完善.在算法方面，除文獻[1517]運用分支定界法對問題進行求解外，其余文獻主要集中在啟發(fā)式算法上.本文基于已有的研究成果，運用啟發(fā)式算法求解軸輻式網絡下的集裝箱甩掛運輸調度問題，對該種模式的問題提取和模型建立進行深入研究.

本文對軸輻式網絡下的集裝箱整箱運輸牽引車調度問題進行研究，研究貢獻集中在：（1）對軸輻式集裝箱甩掛運輸的網絡進行明確的定義及闡述；（2）提出三階段啟發(fā)式算法迅速給出調度方案，保證甩掛企業(yè)實際應用的時效性；（3）對牽引車數量，掛車中心數量、位置，掛車數量、分布，以及緊急任務數量等重要參數進行敏感性分析，為甩掛企業(yè)經營人進行合理的資源配置提供參考.

1 問題描述

如圖1所示，橢圓中的軸輻式網絡由中央集散中心（或港口）與分布在周圍的客戶點、掛車中心（TrailerCenter，TC）和連接各點的弧構成.牽引車的路徑閉合，即從集散中心出發(fā)，最終回到集散中心.

出口集裝箱甩掛運輸操作流程為：牽引車從集散中心出發(fā)，先到TC掛一輛空掛車，再回到集散中

心的堆場取空箱運至客戶點處，并將載有空箱的掛車甩下，然后從客戶點返回集散中心或者駛向下一任務的開始節(jié)點.甩下的空掛車停留在客戶點處進行裝箱作業(yè).待客戶點處裝箱完畢后，牽引車將從客戶點將重掛取回至集散中心，重箱與掛車分離，落至堆場等待干線運輸.需要說明的是，為客戶點送空掛的牽引車和取重掛的牽引車可以不是同一輛.進口集裝箱甩掛運輸操作流程則與之相反.

根據集裝箱流向和客戶的需求，將牽引車的任務類型分為4種：取空箱、送空箱、取重箱、送重箱.4種任務類型兩兩組合可以形成16種任務子序列，當某個任務子序列為兩個送箱任務相連時，牽引車需要在兩任務中間訪問TC取空掛車；當相連任務為取箱任務時，牽引車需要訪問TC還空掛車.本文根據調度的不同階段，將任務分為緊急任務、普通任務和超期任務.緊急任務被定義為：在本規(guī)劃期的牽引車路徑規(guī)劃完成后，企業(yè)接到的新任務或任何需要優(yōu)先于其他任務完成的任務.普通任務被定義為：本規(guī)劃期內不需要被優(yōu)先完成的任務.超期任務被定義為：已經接受客戶申請，但因公司資源條件限制，無法在本規(guī)劃期內完成的任務.加入對緊急任務的處理是本文的創(chuàng)新點之一.

為了日常調度的實用性和時效性，啟發(fā)式算法在解決VRP中被大量應用.本文采用三階段啟發(fā)式算法對問題進行求解，三階段算法分別調度緊急任務、普通任務以及超期任務.在80個客戶點、100項任務、不同資源配置下的50項實驗中，該算法均能在5 s之內給出調度方案，極大地滿足企業(yè)在實際調度工作中對時效性的需求.

2 數學模型

在文獻[18]和[23]的基礎上進行擴展，建立如下數學模型.

2.1 模型假設

一輛牽引車僅能掛一輛掛車；牽引車與掛車在各任務節(jié)點的掛/甩掛車時間已知且不變；所有掛車均載有40英尺的集裝箱.

2.2 參數和變量

2.2.1 參數

G=V，D為運輸網絡；V=0，1，…，i，…，I為節(jié)點集合，其中節(jié)點0表示集散中心，其他節(jié)點表示客戶點及TC；D為節(jié)點之間弧的集合，Dij為兩節(jié)點i與j之間的路網距離；Ck為牽引車k的每千米油耗；K為牽引車總數；M為任務總數；Ma為緊急任務數；Mb為普通任務數；ma為緊急任務序號；mb為普通任務序號；

T為牽引車在規(guī)劃期內能夠完成的任務數上限；Tma，2為所有緊急任務的結束時間；Tmb，1為第一個普通任務的開始時間；Thpm為牽引車從緊前任務h終點到掛車中心p，再到緊后任務m起點的行駛時間；Thm為牽引車從緊前任務h終點到緊后任務m起點的行駛時間；Tm為牽引車從任務m起點到終點的行駛時間；Hm，1為任務m在起點的操作時間；Hm，2為任務m在終點的操作時間；Tk，1為牽引車k開始工作的時間；Tk，2為牽引車k結束工作的時間；TEm為任務m的最早開始執(zhí)行時間；TLm為任務m的最晚開始執(zhí)行時間；NSK為送空箱任務集合；NSZ為送重箱任務集合；NQK為取空箱任務集合；NQZ為取重箱任務集合.

2.2.2 決策變量

2.3 數學模型

式（1）為優(yōu)化目標，即方案總成本最??；式（2）表示每個任務僅被執(zhí)行一次；式（3）保證所有牽引車的任務分配有序；式（4）表示所有普通任務要在緊急任務之后被完成；式（5）～（8）表示每項任務的時間序列，其中式（5）是同一牽引車執(zhí)行前后兩項任務的時間遞推；式（9）表示每輛牽引車的工作時間均在規(guī)劃期內；式（10）保證滿足任務的時間窗要求；式（11）和（12）保證每輛牽引車的路線是閉合的；式（13）～（15）表示對TC的訪問約束，式（13）中當牽引車執(zhí)行第一項任務時，只有涉及送掛車時才會產生訪問TC取掛車的情況，執(zhí)行其他任務時前后兩項任務均需送掛車才會產生訪問TC取掛車的情況.

3 三階段啟發(fā)式算法

設計啟發(fā)式算法進行求解.根據任務的待執(zhí)行緊迫程度，將其分為緊急任務、普通任務和超期任務等3種，而任務性質的劃分則依賴于決策函數（緊迫度函數、懲罰函數和距離函數）.

任務的緊迫度越高，緊迫度函數值越大；任務執(zhí)行方案對其時間窗違反程度越高，懲罰函數值越大；距離函數則是執(zhí)行該任務所需行駛的總距離.

3.1 三階段啟發(fā)式算法總體流程

算法總體思路為優(yōu)先分配緊急任務，然后分配普通任務，最后推遲或外包超期任務，具體見圖2.

3.2 三階段啟發(fā)式算法具體步驟

3.2.1 分配緊急任務

緊急任務的緊迫度函數值相同，因此當同時出現多個緊急任務時，分別計算各任務的懲罰函數值后再進行分配.具體流程見圖3.

3.2.2 分配普通任務

緊急任務分配結束后，以任務的緊迫程度和子序列的懲罰函數值為標準進行普通任務的分配，具體流程見圖4.

3.2.3 外包或推遲超期任務

當存在超出規(guī)劃期的任務時，將這些超期任務推遲至下一規(guī)劃期或外包，具體見圖5.

4 算例實驗

通過改進文獻[18]中的算例，本文分別從牽引車數量、TC數量、掛車數量和緊急任務數量這4個方面驗證算法的有效性，并分析各因素對整體調度方案的影響.

軸輻式網絡由一個集散中心、若干個TC以及80個客戶點組成.TC和客戶點的位置隨機分布在100×100的網格上，集散中心位于網格中心.任意兩點之間采用歐氏距離.另外，本文的規(guī)劃期為早8：00到晚8：00（1天內）.牽引車行駛速度為60 km/h，單位掛/甩掛車時間為30 min.違反時間窗的懲罰因數a=b=1.

4.1 牽引車數量

本例共有11項實驗，牽引車數量從15輛逐一變化至25輛，任務數量均為100個，TC有5個，均勻分布在網絡中.每個TC的可用掛車均為6輛.

由圖6可以看出，牽引車的數量能夠直接影響任務的完成情況.當牽引車數量上升至19輛時，未完成的任務數下降至0，說明該系統(tǒng)內牽引車最低保有數量為19輛.牽引車從15輛逐漸增多，遲到懲罰成本降幅超過提前懲罰成本的漲幅；當牽引車數量超過20輛并繼續(xù)增多時，提前懲罰成本大幅上升，并且覆蓋了遲到懲罰成本的減少，造成總懲罰成本曲線呈“U”型.

4.2 TC數量

為研究TC的地理分布對調度方案總成本的影響，設置TC數量不同的算例，共8項實驗，TC數量有1，3和5個等3種情況.TC分布方式有：TC1～TC5均勻分布，僅設TC1，僅設TC2，僅設TC3，僅設TC4，僅設TC5，設置TC1，TC3和TC5，設置TC1，TC2和TC4等8種.掛車在TC均勻分布，總數均為30輛.

由圖7可以看出，TC的數量和分布方式會直接影響任務的完成情況和系統(tǒng)整體調度方案.總體而言，TC數量越多，分布越均勻，牽引車行駛的總里程及方案的總懲罰成本越小.當僅設置單一TC，且TC分布在1，3，4，5等4個位置時，出現了未完成任務.而當TC位于2位置時，總里程和總懲罰成本較其他算例更優(yōu)，證明TC的選址也會影響經營成本.

圖7 TC數量不同時的算例運算結果

4.3 掛車數量

該算例包括5組25項實驗，TC數量均為1個，分布方式分別為TC1，TC2，TC3，TC4和TC5.每項實驗任務數量均為100個，牽引車數量為20輛，每組實驗TC的掛車數量（NT）從23輛逐漸增至27輛.

由表1可見，在各TC的掛車數量增加的過程中，當掛車數量為23輛和24輛時以及第3組和第5組中當掛車數量為25輛時，因掛車數量難以滿足需要未能給出規(guī)劃結果.掛車數量不僅影響經營成本，還會直接影響經營質量：掛車數量過少無法完成既定的任務，而過多又會增加公司經濟負擔和管理成本.

4.4 緊急任務數量

設置緊急任務數量不同的6項實驗，任務數均為100個，牽引車數量均為20輛，TC可用掛車數均為30輛，5個TC均勻分配掛車，緊急任務的數量從0逐漸增長到5個.

由圖8可以看出，初期隨著緊急任務數量的增加，提前懲罰成本和遲到懲罰成本均逐漸下降，優(yōu)先處理緊急任務可以使整體方案違反時間窗的程度降低；當緊急任務數量上升至5個時，遲到懲罰成本仍保持下降趨勢，但提前懲罰成本增加，導致總懲罰成本上升幅度較大.這說明緊急任務的數量較多時，為盡快完成任務，對時間窗上限的違反程度較高.

圖8 緊急任務數量不同時的算例運算結果

5 結束語

本文建立了軸輻式網絡中甩掛運輸車輛調度問題的模型，提出了基于啟發(fā)式規(guī)則的三階段調度算法.基于牽引車數量不同、掛車中心數量不同、可用掛車數量有限和緊急任務數量不同等4個類型的算例實驗，提出了配置牽引車和掛車數量以及優(yōu)化掛車中心地理位置的具體方法，并闡述了緊急任務數量對調度計劃的影響.全面剖析了甩掛運輸系統(tǒng)調度時各因素的影響，為營運者提供一定的決策借鑒.

未來的研究將考慮甩掛運輸新模式下的調度優(yōu)化問題，例如牽引車對開、相遇后司機折返等.

參考文獻：

[1]胡志華， 洪雯婷， 胡青蜜. 軸輻式物流網絡擴張的樞紐重配置優(yōu)化[J]. 上海海事大學學報， 2015， 36（1）： 1924.

[2]高洪濤， 李紅啟. 道路甩掛運輸組織理論與實踐[M]. 北京： 人民交通出版社， 2010： 1819.

[3]SEMET F， TAILLARD E. Solving reallife vehicle routing problems efficiently using tabu search[J]. Annals of Operations Research， 1993， 41（4）： 469488.

[4]GERDESSEN J C. Vehicle routing problem with trailers[J]. European Journal of Operational Research， 1996， 93（1）： 135147.

[5]CHAO I M. A tabu search method for the truck and trailer routing problem[J]. Computers & Operations Research， 2002， 29（1）： 2251.

[6]SCHEUERER S. A tabu search heuristic for the truck and trailer routing problem[J]. Computers & Operations Research， 2006， 33（4）： 894909.

[7]LIN S W. Solving the truck and trailer routing problem based on a simulated annealing heuristic[J]. Computers & Operations Research， 2009， 36（5）： 16831692.

[8]LIN S W， YU V F， CHOU S Y. A note on the truck and trailer routing problem[J]. Expert Systems with Applications， 2010， 37（1）： 899903.

[9]LIN S W， YU V F， LU C C. A simulated annealing heuristic for the truck and trailer routing problem with time windows[J]. Expert Systems with Applications， 2011， 38（12）： 1524415252.

[10]VILLEGAS J G， PRINS C， PRODHON C. GRASP/VND and multistart evolutionary local search for the single truck and trailer routing problem with satellite depots[J]. Engineering Applications of Artificial Intelligence， 2010， 23（5）： 780794.

[11]VILLEGAS J G， PRINS C， PRODHON C. A GRASP with evolutionary path relinking for the truck and trailer routing problem[J]. Computers & Operations Research， 2011， 38（9）： 13191334.

[12]DERIGS U， PULLMANN M， VOGEL U. Truck and trailer routing problems， heuristics and computational experience[J]. Computers & Operations Research， 2013， 40（2）： 536546.

[13]胡志華. 基于混合進化算法的甩掛配送問題[J]. 公路交通科技， 2013， 30（5）： 147152.

[14]HALL R W， SABNANI V C. Control of vehicle dispatching on a cyclic route serving trucking terminals[J]. Transportation Research Part A： Policy and Practice， 2002， 36（3）： 257276.

[15]SMILOWITZ K. Multiresource routing with flexible tasks： an application in drayage operations[J]. IIE Transaction， 2006， 38（7）： 555568.

[16]FRANCIS P， ZHANG G， SMILOWITZ K. Improved modeling and solution methods for the multiresource routing problem[J]. European Journal of Operational Research， 2007， 180（3）： 10451059.

[17]ZHANG G， SMILOWITZ K， ERERA A. Dynamic planning for urban drayage operations[J]. Transportation Research Part E： Logistics and Transportation Review， 2011， 47（5）： 764777.

[18]TAN K C， CHEW Y H， LEE L H. A hybrid multiobjective evolutionary algorithm for solving truck and trailer vehicle routing problems[J]. European Journal of Operational Research， 2006， 172（3）： 855885.

[19]LEE L H， TAN K C， OU K. Vehicle capacity planning system： a case study on vehicle routing problem with time windows[J]. IEEE Transactions on Systems Man and Cybernetics Part A Systems and Humans， 2003， 33（2）： 169178.

[20]胡志華， 曹楊， 王云霞. 集裝箱集散的空重箱循環(huán)甩掛調度方法[J]. 武漢理工大學學報， 2012， 34（10）： 6873.

[21]胡志華. 集裝箱碼頭間互拖的集卡甩掛運輸調度問題[J]. 重慶交通大學學報（自然科學版）， 2013， 32（2）： 313317.

[22]LI Hongqi， LU Yue， ZHANG Jun， et al. Solving the tractor and semitrailer routing problem based on a heuristic approach[J]. Mathematical Problems in Engineering， 2012. DOI：10.1155/2012/182584.

[23]袁野， 徐家旺， 方云龍. 集裝箱甩掛運輸模型與應用[J]. 沈陽航空航天大學學報， 2014， 31（1）： 9296.

（編輯 賈裙平）