淺析蟻群算法在車輛調(diào)度問題中的應(yīng)用

陳夢圓 余函

摘 要：最優(yōu)解方案是在生活和工作中經(jīng)常出現(xiàn)的問題策略，其往往尋求系統(tǒng)中最高收入最低成本的設(shè)置點(diǎn)。本文以運(yùn)輸業(yè)常見的車輛調(diào)度問題作為案例場景，建立VRP模型。使用蟻群算法進(jìn)行求解，尋找到用時(shí)最短人數(shù)最少的方案。

關(guān)鍵詞：蟻群算法；車輛調(diào)度；數(shù)學(xué)建模；VRP模型

一、引言

當(dāng)今社會(huì)，快遞行業(yè)已成為人們?nèi)粘Ｉ钪须x不開的一部分，快遞行業(yè)的蓬勃發(fā)展為生活帶來了諸多便利。一般地，所有快遞到達(dá)某地后，統(tǒng)一存放在公司總部，然后安排業(yè)務(wù)員將快件一一送達(dá)。對公司而言，既希望能盡快送完當(dāng)日快件，又希望送貨費(fèi)用最省。但越多的業(yè)務(wù)員意味著成本會(huì)越高，因此需要制定合理方案，提前安排好路線，保證任務(wù)的盡快完成，又能讓業(yè)務(wù)員人數(shù)最少。

本文建立送貨線路的VRP模型和最優(yōu)人數(shù)的0-1規(guī)劃模型，使用蟻群算法進(jìn)行求解并將求解方案與現(xiàn)實(shí)方案進(jìn)行對比來說明蟻群算法在車輛調(diào)度問題中的應(yīng)用。

二、送貨線路的VRP模型

車輛調(diào)度問題VRP（Vehicle Routing Problem），可表示為：給定一個(gè)中心點(diǎn)（即公司總部）、一個(gè)車輛（即業(yè)務(wù)員）集合、一個(gè)客戶（即送貨點(diǎn)）集合，每輛 車和客戶都有自己的屬性（載重量，貨物需求量），要求所裝載的貨物不能超過車 輛的總量（即載重量）。起初所有車輛都在中心倉庫，中心倉庫和各客戶點(diǎn)的位置 坐標(biāo)及貨物需求量已知，中心倉庫派送若干車輛。每輛車都必須從起點(diǎn)出發(fā)，完成 若干客戶點(diǎn)的運(yùn)送任務(wù)再回到起點(diǎn)。[1]

先假設(shè)每個(gè)業(yè)務(wù)員只送貨一次，即只往返一趟，求得總路程最短的各個(gè)線路。業(yè)務(wù)員送貨運(yùn)行線路均為平行于坐標(biāo)軸的折線，為便于計(jì)算，先將折線化為直線，即視業(yè)務(wù)員通過任意兩個(gè)相鄰送貨點(diǎn)之間行駛的線路均為直線。

業(yè)務(wù)員從公司總部出發(fā)，到各送貨點(diǎn)送貨，最終返回總部。用點(diǎn) 0 表示總部，并命名為源點(diǎn)，點(diǎn)1，2，...，l表示m個(gè)業(yè)務(wù)員需要到達(dá)的送貨點(diǎn)。

設(shè)任意兩個(gè)送貨點(diǎn)坐標(biāo)分別為，因業(yè)務(wù)員送貨運(yùn)行線路均為平行于坐標(biāo)軸的折線，故這兩點(diǎn)間的距離為：

完成每天快件派送所需業(yè)務(wù)員的最少人數(shù)：

業(yè)務(wù)員每天送貨，既要受限于一次性的快件攜帶量，又要受限于每日工作時(shí)間上限，屬于多約束的非線性規(guī)劃問題，是組合優(yōu)化領(lǐng)域中的典型的NP難問題[2]。一般的求解方法不僅計(jì)算周期長，甚至難以得到結(jié)果，精確算法的計(jì)算量隨著問題規(guī)模的增大而大幅增長。

三、蟻群算法的實(shí)際應(yīng)用

