趙吉祥，姚興貴，孟初夏

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

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

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

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

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

在兩種不同配送車型情況下，容量為qv的車輛，現(xiàn)有L項(xiàng)貨物運(yùn)輸任務(wù)，以1，2，…，l56表示，已知任務(wù)i的貨運(yùn)量為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個(gè)區(qū)域，通過軟件求解對(duì)156個(gè)點(diǎn)進(jìn)行聚類劃分，得六個(gè)區(qū)域所包含的客戶點(diǎn)分布.

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

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

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

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

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

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

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

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

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

3 模型的評(píng)價(jià)與推廣

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

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