基于上海地區貨物配送帶時間窗VRP問題研究

趙吉祥，姚興貴，孟初夏

（安徽農業大學 工學院，安徽 合肥 230036）

某輪胎供應商負責上海地區貨物的運輸安排，需要在一天之內按訂單要求的配送量和運送時間送到客戶手中.綜合考慮客戶訂單數量，具體位置、運送時間和配送量以及時間窗等限制條件進行合理地求解貨物配送方案.

1 合理優化路線模型的建立與求解

所有156個客戶點的位置坐標，每兩個客戶點之間的距離包括任意一點到倉庫的距離，每個客戶點的訂單數及收貨時間，配送車輛載重及工作時間等數據均為已知.156個客戶點數據相對較大，而且較為分散，如果采用直接對其分析最優路線較難實現，所以考慮需要先將整個區域劃分為幾個小的區域，然后再對分出的小區域進行逐一優化內部線路，得出一個完整的配送方案.

首先應用k-means聚類分析[1]對客戶點進行聚類劃分，將大規模的VRPTW問題簡化成小規模的VRPTW問題，然后再對每一個小的VRPTW問題結合貨車的承載能力對其內部建立優化方案，使用模擬退火算法對各個小區域進行優化，通過MATLAB編程，有效地實現了對區域內路徑的自動尋優，建立了一套合理的優化配送模型.

在兩種不同配送車型情況下，容量為qv的車輛，現有L項貨物運輸任務，以1，2，…，l56表示，已知任務i的貨運量為pi（i=1，…，l），且0≤pi≤qv,qmax為最大車型容量，qmin為最小車型容量，m為所需的車輛數.由于事先難以確定用車的數量，所以用下列公式得出用車的大概范圍[5]:

然后在算法中取合適的可能值，結合題目中數據最大容量為150，最小容量為75，所有客戶總的需求量為642，算出用車的大概范圍為6≤m≤9.首先取m=6,即將整體區域劃分為6個區域，通過軟件求解對156個點進行聚類劃分，得六個區域所包含的客戶點分布.

對所有點進行聚類劃分之后使用模擬退火算法對各個區域進行內部優化.本篇文章在林郁丞、李軍、郎茂祥、張潛等[1-4]研究的基礎上，充分考慮問題的約束條件和優化目標，建立以下所述目標函數：

其中v表示第v輛車，N表示總的送貨量，Pv表示第v輛車的載重量，Gv表示由車輛v服務客戶的集合，Si表示車輛在客戶的服務時間,tij表示車輛從客戶i到客戶j所花費的時間，Tvo表示車輛v的開始工作時間,Tkv表示車輛v的結束工作時間,下同.

通過Matlab編程模擬退火算法，根據各種限制條件求得各個區域的最優配送路線.

2 考慮交通影響的合理配送路線模型的建立與求解

現實運輸中需要考慮到實際交通情況，有可能會出現擁堵現象，導致問題一天中在理想情況下得出的優化路線并不能滿足實際情況下的配送要求.

通過從百度地圖上查找的上海市交通路線圖及不同時段的交通通行能力可知，上海市在一天中的堵車高峰時間一般在早晨8-9點.考慮道路擁擠程度對配送的影響，引入交通工程學中的道路阻抗系數λij[1]進而建立了帶時間窗車輛問題的數學模型，應用兩階段啟發式算法求解.

首先，仍采用模型一的算法，先確定使用汽車的數量范圍，使用（公式1.1）進行計算，在算法中取合適的可能值.結合題目中數據最大容量的為150，最小容量為75，所有客戶總的需求量為642，算出用車的大概范圍為6≤m≤9.仍先取m=6，即6輛車，通過軟件求解對156個點進行聚類劃分，得6個區域.考慮道路擁擠程度對配送的影響，引入交通工程學中的道路阻抗系數[1]

其中，qij表示單位時間內路段實際可通過的車輛數；α、β為阻滯系數，其中α、β的取值分別為α=0.15，β=4[1].對所有點進行聚類劃分之后使用模擬退火算法對各個區域進行內部優化,建立目標函數如下所示：

通過MATLAB編程模擬退火算法，綜合時間窗，汽車載重及配送線路距離要求求得各個區域的最優路線，得到合理配送方案結果.

3 模型的評價與推廣

對于通過公式求得的車輛數的使用范圍，本篇文章均取m的最小值，因為從客戶點的分布情況來看，存在一部分較分散的點，這些點之間的距離較大，而使用k-means算法以距離為依據對其進行聚類劃分時即使增加劃分的區域也不可避免距離較大的點劃分為一類的數目仍然較少，所以首先取最少的車輛即劃分區域，然后對局部總載重量超過汽車容量及一輛車無法按照客戶要求時間送到的區域，進行適當的增派車輛.

由于k-means算法的眾多局限性，可以考慮將它與全局搜索法結合起來用于聚類分析中.對于模擬退火算法，可以在基本算法的基礎上與其他算法結合，以便對問題求解更加便捷、準確.