基于有時(shí)間窗的城市配送車輛路徑方案優(yōu)化

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

（交通運(yùn)輸部科學(xué)研究院，北京 100013）

基于有時(shí)間窗的城市配送車輛路徑方案優(yōu)化

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

（交通運(yùn)輸部科學(xué)研究院，北京 100013）

在城市配送業(yè)務(wù)中，配送線路安排的合理與否對(duì)配送速度、成本、效益影響很大。提出了基于有時(shí)間窗、單出發(fā)點(diǎn)的城市配送車輛配送模式，在對(duì)有時(shí)間窗的車輛調(diào)度問(wèn)題進(jìn)行描述的基礎(chǔ)上，建立了有時(shí)間窗的城市配送路徑優(yōu)化問(wèn)題的數(shù)學(xué)模型。利用Lingo軟件，對(duì)城市配送路徑進(jìn)行優(yōu)化實(shí)證，驗(yàn)證模型的適用性。

城市配送；路徑優(yōu)化；時(shí)間窗

1 引言

城市配送是現(xiàn)代物流服務(wù)體系的重要組成部分。城市配送提供的是門到門的服務(wù)，其特點(diǎn)不同于干線運(yùn)輸，需求往往是分散的，且具有隨機(jī)性。基于城市配送的這個(gè)特點(diǎn)，合理地規(guī)劃城市配送車輛路徑，不僅可以提高企業(yè)自身配送效率，節(jié)約配送時(shí)間，提高配送響應(yīng)速度，還可以降低配送成本，為客戶提供優(yōu)質(zhì)服務(wù)。同時(shí)，城市物流運(yùn)輸也給一些大城市交通帶來(lái)高負(fù)荷、多擁擠以及交通污染現(xiàn)象，使得交通管理部門越來(lái)越多地對(duì)城市配送車輛實(shí)施交通限制管理。目前，國(guó)內(nèi)一線城市都對(duì)城市配送車輛有相關(guān)的限行時(shí)間管理控制措施，所以城市配送的路徑優(yōu)化不僅要考慮傳統(tǒng)的成本和速度問(wèn)題，還要考慮通行時(shí)間問(wèn)題，這樣的優(yōu)化方法才更具現(xiàn)實(shí)意義。

從城市配送基礎(chǔ)設(shè)施的角度，考慮時(shí)間窗的城市配送車輛路徑優(yōu)化，有助于更高效地利用城市配送的基礎(chǔ)設(shè)施，不會(huì)造成局部區(qū)域基礎(chǔ)設(shè)施的閑置浪費(fèi)，也不會(huì)造成熱點(diǎn)地區(qū)基礎(chǔ)設(shè)施的供不應(yīng)求，實(shí)現(xiàn)資源的合理利用。

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

從城市配送信息化的角度，考慮時(shí)間窗的城市配送車輛路徑優(yōu)化，是創(chuàng)建智慧城市配送體系的基礎(chǔ)條件。通過(guò)對(duì)道路情況、車輛配載情況的信息數(shù)據(jù)采集，在遠(yuǎn)端實(shí)現(xiàn)對(duì)城市配送車輛的精細(xì)管理，精確指導(dǎo)城市配送車輛的路徑選擇，使城市配送更加智能化。

從城市配送綠色安全的角度，考慮時(shí)間窗的城市配送車輛路徑優(yōu)化，有助于減少車輛空駛帶來(lái)的尾氣排放，從而減低碳排放，實(shí)現(xiàn)一定程度的節(jié)能減排。同時(shí)，對(duì)城市配送車輛進(jìn)行路徑優(yōu)化管理，有助于對(duì)車輛實(shí)施跟蹤管控，降低事故的發(fā)生率，減少其對(duì)社會(huì)產(chǎn)生的負(fù)面影響。

2 國(guó)內(nèi)外研究現(xiàn)狀

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

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

對(duì)現(xiàn)有城市配送車輛路徑優(yōu)化問(wèn)題進(jìn)行算法改進(jìn)方面，國(guó)內(nèi)學(xué)者肖健梅，黃有方，李軍軍，王錫淮（2005）提出一種求解物流配送車輛路徑的離散微粒群優(yōu)化算法，通過(guò)此優(yōu)化算法解決了求解車輛路徑離散組合的問(wèn)題。吳潔明（2011）針對(duì)傳統(tǒng)優(yōu)化方法搜索時(shí)間長(zhǎng)，難以找到最優(yōu)路徑的問(wèn)題，提出一種蟻群算法的物流配送車輛路徑優(yōu)化算法，最后采用蟻群算法對(duì)車輛路徑問(wèn)題的數(shù)學(xué)模型進(jìn)行求解。天津大學(xué)鐘石泉，賀國(guó)光（2004）提出一種多車場(chǎng)的智能處理方法，用遺傳算法進(jìn)行優(yōu)化研究的基本為單車場(chǎng)VRP問(wèn)題。

在車輛路徑優(yōu)化應(yīng)用研究方面，國(guó)內(nèi)學(xué)者郝瑞卿，閆莉（2015）在分析軍事后勤車輛路徑問(wèn)題特點(diǎn)的基礎(chǔ)上，建立了單時(shí)間窗多目標(biāo)動(dòng)態(tài)軍事后勤車輛路徑模型，可有效解決軍事后勤車輛動(dòng)態(tài)路徑優(yōu)化問(wèn)題。賀政綱，劉沙（2015）構(gòu)建了以總回收時(shí)間最短為優(yōu)化目標(biāo)的帶有時(shí)間窗的車輛路徑優(yōu)化模型（VRPTW），以成都市金牛區(qū)醫(yī)療廢棄物回收為例，驗(yàn)證了模型的有效性。國(guó)外學(xué)者Teo和Taniguchi（2015）通過(guò)對(duì)Osaka城市具體配送案例的分析，提出針對(duì)城市配送需求特點(diǎn)改進(jìn)的車輛路徑優(yōu)化模型和系統(tǒng)。

