蟻群算法在通勤班車路徑優(yōu)化中的應(yīng)用

□文/薛雨石

（北京科技大學(xué) 北京）

［提要］結(jié)合北京市優(yōu)質(zhì)教育資源向雄安布局發(fā)展背景，本文提出如何規(guī)劃通勤班車的最優(yōu)路徑，使得既方便教職員工往返于新校區(qū)與宿舍之間，又能為學(xué)校節(jié)約運(yùn)行成本，把現(xiàn)實(shí)中的班車路徑優(yōu)化問(wèn)題巧妙地轉(zhuǎn)化為求解容量受限的車輛路徑問(wèn)題。最后，利用蟻群算法的優(yōu)點(diǎn)，通過(guò)螞蟻個(gè)體間的信息交流與傳遞找到最優(yōu)解，并用MATLAB程序?qū)崿F(xiàn)如下算例：新校區(qū)周圍有20個(gè)?？寇囌?，350位職工具有通勤接送需求，班車運(yùn)行線路以新校區(qū)作為線路的起點(diǎn)和終點(diǎn)，每個(gè)車站只能被訪問(wèn)一次。每輛班車的載荷上限為60人，各車站的人數(shù)和地理位置分布以數(shù)據(jù)的形式被程序調(diào)用。模型支持根據(jù)需求變化動(dòng)態(tài)調(diào)整各參數(shù)，為管理者提供可靠的決策依據(jù)。

黨中央提出京津冀協(xié)同發(fā)展、有序疏解北京非首都功能背景下，北京市一批優(yōu)質(zhì)的教育資源正在通過(guò)整體搬遷、辦分校、聯(lián)合辦學(xué)等多種方式向雄安新區(qū)布局發(fā)展。研究如何打造一個(gè)宜業(yè)宜居的新城市、新校區(qū)，吸引人才向新區(qū)集聚，為人才提供完善的生活配套措施和便利的公共交通條件，打造快捷、便利、綠色、安全的出行環(huán)境十分具有理論價(jià)值和實(shí)際意義。本文通過(guò)蟻群算法這一智能算法優(yōu)化，以通勤班車的路徑優(yōu)化與?？寇囌镜亩ㄎ徊季譃檠芯繉?duì)象，求解出多目標(biāo)非線性整數(shù)規(guī)劃模型的最優(yōu)解，為智慧宜居提供可靠的決策依據(jù)。

一、容量受限的車輛路徑問(wèn)題描述

經(jīng)典車輛路徑問(wèn)題（VRP）最早是由Dantzig和Ramser于1959年提出，它是指有若干輛車，對(duì)若干個(gè)具有貨物需求的顧客進(jìn)行配送，車輛必須從配送中心出發(fā)，完成配送任務(wù)后再回到配送中心，并且所有顧客只能被訪問(wèn)一次，不能重復(fù)，求實(shí)現(xiàn)上述問(wèn)題的最短路徑配送方案。容量受限的車輛路徑問(wèn)題比經(jīng)典VRP的多一個(gè)約束條件：每條配送路線上顧客需求總量不能超過(guò)車輛的載荷上限。

假設(shè)vi（i=1，2，…，n）表示顧客所在地，v0表示配送中心，dij表示vi到vj的距離，每個(gè)地點(diǎn)的配送需求量為qi，共有K輛車執(zhí)行配送任務(wù)，每輛車的載重量為Qk（k=1，2，…，K）。

用nk代表第k輛車配送第n個(gè)顧客所在地，nk=0表示該點(diǎn)未使用第k輛車。

CVRP可建立如下模型：

式（1）為目標(biāo)函數(shù)，求各條配送路徑距離之和的最小值；式（2）為約束函數(shù)，每條配送路徑上顧客需求總量不超過(guò)車輛的載荷上限；式（3）為約束函數(shù)，每條配送路徑上顧客點(diǎn)數(shù)不超過(guò)總站點(diǎn)數(shù)；式（4）保證每個(gè)顧客點(diǎn)都得到配送服務(wù)；式（5）表示每條配送路徑上顧客點(diǎn)的組合及排序；式（6）保證每個(gè)顧客點(diǎn)僅能被一個(gè)車輛完成配送；式（7）表示被訪問(wèn)的顧客點(diǎn)值取1，未被訪問(wèn)的點(diǎn)值取0。

