蟻群算法在通勤班車路徑優化中的應用

□文/薛雨石

（北京科技大學 北京）

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

黨中央提出京津冀協同發展、有序疏解北京非首都功能背景下，北京市一批優質的教育資源正在通過整體搬遷、辦分校、聯合辦學等多種方式向雄安新區布局發展。研究如何打造一個宜業宜居的新城市、新校區，吸引人才向新區集聚，為人才提供完善的生活配套措施和便利的公共交通條件，打造快捷、便利、綠色、安全的出行環境十分具有理論價值和實際意義。本文通過蟻群算法這一智能算法優化，以通勤班車的路徑優化與停靠車站的定位布局為研究對象，求解出多目標非線性整數規劃模型的最優解，為智慧宜居提供可靠的決策依據。

一、容量受限的車輛路徑問題描述

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

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

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

CVRP可建立如下模型：

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

二、蟻群算法介紹

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

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

（二）人工螞蟻與真實螞蟻的相同點。通過對真實螞蟻行為的觀察，將蟻群覓食行為中最關鍵的部分賦予人工螞蟻：真實螞蟻可以在沒有任何提示的情況下找到從食物源到巢穴的最短路徑，并且能在原有路徑上出現障礙物后，自動搜索新的最佳路徑。

1、人工螞蟻和真實螞蟻都可以改變當前的環境：真實螞蟻在經過的路徑上留下信息素，人工螞蟻則會改變所經路徑上存儲的數字信息。這一機制就是控制論中正反饋概念的應用，即以現在的行為去強化未來的行為。通過這種正反饋，螞蟻個體可以通過相互協作在全局范圍內找出最優解決方案。雖然每只螞蟻都能夠建立一個解決方案，但是高質量的解決方案是整個蟻群合作的結果。

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

3、人工螞蟻與真實螞蟻從一個節點移動到下一節點都是通過對信息素濃度的判斷而選擇策略，信息素濃度越高，選擇的概率越高，反之亦然。

（三）人工螞蟻與真實螞蟻的不同點。為了更有效地解決實際問題，人工螞蟻具有真實螞蟻所不具備的本領：（1）人工螞蟻的選擇策略與時間無關。（2）人工螞蟻的每次移動會改變路徑記錄表，以記錄當前的移動坐標。（3）人工螞蟻不是完全盲從的，每次迭代會產生一只最優螞蟻，對信息素濃度矩陣進行加強，以便下一次迭代解的優化。

三、蟻群算法求解步驟

（一）確定螞蟻的下一個訪問點。為了把求解步驟描述清楚，先給出一個簡化的算例：假設有三個停靠車站，每個車站預計分別會有10位、20位、30位乘客上車，每輛車最多可以承載30人，從新校區0點發車，接完全部乘客后再回到0點。新校區與三個車站的坐標如表1，位置圖如圖1所示。（表1、圖1）

圖1 新校區與三個車站的位置圖

表1 新校區與三個車站的坐標一覽表

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

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

螞蟻1在返回新校區后還有車站3未訪問，任務并未完成，因此螞蟻1還需要構建第二條行走路線，路徑集合點表達式為［0，3，0］，螞蟻1的任務執行完畢。

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

（三）更新信息素濃度矩陣。假設最大迭代次數設置為100次，每次迭代有50只螞蟻構建路徑方案。當50只螞蟻遍歷完所有的城市，就完成了一次循環。為了避免殘留的信息素過多，淹沒了啟發信息，降低了啟發函數的作用，因此規定實現完整路徑距離TD最短的螞蟻為本次迭代下的最優螞蟻，它將在其經過的每條路徑上留下信息素。最優螞蟻會對信息素濃度矩陣進行修改，公式如下：

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

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

因為有起始點新校區0和3個遍歷點車站，信息素濃度矩陣是一個4×4的矩陣，且矩陣上的初始值τij均為1。根據式（10）、式（11）、完整路徑方案［2，1，3］，需要修改信息素濃度的點分別為 τ02、τ21、τ13、τ30，得出信息素濃度矩陣為：

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

圖2 蟻群算法求解CVRP問題流程圖

四、實證分析

為了更好地接近現實中的通勤班車路徑優化問題，本文在新校區半徑15公里的通勤圈內隨機選取了20個停靠車站，每輛車都要從新校區出發，最后帶著乘客返回新校區，最優路徑要求每個車站只能被1輛車訪問。為了滿足每車載荷上限60人的約束條件，需要事先統計好各站點擬上車的人數，具體如表2所示。算法在MATLAB 2014B上編譯執行，初始設置50只螞蟻和50次迭代計算。（表2）

表2 發車起始點、車站坐標位置與各站點擬上車人數一覽表

如果沒有計算機輔助執行智能優化算法，完成50只螞蟻、50次迭代的信息素濃度矩陣更新、轉移概率等計算，僅依靠人工幾乎不可能實現，通過計算機執行結果如圖3所示。（圖3）

圖3 蟻群算法求解班車最優路徑線路圖

在可接受的計算時間內，用6輛班車完成了350人次的接送任務，行駛最短總距離215.20公里，并完美地給出了最優路徑規劃方案。行駛路線如下：

行駛路線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

綜上，蟻群算法是一項具有通用性廣、理論依據可靠、推導過程嚴謹等優點的智能優化算法，對每一次迭代的最好解都在不斷地加強進化。通過實證分析，本文構建的模型可以有效地幫助管理者科學決策，規避人類所無法避免的非理性判斷。同時，模型還支持動態調整停靠車站的位置坐標，既實現了對空間格局、功能布局的剛性約束，又實現了為需求變化提供彈性的可塑空間；既節約了班車運行成本，又最大限度地減少了職工長距離通勤，實現了打造新城市新校區宜業宜居的目標。