王清斌，于江寧，鄭建風(fēng)

（大連海事大學(xué)，交通運(yùn)輸工程學(xué)院，遼寧大連 116026）

0 引言

循環(huán)甩掛是用循環(huán)調(diào)度的方法來組織封閉回路上的甩掛作業(yè)，以牽引車為循環(huán)調(diào)度對(duì)象，掛車為需要裝載或卸載的貨物?？蛻酎c(diǎn)為裝卸作業(yè)點(diǎn)，也用于收取貨物、暫時(shí)?？亢屯蠏燔囕v。

在這個(gè)作業(yè)組織過程中，甩掛運(yùn)輸車輛路徑問題(Truck and Trailer Routing Problem，TTRP)是傳統(tǒng)車輛路徑問題的衍生問題。甩掛運(yùn)輸組織者會(huì)根據(jù)顧客的配送時(shí)間要求制定每天的車輛路徑調(diào)度方案。但在實(shí)際中，經(jīng)常會(huì)出現(xiàn)諸如臨時(shí)插單、裝卸點(diǎn)備貨時(shí)間調(diào)整使得原屬于下一天的任務(wù)提前至當(dāng)天，而產(chǎn)生新增運(yùn)輸任務(wù)的情況，這會(huì)對(duì)當(dāng)天的調(diào)度方案造成干擾，導(dǎo)致配送車輛可能無法按照原方案服務(wù)客戶。

針對(duì)新增運(yùn)輸任務(wù)的干擾問題，一些學(xué)者運(yùn)用全局重調(diào)度方法進(jìn)行處理。李兵[1]提出引入虛擬任務(wù)點(diǎn)將動(dòng)態(tài)路徑規(guī)劃問題轉(zhuǎn)化為普通靜態(tài)問題，運(yùn)用改進(jìn)的節(jié)約法對(duì)問題進(jìn)行求解。Tasan[2]等和Zhang[3]等對(duì)動(dòng)態(tài)路徑規(guī)劃問題進(jìn)行了重新優(yōu)化，但沒有將原方案考慮在內(nèi)。然而當(dāng)新增需求過于頻繁時(shí)，路徑的實(shí)時(shí)優(yōu)化無法實(shí)現(xiàn)。葛顯龍等[4]通過將配送時(shí)間劃分時(shí)間段，將動(dòng)態(tài)需求過程轉(zhuǎn)化為多個(gè)瞬時(shí)靜態(tài)子過程進(jìn)行求解，并設(shè)計(jì)云遺傳算法實(shí)時(shí)優(yōu)化配送方案。饒衛(wèi)振[5]針對(duì)新客戶出現(xiàn)的動(dòng)態(tài)事件，將動(dòng)態(tài)車輛路徑問題轉(zhuǎn)化為多車型開放式車輛路徑問題，再進(jìn)一步轉(zhuǎn)化為多個(gè)能力約束車輛路徑問題，在此基礎(chǔ)上建立動(dòng)態(tài)車輛路徑模型，并提出兩階段算法。張文博[6]提出兩階段建模，采用模擬退火算法得到實(shí)時(shí)優(yōu)化后的車輛路徑方案。但由于其運(yùn)用的是全局重調(diào)度法會(huì)造成新方案時(shí)間和路徑與原方案偏離較大，對(duì)系統(tǒng)造成擾動(dòng)。

