基于蟻群算法的多車型物流車輛調(diào)度研究

段麗妮，闞龍營(yíng) DUAN Lini,KAN Longying

（沈陽(yáng)化工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，遼寧 沈陽(yáng) 110000）

0 引 言

車輛路徑問(wèn)題（VRP）由Dantzig和Ramser于1959年首次提出，它是指一家配送企業(yè)向一定數(shù)量的客戶進(jìn)行貨物配送，各客戶擁有不同的貨物需求，由配送中心指派車隊(duì)進(jìn)行貨物配送，組織合適的配送路線，使客戶的需求可以得到滿足，在一定的約束下，可以達(dá)到配送成本最小、配送時(shí)間最短等目標(biāo)。目前，車輛路徑規(guī)劃問(wèn)題不斷發(fā)展，在考慮實(shí)際情況下增加約束滿足目標(biāo)，求解此類問(wèn)題的方法也在不斷改進(jìn)創(chuàng)新。

對(duì)于車輛路徑規(guī)劃問(wèn)題的研究，劉虹慶和王世民在強(qiáng)化學(xué)習(xí)的基礎(chǔ)上分別對(duì)小規(guī)模和大規(guī)模的VRP問(wèn)題進(jìn)行研究，小規(guī)模問(wèn)題應(yīng)用了時(shí)間差分模型，大規(guī)模問(wèn)題應(yīng)用蒙特卡洛模型，為車輛路徑問(wèn)題的研究提出了新思路；鄧友均和穆云飛等考慮了電動(dòng)汽車在配送中的換電成本、車輛損耗成本和慢速放電成本構(gòu)建基于客戶滿意度的多目標(biāo)模型，并應(yīng)用非支配排序遺傳算法驗(yàn)證了模型有效性；姚佼和邵楚薇等建立上層為考慮應(yīng)急救援車輛的調(diào)度費(fèi)用成本和下層考慮救援車輛在途時(shí)間的雙層規(guī)劃模型，降低了調(diào)度成本和行程時(shí)間；胡林和周登輝等提出改進(jìn)的A*算法，在信號(hào)燈轉(zhuǎn)換概率和電動(dòng)汽車的能耗模型基礎(chǔ)上，使得電動(dòng)汽車在起止點(diǎn)通過(guò)的路徑能耗最優(yōu)；李得成和陳彥如等研究了電動(dòng)車和燃油車的混合車輛路徑規(guī)劃問(wèn)題，在獲得初始解之后設(shè)計(jì)分支定界算法獲得最優(yōu)解，提出關(guān)于車輛路徑規(guī)劃相關(guān)建議；杜茂和楊林等提出了一種基于時(shí)空動(dòng)態(tài)交通信息的路徑規(guī)劃算法，在廣義回歸網(wǎng)絡(luò)和A*算法基礎(chǔ)上，可以使得規(guī)劃后的路徑耗時(shí)最短、更加節(jié)能；賀智明和鄭麗等提出一種自適應(yīng)動(dòng)態(tài)搜索蟻群算法（ADACO），并將其與AACO和ADCO以及ACO算法進(jìn)行比較，在算例仿真的結(jié)果中表明其提出的算法路徑規(guī)劃的配送成本和時(shí)間開銷都大幅度減少；羅子涵和彭曠等提出一種分層改進(jìn)A*算法來(lái)解決雨天路徑規(guī)劃問(wèn)題，減少車輛在雨天道路積水時(shí)的風(fēng)險(xiǎn)并提高行車效率；劉曉歡和張德干等利用改進(jìn)的粒子群算法對(duì)模糊神經(jīng)網(wǎng)絡(luò)的參數(shù)進(jìn)行了優(yōu)化，其提出的算法有效地解決了智能駕駛車輛路徑規(guī)劃問(wèn)題。

