邊 展，徐 奇，靳志宏*

(1.首都經(jīng)濟貿(mào)易大學(xué)工商管理學(xué)院，北京100070；2.大連海事大學(xué)交通運輸工程學(xué)院，遼寧大連116026)

0 引言

由于消費者對于貨品送達時間的要求愈加嚴(yán)格，企業(yè)必須思考如何在更短時間內(nèi)以較低的運輸成本滿足客戶需求.因此，帶時間窗的車輛路徑問題(VRPTW)日益受到重視.甩掛運輸路徑優(yōu)化問題(TTRP)為VRP的衍生，Chao[1]以最小化車隊總成本或總行駛距離為目標(biāo)，建立數(shù)學(xué)模型，并將21個經(jīng)典VRP算例改進為TTRP算例.針對該21個算例，Lin[2]運用模擬退火算法求得了其中的17個最優(yōu)解.Villegas等[3]對多場站單車輛的TTRP問題進行研究，設(shè)計并改進了GRASP/VND算法.Derigs等[4]考慮了卡車與拖車之間的貨物轉(zhuǎn)移，采用基于局部搜索、大規(guī)模鄰域搜索與標(biāo)準(zhǔn)泛啟發(fā)式算法的混合算法進行求解.李紅啟等[5]針對城際干線甩掛運輸過程所涉及的卡車調(diào)度這一問題開展研究，建立了整數(shù)規(guī)劃模型，并運用模擬退火算法進行求解.基于此，李紅啟等[6]考慮運輸過程中的碳排放量，通過數(shù)值實驗驗證了TTRP的節(jié)能減排效果.

分析現(xiàn)有研究不難發(fā)現(xiàn)，針對TTRP問題鮮有同時考慮時間窗約束及拖車調(diào)度情形，且拖車停放點通常是隨機選取或選擇停放成本最低的客戶點.而本研究不僅納入時間窗因素，還考慮了現(xiàn)實作業(yè)中拖車只能停放在特殊客戶點的約束，同時優(yōu)化卡車路徑與拖車路徑，從而更加符合實際運輸情形.

1 問題描述與假設(shè)條件

甩掛運輸?shù)恼嚳梢苑譃榭ㄜ嚺c拖車2個部分，如圖1所示.卡車與拖車均可承載貨物，拖車無動力，須附掛于卡車上.卡車可將拖車卸下，單獨以一般卡車的形式行駛，繞行子路徑后重新與拖車接回，以整車形式繼續(xù)服務(wù).

圖1 甩掛運輸示意圖Fig.1 Illustration of the truck-trailer transportation

因此，可將客戶劃分為僅由卡車配送的卡車客戶及由整車或卡車配送的整車客戶，相應(yīng)地，行駛路徑可劃分為卡車路徑，如圖2(a)所示；整車路徑，如圖2(b)所示；混合路徑，如圖2(c)所示.

圖2 配送示意圖Fig.2 Illustration of the truck-trailer distribution

本研究的TTRPTW可歸納為：利用卡車—拖車的整車配送或卡車單獨配送的方式滿足不同服務(wù)時間的客戶需求.假設(shè)條件如下：

①卡車客戶只能以卡車進行配送，整車客戶可以整車或卡車進行配送.

②以整車配送的客戶僅有部分可作為拖車停放點.

③不考慮車輛固定成本及拖車停放費用.

④僅考慮場站與客戶的時間窗上限.

2 符號描述與建模

2.1 符號定義

(1)標(biāo) 號.

h,i,j——節(jié)點標(biāo)號；

k——所有車輛標(biāo)號；

t——卡車標(biāo)號；

v——拖車標(biāo)號.

(2)車輛集合.

T——卡車集合；

V——拖車集合.

(3)節(jié)點集合.

0——場站；

N0vt——場站與路網(wǎng)中的所有節(jié)點；

Nvt——路網(wǎng)中的所有節(jié)點；

N0v——場站與能以整車服務(wù)的節(jié)點；

Nv——能以整車服務(wù)的節(jié)點；

Np——拖車停放點的集合.

(4)參 數(shù).

qi——節(jié)點i的需求量；

Qt——卡車的載重上限；

Qv——拖車的載重上限；

Li——節(jié)點i的配送時間窗上限；

Si——節(jié)點i的服務(wù)時間；

Tp——在拖車停放點拆卸及組裝拖車的時間.

(5)變 量.

di——離開節(jié)點i的時間；

ai——抵達節(jié)點i的時間；

d2i——第2次離開節(jié)點i的時間；

a2i——第2次抵達節(jié)點i的時間.

