網(wǎng)絡型甩掛運輸模式下的車輛調(diào)度問題

余 莉 林 樺 陳伯如

0 引 言

甩掛運輸是指牽引車按照預定的運行計劃，牽引車拖帶掛車至目的地，在目的地點甩下所拖的掛車，換上其他掛車繼續(xù)往另一個目的地的運輸組織方式[1]。在甩掛運輸實際運作中，牽引車與半掛車或掛車之間能夠自由分離、耦合，通過兩者之間的合理調(diào)度、接合，可以大幅度減少牽引車到達目的地后裝卸貨的等待時間，從而提高牽引車的運輸效率。正因如此，甩掛運輸成為我國道路運輸?shù)谋厝悔厔輀2]。

1 甩掛運輸?shù)慕M織模式

道路甩掛運輸?shù)慕M織模式主要有以下幾種：一線兩點、一線多點、一點多線和網(wǎng)絡型甩掛四種模式。

1.1 一線兩點甩掛運輸

一線兩點甩掛運輸是在短途運輸線路上采用的形式。牽引車往復于兩裝卸作業(yè)點之間，牽引車在線路兩端根據(jù)具體條件作甩掛作業(yè)，根據(jù)貨流情況或裝卸能力，可采用“一線兩點，一端甩掛”（即裝甩卸不甩）和“一線兩點，兩端甩掛”。以“一線兩點，兩端甩掛”為例：設有A、B兩個裝卸作業(yè)點，A、B兩點各預留一定數(shù)量的掛車。牽引車拖掛掛車從A點出發(fā)駛向 B點，到達 B點后，卸下掛車，掛上預留在 B點的掛車，駛向 A點。到達 A后卸下掛車，裝上 A點掛車，進行下一循環(huán)。

1.2 一線多點甩掛運輸

由一線兩點的甩掛模式演化而來，裝卸作業(yè)點在兩個以上，所有裝卸作業(yè)點由運輸車輛串聯(lián)。每個裝卸點存在數(shù)量不等的半掛車，由單一的牽引車順次在不同甩掛作業(yè)區(qū)進行甩掛作業(yè)。

1.3 一點多線甩掛運輸

一點多線甩掛運輸也是由一線兩點的模式演化而來，所不同的是，一般其運輸是單向的，即在一個完整的運輸過程中（去程+回程），貨物從集貨點向貨運站方向運輸，或與之相反。因此在該模式下，牽引車去程是空載，回程是滿載，或與之相反。

1.4 網(wǎng)絡型甩掛運輸

網(wǎng)絡型甩掛模式是甩掛運輸發(fā)展到一定階段的產(chǎn)物，適合多個裝卸作業(yè)點的長途運輸。網(wǎng)絡型甩掛運輸?shù)穆肪€不一定是線性的，而是將整個運輸線路有機地結(jié)合起來。網(wǎng)絡中的各個裝卸作業(yè)點可能對任何其他作業(yè)點產(chǎn)生貨運需求。

2 車輛調(diào)度問題

車輛調(diào)度問題（Vehicle scheduling problem，簡稱 VSP）是運輸管理研究中的核心問題之一。VSP一般描述為：對一系列客戶（取、送貨點），組織適當?shù)男熊嚶肪€使車輛有序地通過它們，在滿足一定的約束條件（如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等）下，達到一定的目標（如路程最短、費用極小、時間盡量少、使用車輛數(shù)盡量少等）[3]。

2.1 車輛調(diào)度問題的分類

車輛調(diào)度問題根據(jù)不同的標準可分為不同的類別[4]。根據(jù)車場（或貨場、配送中心等）的數(shù)目分為單車場問題和多車場問題；根據(jù)運輸車輛的種類多少可分為單車型問題（所有車輛容量相同）和多車型問題（車輛的容量不全相同）；根據(jù)車輛是否有容量約束，可分為有容量約束的車輛調(diào)度問題和無容量約束的車輛調(diào)度問題；根據(jù)載貨現(xiàn)狀可以分為滿載車輛路徑問題、非滿載車輛路徑問題；根據(jù)貨運任務的完成是否有時間要求，車輛調(diào)度問題又可分為有時間窗約束和無時間窗約束的車輛調(diào)度問題；根據(jù)路徑規(guī)劃信息是否是一成不變，車輛調(diào)度問題可分為靜態(tài)車輛調(diào)度問題和動態(tài)車輛調(diào)度問題。根據(jù)貨運任務的性質(zhì)，分為純裝貨問題、純卸貨問題以及裝卸貨混合問題。

