陳 亮，周晶晶

(蚌埠汽車士官學校 運輸勤務系，安徽 蚌埠233011)

車輛路由問題(vehicle routing problem，VRP)是分布管理中的核心問題。在CVRP(capacitated VRP)中，一個中心倉庫需要給n個客戶提供服務。CVRP 的目的是找出一種運貨成本最小的路由方式，并且滿足:①每個客戶只接受1 次服務，而且只有1 輛貨車送貨給這個客戶;②每一輛貨車的運貨線路都是從貨倉出發(fā)，并且返回貨倉結束;③每一輛貨車運貨的總質量都不超過自身的質量。由于CVRP 包含了旅行商(traveling saleman problem，TSP)作為其子問題，因此CVRP 是一個NP-難問題。原因是它含有裝箱問題，目標是把客戶看作物品，把所有的客戶“裝進”一個供應線路中去。然后，對于每一條供應線路都需要求出訪問所有客戶的最短訪問路線，這又涉及解答TSP。

由于蟻群算法在求解TSP 上取得了一定的成功，許多學者也開始將蟻群算法應用到求解VRP中。Bullnheimer 等［1］提出了一種ASrank-CVRP，這種方法后來又被Reimann 等［2］進行了改進，得到算法ASrank-CVRPsav。這2 種算法均是在ASrank的基礎上，使用基于存儲啟發(fā)式方法的啟發(fā)式信息，并結合最近鄰域列表構建路徑。國內的研究學者在將蟻群算法用于求解VRP 問題上也作了許多研究，西南交通大學的李軍教授和郭耀煌教授對車輛優(yōu)化調度的基礎理論及各類問題進行了系統(tǒng)的研究。劉曉勇等［3］把城市和倉庫間的距離矩陣和路徑節(jié)約矩陣信息融入到初始信息素矩陣中，作為啟發(fā)式信息引入到蟻群算法中用于求解CVRP。萬旭等［4］提出一種基于改進MMAS 的VRP 算法，通過對最大最小信息素策略和信息素更新方式的改進，提高了有時間窗車輛路徑質量。張錦等［5］提出一種交叉變異蟻群算法，該算法利用遺傳算法對蟻群算法的參數(shù)進行優(yōu)化，然后利用優(yōu)化后的蟻群算法求解車輛路徑問題?？傮w來說，目前我國對車輛調度問題的理論研究仍相對薄弱，需要進一步研究。

1 改進的蟻群算法

1.1 CVRP 的描述

CVRP 可表描述為完全加權有向圖G=(V，A，d)，其中，V= {v0，v1，…，vn}為定點的集合，A={(vi，vj);i≠j}為邊的集合。頂點v0為倉庫，其他頂點為城市或者客戶，非負權重dij與每條邊(vi，vj)相關，代表vi和vj間的距離(或者運行時或者運行費用)。對于每一個客戶vi，都有一個非負需求qi。CVRP 的目標就是找到一條路由方式使得總運貨時間(距離)最小，并且:①每一個客戶只接受1次服務，而且只有1 輛貨車送貨給這個客戶;②每一輛貨車的運貨路線都是從貨倉出發(fā)，并以返回貨倉結束;③每一輛貨車運貨的總量都不超過自身的載質量。

1.2 路徑的構造

蟻群算法求解CVRP，關鍵在于單個螞蟻一次迭代如何構建一個可行解，即可行的路徑。在一次迭代中，螞蟻通過一定的規(guī)則，選擇下一個客戶構建路徑。同時，螞蟻在選擇下一個客戶時，還要考慮螞蟻的載貨量是否滿足客戶的需要，如果載貨量不滿足任何一個未訪問的客戶，就返回貨倉再次出發(fā)，此時螞蟻的貨物容量重新設置為Q。如此循環(huán)，直到所有客戶都被訪問，就構建了一條可行路徑。當所有的螞蟻均構建路徑后，更新信息素完成算法的一次迭代。螞蟻在選擇下一個可訪問的客戶時，受到2 個要素的影響:一個是當前客戶i到選擇客戶j邊上的信息素τij，表示螞蟻訪問完客戶i之后立刻訪問客戶j的期望度，它只與邊有關;另一個是啟發(fā)信息ηij，表示客戶i與j間的可見度。在可訪問的客戶節(jié)點集Ω ={vj∈V:vj是可訪問的客戶}∪{v0}，螞蟻k按照偽隨機比例規(guī)則［6］選擇城市j作為下一個訪問的城市，即

式中:q為均勻分布在區(qū)間［0，1］間的一個隨機變量，q0(0≤q0≤1);J為根據(jù)式(2)概率分布產生的一個隨機變量。

式中:α 為決定信息素的相對影響力參數(shù);β 為啟發(fā)信息素的相對影響力參數(shù);通過調整α、β 來決定殘留信息素和啟發(fā)信息在選擇概率的相對作用大小。對于TSP，啟發(fā)信息被定義為距離的倒數(shù)，即ηij=1/dij。

對于CVRP，啟發(fā)式信息一般是基于存儲啟發(fā)式方法［1-2］，針對CVRP 的存儲算法可簡單描述為每一對客戶(i，j)之間的存儲值，即

式中:下標0 為倉庫;g和f為參數(shù)。

本文采用文獻［2］的方法定義啟發(fā)式信息，即

1.3 信息素的更新