2.2 模型建立

目標(biāo)函數(shù)式為

式(1)為最小化車輛行駛時間，由卡車行駛總時間與整車行駛總時間構(gòu)成.

流量守恒與車輛指派約束為

式(2)和式(3)表示進入與離開路網(wǎng)的所有節(jié)點與場站(不包括拖車停放點)的卡車連線必為1；式(4)和式(5)表示卡車進入與離開拖車停放點的次數(shù)至少為1次，至多2次；式(6)和式(7)表示以整車進行服務(wù)的節(jié)點也可以由卡車進行服務(wù)，因此進入與離開整車客戶點的拖車連線可能為0，至多為1；式(8)表示1輛卡車或1輛拖車最多從場站離開1次；式(9)表示進出節(jié)點的卡車連線數(shù)守恒，進出節(jié)點的拖車連線數(shù)守恒.

車輛載重約束為

式(10)表示整車的載重約束，其中整車載重上限為卡車與拖車載重之和；式(11)表示卡車的載重約束.

變量約束為

式(12)和式(13)約束卡車與拖車的變量取值為0或1；式(14)表示若路徑上拖車變量取值為1，則卡車變量取值必為1；式(15)表示所有整車路徑須避免子回路，即整車路徑須經(jīng)場站1次.

車輛行進過程中時間傳遞約束為

式(16)表示卡車行駛路徑的時間傳遞，其中路徑時間為卡車行駛時間；式(17)表示卡車服務(wù)路徑的車輛順序約束，其中拖車停放點并未停放拖車；式(18)表示卡車服務(wù)路徑的車輛順序約束，其中拖車停放點被選擇停放拖車；式(19)表示整車服務(wù)路徑的時間傳遞；式(20)表示整車服務(wù)路徑的車輛順序約束，其中拖車停放點并未停放拖車；式(21)表示整車服務(wù)路徑的車輛順序約束，其中拖車停放點被選擇停放拖車.

時間窗約束為

式(22)表示抵達各節(jié)點的時間須小于時間窗上限.

節(jié)點時間約束為

式(23)表示抵達節(jié)點的時間加服務(wù)時間等于離開該節(jié)點時間(節(jié)點不包含拖車停放點)；式(24)表示若拖車停放點未被停放拖車，則抵達時間加服務(wù)時間等于離開時間；式(25)和式(26)表示若拖車停放點被停放拖車，則卡車將進入與離開此節(jié)點2次，即此節(jié)點會有2種抵達與離開時間，式(25)表示第1次抵達時間加服務(wù)時間加拆卸拖車時間等于第1次離開該節(jié)點時間，式(26)表示卡車子路徑結(jié)束后第2次返回拖車停放點，此時第2次抵達時間加連接拖車時間等于第2次離開該節(jié)點時間；式(27)和式(28)約束了2次抵達與離開時間的順序.

3 兩階段混合啟發(fā)式算法設(shè)計

算法包括構(gòu)建起始路徑與改善路徑2個部分，架構(gòu)如圖3所示.

3.1 構(gòu)建起始路徑

(1)構(gòu)建整車路徑.

采用2種策略構(gòu)建整車路徑.

策略A加大車輛抵達客戶點的時間與客戶時間窗的差距，計算式如式(29)所，其中，M與P均為固定的常數(shù).計算整車客戶插入現(xiàn)有路徑[1]中的時間，同時考慮由場站指派新車的可能性，比較插入時間與形成新路徑的時間，選擇時間最少的方案.

圖3 算法架構(gòu)圖Fig.3 Illustration of the algorithm

策略B預(yù)留卡車子路徑中的車容量，將整車起始路徑的車容量上限設(shè)為式(30)(R：0.5～1.0).每輛整車選擇距離場站最遠的客戶作為路徑的種子點，其余整車客戶比較插入現(xiàn)有路徑中的時間，選擇時間最少的客戶插入路徑中，直至超過車容量上限，或違反客戶時間窗限制，由場站指派新車進行服務(wù).

(2)構(gòu)建卡車子路徑.

由于場站及整車路徑中的所有拖車停放點均可作為卡車子路徑的起點，因此須計算卡車客戶連接到拖車停放點形成新的子路徑的時間，以及卡車客戶插入現(xiàn)有卡車子路徑的時間，選擇時間最少的位置插入卡車客戶形成子路徑.

(3)構(gòu)建卡車路徑

類似地，運用A、B策略構(gòu)建卡車路徑.

3.2 改善路徑

運用不同方式獲得新路徑，若其滿足車容量及時間窗約束，則計算改善時間成本(若路徑為卡車，則成本記為Ct；若為整車，則記為Cv).