蟻群系統(tǒng)（Ant System或Ant Colony System）是由意大利學(xué)者Dorigo、Maniezzo等人于20世紀(jì)90年代首先提出來的。他們在研究螞蟻覓食的過程中，發(fā)現(xiàn)單個(gè)螞蟻的行為比較簡單，但是蟻群整體卻可以體現(xiàn)一些智能的行為。例如蟻群可以在不同的環(huán)境下，尋找最短到達(dá)食物源的路徑。這是因?yàn)橄伻簝?nèi)的螞蟻可以通過某種信息機(jī)制實(shí)現(xiàn)信息的傳遞。后又經(jīng)進(jìn)一步研究發(fā)現(xiàn)，螞蟻會(huì)在其經(jīng)過的路徑上釋放一種可以稱之為“信息素”的物質(zhì)，蟻群內(nèi)的螞蟻對“信息素”具有感知能力，它們會(huì)沿著“信息素”濃度較高路徑行走，而每只路過的螞蟻都會(huì)在路上留下“信息素”，這就形成一種類似正反饋的機(jī)制，這樣經(jīng)過一段時(shí)間后，整個(gè)蟻群就會(huì)沿著最短路徑到達(dá)食物源了。[2]

蟻群算法的本質(zhì)是一種隨機(jī)搜索算法，是通過對候選解組成的群體的進(jìn)化來搜索全局最優(yōu)解。[3]

使用改進(jìn)的蟻群算法，能夠通過多次迭代找到總路程最短時(shí)的線路條數(shù)，并給出具體線路，不用人為劃分線路條數(shù)。

初始時(shí)刻，各條路徑上的信息素量相等：

將螞蟻隨機(jī)或均勻分布在各送貨點(diǎn)上。

禁忌表tabuk用來標(biāo)記已被訪問過的送貨點(diǎn)，保證不重復(fù)訪問。每只螞蟻通過 訪問各送貨點(diǎn)而形成一個(gè)解，在訪問過程中，將訪問記錄保存在禁忌表中。

在貨運(yùn)點(diǎn)i的每只螞蟻依據(jù)概率公式（1-16），在未訪問過的貨運(yùn)點(diǎn)中選擇下一 個(gè)要訪問的貨運(yùn)點(diǎn)j。循環(huán)進(jìn)行此步，直到訪問完所有貨運(yùn)點(diǎn)。

概率公式為：

計(jì)算每只螞蟻行走的總線路長度，并保存最優(yōu)方案。

進(jìn)行信息素調(diào)整，每只螞蟻完成對所有貨運(yùn)點(diǎn)的遍歷后，更新殘留信息素。

其中，Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度；Lk表示第K只螞蟻在本次循環(huán)中所走線路的總長度。

判斷系統(tǒng)是否滿足停止條件，不滿足則又重新安排螞蟻，再次進(jìn)行運(yùn)算，直至得到最優(yōu)策略。

基本蟻群算法的結(jié)構(gòu)流程圖：

四、總結(jié)

將蟻群算法應(yīng)用于解決優(yōu)化問題的基本思路為：用螞蟻的行走路徑表示待優(yōu)化問題的可行解，整個(gè)螞蟻群體的所有路徑構(gòu)成待優(yōu)化問題的解空間。路徑較短的螞蟻釋放的信息素量較多，隨著時(shí)間的推進(jìn)，較短的路徑上累積的信息素濃度逐漸增高，選擇該路徑的螞蟻個(gè)數(shù)也愈來愈多。最終，整個(gè)螞蟻會(huì)在正反饋的作用下集中到最佳的路徑上，此時(shí)對應(yīng)的便是待優(yōu)化問題的最優(yōu)解。[4]

社會(huì)的高速發(fā)展對時(shí)間的要求越來越嚴(yán)苛，追求高速度的同時(shí)又想要低成本，使用蟻群算法協(xié)調(diào)車輛能夠達(dá)到智能化的最優(yōu)搜索方案。

參考文獻(xiàn)

[1]宋燕子，基于模擬退火算法的啟發(fā)式算法在VRP中的應(yīng)用[D].華中師范大學(xué)，2013.1

[2]康與云，元功能鏈驅(qū)動(dòng)的機(jī)電產(chǎn)品矩陣式創(chuàng)新設(shè)計(jì)方法.山東人民出版社，2015.11

[3]于鳳青，物流配送車輛優(yōu)化調(diào)度問題研究[D].沈陽工業(yè)大學(xué)，2007：28-31

[4]郁磊、史峰、王輝、胡斐，MATLAB智能算法30個(gè)案例分析（第2版）北京航空航天大學(xué)出版社，2015.9

（作者單位：重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院）