基于有時間窗的城市配送車輛路徑方案優化

盧爾賽，李漢卿，趙 輝，王 碩

（交通運輸部科學研究院，北京 100013）

基于有時間窗的城市配送車輛路徑方案優化

盧爾賽，李漢卿，趙 輝，王 碩

（交通運輸部科學研究院，北京 100013）

在城市配送業務中，配送線路安排的合理與否對配送速度、成本、效益影響很大。提出了基于有時間窗、單出發點的城市配送車輛配送模式，在對有時間窗的車輛調度問題進行描述的基礎上，建立了有時間窗的城市配送路徑優化問題的數學模型。利用Lingo軟件，對城市配送路徑進行優化實證，驗證模型的適用性。

城市配送；路徑優化；時間窗

1 引言

城市配送是現代物流服務體系的重要組成部分。城市配送提供的是門到門的服務，其特點不同于干線運輸，需求往往是分散的，且具有隨機性?；诔鞘信渌偷倪@個特點，合理地規劃城市配送車輛路徑，不僅可以提高企業自身配送效率，節約配送時間，提高配送響應速度，還可以降低配送成本，為客戶提供優質服務。同時，城市物流運輸也給一些大城市交通帶來高負荷、多擁擠以及交通污染現象，使得交通管理部門越來越多地對城市配送車輛實施交通限制管理。目前，國內一線城市都對城市配送車輛有相關的限行時間管理控制措施，所以城市配送的路徑優化不僅要考慮傳統的成本和速度問題，還要考慮通行時間問題，這樣的優化方法才更具現實意義。

從城市配送基礎設施的角度，考慮時間窗的城市配送車輛路徑優化，有助于更高效地利用城市配送的基礎設施，不會造成局部區域基礎設施的閑置浪費，也不會造成熱點地區基礎設施的供不應求，實現資源的合理利用。

從城市配送運輸組織模式的角度，考慮時間窗的城市配送車輛路徑優化，在有條件的區域施行城市共同配送，有利于優化現有的城市運輸組織模式，提高車輛的利用率，降低車輛空駛率，疏解城市道路擁堵情況，降低配送成本。

從城市配送信息化的角度，考慮時間窗的城市配送車輛路徑優化，是創建智慧城市配送體系的基礎條件。通過對道路情況、車輛配載情況的信息數據采集，在遠端實現對城市配送車輛的精細管理，精確指導城市配送車輛的路徑選擇，使城市配送更加智能化。

從城市配送綠色安全的角度，考慮時間窗的城市配送車輛路徑優化，有助于減少車輛空駛帶來的尾氣排放，從而減低碳排放，實現一定程度的節能減排。同時，對城市配送車輛進行路徑優化管理，有助于對車輛實施跟蹤管控，降低事故的發生率，減少其對社會產生的負面影響。

2 國內外研究現狀

配送車輛的優化問題一般可根據空間特性和時間特性分為車輛路徑規劃問題和車輛調度問題。當不考慮時間要求，僅根據空間位置安排車輛的線路時稱為車輛路徑規劃問題(VRP--Vehicle Routing Problem)；考慮時間窗要求安排運輸線路時稱為車輛調度問題VSP (VSP--Vehicle Scheduling Problem)。某些學者將有時間要求的車輛路徑規劃問題稱為Vehicle Routing Problem With Time Windows(VRPTW)。從國內外研究上可以分為三大類：第一類是傳統車輛路徑優化問題的拓展問題，即在傳統城市配送車輛路徑優化模型的基礎上增加能力約束、隨機需求等約束條件，使模型更加復雜并貼近實際；第二類是對現有城市配送車輛路徑優化問題進行算法改進，用交叉學科里的優化算法試圖為車輛路徑優化提供最優解集；第三類是應用研究，即在模型和算法固定的基礎上，根據城市具體的配送車輛路徑優化實際案例，提出應用問題解決方案。本文屬于第一類和第三類的融合，既考慮了增加時間窗的約束，以期更滿足現實配送情況，另一方面也是具體配送問題的應用。

