時(shí)效約束的高強(qiáng)度快遞需求區(qū)域車輛調(diào)度模型＊

戢曉峰 陳 方 覃文文 肖俊奇

（昆明理工大學(xué)交通工程學(xué)院1） 昆明 650500） （昆明理工大學(xué)社會科學(xué)學(xué)院2） 昆明 650500）

為了提高快件集散的時(shí)效性，快遞企業(yè)必須減少收派員往返于客戶與點(diǎn)部之間的時(shí)間，此時(shí)就引進(jìn)了“移動倉庫”的概念.移動倉庫又稱“汽車二程接駁”，就是在收、派量大且穩(wěn)定的區(qū)域，租賃場地建立一個或多個“前沿”交接中轉(zhuǎn)站，配合IVCO 貨車的循環(huán)流動，節(jié)省單個收派員往返于客戶與點(diǎn)部之間的時(shí)間，相應(yīng)延長在客戶處的服務(wù)時(shí)間［1］.在此背景下，高強(qiáng)度快遞需求區(qū)域的快遞車輛調(diào)度，直接關(guān)系到整個收派件過程的效率、快遞成本以及顧客滿意度，并將會對企業(yè)的運(yùn)營效益產(chǎn)生重要影響.本文針對高強(qiáng)度快遞需求區(qū)域的車輛調(diào)度問題，考慮收派件時(shí)效約束與移動倉庫容量，建立了有時(shí)限的混裝卸車輛調(diào)度模型，最大限度利用車輛載重量，以保證快遞系統(tǒng)的高效運(yùn)營，提高快遞服務(wù)水平.

1 問題描述

快件收派配送是快遞企業(yè)進(jìn)行客戶服務(wù)的直接手段和重要環(huán)節(jié)，車輛調(diào)度的合理與否對配送速度、運(yùn)營成本及經(jīng)濟(jì)效益均會產(chǎn)生很大影響［2］.高強(qiáng)度快遞需求區(qū)域的車輛調(diào)度問題本質(zhì)上是一個車輛優(yōu)化調(diào)度問題（vehicle scheduling problem，VSP），即一個典型的NP 難題.高強(qiáng)度快遞需求區(qū)域的某個點(diǎn)部中心向n個移動倉庫進(jìn)行收派件，每個工作日共有3批派件進(jìn)港，要求在下一批派件進(jìn)港前必須完成上一批的派件任務(wù)，每個工作日必須完成上午與下午兩個時(shí)段的收件任務(wù)，且上時(shí)段的任務(wù)必須在下時(shí)段來臨前完成，否則會降低時(shí)效性或?qū)е乱苿觽}庫爆滿.求滿足上述時(shí)間限制、車輛容量限制、移動倉庫容量限制且費(fèi)用最少的車輛行駛路線，即為帶時(shí)間窗的車輛調(diào)度問題.由于收派件任務(wù)必須在要求的時(shí)間范圍內(nèi)完成，若超出這個時(shí)間范圍，則得到的解為不可行解，即必須滿足時(shí)間窗約束，因此為帶硬時(shí)間窗的車輛路徑問題.本文在國內(nèi)外VSP研究成果的基礎(chǔ)上，提出適合高強(qiáng)度快遞需求區(qū)域車輛調(diào)度問題模型的目標(biāo)函數(shù)和約束條件，通過構(gòu)造時(shí)間窗檢查約束條件，求解有硬時(shí)間窗的VSP.

1）車輛調(diào)動建模的條件界定 （1）以一個點(diǎn)部中心為源點(diǎn)，且只有一個源點(diǎn)，即單源點(diǎn).區(qū)域收派件貨車從此中心發(fā)出，經(jīng)各移動倉庫，最后回到此中心；（2）點(diǎn)部中心擁有k 輛相同的廂式貨車來完成點(diǎn)部區(qū)域的收派件工作，且每公里成本（包括耗油量及人力成本）相同；（3）根據(jù)收派件任務(wù)的特點(diǎn)，每天必須在相應(yīng)四個時(shí)段完成四批派件進(jìn)港任務(wù)，在兩個大時(shí)段內(nèi)必須完成相應(yīng)時(shí)段所有移動倉庫積累的收件任務(wù)；（4）每個移動倉庫管轄的范圍固定不變 且移動倉庫的貨物存放遵循先進(jìn)先出的原則；（5）所有快件以標(biāo)準(zhǔn)件進(jìn)行計(jì)算，即以件為單位來計(jì)量倉庫容量、快件需求量、車輛最大載重量、剩余載重量、裝載量、派件量與收件量.