從以上學(xué)者研究可以看出，全局重調(diào)度是以整個(gè)系統(tǒng)總費(fèi)用最低為目標(biāo)，進(jìn)行全局優(yōu)化調(diào)整。通過犧牲原運(yùn)輸任務(wù)配送時(shí)間的及時(shí)性和準(zhǔn)確性，從而換取整個(gè)配送系統(tǒng)的更低的成本變動(dòng)。在實(shí)際甩掛運(yùn)輸中，一個(gè)運(yùn)輸任務(wù)涉及到裝、卸貨兩點(diǎn)的時(shí)間窗變動(dòng)，時(shí)間變動(dòng)會(huì)造成兩個(gè)客戶點(diǎn)的服務(wù)體驗(yàn)下降，而物流本身就是一種服務(wù)，在提供運(yùn)輸服務(wù)的過程中必須考慮客戶的服務(wù)體驗(yàn)。因此有學(xué)者提出運(yùn)用干擾管理的思想，楊華龍等[7]針對(duì)客戶時(shí)間窗變動(dòng)情況，設(shè)計(jì)基于禁忌搜索的調(diào)度算法，通過算例證明干擾處理方法優(yōu)于全局重調(diào)度方法。趙亮[8]針對(duì)客戶需求量和時(shí)間窗的變動(dòng)情況，建立干擾管理模型，優(yōu)化同時(shí)送取貨的車輛路徑方案。丁秋雷等[9]針對(duì)行駛時(shí)間延遲情況，從物流配送運(yùn)營商的視角，在模型創(chuàng)建中引入客戶終身價(jià)值，構(gòu)建了擾動(dòng)較小的配送方案。由此可以看出，基于干擾管理思想的研究可以更好地克服全局重調(diào)度方法中存在的問題，但現(xiàn)有的研究多是對(duì)傳統(tǒng)車輛運(yùn)輸模式下客戶時(shí)間窗、需求量等因素變動(dòng)的研究，而對(duì)于新增運(yùn)輸任務(wù)造成的配送車輛調(diào)度問題研究尚少，并且針對(duì)甩掛運(yùn)輸?shù)难芯窟€停留在靜態(tài)車輛路徑問題上。

基于上述情況，本文運(yùn)用干擾管理思想，針對(duì)甩掛運(yùn)輸模式下出現(xiàn)新增運(yùn)輸任務(wù)的問題，以考慮配送車輛調(diào)整、路徑偏離和服務(wù)時(shí)間偏離的廣義總成本最小化為目標(biāo)，對(duì)原車輛路徑調(diào)度方案進(jìn)行調(diào)整，為甩掛運(yùn)輸組織應(yīng)對(duì)新增運(yùn)輸任務(wù)的干擾管理提供決策支持。

1 問題描述

本文考慮由一個(gè)牽引車車場和多個(gè)客戶點(diǎn)組成的甩掛運(yùn)輸系統(tǒng)，在配送開始前，以運(yùn)輸成本最低為目標(biāo)生成初始方案并安排牽引車進(jìn)行配送。本文將干擾發(fā)生時(shí)車輛正在服務(wù)的客戶點(diǎn)視為已完成客戶點(diǎn)，客戶需求發(fā)生的變動(dòng)視為新增運(yùn)輸任務(wù)，干擾發(fā)生時(shí)，基于當(dāng)前系統(tǒng)狀態(tài)，運(yùn)用干擾管理思想生成新的車輛路徑方案，以使干擾對(duì)原方案造成的擾動(dòng)(廣義總費(fèi)用偏離)最小。

2 擾動(dòng)主體的度量分析

顧客下達(dá)配送訂單后，甩掛運(yùn)輸組織者根據(jù)顧客的配送時(shí)間要求以1 d為一個(gè)調(diào)度期生成車輛運(yùn)輸路徑方案，由于在實(shí)際運(yùn)輸過程中存在新增運(yùn)輸任務(wù)，本文以660 min 為接受新增運(yùn)輸任務(wù)的干擾時(shí)刻，若新增運(yùn)輸信息出現(xiàn)在該時(shí)刻以后，該任務(wù)將進(jìn)入下一個(gè)調(diào)度期進(jìn)行配送。

當(dāng)客戶需求發(fā)生變動(dòng)后，系統(tǒng)需要進(jìn)行擾動(dòng)辨識(shí)，判斷干擾事件是否對(duì)原方案造成干擾，若沒有產(chǎn)生干擾，則按照原方案行駛。若產(chǎn)生了干擾，則系統(tǒng)要在最短的時(shí)間內(nèi)，基于干擾管理思想，生成廣義總費(fèi)用偏離最小的車輛路徑方案。廣義總費(fèi)用偏離包含4 方面內(nèi)容：(1)由于新派車產(chǎn)生的費(fèi)用；(2)由于在途車輛運(yùn)輸距離的增減而引起費(fèi)用的增減；(3)對(duì)服務(wù)時(shí)間偏離的處理，通過引入時(shí)間偏離懲罰系數(shù)將時(shí)間的偏離轉(zhuǎn)化為相關(guān)費(fèi)用；(4)由于不能接受新增任務(wù)而放棄客戶的懲罰成本。

