多資源約束下車輛配送路徑優(yōu)化模型

吳正陽，魯工圓,2，馬駟,2

（1. 西南交通大學(xué)，交通運輸與物流學(xué)院，成都610031；2. 綜合交通運輸智能化國家地方聯(lián)合工程實驗室，成都610031）

0 引 言

資源約束下的配送路線優(yōu)化問題是在資源量變化的約束條件下對配送路線進行優(yōu)化的問題。本文多資源指的是影響、限制車輛對配送路線進行規(guī)劃選擇的資源，例如車載能源、車載貨物重量（體積）和車輛剩余可裝貨物重量（體積）等。本文研究在上述資源的消耗約束下尋找最高效的配送路線完成貨物配送，屬于車輛路徑問題范疇。

車輛路徑問題可以描述為：對一系列卸貨點和（或）裝貨點規(guī)劃適當(dāng)?shù)男熊嚶肪€，使車輛按照路線有序地通過，并在滿足一定的約束條件下達到一定的目標(biāo)[1]。車輛路徑問題最早由Dantzig和Ramser[2]于1959年提出，隨后國內(nèi)外學(xué)者對問題與模型進行了完善，提出多種算法對模型進行求解，并不停地對算法進行改進，提高模型解決問題的效率。Toth[3]等對車輛路徑相關(guān)問題進行了定義，介紹了各種類型的車輛路徑問題及其數(shù)學(xué)模型，包括了以車流為基礎(chǔ)的模型、以物流為基礎(chǔ)的模型和集覆蓋模型等三類模型。

張維澤[4]等建立了帶約束條件的物流配送問題的數(shù)學(xué)模型，運用改進的蟻群算法解決物流配送路徑優(yōu)化問題。劉志碩[5]等在分析VRP與TSP區(qū)別的基礎(chǔ)上，構(gòu)造了求解VRP的自適應(yīng)蟻群算法。郎茂祥[6,7]構(gòu)造了求解物流配送路徑優(yōu)化問題數(shù)學(xué)模型的遺傳算法和混合遺傳算法。符卓[8]對開放式車輛路徑問題進行了研究，提出一種用于求解帶裝載能力約束的開放式車輛路徑問題的禁忌搜索算法。周慧等[9]針對物流配送中動態(tài)車輛路徑優(yōu)化問題，綜合考慮動態(tài)需求、路網(wǎng)影響、車輛共享、時間窗以及客戶滿意度，建立了多目標(biāo)動態(tài)數(shù)學(xué)規(guī)劃模型。石銳[10]通過引入時間軸，將時空網(wǎng)絡(luò)模型應(yīng)用到震后救援物資配送研究中，系統(tǒng)地解決了地震災(zāi)后特定時間段內(nèi)物資分配最佳方案的求解問題。郭建紅[11]建立了帶時間窗的動態(tài)車輛路徑優(yōu)化模型，提出了采用兩階段法求解策略和改進型遺傳算法。Yang[12]等提出在電動汽車電池續(xù)航里程限制且能在路網(wǎng)上資源增加點進行電池的充電或者更換的情況下，建立配送路線優(yōu)化選擇問題的混合整數(shù)規(guī)劃模型。李寧[13]、何小鋒[14]等分別提出不同的算法對帶時間窗車輛路徑問題進行了求解。寧濤[15]等針對動態(tài)環(huán)境下車輛路徑問題，以最小化車輛數(shù)和配送里程、最大化載貨率為目標(biāo)，建立動態(tài)車輛路徑問題的數(shù)學(xué)模型，提出了云自適應(yīng)遺傳算法。

多數(shù)已有文獻中路網(wǎng)上的節(jié)點只包含倉庫節(jié)點和客戶節(jié)點，而本文的路網(wǎng)中有三類節(jié)點，包括倉庫節(jié)點、客戶節(jié)點和資源增加節(jié)點，Yang等在文獻[12]中引入上述概念。具有這三類節(jié)點的路網(wǎng)更加接近實際路網(wǎng)的情況，能準(zhǔn)確反映出各資源量在路網(wǎng)中的變化情況，對車輛在路網(wǎng)中所進行動作的描述更加準(zhǔn)確。

1 問題描述

