基于時間窗的多車場車輛路徑問題研究

閆 凱，李愛光，郭 健，陳 冰

（1.信息工程大學， 河南 鄭州 450001）

基于時間窗的多車場車輛路徑問題研究

閆 凱1，李愛光1，郭 健1，陳 冰1

（1.信息工程大學， 河南 鄭州 450001）

啟發式優化算法在解決車輛路徑問題時具有較好的收斂性，整體法在解決時間窗的多車場車輛路徑問題時具有較好的全局性，結合二者優點，進行了算法研究。首先采用整體法得到車輛路徑問題的全局最優解；再采用智能優化算法對配送點進行車場選擇，匹配代價最小的車場；最后通過實驗驗證了該算法在解決時間窗的多車場車輛路徑問題上的有效性。

智能優化算法；整體法；時間窗；多車場車輛路徑

隨著現代物流業的發展，車輛路徑規劃在物流配送領域的作用日趨明顯，設計合理的配送方案，提高配送效率，降低配送成本，已成為物流企業競爭的核心。車輛路徑問題（VRP）[1]，即在配送區域范圍內，所有配送車輛都從配送中心出發，在滿足一定的約束條件（如車輛的最大容載量、貨物需求量、行駛里程約束、時間限制等）的情況下，選擇合適的配送路線來實現特定的目標（如總行駛距離最短、時間最短、使用車輛數目最少、總體費用最低等）。目前，VRP已廣泛應用于軍事物流配送、快遞投放與取件、垃圾回收和牛奶配送等行業。

隨著現代商業的發展，許多大型貨運公司在區域范圍內建立了多個配送中心，因此多車場車輛路徑問題就顯得非常重要。多車場車輛路徑問題（MDVRP）是單車場VRP的一個拓展，VRP屬于完全NP問題，因此MDVRP也屬于NP問題。解決MDVRP主要有3種方法：傳統方式、整體法和啟發式優化法[2-4]。傳統方法是首先將多車場問題轉換為單車場問題，再按照單配送問題進行處理，常用的轉化方法有中垂線分區法、圓域分區法和客戶聚類法等；整體法主要是通過虛擬配送中心的方式來實現多配送中心問題，首先設置虛擬配送中心，再從虛擬配送中心出發，選擇車場后完成配送任務[5]；啟發式優化法主要是采用智能優化方法處理多車場問題，常見的優化算法有遺傳算法、蟻群算法、模擬退火算法和混合算法等[6]。傳統方法求解MDVRP時，在一定程度上降低了問題的復雜性，但失去了問題的整體性；整體法求解時，注重問題的整體性，但忽略了單一車輛的優化；啟發式優化算法通過構造的方式對MDVRP進行求解，注重了單一車輛，忽視了問題的整體性[7-9]。本文擬采用啟發式優化算法和整體法求解基于時間窗的VRP，不僅考慮了VRP的整體性，還兼顧了單一車輛的優化。

1 問題描述及數學建模

基于時間窗的MDVRP（圖1）可描述為：配送區域內有M個車場，每個車場具有運載能力為Q的車輛Km（m=1,2,…,M）輛，配送區域有N個客戶，每個客戶的需求量為qi(i=1,2,…,N)，且對于任意客戶i都有需求量qi

圖1 多配送中心問題

客戶編號為0,1,2,…,N；車場編號為N+1,N+2,…, N+M。為建模方便，定義兩個變量：

基于時間窗的MDVRP數學模型為：

其中，式（3）表示配送完所有客戶點所花費的費用最低，包括車輛啟用的固定成本、運行過程中的油料消耗和由于時間延誤造成的懲罰費用；式（4）表示車輛的容量限制，即一輛車所配送客戶的總需求不能超過車輛的最大容載量；式（5）表示每個車場完成配送任務使用的車輛數目不超過該車場車輛總數；式（6）表示一個客戶點的任務只能對應一個車場中的一輛車；式（7）、（8）表示每個客戶只能被來自同一車場的同一輛車服務，其他車場的車輛不能對該客戶進行服務；式（9）表示所有配送車輛從配送中心出發，完成配送任務后再返回配送中心；式（10）表示車輛不能從一個車場達到另一個車場；式（11）表示客戶的時間窗約束，即在規定時間內，客戶需求得到滿足，否則車輛將增加一定的懲罰成本。

2 多車場問題的解決方法分析