在路徑偏離上，僅由于牽引車行駛路徑的偏離產(chǎn)生的與路徑距離有關(guān)的運(yùn)輸成本變化可分為兩種情況，如圖1所示。設(shè)原路徑為rijk(表示空掛從i到j(luò)的路徑)，第1 種情況是牽引車完成任務(wù)m，空掛從i出發(fā)前就已知要改變原路線，先去服務(wù)新任務(wù)m′再去服務(wù)m+1，如圖1(a)所示，設(shè)T表示干擾發(fā)生時(shí)刻，Li表示車輛從i離開的時(shí)間，則這種情況可以表示為T ＜Li，這時(shí)路徑的偏離可表示為空掛rijk的減少和空掛rigk、rhjk，重掛rghk的增加；第2種情況是牽引車完成任務(wù)m，空掛從i出發(fā)后，臨時(shí)得知需要變更下一個(gè)客戶點(diǎn)，即車輛是空掛狀態(tài)駛向下一任務(wù)點(diǎn)，此時(shí)車輛位置為p，如圖1(b)所示，設(shè)Sj表示開始服務(wù)j的時(shí)間，則這種情況可以表示為Li ＜T ＜Sj，這時(shí)原路線并沒有完全減少，而是與新路線有重合部分空掛ripk，路徑的偏離可表示為空掛rpjk的減少和空掛rpgk、rhjk，重掛rghk的增加。當(dāng)干擾信息發(fā)生時(shí)車輛若為甩掛運(yùn)輸任務(wù)狀態(tài)，要等到任務(wù)結(jié)束在進(jìn)行調(diào)整，或在車場派送新的牽引車。

圖1 車輛路徑偏離情況Fig.1 Deviation of vehicle route

在運(yùn)輸任務(wù)的服務(wù)時(shí)間偏離方面，本文引入時(shí)間費(fèi)用偏離懲罰系數(shù)把時(shí)間偏離量化成廣義時(shí)間費(fèi)用偏離[10]。即調(diào)整原車輛調(diào)度方案后，若配送車輛到達(dá)任務(wù)m客戶點(diǎn)開始服務(wù)時(shí)刻，在任務(wù)m允許的最早開始服務(wù)時(shí)刻之前，車輛因等待產(chǎn)生了損失成本，此時(shí)，時(shí)間偏離懲罰系數(shù)記為α；若配送車輛到達(dá)任務(wù)m客戶點(diǎn)開始服務(wù)時(shí)刻，在任務(wù)m允許的最遲開始服務(wù)時(shí)刻和客戶允許的延遲時(shí)間Δt之間，則會(huì)對(duì)客戶的滿意度造成一定的影響，此時(shí)，將時(shí)間偏離懲罰系數(shù)記為λ；若車輛到達(dá)客戶點(diǎn)時(shí)，該客戶的時(shí)間窗已經(jīng)關(guān)閉，該車輛不能再對(duì)其服務(wù)，將懲罰系數(shù)定義為一個(gè)無窮大的正數(shù)M。

在式(1)的基礎(chǔ)上，本文基于干擾管理的思想，需盡可能減少新方案與原方案的差異。因此，加入新方案與原方案中任務(wù)開始服務(wù)時(shí)間的偏離費(fèi)用，即

本文從兩方面考慮：一方面是基于實(shí)際服務(wù)時(shí)間與時(shí)間窗差異，而產(chǎn)生的一個(gè)時(shí)間窗懲罰成本；另一方面是基于干擾管理的思想，盡量小的擾動(dòng)，盡快恢復(fù)系統(tǒng)正常運(yùn)行。為盡可能使新方案與原方案之間的偏離程度更小，該計(jì)算是判斷新方案優(yōu)劣的一個(gè)指標(biāo)，將任務(wù)開始服務(wù)時(shí)間的偏離轉(zhuǎn)化一個(gè)時(shí)間偏離懲罰成本，由此構(gòu)造出廣義費(fèi)用這一概念。本文客戶點(diǎn)的時(shí)間窗是對(duì)牽引車開始服務(wù)的時(shí)間限制，因此，如果出現(xiàn)牽引車實(shí)際到達(dá)后的時(shí)刻在客戶時(shí)間窗內(nèi)，但甩掛作業(yè)結(jié)束后超過客戶允許時(shí)間范圍，這種情況不會(huì)對(duì)客戶的滿意度造成影響，時(shí)間懲罰不予以考慮。