本文研究在車輛行駛過程中多種有限資源約束下，從配送中心（物流據(jù)點）用多輛汽車向多個需求點（顧客）送貨的配送路線優(yōu)化問題。零售商（客戶）為了控制倉儲成本，希望上游配貨商選用少量多次的配送方式進行貨物配送，一輛車通常需要服務(wù)多個客戶點，車輛完成一次配送任務(wù)所需行駛的距離大大增加。為了防止車輛在配送途中因燃油不夠而導(dǎo)致行駛距離增加的情況出現(xiàn)，所以在進行配送路徑的規(guī)劃時將加油站點增加到路網(wǎng)中去。

對于該問題建立無向圖G=(N,E,W1,W2,W3)，其中G表示道路交通網(wǎng)絡(luò)，N為路網(wǎng)上的節(jié)點集合，i,j,k∈N；E表示網(wǎng)絡(luò)圖上的弧集，e∈E。W1,W2,W3表示網(wǎng)絡(luò)弧上的三個權(quán)值，分別為車輛從i到j(luò)所需要花費的時間w1(e)=ctij、行駛的距離w2(e)=dij和消耗的資源w3(e)=crij。在路網(wǎng)中，通過某條配送路徑P所花費的時間為其中邊e=(i,j)是組成路徑P的一段弧，在該問題中需要將倉庫點虛擬成起點o和終點d，如圖1所示。

圖1 網(wǎng)絡(luò)構(gòu)造Fig.1 Network topology

本文主要研究多資源約束對路線優(yōu)化問題的影響。以車載能源量和車輛載重能力為資源約束，在給定每個客戶的位置和需求量、車輛載重量、倉庫位置情況下，以倉庫為起點合理安排車輛路線，使所有車輛在滿足運輸需求的同時達到總旅行時間最少，并滿足以下條件：

（1）滿足資源量變化約束，車輛將車載資源消耗完之前必須到達資源增加點，并在資源增加點將車載資源量增加至飽和。

（2）每個客戶點的需求必須滿足，且只能由一輛車完成送貨，車輛訪問資源增加點的次數(shù)不限。

（3）配送車輛從倉庫出發(fā)完成配送并回到該倉庫。

2 多資源約束下配送路徑優(yōu)化模型

模型的目標(biāo)函數(shù)為所有車輛從倉庫出發(fā)完成配送任務(wù)回到出發(fā)倉庫所花費的時間總和最少，可以簡化為所有車輛完成配送任務(wù)所行駛的總時間最小。

2.1 多資源約束下的靜態(tài)配送路徑優(yōu)化模型

2.1.1 數(shù)學(xué)模型

靜態(tài)配送路徑優(yōu)化模型是以車流為基礎(chǔ)建立的，并基于物理網(wǎng)絡(luò)對車輛的狀態(tài)進行描述，增加資源消耗約束條件。

（1）目標(biāo)函數(shù)為所有車輛完成配送任務(wù)所耗的總時間最?。?/p>

式中，ctij為車輛經(jīng)過弧(i,j)所需花費的時間，

ctij=dijs；s為車輛行駛速度；為0-1變量，車輛v經(jīng)過弧(i,j)時取1，否則取0；N為所有節(jié)點的集合，V為車輛集合。

（2）約束條件

模型考慮流平衡約束、服務(wù)唯一性約束、資源量變化約束與變量取值約束等，以保證車輛滿足配送路徑中的限制條件。

① 流平衡約束，保證每輛車從倉庫（起點o）出發(fā)，對客戶進行服務(wù)后必須離開，最后返回倉庫（終點d）：

② 服務(wù)唯一性約束，保證每個需求客戶點只能被一輛車服務(wù)一次：

③ 弧上資源量變化約束，描述了鄰接節(jié)點i,j間資源w的數(shù)量關(guān)系：

④ 點上資源量變化約束，描述了車輛離開節(jié)點時的資源量與到達該節(jié)點時的數(shù)量關(guān)系：

⑤ 變量取值約束：

2.1.2 子回路問題的解決方法

