多資源約束下車輛配送路徑優化模型

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

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

0 引 言

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

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

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

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

1 問題描述

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

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

圖1 網絡構造Fig.1 Network topology

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

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

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

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

2 多資源約束下配送路徑優化模型

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

2.1 多資源約束下的靜態配送路徑優化模型

2.1.1 數學模型

靜態配送路徑優化模型是以車流為基礎建立的，并基于物理網絡對車輛的狀態進行描述，增加資源消耗約束條件。

（1）目標函數為所有車輛完成配送任務所耗的總時間最小：

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

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

（2）約束條件

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

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

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

③ 弧上資源量變化約束，描述了鄰接節點i,j間資源w的數量關系：

④ 點上資源量變化約束，描述了車輛離開節點時的資源量與到達該節點時的數量關系：

⑤ 變量取值約束：

2.1.2 子回路問題的解決方法

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

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

圖2 物理網絡改造Fig.2 Transformation of the physical network

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

2.2 多資源約束下的動態配送路徑優化模型

動態配送路徑優化模型基于時空網絡建立，不存在靜態配送路徑優化模型中的子回路問題。時空網絡模型首先由Hane[16]等人提出，用以解決航空調度的路徑問題。基于時空網絡的動態配送路徑優化模型可以清楚地描述車輛在路網上的狀態變化過程，圖3展示了在單資源約束下，車輛在時空網絡上的狀態變化過程。

圖3 時空網絡的構建Fig.3 Construction of the space-time network

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

動態配送路徑優化模型如下：

（1）目標函數：

（2）約束條件：

① 流平衡約束：

② 服務唯一性約束：

③ 弧上資源量變化約束：

④ 點上資源量變化約束：

⑤ 變量取值約束：

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

3 算例實驗

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

3.1 算例1

物理網絡結構如圖4所示，相鄰點間的距離dij（單位為km）如表1所示。

圖4 物理網絡結構圖Fig.4 Network structure

表1 各節點間的距離Tab.1 Distance information

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

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

3.1.1 算例1基于靜態配送優化模型的求解

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

當車輛從倉庫A出發時，求得最優路徑P=（A,1,2,5,3,4,A），如圖5所示，目標函數z=162min。圖中括號內數值依次表示到達時油量、出發時油量與出發時剩余載重量。

圖5 從倉庫A出發的最優配送路徑Fig.5 Optimal delivery path from depot A

當車輛從倉庫B出發時，不增設虛擬資源點，靜態模型無法求解出最優配送路線，所以需要對配送網絡進行改進。參照上述改進的方法，取車輛訪問資源點的次數為a=2，即增設一個虛擬資源增加點，如圖6（a）所示。

用靜態模型對改進后的配送網絡進行求解，得出最優配送路徑P=（B,3,5',2,1,5,4,B），目標函數為186 min，如圖6（b）所示。圖中括號內數值意義與圖5中相同。

圖6 從倉庫B出發的最優配送路線Fig.6 Optimal delivery path from depot B

3.1.2 算例1基于動態配送優化模型的求解

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

當車輛從倉庫A出發時，求得最優路徑P=（A,4,3,5,2,1,A），目標函數z=162min，配送路徑如圖7（a）所示。

當車輛從倉庫B出發時，求得最優路徑P=（B,4,5,1,2,5,3,B），目標函數z=186min，配送路徑如圖7（b）所示。

圖7 從倉庫A、B出發的最優配送路線Fig.7 Optimal delivery path from depot A and B

3.2 算例2

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

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

表3 各節點的位置坐標與貨物需求量Tab.3 Position and demand of each node

表4 各使用車數下所對應的目標函數和車輛路徑Tab.4 The objective function and path corresponding to the number of vehicles used

圖8 最優配送路徑Fig.8 Optimal delivery path

用動態配送路徑優化模型在求解算例2時，以GAP=10%為求解器計算終止條件，輸出求解結果。在該算例中CPLEX耗時31min達到GAP8.35%，目標函數值121min。

4 結 論

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

（2）多資源約束下的靜態配送路徑優化模型中針對車輛各種資源狀態參數在物理網絡中進行標記，通過增加虛擬資源點，解決了該類模型中存在的子回路問題。

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

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

[1] 趙燕偉，張景玲，王萬良. 物流配送的車輛路徑優化方法[M]. 北京：科學出版社，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] 張維澤，林劍波，吳洪森，等. 基于改進蟻群算法的物流配送路徑優化[J]. 浙江大學學報：工學版，2008，42（4）：574-578.

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

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

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

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

[9] 周慧，周良，丁秋林. 多目標動態車輛路徑問題建模及優化[J]. 計算機科學，2015，42（6）：204-209

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

[11] 郭建紅. 帶時間窗的卷煙物流配送動態車輛路徑優化方法研究[D]. 北京：北京交通大學，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]. 系統工程理論與實踐，2004，24（4）：130-135.

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

[15] 寧濤，陳榮，郭晨，等. 一種基于云計算環境的動態車輛路徑問題解決策略[J]. 交通運輸工程與信息學報，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.