在當前物流配送中對車輛調度問題的研究主要集中在配送規模較大、范圍廣、客戶數量多的多配送中心模式，且在實踐中發現一般規模較大的物流企業都采用多配送中心車輛調度模式，因此研究多配送中心車輛調度問題具有重要的現實意義[10]。目前解決多配送中心車輛調度問題主要采用傳統方法、整體法和啟發式優化法。

2.1 分區法求解VRP

傳統方法是將多配送中心車輛調度問題看作是多個單配送中心車輛調度問題的組合，先將其分離再進行優化[11]。傳統方法的研究重點在于如何將多配送中心車輛調度問題拆分成多個單配送中心車輛調度問題，然后在全局的基礎上對其解進行優化。拆分過程中主要按照距離最近或劃分邊界的原則確定各配送點與配送中心的對應關系；實際應用中一般以配送中心的總配送路程最短優先，因此選取距離最近原則來劃分客戶。傳統方法的求解方式有圓域分區法、中垂線分區法和最近鄰域法（圖2）。傳統方法具有一定的可行性，但在拆分過程中失去了問題的整體性，僅在各配送中心范圍內取得費用最少，很難在整體上取得最優解。

圖2 分區法解決多配送中心車輛調度問題

2.2 整體法求解VRP

與傳統方法的思路相反，整體法在解決多配送中心車輛調度問題時將配送過程看作一個整體，首先設置虛擬的配送中心，然后使所有配送車輛從虛擬配送中心出發，到達實際配送中心后，按照就近原則選擇要服務的客戶點，完成配送任務后，返回實際配送中心[12]。整體法從全局角度考慮了問題的最優解，但是在解決時間窗的多配送中心車輛調度問題時，距離最近并不意味整體消耗最少，配送點的選擇不僅要考慮配送點之間的距離，而且要考慮配送點的時間窗要求（圖3）。

2.3 啟發式優化法求解VRP

啟發式優化法的思想是把多配送中心車輛調度問題看作是復雜的多個問題的組合，在此基礎上進行優化研究[13]。與傳統方法和整體法不同，啟發式優化法是通過一系列方法來簡化求解計算過程，以降低求解搜索的復雜程度。常用的啟發式優化算法有遺傳算法、蟻群算法、模擬退火算法、禁忌搜索算法和人工神經網絡算法等。啟發式優化算法在求解VRP時，首先對路徑進行編碼，再通過不斷更新節點的順序獲取VRP的最優解。它具有較好的收斂性，求解質量高，但過分關注求解每一輛車的最優路徑，忽視了問題的整體性（圖4）。

圖3 整體法解決多配送中心車輛調度問題

圖4 啟發式優化方法求解多配送中心車輛調度問題

3 混合算法設計

啟發式優化算法在解決單車場問題時具有較好的收斂性，整體法在求解多車場問題時具有較好的全局性。鑒于此，首先設置虛擬配送中心將多配送中心車輛調度問題轉化為單車場VRP，然后采用啟發式優化算法求解單車場VRP，最后為每個配送點選擇車場?；旌纤惴鞒倘鐖D5所示。

混合算法的一般步驟為：

1）參數設置，主要包括選擇自適應的交叉率和變異率，蟻群信息素的總量、螞蟻個數以及α、β；

2）確定染色體編碼方式和適應度函數的計算方式；

3）對所有節點進行染色體編碼，并計算染色體的適應度值，選擇父代中較好的一部分染色體遺傳到下一代，子代進行自適應的交叉和變異過程，并產生新的染色體；

4）計算新染色體適應度值，并根據適應度值進行折半排序；

5）計算相鄰兩代染色體適應度值的平均值，并計算相鄰兩代染色體的進化率，若相鄰兩代染色體的進化率不超過3%或超過遺傳算法中設置的最大迭代次數，則將該組染色體的適應度值轉化成蟻群算法中初始狀態下的信息素濃度，否則重新進行選擇、交叉和變異操作；

6）將所有螞蟻隨機放置在任意一個頂點，螞蟻根據狀態轉移規則選擇下一個待訪問的節點，當螞蟻選擇完所有節點后，形成多條訪問路徑；

圖5 混合算法設計流程圖

7）計算當前所有路徑適應度值，并標記適應度值最好的螞蟻；

8）更新當前最優路徑上的信息素濃度，然后更新所有路徑上的信息素濃度；