2 車輛調(diào)度模型建立

1）系統(tǒng)初始化 令eit＝0，即在工作日開始令每個移動倉庫的庫存量為0.

4）車輛的行車路線的確定 每批派件任務(wù)采用相同的車型，且車輛的最大載重量為Q，貨車的數(shù)量沒有限制.每輛車派件運(yùn)行時(shí)間需要滿足的時(shí)間條件為

3 車輛路線求解

針對車輛路線問題采用節(jié)約里程法求解，綜合考慮路線距離和時(shí)間因素，如服務(wù)需求穩(wěn)定且配送時(shí)間固定，可采用中間指標(biāo)：路程長度／平均車速；結(jié)合快件服務(wù)需求特點(diǎn)及收派件實(shí)際流程，可采用指標(biāo)：路程長度／平均車速＋每個節(jié)點(diǎn)的停留時(shí)間即收派件的裝卸貨時(shí)間.

如圖1所示，點(diǎn)部中心0向第1－n個移動倉庫派件，Pαi為第α 批第i 個移動倉庫的派件量，件：ti為每個移動倉庫的裝卸貨時(shí)間；t0i為點(diǎn)部中心0與第i個移動倉庫之間的最短運(yùn)行時(shí)間；tij為移動倉庫之間的最短運(yùn)行時(shí)間，h.

圖1 點(diǎn)部與移動倉庫路徑分布車輛路線求解步驟如下.

步驟1 計(jì)算點(diǎn)部中心至各移動倉庫以及各移動倉庫之間的最短作業(yè)時(shí)間（包括運(yùn)行時(shí)間和裝卸貨時(shí)間），如表1所列.

表1 最短時(shí)間表

步驟2 由上述最短作業(yè)時(shí)間計(jì)算出由點(diǎn)部中心0到各移動倉庫之間的節(jié)約時(shí)間，并得到節(jié)約時(shí)間表2（節(jié)約時(shí)間為負(fù)數(shù)時(shí)，無實(shí)際意義，為0），根據(jù)節(jié)約里程法的基本原理：三角形一邊之長必定小于另外兩邊之和，則節(jié)約里程Sij＝D0i＋D0j－Dij，如圖2所示（i，j 表示移動倉庫）.根據(jù)快遞收派件的具體流程，得到節(jié)約時(shí)間為

表2 節(jié)約時(shí)間表

步驟3 根據(jù)節(jié)約時(shí)間多少的順序，編制節(jié)約時(shí)間順序表，以便使得節(jié)約時(shí)間最多的移動倉庫組合裝車完成收派件任務(wù).

圖2 節(jié)約里程法的基本原理

步驟4 根據(jù)節(jié)約時(shí)間順序表和配車約束（車輛最大載重量限制）、車輛收派件的間限制等約束條件，即

Wk＝∑Pαi≤Q 且ETα≤Si≤LTα且∑（t0i＋tij＋tj0）＋∑ti≤LTα－ETα，得到每輛車的派件路徑以及裝載貨物的分配.由此，得到每一條派件路徑后從集合Cαi剔除該次循環(huán) 點(diǎn)，進(jìn)行第二次路徑選擇，并進(jìn)行循環(huán).

步驟5 將Cαi中剩余無法分配的點(diǎn)在滿足時(shí)間條件：ETα≤Si≤LTα且∑（t0i＋tij＋tj0）＋∑ti≤LTα－ETα的前提下，分配到WK＜Q 的車輛，使得車輛的利用率達(dá)到最大.如果有剩余派件量，單獨(dú)派車來完成，最后分配成為x 個組.

4 車輛調(diào)度模型優(yōu)化

1）車輛數(shù)k的確定 將以上x 個組合中對應(yīng)的收派件任務(wù)完成時(shí)間進(jìn)行分析，并重新進(jìn)行二次分組，形成了y 個組合，這些組合的收派件任務(wù)完成的作業(yè)時(shí)間積累量均滿足t≤LTα－ETα，單獨(dú)遺留下z 個組合不能重新進(jìn)行二次分組，則需要的車輛數(shù)k＝y(tǒng)＋z.