3 模型構(gòu)建

模型中的變量及參數(shù)符號(hào)定義如下：

T——擾動(dòng)發(fā)生的時(shí)刻；

D——客戶集合，D={1,2,…,n} ，n為客戶點(diǎn)數(shù)量；

N——地點(diǎn)集合，N=D?{O} ；

O——車場；

K——已使用牽引車數(shù)量；

P——待使用牽引車數(shù)量(車場剩余)；

p——增派車輛數(shù)；

M——甩掛時(shí)段內(nèi)的運(yùn)輸任務(wù)總數(shù)；

m′——甩掛時(shí)段內(nèi)新增任務(wù)數(shù)；

M′——擾動(dòng)發(fā)生時(shí)原方案為服務(wù)任務(wù)數(shù)；

Cij——從位置i到j(luò)的運(yùn)輸成本；

tij——從位置i到j(luò)的行駛時(shí)間；

C——完成甩掛任務(wù)所需要總費(fèi)用；

C0——每輛牽引車每天出車固定費(fèi)用(車輛購置費(fèi)用，維修費(fèi)用以及駕駛員工資)；

V1——牽引車空掛時(shí)行駛速度；

V2——牽引車重掛時(shí)行駛速度；

Gk——牽引車k的額定載重；

gk——掛車的空車質(zhì)量；

gm——任務(wù)m運(yùn)輸任務(wù)量；

α——若車輛到達(dá)任務(wù)m客戶點(diǎn)時(shí)刻，在時(shí)間窗之前到達(dá)的時(shí)間偏離懲罰系數(shù)；

λ——若車輛到達(dá)任務(wù)m客戶點(diǎn)時(shí)刻，在任務(wù)m期望服務(wù)截止時(shí)間和客戶允許的延遲時(shí)間Δt之間的時(shí)間偏離懲罰系數(shù)；

β——若車輛到達(dá)任務(wù)m客戶點(diǎn)時(shí)刻，偏離原任務(wù)開始時(shí)間的時(shí)間偏離懲罰系數(shù)；

F——放棄一個(gè)客戶的懲罰費(fèi)用；

Δt——客戶時(shí)間容忍度；

M——客戶時(shí)間窗已經(jīng)關(guān)閉，該車輛再對(duì)其服務(wù)的時(shí)間偏離懲罰系數(shù)；

sm——任務(wù)m裝貨點(diǎn)；

rm——任務(wù)m卸貨點(diǎn)；

Sm——原方案開始服務(wù)任務(wù)m的時(shí)刻；

S'm——新方案開始服務(wù)任務(wù)m的時(shí)刻；

R'm——新方案到達(dá)任務(wù)m裝貨點(diǎn)的時(shí)刻；

t'kn,s——牽引車k執(zhí)行第n次運(yùn)輸任務(wù)時(shí)的開始時(shí)刻；

tknmsm+1——牽引車k執(zhí)行從運(yùn)輸任務(wù)m的終到點(diǎn)到運(yùn)輸任務(wù)m+1的起始點(diǎn)所需時(shí)間；

Sm,s——任務(wù)m最遲開始時(shí)刻；

Sm,f——任務(wù)m結(jié)束時(shí)刻；

tm——甩掛運(yùn)輸持續(xù)時(shí)間；

tp——甩掛作業(yè)時(shí)間；

[TE,m,TL,m]——任務(wù)m要求的時(shí)間窗；

TE,m——任務(wù)m允許的最早開始服務(wù)時(shí)刻；

TL,m——任務(wù)m允許的最遲開始服務(wù)時(shí)刻；

φm——任務(wù)m的時(shí)間偏離懲罰費(fèi)用；

dij——客戶i到j(luò)的距離；

dpjk——擾動(dòng)發(fā)生后原車輛k從當(dāng)前位置到客戶j的行駛距離；

d1k——擾動(dòng)發(fā)生后車輛k按原方案服務(wù)剩余空掛的總行駛距離；

d2k——擾動(dòng)發(fā)生后車輛k按原方案服務(wù)剩余重掛的總行駛距離；

