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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在車(chē)輛路徑優(yōu)化應(yīng)用研究方面，國(guó)內(nèi)學(xué)者郝瑞卿，閆莉（2015）在分析軍事后勤車(chē)輛路徑問(wèn)題特點(diǎn)的基礎(chǔ)上，建立了單時(shí)間窗多目標(biāo)動(dòng)態(tài)軍事后勤車(chē)輛路徑模型，可有效解決軍事后勤車(chē)輛動(dòng)態(tài)路徑優(yōu)化問(wèn)題。賀政綱，劉沙（2015）構(gòu)建了以總回收時(shí)間最短為優(yōu)化目標(biāo)的帶有時(shí)間窗的車(chē)輛路徑優(yōu)化模型（VRPTW），以成都市金牛區(qū)醫(yī)療廢棄物回收為例，驗(yàn)證了模型的有效性。國(guó)外學(xué)者Teo和Taniguchi（2015）通過(guò)對(duì)Osaka城市具體配送案例的分析，提出針對(duì)城市配送需求特點(diǎn)改進(jìn)的車(chē)輛路徑優(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表示銷(xiāo)售點(diǎn)，A是弧集，表示銷(xiāo)售點(diǎn)之間或配送中心與銷(xiāo)售點(diǎn)之間的道路連接。每一條弧上有一個(gè)非負(fù)數(shù)我們定義這個(gè)數(shù)為運(yùn)輸距離。將所有的cij寫(xiě)成矩陣的形式，即若C是對(duì)稱(chēng)矩陣，將弧集A用邊集E代替。另外，我們假定在貨場(chǎng)有m個(gè)車(chē)可用，其中ml≤m≤mu。為簡(jiǎn)單起見(jiàn)，我們假定所有車(chē)輛是相同的，并且有相同的運(yùn)輸能力D。我們的目標(biāo)就是設(shè)計(jì)一套運(yùn)輸配送方案，使總費(fèi)用最少，并且滿(mǎn)足下列約束：

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

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

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

3.2 假設(shè)條件

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

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

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

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

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

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

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

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

3.3 模型建立

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

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

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

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

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

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

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

下面以沈陽(yáng)市為例，對(duì)一輛車(chē)的行車(chē)路線進(jìn)行優(yōu)化。假設(shè)該車(chē)負(fù)責(zé)對(duì)2、3、4、5、7、9、10、11的銷(xiāo)售點(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）表示形成的回路中沒(méi)有子回路。

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

為了方便計(jì)算，對(duì)2、3、4、5、7、9、10、11用2到9表示，1表示配送中心。各點(diǎn)之間的距離矩陣見(jià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)的城市配送車(chē)輛配送模式，在對(duì)有時(shí)間窗的車(chē)輛調(diào)度問(wèn)題進(jìn)行描述的基礎(chǔ)上，建立了有時(shí)間窗的城市配送路徑優(yōu)化問(wèn)題的數(shù)學(xué)模型。利用Lingo軟件，對(duì)城市配送路徑進(jìn)行優(yōu)化實(shí)證，驗(yàn)證模型的適用性。在約束條件設(shè)定上考慮了城市配送路徑最短且一定沒(méi)有回程和空駛。算例以沈陽(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]鄧愛(ài)民.城市配送系統(tǒng)優(yōu)化研究[D].武漢:武漢理工大學(xué), 2005.

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

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

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

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

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

[9]郎茂樣.多配送中心車(chē)輛調(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ē)場(chǎng)車(chē)輛調(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ù)、物流工程咨詢(xún)、交通規(guī)劃；李漢卿，男，北京交通大學(xué)管理科學(xué)與工程博士，美國(guó)馬里蘭大學(xué)物流系訪問(wèn)學(xué)者，交通運(yùn)輸部科學(xué)研究院助理研究員，中國(guó)物流學(xué)會(huì)特約研究員，IJEI和《交通發(fā)展研究》國(guó)際國(guó)內(nèi)核心期刊審稿人。