帶時(shí)間窗的多車型車輛路徑問題研究

陳 磊

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州730070）

車 輛 路 徑 問 題 （Vehicle Routing Problem，VRP）已被證明是NP難題，帶時(shí)間窗的車輛路徑問題（Vehicle Routing Problem with Time Windows，VRPTW）由于增加了時(shí)間約束，使得問題在求解中變得更加復(fù)雜，VRP為組合優(yōu)化問題，本文選用的配送車輛為多車型，這使得問題的解呈幾何型增長(zhǎng)，當(dāng)配送點(diǎn)的數(shù)目增大時(shí)，采用精確算法很難求得問題的精確解。因此用啟發(fā)式算法在一定的時(shí)間內(nèi)求得問題的滿意解已成為研究的主要方向。

Dorigo等人首先提出了蟻群算法，它是一種新的種群?jiǎn)l(fā)式算法，利用一群人工螞蟻的協(xié)同工作來進(jìn)行尋優(yōu)，每只螞蟻都遵循一定的規(guī)則隨機(jī)選擇下一個(gè)節(jié)點(diǎn)，并在到達(dá)下一節(jié)點(diǎn)后釋放一定量的信息素，從而對(duì)下一只螞蟻起到引導(dǎo)作用，最后螞蟻將會(huì)傾向于選擇路程最短的路徑。其具有很強(qiáng)的魯棒性，是解決組合優(yōu)化問題的有效手段，該思想已被應(yīng)用到各個(gè)研究領(lǐng)域，并取得了大量的研究成果，而在VRPTW方面的研究則較少，本文在蟻群系統(tǒng)的基礎(chǔ)上，將螞蟻周期算法與最大最小螞蟻系統(tǒng)（MMAS）相結(jié)合，在尋找最優(yōu)解的過程中采用信息素動(dòng)態(tài)揮發(fā)策略；在對(duì)下一個(gè)客戶的選擇中，考慮了時(shí)間窗跨度及服務(wù)等待時(shí)間等因素，使問題的解更接近實(shí)際情況；通過轉(zhuǎn)移狀態(tài)規(guī)則求得可行節(jié)點(diǎn)的概率后，為避免算法陷入局部最優(yōu)，采用輪盤選擇來確定下一點(diǎn)；在求得問題可行解后，為了在不丟失最優(yōu)解的情況下，更快地產(chǎn)生最優(yōu)解，采用路徑內(nèi)的2－opt及路徑間的2－opt＊優(yōu)化策略。最后，經(jīng)過一系列的實(shí)驗(yàn)測(cè)試驗(yàn)證了改進(jìn)的蟻群算法對(duì)VRPTW的適用性及算法的有效性。

1 問題描述與模型建立

VRPTW的一般定義為:某一配送中心，負(fù)責(zé)向n個(gè)客戶點(diǎn)送貨，每個(gè)客戶點(diǎn)i的需求量qi及位置（通常用坐標(biāo)表示）已知，配送中心派k輛貨車進(jìn)行送貨；要求貨車必須在其時(shí)間窗內(nèi)為其進(jìn)行服務(wù)，如果配送車輛提前到達(dá)，也必須等待，直到時(shí)間窗開始為止；每輛貨車載重量一定，每條線路上客戶點(diǎn)的需求量之和不超過貨車車載重量；每輛貨車的最大行駛距離一定，每條線路的總長(zhǎng)度不能超過貨車的最大行駛距離；每個(gè)客戶的需求必須且只能由一輛貨車來提供，目標(biāo)是使配送的總成本（配送路徑總長(zhǎng)度和配送車輛數(shù)）最小。則該問題的數(shù)學(xué)模型可寫為

式（1）表示費(fèi)用和所需車輛數(shù)最少的目標(biāo)函數(shù)；式（2）表示車輛k運(yùn)送線路的貨物總量不超過車的最大載重量Qk；式（3）表示每輛車從配送中心出發(fā)完成配送任務(wù)必須回到配送中心；式（4）表示車輛在服務(wù)完客戶i后直接為客戶j服務(wù)；式（5）表示車輛在服務(wù)j之前只服務(wù)一個(gè)客戶i；式（6）指每個(gè)客戶i的需求只能由一輛車來滿足；式（7）是避免配送過程中產(chǎn)生循環(huán)子回路；，為決策變量，當(dāng)車輛k從點(diǎn)i駛向點(diǎn)j時(shí)，＝1，否則＝0，當(dāng)客戶i由的需求由車輛k來完成時(shí)，＝1，否則＝0；式（8）可根據(jù)時(shí)間窗約束的嚴(yán)格與否分為硬時(shí)間窗約束和軟時(shí)間窗約束，本文針對(duì)軟時(shí)間窗約束展開研究。

2 改進(jìn)的蟻群算法

