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

陳夢圓 余函

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

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

一、引言

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

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

二、送貨線路的VRP模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

概率公式為：

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

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

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

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

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

四、總結(jié)

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

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

參考文獻(xiàn)

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

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

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

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

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