由于允許車輛多次訪問同一個資源增加點，所以最優(yōu)配送路線就可能包含子回路。但是對資源量的描述是基于一維物理網(wǎng)絡(luò)上的節(jié)點，無法表示出一個節(jié)點上的多個資源量狀態(tài)，即不能求解具有子回路的配送問題。

配送路線中產(chǎn)生子回路的直接原因是車輛多次訪問了資源增加點，所以將車輛多次訪問一個資源增加點轉(zhuǎn)化為車輛訪問多個資源增加點，且每個資源增加點最多只能訪問一次。對每個資源增加點增加與其相對應(yīng)的虛擬資源增加點，且對應(yīng)的個數(shù)應(yīng)不小于在轉(zhuǎn)化前車輛需要訪問一個資源增加點的次數(shù)a，a通常為2。實際點與其相對應(yīng)的虛擬點之間兩兩互不相通，如圖2所示。

圖2 物理網(wǎng)絡(luò)改造Fig.2 Transformation of the physical network

通過以上處理，就可以用靜態(tài)模型求解一般的配送路徑優(yōu)化問題。相關(guān)方面的專家學(xué)者還提出了其他解決子回路的辦法，文獻[12]通過改進載重約束條件，允許車輛對資源點進行多次訪問。

2.2 多資源約束下的動態(tài)配送路徑優(yōu)化模型

動態(tài)配送路徑優(yōu)化模型基于時空網(wǎng)絡(luò)建立，不存在靜態(tài)配送路徑優(yōu)化模型中的子回路問題。時空網(wǎng)絡(luò)模型首先由Hane[16]等人提出，用以解決航空調(diào)度的路徑問題?；跁r空網(wǎng)絡(luò)的動態(tài)配送路徑優(yōu)化模型可以清楚地描述車輛在路網(wǎng)上的狀態(tài)變化過程，圖3展示了在單資源約束下，車輛在時空網(wǎng)絡(luò)上的狀態(tài)變化過程。

圖3 時空網(wǎng)絡(luò)的構(gòu)建Fig.3 Construction of the space-time network

圖3對一個包含4個節(jié)點3條弧的物理網(wǎng)絡(luò)進行了時空網(wǎng)絡(luò)的構(gòu)建，車輛的最大資源儲存量為4個單位。圖（a）、（b）分別展示了車輛在物理網(wǎng)絡(luò)和時空網(wǎng)絡(luò)上的資源變化過程。[ct,cr] 中的ct、cr分別表示車輛在弧上的行駛時間和資源消耗，（ra,rl）中的ra、rl分別表示車輛到達、離開節(jié)點時的資源量。以時空網(wǎng)絡(luò)路徑③為例，車輛從（A，3）出發(fā)，出發(fā)時資源量為4個單位，經(jīng)過2個單位的行駛時間，消耗掉2個單位資源量，到達點（B，5），到達點（C，6）時的資源量為1個單位，加滿油后，車輛離開時的資源量為4個單位。

動態(tài)配送路徑優(yōu)化模型如下：

（1）目標(biāo)函數(shù)：

（2）約束條件：

① 流平衡約束：

② 服務(wù)唯一性約束：

③ 弧上資源量變化約束：

④ 點上資源量變化約束：

⑤ 變量取值約束：

式中，ctijtlta為通過時空網(wǎng)絡(luò)弧(i,j,tl,ta)所需花費的時間；為0-1變量，車輛v通過時空網(wǎng)絡(luò)弧(i,j,tl,ta)時取1，否則取0。為車輛v在時刻ta（tl）到達（離開）點j時的資源h的數(shù)量；T為時間集合。在時空網(wǎng)絡(luò)模型中，Tv、T'分別為研究時間域的起點與終點。v

3 算例實驗

本文兩個算例都是在CPU為Intel（R）Core（TM）i7-4710HQCPU@2.5GHZ、內(nèi)存為16GB的計算機上，采用商業(yè)優(yōu)化軟件IBM ILOG CPLEX 12.6.2的OPL（Optimization Programming Language）編程語言編程求解。

3.1 算例1

物理網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示，相鄰點間的距離dij（單位為km）如表1所示。

圖4 物理網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.4 Network structure

表1 各節(jié)點間的距離Tab.1 Distance information