二、蟻群算法介紹

蟻群算法是意大利學(xué)者M(jìn).Dorigo受到自然界中真實(shí)螞蟻集體覓食行為的啟發(fā)，于1991年首次提出的一種基于螞蟻種群的智能優(yōu)化算法。螞蟻個(gè)體之間是通過(guò)一種叫信息素的物質(zhì)進(jìn)行信息傳遞和交流的，每只螞蟻在移動(dòng)過(guò)程中都能釋放信息素，并且感知到其他螞蟻留下的信息素，以此指導(dǎo)自己的運(yùn)動(dòng)方向。某一路徑上走過(guò)的螞蟻越多，后面的螞蟻選擇該路徑的概率就越大，通過(guò)這種信息的正反饋，能夠選擇最優(yōu)的路徑實(shí)現(xiàn)搜索食物的目的。由于蟻群算法在解決組合優(yōu)化問(wèn)題中取得了滿意的實(shí)驗(yàn)結(jié)果，因此逐漸被應(yīng)用到實(shí)際工程問(wèn)題中，通過(guò)模仿生物的特性，更好地為人類服務(wù)。

（一）蟻群算法優(yōu)點(diǎn)。（1）蟻群算法通過(guò)多個(gè)個(gè)體間的合作，信息不斷地傳遞與交流，可很快收斂于解空間的某一子集，有利于發(fā)現(xiàn)較好解。（2）蟻群算法采用了正反饋原理，不易陷入局部最優(yōu)解。（3）蟻群算法易于與其他啟發(fā)式算法結(jié)合，以改善算法的性能。

（二）人工螞蟻與真實(shí)螞蟻的相同點(diǎn)。通過(guò)對(duì)真實(shí)螞蟻行為的觀察，將蟻群覓食行為中最關(guān)鍵的部分賦予人工螞蟻：真實(shí)螞蟻可以在沒(méi)有任何提示的情況下找到從食物源到巢穴的最短路徑，并且能在原有路徑上出現(xiàn)障礙物后，自動(dòng)搜索新的最佳路徑。

1、人工螞蟻和真實(shí)螞蟻都可以改變當(dāng)前的環(huán)境：真實(shí)螞蟻在經(jīng)過(guò)的路徑上留下信息素，人工螞蟻則會(huì)改變所經(jīng)路徑上存儲(chǔ)的數(shù)字信息。這一機(jī)制就是控制論中正反饋概念的應(yīng)用，即以現(xiàn)在的行為去強(qiáng)化未來(lái)的行為。通過(guò)這種正反饋，螞蟻個(gè)體可以通過(guò)相互協(xié)作在全局范圍內(nèi)找出最優(yōu)解決方案。雖然每只螞蟻都能夠建立一個(gè)解決方案，但是高質(zhì)量的解決方案是整個(gè)蟻群合作的結(jié)果。

2、人工螞蟻和真實(shí)螞蟻有著共同的任務(wù)：尋找起點(diǎn)（蟻穴）至終點(diǎn)（食物源）的最短路徑（最小代價(jià)）。真實(shí)螞蟻和人工螞蟻都不具有跳躍性，它們只能沿著相鄰節(jié)點(diǎn)一步步地移動(dòng)，直至遍歷完所有節(jié)點(diǎn)。

3、人工螞蟻與真實(shí)螞蟻從一個(gè)節(jié)點(diǎn)移動(dòng)到下一節(jié)點(diǎn)都是通過(guò)對(duì)信息素濃度的判斷而選擇策略，信息素濃度越高，選擇的概率越高，反之亦然。