信息素更新有局部更新和全局更新2 種方式。

(1)局部更新。每只螞蟻從城市i移動到城市j后，就會去掉邊(i，j)上一定量的信息素，以增加探索其余路徑的可能性。更新規(guī)則為

式中:ε(0≤ε≤1)為局部信息素揮發(fā)系數(shù);τ0為信息素的初始值。

(2)全局更新。當所有螞蟻走完全部城市后，僅對最優(yōu)路徑上的信息素進行更新。更新規(guī)則為

1.4 局部的搜索

在螞蟻完成路徑構造之后，對每條路徑的每個子路徑采用GIIM 算子［7］優(yōu)化，以提高解的性能。該算子不僅能防止早熟、跳出局部最優(yōu)，而且還具有很強的鄰域搜索能力［7］。

1.5 基于DT 的候選列表

在求解TSP 中，實驗結果表明候選列表可提高ACO 算法所能獲取的解的質量，同時也會明顯加快求解速度［8］。文獻［1—2］采用最近鄰域候選列表以提高解的質量;文獻［9］研究表明，采用基于DT(delaunay triangulation)策略的候選列表較最近鄰域候選列表更優(yōu)。因此，本文采用基于DT 策略的候選列表。

綜合以上要點，得到改進的蟻群算法(IACS-CVRP)流程如下:

讀入城市坐標;輸出最優(yōu)路徑及長度。

2 實驗比較

為了驗證改進的蟻群算法(IACS-CVRP)在求解CVRP 問題上的性能，本文采用VRPLIB 的一組基準數(shù)據(jù)集，數(shù)據(jù)集分為4 類:A、B、E 和P，每類按規(guī)模小、中、大各選擇1 組數(shù)據(jù)。將IACS-CVRP 與ACS-CVRP 及文獻［1］ASrank-CVRP 進行比較。本實驗全部采用Matlab2010b 編程，運行環(huán)境為Window XP sp2、intel Core i3-2100 CPU 3.10GHZ、DDR3 1333MHZ 2GB PC。

2.1 參數(shù)設置

ASrank-CVRP 和ACS-CVRP 這2種算法的基本參數(shù)設置見文獻［1，3］。IACS-CVRP 的參數(shù)設置［6］如下:螞蟻數(shù)m為10，迭代次數(shù)T為1 000次，α、β、ε 和p分別取1、2、0.1 和0.1，偽隨機比例行為選擇規(guī)則中q0=0.9。

2.2 實驗結果

為了更科學、客觀地進行比較，實驗結果均是算法在相同環(huán)境和參數(shù)配置條件下運行20 次的平均值(見表1)。Best 為得到的最優(yōu)解路徑長度;Worst 得到的最差路徑長度;μ 和σ 分別為運行20次得到解的路徑平均長度和標準偏差;T為算法的平均收斂時間。

表1 IACS-CVRP 算法與其他算法的總體性能比較

從求得的路徑長度(見表1)來看，IACS-CVRP 比另外2 種算法在12 個數(shù)據(jù)集上獲得的最優(yōu)路徑長度、平均路徑長度和路徑長度標準差都要好，最差路徑長度與ASrank-CVRP 相當，并且算法的平均收斂時間較ASrank-CVRP 有很大提高。

3 結 論

本文利用ACS 求解TSP 的優(yōu)良特性。在ACS的基礎上，引入了基于DT 策略的候選列表，提高了構建路徑質量;同時在每次迭代中加入了GIIM算子，加強了算法的局部搜索能力。將改進的ACS 算法應用于CVRP，并與2 種蟻群算法在一組數(shù)據(jù)集上的實驗表明，IACS-CVRP 能獲得更好質量的解，并且具有較快的收斂速度。

［1］ Bullnheimer B，Hartl R F，Strauss C. An improved ant system algorithm for the Vehicle Routing Problem［J］.Annals of operations Research，1999，89:319-328.

［2］ Reimann M，Stummer M，Doerner K.A saving based Ant System for the vehicle routing problem［C］//Proceedings of the Genetic and Evolutionary Computation Conference(GECCO-2002)，2002:1317-1325.

［3］ 劉曉勇，付輝. 基于啟發(fā)式蟻群算法的VRP 問題研究［J］.計算機工程與應用，2011，47(32):246-248.

［4］ 萬旭，林健良，楊曉偉. 改進的最大-最小螞蟻算法在有時間窗車輛路徑問題中的應用［J］. 計算機集成制造系統(tǒng)，2005，11(4):572-576.

［5］ 張錦，李偉，費騰.交叉變異蟻群算法在VRP 問題中的應用研究［J］. 計算機工程與應用，2009，45(34):201-203.

［6］ Dorigo M，Stutzle T. 蟻群優(yōu)化［M］. 張軍，胡曉敏，羅旭耀，譯. 北京:清華大學出版社，2007:75-76.

［7］ 王超學.遺傳算法和蟻群算法及其在TSP 問題和配電網(wǎng)重構問題中的應用研究［D］.西安:西安理工大學，2004.

［8］ Gambardella L M，Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies［C］//Proceedings of the1996 IEEE International Conference on Evolutionary Computation(ICEC’96)，1996:622-627.

［9］ 陳亮，李暢. 一種基于知識的快速求解TSP 的蟻群算法［J］. 軍事交通學院學報，2013，15(3):78-81.