MMAS對(duì)AS的關(guān)鍵改進(jìn)在于將路徑上的信息素濃度限定在 ［τmin，τ］max間，較好地避免了搜索陷入局部最優(yōu)。由于在搜索過程中，隨著信息素的揮發(fā)和累計(jì)，某些路徑上的信息素濃度會(huì)遠(yuǎn)高于其他路徑，從而導(dǎo)致了搜索的過早停滯。

2.1 可行路徑的構(gòu)造

在滿足容量、路程、時(shí)間窗等約束條件下，螞蟻在選擇下一個(gè)節(jié)點(diǎn)時(shí)，需要考慮以下三方面因素:

1）通往下個(gè)客戶點(diǎn)的路徑長(zhǎng)度以及當(dāng)前路徑上的信息量；

2）客戶時(shí)間窗約束因素，由下個(gè)客戶j的時(shí)間窗寬度和所在客戶i到達(dá)客戶j的時(shí)間長(zhǎng)度等因素決定；選擇的原則為需要等待時(shí)間較短和時(shí)間窗寬度較小時(shí)優(yōu)先選擇；

3）基于 Wissner－Gross，A.D.的事物傾向于向自由度較大的方向進(jìn)化的理論，傾向于選擇下一可行節(jié)點(diǎn)數(shù)多的節(jié)點(diǎn)。

令τij為信息素濃度為能見度；dij為顧客i，j之間距離；α為信息啟發(fā)因子；β為期望啟發(fā)因子；γ為時(shí)間窗跨度的相對(duì)重要性；δ為等待時(shí)間的影響因子；waitj為開始服務(wù)j需要的等待時(shí)間，等待時(shí)間短的顧客j被選中的概率較大；ETj為顧客j的最最早開始時(shí)間，LTj為顧客j的最遲開始時(shí)間，則顧客j的時(shí)間窗跨度為widthj＝LTj－ETj，根據(jù)因素（2）在等待時(shí)間相同的條件下，優(yōu)先選擇時(shí)間窗跨度較小的節(jié)點(diǎn)，時(shí)間窗跨度表示了客戶的服務(wù)緊迫性。

狀態(tài)轉(zhuǎn)移概率表示螞蟻k從i點(diǎn)移動(dòng)到j(luò)點(diǎn)的概率，轉(zhuǎn)移規(guī)則為

式中:為車輛k從i點(diǎn)出發(fā)可訪問的所有j（滿足容量及時(shí)間窗約束且未被訪問過的顧客）的集合；r為在 ［0，1］上服從均勻分布的隨機(jī)變量；r0（0≤r0≤1）為用來控制轉(zhuǎn)移規(guī)則的參數(shù)；當(dāng)r≤r0時(shí)，算法采用確定性搜索，此時(shí)螞蟻以概率r0選擇距離較短的路徑；當(dāng)r＞r0時(shí)，算法采用探索性搜索，此時(shí)螞蟻以概率1－r0隨機(jī)選擇路徑。為了加快構(gòu)造初始解，在算法迭代的初期r0選取較大的初始值，以較大的概率進(jìn)行確定性搜索；在算法的中期r0選取較小的值，增大探索性搜索的概率，這樣可以擴(kuò)大搜索空間，有效防止算法停滯，陷入局部最優(yōu)解，在算法的后期恢復(fù)r0的初始值，加快算法收斂速度。

2.2 算法步驟

Step1:初始化。置迭代步數(shù)nc＝0，初始化各個(gè)參數(shù)，讀取客戶數(shù)據(jù)，將所有螞蟻放在配送中心；

Step2:令一螞蟻從配送中心出發(fā)，讓每只螞蟻按轉(zhuǎn)移規(guī)則（11）選擇下一訪問點(diǎn)j，同時(shí)更新禁忌表，將新的客戶點(diǎn)加入到該“螞蟻”的禁忌表中；

Step3:判斷禁忌表的狀況，如果還有未訪問的顧客點(diǎn)，轉(zhuǎn)Step2，否則表示第k只螞蟻完成迭代，執(zhí)行Step4；

Step4:計(jì)算并保存禁忌表中第k只螞蟻所經(jīng)過的客戶節(jié)點(diǎn)和總路徑長(zhǎng)度len（k）；

Step5:更新信息素，并將信息素限定在 ［τmin，τmax］，增加螞蟻搜索路徑的隨機(jī)性。

Step6:計(jì)算m只螞蟻中所經(jīng)過的路徑長(zhǎng)度并計(jì)算出最短路徑，采用路徑內(nèi)的2－opt及路徑間的2－opt＊優(yōu)化策略，找出當(dāng)前最優(yōu)解；

Step7:若nc≤max＿nc，則nc＝nc＋1，清空記錄表，轉(zhuǎn)Step2，否則，流程結(jié)束。

3 實(shí)驗(yàn)結(jié)果與分析

選用需求點(diǎn)為25個(gè)的數(shù)據(jù)集，其中配送中心的編號(hào)為0，坐標(biāo)為（35km，35km），其他客戶屬性如表1所示。