車輛的額定載重量U=4t，每個客戶點的需求量qi如表2所示。。車輛從倉庫出發(fā)時的初始能源量與車輛的最大能源裝載量相同，可供車輛行駛距離為90km。車輛可以從倉庫A（B）出發(fā)，最后回到倉庫A（B）。

表2 客戶點的需求量Tab.2 Demand at each customer points

3.1.1 算例1基于靜態(tài)配送優(yōu)化模型的求解

車輛經(jīng)過弧(i,j)的時間消耗ctij=dij/s，能源消耗量與車輛行駛距離成正相關(guān)，所以取這里取s=1km/min，通過軟件CPLEX12.6.2，用靜態(tài)模型求解配送最優(yōu)路徑。

當(dāng)車輛從倉庫A出發(fā)時，求得最優(yōu)路徑P=（A,1,2,5,3,4,A），如圖5所示，目標(biāo)函數(shù)z=162min。圖中括號內(nèi)數(shù)值依次表示到達時油量、出發(fā)時油量與出發(fā)時剩余載重量。

圖5 從倉庫A出發(fā)的最優(yōu)配送路徑Fig.5 Optimal delivery path from depot A

當(dāng)車輛從倉庫B出發(fā)時，不增設(shè)虛擬資源點，靜態(tài)模型無法求解出最優(yōu)配送路線，所以需要對配送網(wǎng)絡(luò)進行改進。參照上述改進的方法，取車輛訪問資源點的次數(shù)為a=2，即增設(shè)一個虛擬資源增加點，如圖6（a）所示。

用靜態(tài)模型對改進后的配送網(wǎng)絡(luò)進行求解，得出最優(yōu)配送路徑P=（B,3,5',2,1,5,4,B），目標(biāo)函數(shù)為186 min，如圖6（b）所示。圖中括號內(nèi)數(shù)值意義與圖5中相同。

圖6 從倉庫B出發(fā)的最優(yōu)配送路線Fig.6 Optimal delivery path from depot B

3.1.2 算例1基于動態(tài)配送優(yōu)化模型的求解

出發(fā)時刻Tv和到達終點時刻Tv'分別設(shè)為第1min末與第190min末。通過軟件CPLEX12.6.2，用動態(tài)模型求解配送最優(yōu)路徑，如圖7所示。圖中括號內(nèi)數(shù)值依次表示到達時間、出發(fā)時間、到達時油量、出發(fā)時油量與出發(fā)時剩余載重量。

當(dāng)車輛從倉庫A出發(fā)時，求得最優(yōu)路徑P=（A,4,3,5,2,1,A），目標(biāo)函數(shù)z=162min，配送路徑如圖7（a）所示。

當(dāng)車輛從倉庫B出發(fā)時，求得最優(yōu)路徑P=（B,4,5,1,2,5,3,B），目標(biāo)函數(shù)z=186min，配送路徑如圖7（b）所示。

圖7 從倉庫A、B出發(fā)的最優(yōu)配送路線Fig.7 Optimal delivery path from depot A and B

3.2 算例2

車輛的最大能源裝載量與車輛從倉庫出發(fā)時的初始能源量相同，可供車輛行駛距離為30 km。最少需要3輛車進行貨物配送。取s=1km/min，能源消耗量取值為。通過軟件CPLEX12.6.2，用靜態(tài)模型求解配送最優(yōu)路徑，詳細情況如表4所示。

將上述三個方案進行比較，配送方案為4輛車的行駛時間最短，所以最優(yōu)方案為4輛車的配送方案，最優(yōu)配送路徑如圖8所示，圖中括號內(nèi)的數(shù)值依次表示車輛編號、到達時油量、出發(fā)時油量與出發(fā)時剩余載重量。

表3 各節(jié)點的位置坐標(biāo)與貨物需求量Tab.3 Position and demand of each node

表4 各使用車數(shù)下所對應(yīng)的目標(biāo)函數(shù)和車輛路徑Tab.4 The objective function and path corresponding to the number of vehicles used

圖8 最優(yōu)配送路徑Fig.8 Optimal delivery path

用動態(tài)配送路徑優(yōu)化模型在求解算例2時，以GAP=10%為求解器計算終止條件，輸出求解結(jié)果。在該算例中CPLEX耗時31min達到GAP8.35%，目標(biāo)函數(shù)值121min。