——擾動(dòng)發(fā)生后車輛k正在服務(wù)任務(wù)m的結(jié)點(diǎn)；

Pk——擾動(dòng)發(fā)生后車輛k空掛在行駛途中。

擾動(dòng)后模型為

式(3)表示任務(wù)m的運(yùn)輸重量與半掛車的重量和不超過牽引車k的最大額定載重量；式(4)表示甩掛運(yùn)輸任務(wù)m只能由牽引車k完成；式(5)表示牽引車k從原點(diǎn)出發(fā)執(zhí)行運(yùn)輸任務(wù)；式(6)表示牽引車k完成運(yùn)輸任務(wù)最終回到原點(diǎn)；式(7)表示出發(fā)返回必須是空車；式(8)表示牽引車進(jìn)入和駛出節(jié)點(diǎn)數(shù)量相同；式(9)為牽引車執(zhí)行運(yùn)輸任務(wù)被完成的先后次序約束；式(10)表示新方案中執(zhí)行任務(wù)m甩掛運(yùn)輸持續(xù)時(shí)間；式(11)表示時(shí)間偏離懲罰取值

4 算法設(shè)計(jì)

實(shí)際配送過程中，雖然客戶會(huì)發(fā)生需求變動(dòng)，但并不是所有客戶的需求變動(dòng)都會(huì)對(duì)原方案造成干擾，如，新增任務(wù)的時(shí)間窗及路段為原方案中牽引車在該時(shí)段空掛行駛的路線，則該變動(dòng)不會(huì)對(duì)原方案造成影響，也就不會(huì)產(chǎn)生干擾，否則，該變動(dòng)會(huì)對(duì)原方案產(chǎn)生干擾。

在配送過程中，原方案是從車場出發(fā)回到車場的閉環(huán)路徑方案，而針對(duì)新增運(yùn)輸任務(wù)變動(dòng)路徑方案的算法設(shè)計(jì)，是在調(diào)度時(shí)刻從各個(gè)在途車輛所在虛擬客戶點(diǎn)的位置回到車場的路徑算法設(shè)計(jì)，實(shí)質(zhì)是由多點(diǎn)返回到車場。

在實(shí)際中，當(dāng)干擾發(fā)生，需要對(duì)車輛路徑進(jìn)行調(diào)整時(shí)，將車輛在途和車輛正在某個(gè)客戶點(diǎn)等待的情況，都看作是車輛停留在“虛擬客戶點(diǎn)”，這樣新方案則發(fā)生在服務(wù)完虛擬客戶點(diǎn)之后。本文通過修改虛擬客戶點(diǎn)的屬性，將多點(diǎn)返回到車場的開環(huán)路徑轉(zhuǎn)變?yōu)殚]環(huán)路徑問題，采用改進(jìn)的多種群并行遺傳算法求解，算法設(shè)計(jì)整體框架如圖2所示。

圖2 算法設(shè)計(jì)整體框架Fig.2 Overall framework of algorithm design

本文采用改進(jìn)的多種群并行遺傳算法求解該問題，步驟如下：

Step 1 隨機(jī)產(chǎn)生指定個(gè)體數(shù)目的3 個(gè)初始種群作為并行算法的子種群。

Step 2 并行計(jì)算各子種群中個(gè)體的適應(yīng)度。

Step 3 采用輪盤賭方式并行執(zhí)行各子算法的選擇算子。

Step 4 按交叉概率并行執(zhí)行各子算法的交叉算子。

Step 5 按變異概率并行執(zhí)行各子算法的變異算子。

Step 6 在各子種群中優(yōu)選適應(yīng)度較好的個(gè)體。

Step 7 若滿足停止準(zhǔn)則，輸出結(jié)果；否則，轉(zhuǎn)Step 2。

結(jié)合虛擬客戶點(diǎn)策略的并行遺傳算法本身不需要做結(jié)構(gòu)調(diào)整，只需要在干擾調(diào)度時(shí)刻重新對(duì)虛擬客戶點(diǎn)、新增客戶點(diǎn)和原計(jì)劃未服務(wù)客戶點(diǎn)信息的重新匯總并在算法中重新對(duì)這類客戶讀取數(shù)據(jù)。

5 數(shù)值驗(yàn)證