9）判斷當前迭代次數與最大迭代次數的關系，若當前迭代次數小于蟻群算法的最大迭代次數，則將每只螞蟻重新放置在各節點處，按照狀態轉移規則重新訪問所有節點，否則停止蟻群算法，得到當前一組最優路徑；

10）對于當前每一條路徑，采用2-opt算法進行路徑優化，得到一組基于虛擬配送中心的車輛路徑，再對所有路徑進行排序；

11）計算每輛車到實際配送中心的消耗，再將虛擬配送中心轉換成實際配送中心，總消耗最小的轉換結果即為當前最優的配送方案。

4 案例分析

為了驗證混合算法的有效性，實驗采用標準的MDVRPTW問題進行實驗驗證。實驗環境為Inter酷睿i5，內存8 G，操作系統為Windows10，編程語言為C++，開發環境為VS2010。

標準的MDVRPTW問題是：有3個配送中心A、B、C，每個配送中心貨物充足，有15個配送點，每個客戶點具有一定的需求量，也有一定的時間窗限制，具體的車輛路徑實驗數據如表1、2所示[14]。

為了驗證算法的有效性，實驗分別采用MDVRP的傳統方法（中垂線法）、整體法、啟發式優化算法以及本文設計的混合算法對多車場的時間窗問題進行求解。實驗中設定車輛的單位油耗為8，車輛的啟動成本為60，配送過程早到所產生的等待成本為0.5，晚到所產生的懲罰成本為1.5，測試結果如表3所示。

表1 客戶點的實驗數據

表2 配送中心的實驗數據

表3 測試結果統計

由表3可知，分區法、整體法和啟發式優化算法在求解帶時間窗的MDVRP時，分區法的效果最差，整體法次之，啟發式優化算法最好，而混合算法比啟發式優化算法的平均費用降低了85個單位。因此，采用混合算法可降低帶時間窗的MDVRP的費用。

5 結 語

本文針對基于時間窗的MDVRP建立了配送方案的最小費用模型，分析了分區法、整體法和啟發式優化算法在解決MDVRP時的優劣；并結合整體法和啟發式優化算法，進行了混合算法的設計，最后通過實驗驗證了混合算法在解決帶時間窗的MDVRP的有效性。

[1] 楊從平.基于蟻群算法的快遞物流配送路徑優化[J].物流工程與管理,2014(4)：65-67

[2] 姚婷婷.車輛調度有及其遺傳算法[D].蘭州：西北師范大學,2013：2-3

[3] 鄒彤,李寧,孫德寶,等.多車場車輛路徑問題的遺傳算法[J].計算機工程與應用,2004(21)：82-83

[4] 楊元峰.多車場多車型車輛路徑問題的改進遺傳算法[J].計算機與現代化,2008(9)：10-13

[5] 鐘石泉,賀國光.多車場有時間窗的多車型車輛調度及其禁忌算法研究[J].運籌學學報,2005(4)：67-73

[6] 李小花.多車場帶容量限制弧路徑規劃問題研究[D].重慶：重慶大學,2009：23-25

[7] 戴樹貴,陳文蘭,潘蔭榮,等.多配送中心車輛路徑安排問題混合蟻群算法[J].四川大學學報(工程科學版),2008(6)：154-158 [8] 孫世權.多配送中心車輛路徑優化問題的研究[D].西安：西安電子科技大學,2012：3-4

[9] 汪平.多生產點煙草企業的原材料運輸車輛路徑問題研究[D].武漢：華中科技大學,2010：12-14

[10] 高志剛.多車輛配送路徑分析及與GIS平臺的集成技術研究[D].武漢：武漢理工大學,2005：10-11

[11] 王詩瑤,王文發,富文軍,等.大規模單車場VRP問題中掃描法的改進[J].現代電子技術,2014(24)：34-36

[12] 高特,李莉,鐘蓮,等.烏魯木齊市社區蔬菜直銷統一配送路徑優化[J].物流技術,2014(11)：168-170

[13] 張立峰,趙方庚,孫江生,等.戰時備件配送的MDVRP問題及其遺傳算法求解[J].計算機應用與軟件,2010(2)：194-196 [14] 鐘石泉.物流配送車輛調度智能優化方法研究[D].天津：天津大學,2004：3-5

P208

B

1672-4623（2017）05-0035-04

10.3969/j.issn.1672-4623.2017.0051.1

閆凱，碩士研究生，主要研究方向為運籌地理信息系統。

2016-10-31。

項目來源：國家自然科學基金資助項目（7130939）。