戢曉峰 陳 方 覃文文 肖俊奇

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

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

1 問題描述

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

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

2 車輛調度模型建立

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

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

3 車輛路線求解

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

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

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

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

表1 最短時間表

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

表2 節(jié)約時間表

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

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

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

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

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

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

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

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

3）進行派件任務時的收件量分配情況，若0≤dit≤Yαki，則Sαki＝dit；若dit＞Yαki，則Sαki＝Yαki.

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

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

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

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

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

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

6 結束語

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

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

［2］李 杰.基于網(wǎng)絡的郵政運輸車輛調度問題研究［D］.成都：西華大學，2009.

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

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