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

趙吉祥，姚興貴，孟初夏

（安徽農(nóng)業(yè)大學(xué) 工學(xué)院，安徽 合肥 230036）

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

1 合理優(yōu)化路線模型的建立與求解

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

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

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

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

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

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

通過Matlab編程模擬退火算法，根據(jù)各種限制條件求得各個區(qū)域的最優(yōu)配送路線.

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

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

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

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

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

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

3 模型的評價與推廣

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

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