網(wǎng)絡型甩掛運輸網(wǎng)絡中存在多個車場，牽引車拖掛掛車在各節(jié)點間進行作業(yè)，因此網(wǎng)絡型甩掛運輸模式下的車輛調(diào)度問題屬于滿載多車場車輛調(diào)度問題。

2.2 甩掛運輸調(diào)度問題

甩掛運輸?shù)淖畲筇攸c在于牽引車和掛車可以相互分離，其車輛調(diào)度問題也與傳統(tǒng)車輛調(diào)度問題有所區(qū)別，這對車輛調(diào)度工作提出了新的要求。本文研究滿載運輸情況下的“一車一掛”甩掛運輸車輛調(diào)度問題，文中將甩掛運輸網(wǎng)絡中的各個運輸節(jié)點（如港口碼頭、物流園區(qū)、客戶倉庫等）視為牽引車的“服務點”，并假設這些服務點均有足夠的空間存放掛車。

下面通過一個實際操作中的簡單示例來說明這種甩掛運輸?shù)牟僮鞣椒ê驼{(diào)度過程。

（1）問題描述

假設在 2個車場和 5個服務點之間實行甩掛運輸，2個車場編號分別是車場A和車場B；5個服務點編號分別是服務點 a、服務點 b、服務點 c，服務點d和服務點e。服務點a需要運1單位掛車貨至服務點b，服務點b有1單位掛車貨將根據(jù)貨物類型運至服務點c或服務點d，服務點e要運2單位掛車貨至服務點d。各服務點的運輸需求和位置關(guān)系如圖1所示。車場的空掛車數(shù)量不限，車場之間牽引車和掛車可以相互調(diào)用，牽引車實行“一車一掛”的甩掛運輸，運輸需求完成后，各服務點的掛車數(shù)目保持不變，牽引車返回車場。需要調(diào)度人員根據(jù)各服務點的貨運需求和所擁有的車輛資源對這一系列任務進行調(diào)度。

圖1 甩掛運輸車輛調(diào)度示意Fig.1 Sketch map of drop and pull transport vehicle scheduling

（2）調(diào)度過程

第一階段：先從距離服務點a最近的車場A派出牽引車1拖掛空掛車至服務點a，卸下空掛車，掛上服務點a事先裝載好的送往服務點b的重掛車。同時從距離服務點e最近的車輛B派出牽引車2拖掛空掛車至服務點e，卸下空掛車后，掛上事先裝載好的送往服務點d的重掛車。

第二階段：牽引車1從服務點a將重掛車運至服務點b，卸下重掛、裝上在服務點b的空掛車。牽引車2從服務點e將重掛運至服務點d，卸下重掛、裝上在服務點d的空掛車。

第三階段：牽引車1從服務點b將重掛運至服務點c，卸下重掛車，裝上在服務點c或d的空掛車。

牽引車2從服務點d將空掛車運至服務點e，卸下空掛車，裝上事先裝載好的送往服務點d的重掛車。

第四階段：牽引車1從服務點c或d將空掛帶回車場A或B。

牽引車2從服務點e將重掛運至服務點d，卸下重掛車，裝上在服務點d的空掛車。

第五階段：牽引車2從服務點d將空掛車帶回車場B。

牽引車的總路線流程為：

牽引車2：

該問題的車輛調(diào)度如圖1所示。

3 網(wǎng)絡型甩掛運輸車輛調(diào)度問題的數(shù)學建模

3.1 問題描述

甩掛運輸車輛的調(diào)度問題可以描述為：

某個運輸系統(tǒng)里分布有多個車場和多個服務點，牽引車只能停放在車場，每個車場可提供的牽引車和空掛車數(shù)量不限，車場之間的牽引車和掛車資源共享，但牽引車運輸不可以從車場到車場。服務點有足夠數(shù)量的空掛車，服務點之間的掛車可以通用，但服務點自身擁有的掛車數(shù)保持不變。為滿足服務點之間的貨運需求，在甩掛運輸?shù)哪Ｊ较?，牽引車從車場出發(fā)向多個服務點執(zhí)行配送任務，在有限時間內(nèi)完成貨運需求后返回車場，如何安排牽引車合理的配送路線，使得總運輸成本最小。

（1）已知條件

①車場與服務點之間的往返路線不一定對稱，運輸網(wǎng)絡中各個車場及各服務點之間的距離固定。②用單位掛車作為兩點間的貨運需求量的單位。③多個車場服務多個服務點，且車場能提供牽引車和掛車的數(shù)量不限。