表1 客戶需求信息表

本文采用MATLAB7.8.0對(duì)模型進(jìn)行求解，試驗(yàn)中客戶數(shù)是螞蟻數(shù)的1.5倍，信息啟發(fā)因子α＝1，期望啟發(fā)因子β＝2，γ＝1.5，δ＝2，信息素殘留因子ρ＝0.9，迭代次數(shù)nc＝1 000，配送貨物的貨車類型有三種，其載重容量分別為6t，7t，8t，對(duì)應(yīng)的行駛速度分別為45km／h，40km／h，35km／h，最大行駛距離為150km，180km，200km。對(duì)于同一數(shù)據(jù)集，分別選用不同的車輛類型對(duì)此問題進(jìn)行求解，結(jié)果如表2所示。

表2 實(shí)驗(yàn)結(jié)果

從表2可以看出，對(duì)于同一數(shù)據(jù)集，隨著車輛載重量的增加，配送車輛數(shù)逐漸減少，由于每輛配送車在完成配送任務(wù)后，均要回到配送中心，從而總路徑長(zhǎng)度也會(huì)相應(yīng)縮短，但考慮到大容量車輛的大能耗，反而會(huì)增加配送成本，最后選取一個(gè)折中的派送方案——混合車型，從表2可以看出，在配送車輛數(shù)不變的情況小，可以得到一個(gè)滿意解，在實(shí)際的配送任務(wù)中，考慮到小車型的快捷性、低能耗及人們對(duì)配送的及時(shí)性要求越來越高，多車型組合的配送方案將在很大程度上提高服務(wù)質(zhì)量，降低配送成本。

為了更清楚地表示出運(yùn)行結(jié)果，圖1、圖2、圖3分別為車型為6t和混合車型的運(yùn)行結(jié)果路徑圖和進(jìn)化圖。

圖1 車型為6t和混合車型配送方案

圖2 車型為6t進(jìn)化

圖3 混合車型進(jìn)化

從圖2和圖3的程序進(jìn)化圖可以看出，當(dāng)車型為6t時(shí)，在算法迭代到100次時(shí)算法已趨于收斂，表明本文提供的算法能快速準(zhǔn)確地求出帶時(shí)間窗約束的車輛路徑問題的最優(yōu)解，而對(duì)于混合車型，在算法迭代到300次時(shí)求得的最優(yōu)解仍有波動(dòng)，這是因?yàn)樵诖_定配送方案時(shí)還需要考慮車型對(duì)目標(biāo)的影響，增加了算法復(fù)雜度，這也驗(yàn)證了在時(shí)間窗約束的基礎(chǔ)上增加多車型這一約束時(shí)算法將會(huì)變得更加復(fù)雜。

4 結(jié)束語

本文針對(duì)多車型的帶軟時(shí)間窗約束的車輛路徑問題展開研究，以配送車輛總行駛距離和車輛數(shù)最小化為優(yōu)化目標(biāo)，建立了該問題的數(shù)學(xué)模型，并設(shè)計(jì)了改進(jìn)的最大最小蟻群算法對(duì)該數(shù)學(xué)模型進(jìn)行求解。最后結(jié)合算例實(shí)驗(yàn)基于多車型的帶軟時(shí)間窗的車輛路徑進(jìn)行驗(yàn)證，結(jié)果顯示可以有效減少配送成本，證實(shí)了算法的有效性和選用多車型方案的科學(xué)性。

［1］ Mester D，Br?ysy O.Active guided evolution strategies for large－scale vehicle routing problems with time windows［J］.Computers ＆ Operations Research，2005，32（6）:1593－1614.

［2］ 王建玲，齊紫茜，何璐.基于蟻群算法的車輛調(diào)度問題［J］.交通科技與經(jīng)濟(jì)，2014，16（6）:37－39.

［3］ M D，V M，A C.Ant System:Optimization By A Colony Of Cooperating Agents［J］.IEEE Trans Syst Man Cybern B Cybern，1996，26（1）:29－41.

［4］ Demirel N，Duran Toksar? M.Optimization of the quadratic assignment problem using an ant colony algorithm［J］.Applied Mathematics ＆ Computation，2006，183（1）:427－435.

［5］ Ellabib I，Calamai P，Basir O.Exchange strategies for multiple ant colony system ［C］.／／Information Sciences，2007:1248－1264.

［6］ Stützle T，Hoos H.Improvements on the Ant－System:Introducing the MAX－MIN Ant System［J］.Artificial Neural Nets ＆ Genetic Algorithms，1997.

［7］ 萬旭，林健良，楊曉偉.改進(jìn)的最大－最小螞蟻算法在有時(shí)間窗車輛路徑問題中的應(yīng)用［J］.計(jì)算機(jī)集成制造系統(tǒng)，2005，11（4）:572－576.

［8］ AD W，CE.F.Causal Entropic Forces［J］.Physical Review Letters，2013，110（16）:1－5.