帶時(shí)間窗的甩掛運(yùn)輸路徑優(yōu)化問題研究

邊 展，徐 奇，靳志宏*

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

0 引言

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

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

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

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

圖1 甩掛運(yùn)輸示意圖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可歸納為：利用卡車—拖車的整車配送或卡車單獨(dú)配送的方式滿足不同服務(wù)時(shí)間的客戶需求.假設(shè)條件如下：

①卡車客戶只能以卡車進(jìn)行配送，整車客戶可以整車或卡車進(jìn)行配送.

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

③不考慮車輛固定成本及拖車停放費(fèi)用.

④僅考慮場(chǎng)站與客戶的時(shí)間窗上限.

2 符號(hào)描述與建模

2.1 符號(hào)定義

(1)標(biāo) 號(hào).

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

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

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

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

(2)車輛集合.

T——卡車集合；

V——拖車集合.

(3)節(jié)點(diǎn)集合.

0——場(chǎng)站；

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

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

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

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

Np——拖車停放點(diǎn)的集合.

(4)參 數(shù).

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

Qt——卡車的載重上限；

Qv——拖車的載重上限；

Li——節(jié)點(diǎn)i的配送時(shí)間窗上限；

Si——節(jié)點(diǎn)i的服務(wù)時(shí)間；

Tp——在拖車停放點(diǎn)拆卸及組裝拖車的時(shí)間.

(5)變 量.

di——離開節(jié)點(diǎn)i的時(shí)間；

ai——抵達(dá)節(jié)點(diǎn)i的時(shí)間；

d2i——第2次離開節(jié)點(diǎn)i的時(shí)間；

a2i——第2次抵達(dá)節(jié)點(diǎn)i的時(shí)間.

2.2 模型建立

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

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

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

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

車輛載重約束為

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

變量約束為

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

車輛行進(jìn)過程中時(shí)間傳遞約束為

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

時(shí)間窗約束為

式(22)表示抵達(dá)各節(jié)點(diǎn)的時(shí)間須小于時(shí)間窗上限.

節(jié)點(diǎn)時(shí)間約束為

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 改善路徑

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

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

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

整車路徑內(nèi)為

卡車路徑內(nèi)為

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

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

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

整車路徑內(nèi)為

卡車路徑內(nèi)為

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

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

3.2.2 路徑間改善交換

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

整車路徑間為

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

卡車子路徑間為

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

卡車路徑間為

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

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

整車路徑間為

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

卡車子路徑間為

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

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

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

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

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

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

卡車路徑間為

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

圖11 卡車路徑間1-1節(jié)點(diǎn)交換示意圖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é)點(diǎn)插入.

整車—卡車路徑間為

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

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

卡車—卡車子路徑間為

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

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

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

卡車—卡車子路徑間為

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

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

3.2.3 拖車停放點(diǎn)交換

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

拖車停放點(diǎn)交換示意圖如圖16所示.

圖16 拖車停放點(diǎn)交換示意圖Fig.16 The parking dots switching of trailers

4 實(shí)驗(yàn)及結(jié)果分析

4.1 小規(guī)模實(shí)驗(yàn)

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

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

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

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

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

4.2 大規(guī)模實(shí)驗(yàn)

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

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

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

[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]李紅啟,盧越,朱曉寧.城際干線甩掛運(yùn)輸牽引車調(diào)度問題的模擬退火算法研究[J].交通運(yùn)輸工程與信息學(xué)報(bào),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]李紅啟,趙文聰,李嫣然.時(shí)效要求下的甩掛牽引車調(diào)度問題與求解[J].交通運(yùn)輸工程學(xué)報(bào),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.