蟻群算法在路徑規(guī)劃中的應(yīng)用，王慶和徐海明等在傳統(tǒng)蟻群算法收斂速度慢、容易陷入局部最優(yōu)的基礎(chǔ)上進(jìn)行改進(jìn)，并將其應(yīng)用在無(wú)人機(jī)航跡規(guī)劃，算法增加了蟻群全局搜索能力和效率，更好地適應(yīng)了無(wú)人機(jī)的飛行需求；胡佳斌和王祥澍等通過(guò)差異化更新信息素并對(duì)啟發(fā)函數(shù)改進(jìn)，設(shè)計(jì)了優(yōu)化的多步長(zhǎng)蟻群算法，提高了算法的收斂速度；胡蓉和陳文博等針對(duì)城市中心擁堵情況嚴(yán)重問(wèn)題，提出一種知識(shí)模型的學(xué)習(xí)型蟻群優(yōu)化算法，算法引入了多鄰域局部搜索增強(qiáng)了搜索深度和算法性能；曹建秋和徐鵬等以蟻群算法為基礎(chǔ)，并將粒子群算法中的適應(yīng)度作為啟發(fā)值引入蟻群算法的信息素更新中，使用貪心策略優(yōu)化算法的選擇，利用A*算法進(jìn)行隨機(jī)初始化，有效地提高了算法的收斂速度和求解質(zhì)量；劉博省和毛范海等在解決生產(chǎn)規(guī)劃和排程問(wèn)題時(shí)，將蟻群算法與禁忌搜索算法進(jìn)行互補(bǔ)結(jié)合，提出蟻群禁忌搜索融合算法來(lái)解決車間調(diào)度問(wèn)題；王原和陳名等將深度學(xué)習(xí)方法應(yīng)用至蟻群算法中，使得蟻群算法可以利用深度強(qiáng)化學(xué)習(xí)提取啟發(fā)式信息，并利用經(jīng)典的TSP問(wèn)題進(jìn)行驗(yàn)證，結(jié)果表明該算法有良好地求解優(yōu)勢(shì)和穩(wěn)定性。

學(xué)者們對(duì)于物流車輛路徑優(yōu)化問(wèn)題已設(shè)計(jì)多個(gè)領(lǐng)域，包括冷鏈物流、電子商務(wù)、零售企業(yè)等，將VRP進(jìn)一步發(fā)展，建立了具有容量約束、軟硬時(shí)間窗約束或者顧客滿意度約束的模型，并使用算法進(jìn)行求解和實(shí)例仿真，為現(xiàn)實(shí)生活中的路徑優(yōu)化提供良好的思路；但是目前的研究很多是基于單一車型的研究，而在實(shí)際的生活中，通常會(huì)出現(xiàn)多車型進(jìn)行物流配送，本文考慮實(shí)際情況中的多車型問(wèn)題，研究物流車輛配送路徑優(yōu)化問(wèn)題。

1 模型建立

考慮物流運(yùn)送中的成本約束，本文僅考慮單一配送中心，并做了以下假設(shè)：

（1）只有一家物流企業(yè)提供配送服務(wù)；

（2）每個(gè)客戶被訪問(wèn)且僅訪問(wèn)一次；

（3）物流企業(yè)有多種車型車輛進(jìn)行配送，不同車型的車輛出車成本和載重量不同；

（4）不同車型車輛配送數(shù)量限制不同，組合車型和單車型車輛配送數(shù)量限制不同。

各參數(shù)與集合定義如表1所示：

表1

根據(jù)參數(shù)信息等，構(gòu)建的數(shù)學(xué)模型如下：

其中：目標(biāo)函數(shù)為總成本最小，包含了運(yùn)輸成本和出車成本兩部分；約束條件為式（1）至式（5），式（1）表示車輛的容量約束，式（2）表示車輛運(yùn)輸?shù)目倳r(shí)間約束，式（3）表示每種類型車輛數(shù)量限制，式（4）和式（5）表示每個(gè)客戶點(diǎn)僅被一種車型訪問(wèn)一次。

2 蟻群算法

車輛路徑規(guī)劃問(wèn)題屬于NP難問(wèn)題，求解此類問(wèn)題通常采用的方法有兩大類，分別是：精確算法和啟發(fā)式算法。精確算法通常是指運(yùn)用運(yùn)籌學(xué)中的線性規(guī)劃、非線性規(guī)劃等數(shù)學(xué)規(guī)劃的技術(shù)來(lái)進(jìn)行求解小規(guī)模的確定性VRP問(wèn)題，而對(duì)于較大規(guī)模的復(fù)雜問(wèn)題時(shí)，通常采用啟發(fā)式算法來(lái)進(jìn)行求解，目前應(yīng)用的啟發(fā)式算法種類有很多，本文基于蟻群算法的收斂效率和求解速度以及其不易陷入局部最優(yōu)解的特點(diǎn)，選擇蟻群算法來(lái)進(jìn)行求解。