3.2.1 路徑內(nèi)改善交換

(1)路徑內(nèi)Or-opt節(jié)點交換.

整車路徑內(nèi)為

卡車路徑內(nèi)為

路徑內(nèi)Or-opt節(jié)點交換示意圖如圖4所示.

圖4 路徑內(nèi)Or-opt節(jié)點交換示意圖Fig.4 The Or-opt node switching of one route

(2)路徑內(nèi)2-opt節(jié)點交換.

整車路徑內(nèi)為

卡車路徑內(nèi)為

路徑內(nèi)2-opt節(jié)點交換示意圖如圖5所示.

圖5 路徑內(nèi)2-opt節(jié)點交換示意圖Fig.5 The 2-opt node switching of one route

3.2.2 路徑間改善交換

(1)同種路徑間1-0節(jié)點插入.

整車路徑間為

整車路徑間1-0節(jié)點插入示意圖如圖6所示.

卡車子路徑間為

卡車子路徑間1-0節(jié)點插入示意圖如圖7所示.

卡車路徑間為

卡車路徑間1-0節(jié)點插入示意圖如圖8所示.

(2)同種路徑間1-1節(jié)點交換.

整車路徑間為

整車路徑間1-1節(jié)點交換示意圖如圖9所示.

卡車子路徑間為

卡車子路徑間1-1節(jié)點交換示意圖如圖10所示.

圖6 整車路徑間1-0節(jié)點插入示意圖Fig.6 The 1-0 node insert between vehicle routes

圖7 卡車子路徑間1-0節(jié)點插入示意圖Fig.7 The 1-0 node insert between truck sub-routes

圖8 卡車路徑間1-0節(jié)點插入示意圖Fig.8 The 1-0 node insert between truck routes

圖9 整車路徑間1-1節(jié)點交換示意圖Fig.9 The 1-1 node switching between vehicle routes

圖10 卡車子路徑間1-1節(jié)點交換示意圖Fig.10 The 1-1 node switching between truck sub-routes

卡車路徑間為

卡車路徑間1-1節(jié)點交換示意圖如圖11所示.

圖11 卡車路徑間1-1節(jié)點交換示意圖Fig.11 The 1-1 node switching between truck routes

(3)同種路徑間2-opt路徑交換.

整車路徑間為

卡車路徑間為

同種路徑間2-opt路徑交換示意圖如圖12所示.

圖12 同種路徑間2-opt路徑交換示意圖Fig.12 The 2-opt path switching between same routes

(4)異種路徑間1-0節(jié)點插入.

整車—卡車路徑間為

整車—卡車路徑間1-0節(jié)點插入示意圖如圖13所示.

圖13 整車—卡車路徑間1-0節(jié)點插入示意圖Fig.13 The 1-0 node insert between vehicle-truck routes

卡車—卡車子路徑間為

卡車—卡車子路徑間1-0節(jié)點插入示意圖如圖14所示.

圖14 卡車—卡車子路徑間1-0節(jié)點插入示意圖Fig.14 The 1-0 node insert between truck routes and truck sub-routes

(5)異種路徑間1-1節(jié)點交換.

卡車—卡車子路徑間為

卡車—卡車子路徑間1-1節(jié)點交換示意圖如圖15所示.

圖15 卡車—卡車子路徑間1-1節(jié)點交換示意圖Fig.15 The 1-1 node switching between truck routes and truck sub-routes

3.2.3 拖車停放點交換

視原拖車停放點所在的卡車子路徑為一閉合回路，移除該回路的1條連線，選擇其他的插入后增加時間最少的拖車停放點重新相連.

拖車停放點交換示意圖如圖16所示.

圖16 拖車停放點交換示意圖Fig.16 The parking dots switching of trailers

4 實驗及結(jié)果分析

4.1 小規(guī)模實驗

本研究以Solomon[7]的VRPTW實驗作為基礎(chǔ)，客戶坐標(biāo)與服務(wù)需求參考Baldacci等[8]，選擇其中R1、C1、RC1具有100%時間窗約束的17例構(gòu)建TTRPTW測試題庫.以客戶之間的直線距離代表卡車的行駛時間，整車行駛時間為該值的1.2倍，拆卸、組裝拖車的時間均為30個時間單位.

表1 小規(guī)模測試?yán)斜鞹able 1 The case list of small scale experiments

運用Visual C++6.0進行算法編寫，以Microsoft Visual Studio 2008進行編譯，在計算機(Intel Core I5 CPU，4.0 GB memory，2.50 GHz)上運行.