傳統車輛路徑優化問題的拓展問題方面，車輛路徑問題在經典VRP問題的基礎上產生了許多不同的延伸和變化型態，包括TSP、帶能力約束的車輛路徑問題、隨機需求車輛路徑問題、帶時間窗的車輛路徑問題、動態車輛路徑問題、追求最佳服務時間的車輛路徑問題、多車型車輛路徑問題、車輛多次使用的車輛路徑問題、考慮回路的車輛路徑問題。國內學者楊錦冬，徐麗群（2004）基于交通條件約束、客戶時間窗約束以及車輛承載能力約束條件下，以車輛的配送路徑最短、拼裝貨品最多為優化目標，提出車輛配送與配載的兩目標優化調度模型組。國外專家Fisher（1997）研究了有時間窗的多配送中心車輛調度問題；Tailllard（1994）將多配送中心車輛調度問題分解成兩個子問題：多配送中心的選址問題和一般的單配送中心車輛調度問題。

對現有城市配送車輛路徑優化問題進行算法改進方面，國內學者肖健梅，黃有方，李軍軍，王錫淮（2005）提出一種求解物流配送車輛路徑的離散微粒群優化算法，通過此優化算法解決了求解車輛路徑離散組合的問題。吳潔明（2011）針對傳統優化方法搜索時間長，難以找到最優路徑的問題，提出一種蟻群算法的物流配送車輛路徑優化算法，最后采用蟻群算法對車輛路徑問題的數學模型進行求解。天津大學鐘石泉，賀國光（2004）提出一種多車場的智能處理方法，用遺傳算法進行優化研究的基本為單車場VRP問題。

在車輛路徑優化應用研究方面，國內學者郝瑞卿，閆莉（2015）在分析軍事后勤車輛路徑問題特點的基礎上，建立了單時間窗多目標動態軍事后勤車輛路徑模型，可有效解決軍事后勤車輛動態路徑優化問題。賀政綱，劉沙（2015）構建了以總回收時間最短為優化目標的帶有時間窗的車輛路徑優化模型（VRPTW），以成都市金牛區醫療廢棄物回收為例，驗證了模型的有效性。國外學者Teo和Taniguchi（2015）通過對Osaka城市具體配送案例的分析，提出針對城市配送需求特點改進的車輛路徑優化模型和系統。

3 基于時間窗的路徑優化模型

3.1 問題描述

城市配送需要選擇合適的線路，在保證需求及時的前提下，盡可能的使運輸線路最短，即VRP問題。

設G=(V,A)是一個有向圖，其中V={ } 0,1,…,n是頂點集、頂點0表示配送中心，頂點1，2，…，n表示銷售點，A是弧集，表示銷售點之間或配送中心與銷售點之間的道路連接。每一條弧上有一個非負數我們定義這個數為運輸距離。將所有的cij寫成矩陣的形式，即若C是對稱矩陣，將弧集A用邊集E代替。另外，我們假定在貨場有m個車可用，其中ml≤m≤mu。為簡單起見，我們假定所有車輛是相同的，并且有相同的運輸能力D。我們的目標就是設計一套運輸配送方案，使總費用最少，并且滿足下列約束：

（1）V中的每個銷售點訪問一次并且只能訪問一次；

（2）所有車輛必須從配送中心出發并回到配送中心；

（3）滿足一些實際的附加約束條件。

3.2 假設條件

現有m輛相同的車停在配送中心V0，它需要給n個銷售點提供貨物，并且配送中心和銷售點的坐標已知。每個客戶同一時刻只能接受1輛車的服務，1個子回路對應1輛車。車輛完成運輸任務后必須返回配送中心。

（1）集合。ci表示第i輛車對應的路線中銷售點的集合，cij∈ci。

（2）常量及變量說明

li：每條回路上的銷售點數目；

Qij：第i輛車在其子回路上對應的第j個銷售點的需求量；

Cij：第i輛車對應的子回路中順序為j的點；m：配送中心擁有的車輛數目；

N：滿足運輸任務需要車的最少數量；M：車輛的最大載重量；L：車輛的最大行駛距離；di(j-1)：第i輛車對應的路線中順序排列的第j-1個銷售點和第j個銷售點之間的距離；

di(li)(0)：第i輛車對應的路線中第li個銷售點與配送中心V0之間的距離。

3.3 模型建立

約束（1）表示每條回路上的運輸總量不能超過車的最大載重量和最大行駛距離；

約束（2）表示各條回路上的銷售點數量之和等于n；

約束（3）表示每條回路上的銷售點不超過n；

約束（4）表示所用車的數量不能超過備用車的數量；

約束（5）表示1個子回路對應1輛車；

約束（6）表示每個客戶同一時刻只能接受1輛車的服務；

約束（7）表示一個0-1整數變量。

下面以沈陽市為例，對一輛車的行車路線進行優化。假設該車負責對2、3、4、5、7、9、10、11的銷售點進行配送，各點的坐標已經給出。則目標函數和約束條件如下所示：