其中：Δτ表示所有螞蟻在城市與連接路上釋放的信息素濃度總和。ρ為軌跡的持久性，1-ρ為軌跡衰減度，表示消減程度。為正常數(shù)，L為螞蟻在此次運(yùn)動(dòng)中所走路徑的長(zhǎng)度。用蟻群算法求解車輛路徑優(yōu)化問(wèn)題的算法流程如圖1所示，具體步驟的含義如下：

圖1 蟻群算法步驟

步驟1：對(duì)相關(guān)參數(shù)進(jìn)行初始化，包括螞蟻初始化群規(guī)模、信息素因子、啟發(fā)函數(shù)因子、信息素、揮發(fā)因子、信息素常數(shù)、最大迭代次數(shù)等，以及將數(shù)據(jù)讀入程序，并對(duì)數(shù)據(jù)進(jìn)行基本的處理，如將城市的坐標(biāo)位置，轉(zhuǎn)為城市間的矩陣。

步驟2：隨機(jī)將螞蟻放于固定出發(fā)點(diǎn)，對(duì)每個(gè)螞蟻計(jì)算其下一個(gè)訪問(wèn)城市，直至所更新信息素表有螞蟻訪問(wèn)完所有城市。

步驟3：計(jì)算各個(gè)螞蟻經(jīng)過(guò)路徑的花費(fèi)，記錄當(dāng)前迭代次數(shù)中的最優(yōu)解，同時(shí)對(duì)各個(gè)城市連接路徑上的信息素濃度進(jìn)行更新。

步驟4：判斷是否達(dá)到最大迭代次數(shù)，若否，則返回步驟2，否則終止程序。

步驟5：輸出程序運(yùn)行結(jié)果，并且根據(jù)需要輸出蟻群算法運(yùn)行結(jié)果，包括最優(yōu)路徑規(guī)劃和最低成本等。

3 算例仿真

某物流企業(yè)擁有多種不同類型的車輛進(jìn)行物流配送業(yè)務(wù)，該公司在一天內(nèi)的配送業(yè)務(wù)（包括物流企業(yè)及客戶的坐標(biāo)位置及客戶需求量）如表2所示，其中物流企業(yè)的標(biāo)號(hào)為0，到達(dá)客戶點(diǎn)卸貨驗(yàn)貨耗時(shí)規(guī)定為15min，車輛行駛速度為60km/h，可用車輛的載重類型為4噸、6噸、8噸，出車成本及距離成本如表3所示。

表2 物流中心、客戶坐標(biāo)點(diǎn)集合及各客戶需求量

表3 車輛類型及信息

利用Python軟件進(jìn)行模擬仿真計(jì)算，設(shè)各參數(shù)分別為：蟻群數(shù)量為100，α、β無(wú)限接近1，在仿真計(jì)算之后，得出組合車輛最優(yōu)成本為1 874.63元，具體車輛路徑如表4所示，并對(duì)單車型車輛進(jìn)行仿真計(jì)算，規(guī)定單車型4噸車輛為6輛、單車型6噸車輛為4輛、單車型8噸車輛為3輛，得出單車型車輛配送成本及路徑分別為：?jiǎn)诬囆?噸車輛配送成本2 013.12元，路徑為0-8-4-12-0、0-1-2-27-6-15-9-0、0-13-11-0、0-7-18-3-16-0、0-10-0、0-14-5-0；單車型6噸車輛配送成本2 196.21元，路徑為0-5-4-2-17-14-18-0、0-3-11-8-10-7-1-16-9-0、0-12-13-0、0-15-6-0；單車型8噸車輛配送成本2 652.96元，路徑為0-5-4-17-15-16-14-1-9-2-0、0-6-11-0、0-12-13-18-10-3-7-0。多組合車型配送成本明顯低于單車型配送成本。

表4 組合車輛路徑規(guī)劃

4 結(jié)論及意義

物流運(yùn)輸合理規(guī)劃可以使得企業(yè)降低成本、提高效率、提高顧客滿意度，從而增加企業(yè)的經(jīng)濟(jì)效益。本文通過(guò)建立多車型物流規(guī)劃配送模型，以配送成本最低為目標(biāo)，加入時(shí)間約束和車輛載重約束等，并使用蟻群算法對(duì)模型求解。求解結(jié)果表明多車型組合配送成本低于單車型配送成本且具有較大優(yōu)勢(shì)，為物流企業(yè)配送運(yùn)輸提供一定的參考價(jià)值。此外，本文的研究未考慮多車場(chǎng)及算法的組合優(yōu)化改進(jìn)，在未來(lái)可以進(jìn)一步研究。