時效約束的高強度快遞需求區域車輛調度模型＊

戢曉峰 陳 方 覃文文 肖俊奇

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

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

1 問題描述

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

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

2 車輛調度模型建立

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

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

3 車輛路線求解

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

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

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

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

表1 最短時間表

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

表2 節約時間表

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

圖2 節約里程法的基本原理

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

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

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

4 車輛調度模型優化

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

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

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 基于移動倉庫優先度的路徑優化

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

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

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

6 結束語

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

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

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

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

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