2）發(fā)車時(shí)間的安排 從車場調(diào)度出來的k輛車同時(shí)發(fā)車.針對上述的y 輛車，每輛車根據(jù)所派送的任務(wù)中對應(yīng)的移動倉庫的優(yōu)先度積累量進(jìn)行比較，按照從大到小的順序依次進(jìn)行派送，同一輛車根據(jù)它的配送任務(wù)進(jìn)行連續(xù)發(fā)車，直到任務(wù)完成，則停止發(fā)車.

3）進(jìn)行派件任務(wù)時(shí)的收件量分配情況，若0≤dit≤Yαki，則Sαki＝dit；若dit＞Yαki，則Sαki＝Y(jié)αki.

若收派件任務(wù)完成后，車輛仍有剩余載重量且下一刻沒有派件任務(wù)，則在滿足時(shí)間限制ETα≤Si≤LTα且∑（t0i＋tij＋tj0）＋∑ti≤LTα－ETα的條件 下，加入其他移動倉庫，進(jìn)行單獨(dú)收件，使得車輛的利用率達(dá)到最大.

需要指出的是，對于以上調(diào)度車輛，在完成派件任務(wù)后，在下一批派件任務(wù)來臨之前，啟動單獨(dú)收件任務(wù)管理機(jī)制.要求必須在兩個時(shí)刻T1，T2前完成對應(yīng)的兩個時(shí)段的收件積累量，每天收派員的最早工作時(shí)間為T0.

5 基于移動倉庫優(yōu)先度的路徑優(yōu)化

鑒于移動倉庫服務(wù)能力的限制，需要考慮移動倉庫的優(yōu)先度問題，以防止出現(xiàn)倉庫爆滿現(xiàn)象，本文按照優(yōu)先度從高到低的順序得到路徑，方法簡述如下

1）當(dāng)每個移動倉庫的優(yōu)先度eit均不相等時(shí)，按優(yōu)先度排列順序進(jìn)行相應(yīng)倉庫快件的收取.

2）當(dāng)存在兩個以上的移動倉庫的優(yōu)先度相等時(shí)，設(shè)這些移動倉庫組成的集合為C，針對這幾個移動倉庫按照基于Dijkstra算法來選擇最優(yōu)路徑，使得目標(biāo)函數(shù)滿足：

6 結(jié)束語

本文針對高強(qiáng)度快遞需求區(qū)域車輛調(diào)度問題的實(shí)際需求，建立了有時(shí)限的混裝卸車輛調(diào)度問題模型.通過構(gòu)造時(shí)間窗檢查約束條件，求解有硬時(shí)間窗的VSP.在解決問題的過程中，對節(jié)約里程算法進(jìn)行適當(dāng)了修正，基于Dijkstra算法進(jìn)行路徑優(yōu)化，不但求得滿足實(shí)際需求的可行解，而且還可分析剩余點(diǎn)對最終線路的影響，能夠指導(dǎo)高強(qiáng)度快遞需求區(qū)域建立移動倉庫后的車輛調(diào)度實(shí)際問題.

［1］教育部高等學(xué)校物流類專業(yè)教學(xué)指導(dǎo)委員會.“SF杯”第三屆全國大學(xué)生物流設(shè)計(jì)大賽案例［Z］.北京：教育部高等學(xué)校物流類專業(yè)教學(xué)指導(dǎo)委員會，2010.

［2］李 杰.基于網(wǎng)絡(luò)的郵政運(yùn)輸車輛調(diào)度問題研究［D］.成都：西華大學(xué)，2009.

［3］陳曉偉，張悟移，耿繼武.節(jié)約法在配送路線選擇中的應(yīng)用［J］.昆明理工大學(xué)學(xué)報(bào)：理工版，2003，28（4）：140－143.

［4］王宏勇，盧戰(zhàn)偉.嵌入式GIS 最短路徑分析中Dijkstra法改進(jìn)［J］.測繪學(xué)院學(xué)報(bào)，2005，22（1）：43－45.