（三）人工螞蟻與真實(shí)螞蟻的不同點(diǎn)。為了更有效地解決實(shí)際問(wèn)題，人工螞蟻具有真實(shí)螞蟻所不具備的本領(lǐng)：（1）人工螞蟻的選擇策略與時(shí)間無(wú)關(guān)。（2）人工螞蟻的每次移動(dòng)會(huì)改變路徑記錄表，以記錄當(dāng)前的移動(dòng)坐標(biāo)。（3）人工螞蟻不是完全盲從的，每次迭代會(huì)產(chǎn)生一只最優(yōu)螞蟻，對(duì)信息素濃度矩陣進(jìn)行加強(qiáng)，以便下一次迭代解的優(yōu)化。

三、蟻群算法求解步驟

（一）確定螞蟻的下一個(gè)訪問(wèn)點(diǎn)。為了把求解步驟描述清楚，先給出一個(gè)簡(jiǎn)化的算例：假設(shè)有三個(gè)?？寇囌?，每個(gè)車站預(yù)計(jì)分別會(huì)有10位、20位、30位乘客上車，每輛車最多可以承載30人，從新校區(qū)0點(diǎn)發(fā)車，接完全部乘客后再回到0點(diǎn)。新校區(qū)與三個(gè)車站的坐標(biāo)如表1，位置圖如圖1所示。（表1、圖1）

圖1 新校區(qū)與三個(gè)車站的位置圖

表1 新校區(qū)與三個(gè)車站的坐標(biāo)一覽表

根據(jù)式（7）、式（8）得出，螞蟻1從新校區(qū)到車站1、2、3的概率分別為：

（二）構(gòu)建螞蟻行走路線。根據(jù)公式計(jì)算出的概率構(gòu)建輪盤賭轉(zhuǎn)盤，概率越大面積越大，被選中的可能性越高。假設(shè)螞蟻1從新校區(qū)出發(fā)，初次選中車站2，按照規(guī)則車站2的20位乘客全部上車，把車站2添加進(jìn)路徑集合的表達(dá)式為［0，2］。接下來(lái)螞蟻1從車站2選擇下一個(gè)車站，需要考慮每輛車有30人的最大承載量，車站3因有30位乘客而不滿足約束條件，螞蟻1只能選擇路徑至車站1，車站1的10位乘客全部上車，符合約束條件，最后返回新校區(qū)，此時(shí)螞蟻1的第一條行走路線上的路徑集合點(diǎn)表達(dá)式為［0，2，1，0］。

螞蟻1在返回新校區(qū)后還有車站3未訪問(wèn)，任務(wù)并未完成，因此螞蟻1還需要構(gòu)建第二條行走路線，路徑集合點(diǎn)表達(dá)式為［0，3，0］，螞蟻1的任務(wù)執(zhí)行完畢。

螞蟻1構(gòu)建完成了一個(gè)完整的路徑方案，里面包括若干條行走路線內(nèi)所有的車站都已完成一次遍歷，有幾條行走路線就代表要派出幾輛車完成通勤任務(wù)。上述完整路徑方案為［2，1，3］，根據(jù)該方案更新信息素濃度矩陣。

（三）更新信息素濃度矩陣。假設(shè)最大迭代次數(shù)設(shè)置為100次，每次迭代有50只螞蟻構(gòu)建路徑方案。當(dāng)50只螞蟻遍歷完所有的城市，就完成了一次循環(huán)。為了避免殘留的信息素過(guò)多，淹沒(méi)了啟發(fā)信息，降低了啟發(fā)函數(shù)的作用，因此規(guī)定實(shí)現(xiàn)完整路徑距離TD最短的螞蟻為本次迭代下的最優(yōu)螞蟻，它將在其經(jīng)過(guò)的每條路徑上留下信息素。最優(yōu)螞蟻會(huì)對(duì)信息素濃度矩陣進(jìn)行修改，公式如下：

其中，ρ為信息素的揮發(fā)因子，1-ρ就表示信息素?fù)]發(fā)后的殘留系數(shù)。為了避免找到一個(gè)局部最優(yōu)解而不再向全局最優(yōu)的方向做進(jìn)一步搜索，因此有必要在蟻群算法中設(shè)計(jì)一種揮發(fā)機(jī)制，類似于真實(shí)信息素的揮發(fā)。這種機(jī)制可以使螞蟻逐漸忘記過(guò)去，不會(huì)受到以前經(jīng)驗(yàn)的過(guò)分約束，從而指引螞蟻向著新方向進(jìn)行搜索，避免過(guò)早收斂。Q為螞蟻構(gòu)建一次完整路徑所釋放的信息素總量，Q值越大，算法的收斂速度越快。TD為計(jì)算值，代表螞蟻構(gòu)建一次完整路徑所行駛的總距離。