其中，約束條件是總距離最短。約束條件（1）表示每個點只有一個邊出去，（2）表示每個點只有一個邊進入，約束（3）、（4）表示形成的回路中沒有子回路。

4 模型計算結果

為了方便計算，對2、3、4、5、7、9、10、11用2到9表示，1表示配送中心。各點之間的距離矩陣見表1。

表1 距離矩陣

Lingo編碼如圖1所示。運行結果如圖2所示。

圖1 Lingo操作編碼頁面

圖2 Lingo運作結果界面

可以得到最優的配送線路是1-9-10-6-11-4-5-3-2-7-1，對應于沈陽市的配送線路為R-9-10-6-11-4-5-3-2-7-R，此時對應于坐標的最短距離為266。如圖3所示。

圖3 配送路徑優化算例結果示意圖

5 結論

本研究提出了基于有時間窗、單出發點的城市配送車輛配送模式，在對有時間窗的車輛調度問題進行描述的基礎上，建立了有時間窗的城市配送路徑優化問題的數學模型。利用Lingo軟件，對城市配送路徑進行優化實證，驗證模型的適用性。在約束條件設定上考慮了城市配送路徑最短且一定沒有回程和空駛。算例以沈陽為例，展示了運用有時間窗的城市配送路徑優化模型，計算后從配送中心出發給全市11個點無回程和空駛的配送方案。

[1]李明澤.城市農產品冷鏈物流配送路徑優化研究[D].大連:大連海事大學,2013.

[2]鄭國華,周小強,張力敏.基于時間窗的城市醫藥品動態配送路徑優化模型與算法[J].鐵道科學與工程學報,2011,(4):80-85.

[3]鄧愛民.城市配送系統優化研究[D].武漢:武漢理工大學, 2005.

[4]肖健梅,黃有方,李軍軍,等.基于離散微粒群優化的物流配送車輛路徑問題[J].系統工程,2005,(4):12-15.

[5]吳潔明.物流配送車輛路徑優化問題的仿真研究[J].計算機仿真,2011,(7):25-27.

[6]楊錦冬,徐麗群.城市物流中心車輛配送配載調度指派模型研究[J].同濟大學學報(自然科學版),2004,(11):13-16.

[7]郝瑞卿,閆莉.軍事配送式后勤車輛路徑問題研究[J].西安工業大學學報,2015,(1):5-7.

[8]賀政綱,劉沙.城市醫療廢棄物回收路徑優化研究-以成都市金牛區為例[J].物流技術,2015,(1):34-37.

[9]郎茂樣.多配送中心車輛調度問題的模型與算法研究[J].交通運輸系統工程與信息,2006,(10):34-36.

[10]Fisher M.Vehicle routing with time windows'two optimization algorithms[J].Operations Research,1997,45(3):48-49.

[11]Laporte G.The vehicle routing problem:An over view of exact and approximate algorithm[J].European Journal of Operational Research,1992,59(3):34-35.

[12]Tailllard E.Parallel interative search method for vehicle routing problem[J].Operations Research Socitey,1994,45(10): 115-116.

[13]鐘石泉,賀國光.多車場車輛調度智能優化研究[J].華東交通大學學報,2004,21(6):25-26.

[14]Teo Taniguchi.Evaluation of Urban Distribution Center Using Multiagent Model with Geographic Information Systems[A]. Transportation Research Board 94th Annual Meeting[C].2015.

Optimization of Routing Plan of Urban Distribution Vehicles with Time Window

Lu Ersai,Li Hanqing,Zhao Hui,Wang Shuo
(China Academy of Transportation Sciences,Beijing 100013,China)

In this paper,we proposed the urban distribution mode with time window and single point of departure,then on the basis of a description of the VRP with time window,built the corresponding mathematical model and at the end,used Lingo to verify the applicability of the model in urban distribution route optimization.

urban distribution;route optimization;time window

F252.14;F224.0

A

1005-152X(2016)12-0093-04

10.3969/j.issn.1005-152X.2016.12.022

2016-10-18

盧爾賽（1988-），交通運輸部科學研究院工程師，研究方向：物流大數據、物流工程咨詢、交通規劃；李漢卿，男，北京交通大學管理科學與工程博士，美國馬里蘭大學物流系訪問學者，交通運輸部科學研究院助理研究員，中國物流學會特約研究員，IJEI和《交通發展研究》國際國內核心期刊審稿人。