求解結(jié)果如表2所示.針對每一小規(guī)模測試?yán)?，本文算法均可? s內(nèi)求得結(jié)果.求解效率上，策略B的求解時間小于策略A，其中A的平均求解時間為2.04 s，B為1.77 s；運用策略A構(gòu)建起始路徑的時間成本較低，平均值為2 633.39，而B為2 773.66；運用策略A求解最優(yōu)路徑的時間也低于B，其中A的最優(yōu)路徑時間平均值為1 793.54，而B為1 829.72.

表2 小規(guī)模實驗結(jié)果列表Table 2 The results of small scale experiments

4.2 大規(guī)模實驗

為進一步測試本研究提出算法的有效性，設(shè)計了8組大規(guī)模測試?yán)?，如?所示，其中客戶數(shù)量為200～900，卡車與拖車的載重設(shè)為200.

同樣運用2種策略分別進行求解，結(jié)果如表4所示.

表3 大規(guī)模測試?yán)斜鞹able 3 The case list of large scale experiments

表4 大規(guī)模實驗結(jié)果列表Table 4 The results of large scale experiments

由表4可以看出，當(dāng)客戶規(guī)模增至800時，由于內(nèi)存限制運用策略A無法順利求解；隨著路網(wǎng)規(guī)模的擴大，2種策略下的求解耗時均呈現(xiàn)非線性大幅度增加的趨勢，而策略A下求解耗時較短.在最優(yōu)路徑的目標(biāo)時間成本方面，策略A較策略B的時間成本更低.針對每一測試?yán)?種策略下用車總數(shù)基本相同，而單獨比較整車或卡車數(shù)量，策略A下需要整車運輸?shù)臄?shù)量明顯低于B，而卡車運輸數(shù)量則相反，因此可根據(jù)實際行車需求權(quán)衡適當(dāng)?shù)闹概山M合.

綜合上述不同規(guī)模的實驗可知，針對小規(guī)模的路網(wǎng)問題，策略B的求解效率更高；而當(dāng)路網(wǎng)規(guī)模擴大時，選擇A可獲得更高的求解效率.無論路網(wǎng)規(guī)模大小，運用策略A求得的最優(yōu)路徑目標(biāo)值均低于B.

5 結(jié)論

本文針對TTRPTW問題，兼顧卡車與拖車2種車輛調(diào)度的特點，以最小化配送時間為目標(biāo)建立模型，并開發(fā)了兩階段混合算法，以求得最優(yōu)的車輛路徑組合.實驗均以實務(wù)為參照標(biāo)準(zhǔn)，結(jié)果表明運用本文模型與算法能夠在0.5 h內(nèi)求出大規(guī)模算例的滿意解，且可根據(jù)企業(yè)實際選擇適當(dāng)?shù)目ㄜ?、拖車?shù)量組合，具有良好的可行性.

參考文獻：

[1]CHAO I M.A tabu search method for the truck and trailer routing problem[J].Computers&Operations Research,2002,29(1):22-51.

[2]LIN S W.Solving the truck and trailer routing problem based on a simulated annealing heuristic[J].Computers&Operations Research,2009,36(5):1683-1692.

[3]VILLEGAS J G,PRINS C,PRODHON C,et al.A GRASP with evolutionary path relinking for the truck and trailer routing problem[J].Computers&Operations Research,2011,38(9):1319-1334.

[4]DERIGS U,PULLMANN M,VOGEL U.Truck and trailer routing problems-heuristics and computational experience[J].Computers&Operations Research,2013,40(2):536-546.

[5]李紅啟,盧越,朱曉寧.城際干線甩掛運輸牽引車調(diào)度問題的模擬退火算法研究[J].交通運輸工程與信息學(xué)報,2015,13(4):77-84,95.[LI H Q,LU Y,ZHU X N.A simulated annealing approach to the tractor dispatching problem of intercity dropping and pulling transport[J].Journal of Transportation Engineering and Information,2015,13(4):77-84,95.]

[6]李紅啟,趙文聰,李嫣然.時效要求下的甩掛牽引車調(diào)度問題與求解[J].交通運輸工程學(xué)報,2016,16(5):95-102.[LI H Q,ZHAO W C,LI Y R.Trailer pick-up tractor routing problem with timeliness requirement and solving[J].Journal of Traffic and Transportation Engineering,2016,16(5):95-102.]

[7]SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research,1987,35(2):254-265.

[8]BALDACCI R,CHRISTOFIDES N,MINGOZZI A.An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts[J].Mathematical Programming,2008,115(2):351-385.