本文初始假設(shè)ρ=0.2，Q=5，第一次迭代的最優(yōu)螞蟻TD=12+10＝22。

因?yàn)橛衅鹗键c(diǎn)新校區(qū)0和3個(gè)遍歷點(diǎn)車站，信息素濃度矩陣是一個(gè)4×4的矩陣，且矩陣上的初始值τij均為1。根據(jù)式（10）、式（11）、完整路徑方案［2，1，3］，需要修改信息素濃度的點(diǎn)分別為 τ02、τ21、τ13、τ30，得出信息素濃度矩陣為：

蟻群算法求解CVRP問(wèn)題的流程如圖2所示。（圖2）

圖2 蟻群算法求解CVRP問(wèn)題流程圖

四、實(shí)證分析

為了更好地接近現(xiàn)實(shí)中的通勤班車路徑優(yōu)化問(wèn)題，本文在新校區(qū)半徑15公里的通勤圈內(nèi)隨機(jī)選取了20個(gè)?？寇囌荆枯v車都要從新校區(qū)出發(fā)，最后帶著乘客返回新校區(qū)，最優(yōu)路徑要求每個(gè)車站只能被1輛車訪問(wèn)。為了滿足每車載荷上限60人的約束條件，需要事先統(tǒng)計(jì)好各站點(diǎn)擬上車的人數(shù)，具體如表2所示。算法在MATLAB 2014B上編譯執(zhí)行，初始設(shè)置50只螞蟻和50次迭代計(jì)算。（表2）

表2 發(fā)車起始點(diǎn)、車站坐標(biāo)位置與各站點(diǎn)擬上車人數(shù)一覽表

如果沒(méi)有計(jì)算機(jī)輔助執(zhí)行智能優(yōu)化算法，完成50只螞蟻、50次迭代的信息素濃度矩陣更新、轉(zhuǎn)移概率等計(jì)算，僅依靠人工幾乎不可能實(shí)現(xiàn)，通過(guò)計(jì)算機(jī)執(zhí)行結(jié)果如圖3所示。（圖3）

圖3 蟻群算法求解班車最優(yōu)路徑線路圖

在可接受的計(jì)算時(shí)間內(nèi)，用6輛班車完成了350人次的接送任務(wù)，行駛最短總距離215.20公里，并完美地給出了最優(yōu)路徑規(guī)劃方案。行駛路線如下：

行駛路線1：0→13→17→19→0

行駛路線2：0→15→18→0

行駛路線3：0→16→14→12→0

行駛路線4：0→5→1→2→4→0

行駛路線5：0→3→7→6→9→0

行駛路線6：0→8→11→10→20→0

綜上，蟻群算法是一項(xiàng)具有通用性廣、理論依據(jù)可靠、推導(dǎo)過(guò)程嚴(yán)謹(jǐn)?shù)葍?yōu)點(diǎn)的智能優(yōu)化算法，對(duì)每一次迭代的最好解都在不斷地加強(qiáng)進(jìn)化。通過(guò)實(shí)證分析，本文構(gòu)建的模型可以有效地幫助管理者科學(xué)決策，規(guī)避人類所無(wú)法避免的非理性判斷。同時(shí)，模型還支持動(dòng)態(tài)調(diào)整?？寇囌镜奈恢米鴺?biāo)，既實(shí)現(xiàn)了對(duì)空間格局、功能布局的剛性約束，又實(shí)現(xiàn)了為需求變化提供彈性的可塑空間；既節(jié)約了班車運(yùn)行成本，又最大限度地減少了職工長(zhǎng)距離通勤，實(shí)現(xiàn)了打造新城市新校區(qū)宜業(yè)宜居的目標(biāo)。