④牽引車行駛路線的起點和終點均為車場，但牽引車不可從車場直接行駛到車場。

⑤客戶自身擁有足夠數(shù)量的空掛車，所有待運貨物都在牽引車到來之前裝上，客戶間的掛車可以通用，但客戶擁有的掛車數(shù)量保持不變。

⑥牽引車卸掛和裝掛的作業(yè)時間較短，忽略不計。⑦牽引車以固定的平均行駛速度進行運輸作業(yè)。（2）優(yōu)化目標

單目標：總運輸成本最低。

3.2 模型構(gòu)建

3.2.1 建模說明

為了滿足服務點i到服務點j之間的貨運需求，首先牽引車從距離服務點 i最近的車場或服務點出發(fā)，將空掛車送至服務點 i，換上重掛后將重掛運至服務點 j。到達服務點 j之后，卸下重掛，換上服務點j的空掛車，如無服務，則牽引車掛上空掛返回最近車場；如有服務，則掛上空掛駛向另一個服務點。整個運作過程中，牽引車運輸作業(yè)不產(chǎn)生等待時間。

由以上描述可知，對于甩掛運輸網(wǎng)絡中的每一個節(jié)點，為完成貨運需求都需要牽引車到達和離開該節(jié)點。

牽引車的行駛狀態(tài)分為兩種類型：

①h=1：牽引車拖掛空掛車行駛；

②h=2：牽引車拖掛重掛車行駛。

對于每個服務點而言，可能是牽引車拖掛空掛或重掛到達，也可能是牽引車拖掛重掛和空掛離開。對于車場，牽引車到達和離開都只能是拖掛或空掛狀態(tài)。牽引車拖掛空掛和重掛的單位成本不同。

3.2.2 數(shù)學模型

（1）變量設置：

D：所有車場的集合, D =｛ 1， 2， 3，…, d｝；

C：所有服務點集合， C =｛ 1， 2， 3， … , c｝；

V：所有牽引車的集合， V =｛ 1， 2， 3， … , v｝；

H：牽引車的行駛狀態(tài)集合， H ={1， }2；

d：第d個車場；

v：第v輛牽引車；

lij：點i到點j的距離（km）；

Qij：點i到點j的貨運量（掛車）；

C(h)：牽引車行駛狀態(tài)為h時的單位成本（元）；

T：完成所有貨運需求的最大工作時間（h）；

S：牽引車平均行駛速度（km/h）；

（2）建立模型

s.t.

式（1）表示模型的目標函數(shù)是實現(xiàn)總運輸成本最小。

式（2）表示牽引車拖掛重掛從服務點 i到服務點j行駛的次數(shù)等于服務點i到服務點j的運輸需求；

式（3）表示每個服務點掛車數(shù)不變；

式（4）表示牽引車拖掛重掛到達服務點 i的總和等于其他各服務點到服務點i的貨運量的總和；

式（5）表示牽引車拖掛重掛離開服務點 i的總和等于服務點i到其他各服務點的貨運量的總和；

式（6）表示牽引車只能拖掛空掛從車場出發(fā)；

式（7）表示牽引車只能拖掛空掛返回車場；

式（8）表示牽引車不能直接從車場到車場；

式（9）表示所有貨運需求必須要在牽引車有限工作時間內(nèi)完成。

4 算法設計

4.1 算法思想

根據(jù)各服務點的貨運需求，將服務點之間連成有向圖，并根據(jù)貨運量大小賦予權(quán)值。一輛牽引車完成一個有向圖；若完成該有向圖的時間超過設定的最大牽引車工作時間，則該有向圖分解成若干個有向圖，由不同的牽引車完成。當牽引車到達有向圖中最后一個服務點時，根據(jù)距離大小，判斷是返回最近的車場還是繼續(xù)完成下一個有向圖的任務，直到所有任務完成。

4.2 算法步驟

步驟1：初始化集合；

步驟2：更新各服務點參數(shù)（貨運量、掛車數(shù)量）；

步驟3：將各服務點根據(jù)貨運需求連成有向圖，權(quán)值為貨運量（貨運量以掛車為單位）。

步驟4：判斷有向圖中各服務點的貨運需求所需時間是否會超過牽引車的最大設定工作時限，lij計算（2n-1）次，其中 n為有向邊的權(quán)值。若未超過設定時限，執(zhí)行步驟5；否則，執(zhí)行步驟7。

步驟5：選定離有向圖起點最近的車場。

步驟 6：判斷離有向圖止點最近的車場的距離1l和離該止點最近的另一個有向圖起點的距離2l的大小關(guān)系：若12ll≤，選定車場，執(zhí)行步驟10；否則，執(zhí)行步驟9。