3 基于時(shí)間窗的路徑優(yōu)化模型

3.1 問(wèn)題描述

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

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

（1）V中的每個(gè)銷售點(diǎn)訪問(wèn)一次并且只能訪問(wèn)一次；

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

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

3.2 假設(shè)條件

現(xiàn)有m輛相同的車停在配送中心V0，它需要給n個(gè)銷售點(diǎn)提供貨物，并且配送中心和銷售點(diǎn)的坐標(biāo)已知。每個(gè)客戶同一時(shí)刻只能接受1輛車的服務(wù)，1個(gè)子回路對(duì)應(yīng)1輛車。車輛完成運(yùn)輸任務(wù)后必須返回配送中心。

（1）集合。ci表示第i輛車對(duì)應(yīng)的路線中銷售點(diǎn)的集合，cij∈ci。

（2）常量及變量說(shuō)明

li：每條回路上的銷售點(diǎn)數(shù)目；

Qij：第i輛車在其子回路上對(duì)應(yīng)的第j個(gè)銷售點(diǎn)的需求量；

Cij：第i輛車對(duì)應(yīng)的子回路中順序?yàn)閖的點(diǎn)；m：配送中心擁有的車輛數(shù)目；

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

di(li)(0)：第i輛車對(duì)應(yīng)的路線中第li個(gè)銷售點(diǎn)與配送中心V0之間的距離。

3.3 模型建立

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

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

約束（3）表示每條回路上的銷售點(diǎn)不超過(guò)n；

約束（4）表示所用車的數(shù)量不能超過(guò)備用車的數(shù)量；

約束（5）表示1個(gè)子回路對(duì)應(yīng)1輛車；

約束（6）表示每個(gè)客戶同一時(shí)刻只能接受1輛車的服務(wù)；

約束（7）表示一個(gè)0-1整數(shù)變量。

下面以沈陽(yáng)市為例，對(duì)一輛車的行車路線進(jìn)行優(yōu)化。假設(shè)該車負(fù)責(zé)對(duì)2、3、4、5、7、9、10、11的銷售點(diǎn)進(jìn)行配送，各點(diǎn)的坐標(biāo)已經(jīng)給出。則目標(biāo)函數(shù)和約束條件如下所示：

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

4 模型計(jì)算結(jié)果

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

表1 距離矩陣

Lingo編碼如圖1所示。運(yùn)行結(jié)果如圖2所示。

圖1 Lingo操作編碼頁(yè)面

圖2 Lingo運(yùn)作結(jié)果界面

可以得到最優(yōu)的配送線路是1-9-10-6-11-4-5-3-2-7-1，對(duì)應(yīng)于沈陽(yáng)市的配送線路為R-9-10-6-11-4-5-3-2-7-R，此時(shí)對(duì)應(yīng)于坐標(biāo)的最短距離為266。如圖3所示。

圖3 配送路徑優(yōu)化算例結(jié)果示意圖

5 結(jié)論

本研究提出了基于有時(shí)間窗、單出發(fā)點(diǎn)的城市配送車輛配送模式，在對(duì)有時(shí)間窗的車輛調(diào)度問(wèn)題進(jìn)行描述的基礎(chǔ)上，建立了有時(shí)間窗的城市配送路徑優(yōu)化問(wèn)題的數(shù)學(xué)模型。利用Lingo軟件，對(duì)城市配送路徑進(jìn)行優(yōu)化實(shí)證，驗(yàn)證模型的適用性。在約束條件設(shè)定上考慮了城市配送路徑最短且一定沒有回程和空駛。算例以沈陽(yáng)為例，展示了運(yùn)用有時(shí)間窗的城市配送路徑優(yōu)化模型，計(jì)算后從配送中心出發(fā)給全市11個(gè)點(diǎn)無(wú)回程和空駛的配送方案。

[1]李明澤.城市農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[D].大連:大連海事大學(xué),2013.

[2]鄭國(guó)華,周小強(qiáng),張力敏.基于時(shí)間窗的城市醫(yī)藥品動(dòng)態(tài)配送路徑優(yōu)化模型與算法[J].鐵道科學(xué)與工程學(xué)報(bào),2011,(4):80-85.

[3]鄧愛民.城市配送系統(tǒng)優(yōu)化研究[D].武漢:武漢理工大學(xué), 2005.

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

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

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

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

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

[9]郎茂樣.多配送中心車輛調(diào)度問(wèn)題的模型與算法研究[J].交通運(yùn)輸系統(tǒng)工程與信息,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]鐘石泉,賀國(guó)光.多車場(chǎng)車輛調(diào)度智能優(yōu)化研究[J].華東交通大學(xué)學(xué)報(bào),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-），交通運(yùn)輸部科學(xué)研究院工程師，研究方向：物流大數(shù)據(jù)、物流工程咨詢、交通規(guī)劃；李漢卿，男，北京交通大學(xué)管理科學(xué)與工程博士，美國(guó)馬里蘭大學(xué)物流系訪問(wèn)學(xué)者，交通運(yùn)輸部科學(xué)研究院助理研究員，中國(guó)物流學(xué)會(huì)特約研究員，IJEI和《交通發(fā)展研究》國(guó)際國(guó)內(nèi)核心期刊審稿人。