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

摘要：

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

關(guān)鍵詞：

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

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

文獻(xiàn)標(biāo)志碼： A

0 引 言

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

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

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

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

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

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

1 問題描述

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

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

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

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

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

2 數(shù)學(xué)模型

在文獻(xiàn)[18]和[23]的基礎(chǔ)上進(jìn)行擴(kuò)展，建立如下數(shù)學(xué)模型.

2.1 模型假設(shè)

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

2.2 參數(shù)和變量

2.2.1 參數(shù)

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

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

2.2.2 決策變量

2.3 數(shù)學(xué)模型

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

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

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

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

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

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

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

3.2.1 分配緊急任務(wù)

緊急任務(wù)的緊迫度函數(shù)值相同，因此當(dāng)同時出現(xiàn)多個緊急任務(wù)時，分別計算各任務(wù)的懲罰函數(shù)值后再進(jìn)行分配.具體流程見圖3.

3.2.2 分配普通任務(wù)

緊急任務(wù)分配結(jié)束后，以任務(wù)的緊迫程度和子序列的懲罰函數(shù)值為標(biāo)準(zhǔn)進(jìn)行普通任務(wù)的分配，具體流程見圖4.

3.2.3 外包或推遲超期任務(wù)

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

4 算例實驗

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

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

4.1 牽引車數(shù)量

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

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

4.2 TC數(shù)量

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

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

圖7 TC數(shù)量不同時的算例運算結(jié)果

4.3 掛車數(shù)量

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

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

4.4 緊急任務(wù)數(shù)量

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

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

圖8 緊急任務(wù)數(shù)量不同時的算例運算結(jié)果

5 結(jié)束語

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

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

參考文獻(xiàn)：

[1]胡志華， 洪雯婷， 胡青蜜. 軸輻式物流網(wǎng)絡(luò)擴(kuò)張的樞紐重配置優(yōu)化[J]. 上海海事大學(xué)學(xué)報， 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ìn)化算法的甩掛配送問題[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)甩掛調(diào)度方法[J]. 武漢理工大學(xué)學(xué)報， 2012， 34（10）： 6873.

[21]胡志華. 集裝箱碼頭間互拖的集卡甩掛運輸調(diào)度問題[J]. 重慶交通大學(xué)學(xué)報（自然科學(xué)版）， 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]袁野， 徐家旺， 方云龍. 集裝箱甩掛運輸模型與應(yīng)用[J]. 沈陽航空航天大學(xué)學(xué)報， 2014， 31（1）： 9296.

（編輯 賈裙平）