4 結(jié) 論

（1）本文所建立的資源約束下配送路徑優(yōu)化靜、動態(tài)模型，能夠描述與解決在車載能源量、車輛載貨能力等多資源約束下的車輛配送路線優(yōu)化問題，可統(tǒng)一描述資源量增加和減少兩種情況。

（2）多資源約束下的靜態(tài)配送路徑優(yōu)化模型中針對車輛各種資源狀態(tài)參數(shù)在物理網(wǎng)絡(luò)中進行標(biāo)記，通過增加虛擬資源點，解決了該類模型中存在的子回路問題。

（3）多資源約束下的動態(tài)配送路徑優(yōu)化模型基于時空網(wǎng)絡(luò)建立，能夠有效避免子回路問題，對問題的描述及求解結(jié)果更加直觀準(zhǔn)確。動態(tài)模型以擴大模型規(guī)模為代價豐富了車輛配送路徑選擇方案，同時能準(zhǔn)確得到車輛到達、離開客戶點的時間。

對于具有NP-Hard特征的VRP問題，尤其是考慮多種資源約束情況下，求解器在網(wǎng)絡(luò)規(guī)模擴大導(dǎo)致問題規(guī)模變大時存在效率問題，進一步研究工作重點在于針對該模型尋找高效的求解算法。

[1] 趙燕偉，張景玲，王萬良. 物流配送的車輛路徑優(yōu)化方法[M]. 北京：科學(xué)出版社，2014.

[2] DANTZIG G B，RAMSER J H. The truck dispatching problem [J]. Management Science，1959，6（1）：80-91.

[3] TOTH P，VIGO D. The vehicle routing problem [M].Society for Industrial and Applied Mathematics，2002.

[4] 張維澤，林劍波，吳洪森，等. 基于改進蟻群算法的物流配送路徑優(yōu)化[J]. 浙江大學(xué)學(xué)報：工學(xué)版，2008，42（4）：574-578.

[5] 劉志碩，申金升，柴躍廷. 基于自適應(yīng)蟻群算法的車輛路徑問題研究[J]. 控制與決策，2005，20（5）：562-566.

[6] 郎茂祥. 基于遺傳算法的物流配送路徑優(yōu)化問題研究[J]. 中國公路學(xué)報，2002，15（3）：76-79.

[7] 郎茂祥，胡思繼. 用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究[J]. 中國管理科學(xué)，2002，10（5）：51-56.

[8] 符卓. 帶裝載能力約束的開放式車輛路徑問題及其禁忌搜索算法研究[J]. 系統(tǒng)工程理論與實踐，2004，24（3）：123-128.

[9] 周慧，周良，丁秋林. 多目標(biāo)動態(tài)車輛路徑問題建模及優(yōu)化[J]. 計算機科學(xué)，2015，42（6）：204-209

[10] 石銳. 基于時空網(wǎng)絡(luò)的震后救援物資配送模型研究[D].上海：華中科技大學(xué)，2011.

[11] 郭建紅. 帶時間窗的卷煙物流配送動態(tài)車輛路徑優(yōu)化方法研究[D]. 北京：北京交通大學(xué)，2013.

[12] YANG J，SUN H. Battery swap station location-routing problem with capacitated electric vehicles [J]. Computers& Operations Research，2015，55：217-232.

[13] 李寧，鄒彤，孫德寶. 帶時間窗車輛路徑問題的粒子群算法[J]. 系統(tǒng)工程理論與實踐，2004，24（4）：130-135.

[14] 何小鋒，馬良. 帶時間窗車輛路徑問題的量子蟻群算法[J]. 系統(tǒng)工程理論與實踐，2013，33（5）：1255-1261.

[15] 寧濤，陳榮，郭晨，等. 一種基于云計算環(huán)境的動態(tài)車輛路徑問題解決策略[J]. 交通運輸工程與信息學(xué)報，2015，13（3）：1-6.

[16] HANE C A，BARNHART C，JOHNSON E L，et al. The fleet assignment problem：solving a large-scale integer program [J]. Mathematical Programming，1995，70（1-3）：211-232.