步驟7：將該有向圖進行分段，最大的不超過設定時間的部分，執(zhí)步驟行8；剩余部分，執(zhí)行步驟4。

步驟8：尋找離有向圖起點最近的車場和離有向圖止點最近的車場，執(zhí)行10。

步驟9：將有向圖止點與尋找到的有向圖起點連接，執(zhí)行4。

步驟 10：將選定的起止車場和有向圖連接，形成線路。

步驟 11：判斷是否還有服務點未與車場形成線路，若是，執(zhí)行步驟2；否則，任務結(jié)束。

具體算法流程參見圖2。

4.3 算例分析

假設在一個有13個節(jié)點的網(wǎng)絡中，有3個車場，在運輸系統(tǒng)的編號分別為車場A、車場B、車場C；10個服務點在運輸系統(tǒng)的編號分別為服務點1、服務點2、服務點3、服務點4、服務點5、服務點6、服務點7、服務點8、服務點9、服務點10。各節(jié)點之間相互距離以及貨運需求如表1、表2所示。在這10個客戶點之間隨機生成貨運需求，并假設牽引車每天最大工作時限為 24小時，牽引車行駛平均速度為60km/h。牽引車從車場出發(fā)滿足客戶點之間貨運需求后，返回最近車場，目標是使得牽引車的總行程最小。

圖2 甩掛運輸車輛調(diào)度的算法流程Fig.2 Algorithm process of drop and pull transport scheduling

表1 運輸網(wǎng)絡中各節(jié)點間的距離（單位：km)Tab.1 Distances between each node in the transportation network（unit: km）

表2 客戶點之間的貨運需求（單位：掛車）Tab.2 Freight demands between customers（unit: trailer）

（1）根據(jù)貨運需求形成初步有向圖，并對每邊賦予權(quán)值，標注節(jié)點間距離：

（2）根據(jù)有向圖生成原則，有向圖調(diào)整為：

（3）根據(jù)各有向圖起止點選定起止車場，連成牽引車行駛路線：

4.4 實驗結(jié)果

假設各服務點之間是高速公路對接的，設牽引車行駛平均速度為 60km/h；一般情況下，可設裝貨時間為1.5h/掛，卸貨時間為1h/掛；設牽引車重載行駛的成本為0.5元/km，空載行駛的成本為0.35元/km；在牽引車每天最大工作時限為24小時的情況下，傳統(tǒng)運輸模式和甩掛運輸模式有不同的運輸結(jié)果，如表3所示。

由表3可知，甩掛運輸能有效地減少汽車空載行程，提高運輸效率；由于甩掛運輸不產(chǎn)生等待時間，能夠有效地減少工作時間，且運距越短，節(jié)約時間的效果也越明顯。

表3 傳統(tǒng)運輸模式和甩掛運輸模式的實驗結(jié)果分析Tab.3 Experimental result analysis of the traditional transport and drop-pull transport

5 結(jié)束語

甩掛運輸作為一種高效的運輸方式，已經(jīng)在國內(nèi)外多地得到廣泛的應用。研究其車輛調(diào)度問題，有助于更好地發(fā)揮降低物流成本，促進節(jié)能減排、提高經(jīng)濟效益的優(yōu)勢。有關(guān)甩掛運輸車輛調(diào)度的研究還不多，本文只是進行了初步的探索和研究，如一車多掛和動態(tài)情況下的甩掛運輸?shù)鹊能囕v調(diào)度還值得進一步研究。

[1] 吳 宇, 曾傳華, 楊 偉. 道路運輸組織甩掛運輸策略研究[J]. 物流工程與管理, 2010,(08): 83-85.

[2] 溫旖旎. 道路運輸發(fā)展的必然趨勢[J]. 現(xiàn)代經(jīng)濟信息(產(chǎn)業(yè)經(jīng)濟), 2012,(3): 273

[3] 肖建軍. 車輛路徑優(yōu)化文獻綜述[J]. 廣東技術(shù)師范學院學報(自然科學版), 2010,(2): 31-36.

[4] 陳君蘭, 葉春明. 物流配送車輛調(diào)度問題算法綜述[J]. 物流科技, 2012,(3): 08-12.

[5] 王 瑩. 拖掛分離模式集裝箱運輸車輛調(diào)度研究[D]. 武漢：武漢理工大學, 2010.

[6] 熊 浩. 多車場物流配送車輛調(diào)度研究[D]. 武漢：華中科技大學, 2006.