為了驗(yàn)證模型和算法的有效性，本文在300 km×300 km 平面采用隨機(jī)方式選取15 個(gè)點(diǎn)，生成40個(gè)運(yùn)輸任務(wù)。某日甩掛運(yùn)輸系統(tǒng)接到15個(gè)客戶點(diǎn)的訂單，物流配送中心和客戶點(diǎn)的坐標(biāo)如表1所示，運(yùn)輸任務(wù)和時(shí)間窗信息如表2所示，其中，標(biāo)號(hào)1 表示車場。車場有15 輛牽引車，300 km×300 km平面中重掛行駛速度80 km·h-1，空掛行駛速度100 km·h-1，C1=1.8 元·km-1，C2=3.6 元·km-1，C0=416 元·車-1[11，]α=10 元·min-1，β=1 元·min-1，λ=10 元·min-1，Δt=30 min[12]。

表1 甩掛中心及客戶點(diǎn)位置Table 1 Drop and pull center and customer location（km）

表2 運(yùn)輸任務(wù)信息Table 2 Transportation task information

以成本最低為目標(biāo)得到初始配送方案如表3所示，配送車輛按該方案執(zhí)行至?xí)r間為660 min時(shí)，累計(jì)接到新增運(yùn)輸任務(wù)信息如表4所示。將新增運(yùn)輸任務(wù)分別并入到3種調(diào)度方案中進(jìn)行比較，派車方案如表5所示。

表3 原優(yōu)化運(yùn)輸方案Table 3 Original optimized transportation plan

表4 新增運(yùn)輸任務(wù)信息Table 4 New transportation task information

表5 3組優(yōu)化方案最終牽引車運(yùn)輸任務(wù)序列Table 5 Final tractor transportation task sequence of three groups of optimization schemes

本文提出的干擾管理方法與其他兩種處理方法對(duì)比結(jié)果如表6所示。對(duì)比結(jié)果可以看出，在路徑偏離上，全局重調(diào)度方案略低于干擾管理方法，表明若系統(tǒng)單純考慮成本最低，不考慮時(shí)間偏離對(duì)客戶滿意度是否影響的情況下，全局重調(diào)度方案具有明顯優(yōu)勢；在時(shí)間偏離上，本文方案明顯優(yōu)于全局重調(diào)度法，高于新派車輛法；在廣義總費(fèi)用偏離上，本文干擾管理方法明顯低于全局重調(diào)度和新派車輛方法。若采取新派車輛法，雖然降低時(shí)間偏離，但浪費(fèi)了當(dāng)前配送車輛的運(yùn)力，增加了新派車輛的成本和路徑偏離的成本；若采取全局重調(diào)度方案，盡管降低路徑偏離成本，但時(shí)間偏離成本明顯增加，可以看出全局重調(diào)度法是從犧牲客戶滿意度的情況下進(jìn)行擾動(dòng)恢復(fù)。在實(shí)際中，系統(tǒng)既要考慮路徑變動(dòng)帶來的成本偏離，也要考慮配送時(shí)間變動(dòng)對(duì)客戶的影響，從而產(chǎn)生的時(shí)間偏離成本。

表6 3種方案結(jié)果比較Table 6 Comparison of results of three schemes

綜上，在考慮路徑偏離和時(shí)間偏離的影響上，本文研究的干擾管理方法有明顯的優(yōu)化，在保證甩掛運(yùn)輸組織有效運(yùn)營的同時(shí)更好地保證對(duì)客戶的服務(wù)質(zhì)量，一定程度上減少干擾事件對(duì)系統(tǒng)的擾動(dòng)。

6 結(jié)論

本文以甩掛運(yùn)輸過程中新增運(yùn)輸任務(wù)的出現(xiàn)作為研究，在滿足客戶時(shí)間窗最小配送成本為目標(biāo)的基礎(chǔ)上，考慮路徑偏離成本、客戶服務(wù)時(shí)間偏離成本構(gòu)建干擾管理模型。本文干擾管理方法相較于全局重調(diào)度法和新派車輛法，能夠更大程度降低成本的增加，降低由于客戶服務(wù)時(shí)間偏離而產(chǎn)生的時(shí)間懲罰成本，進(jìn)而降低廣義總費(fèi)用偏離，降低系統(tǒng)擾動(dòng)程度。