陳 亮，周晶晶

(蚌埠汽車士官學(xué)校 運(yùn)輸勤務(wù)系，安徽 蚌埠233011)

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

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

1 改進(jìn)的蟻群算法

1.1 CVRP 的描述

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

1.2 路徑的構(gòu)造

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

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

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

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

式中:下標(biāo)0 為倉(cāng)庫(kù);g和f為參數(shù)。

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

1.3 信息素的更新

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

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

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

(2)全局更新。當(dāng)所有螞蟻?zhàn)咄耆砍鞘泻?，僅對(duì)最優(yōu)路徑上的信息素進(jìn)行更新。更新規(guī)則為

1.4 局部的搜索

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

1.5 基于DT 的候選列表

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

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

讀入城市坐標(biāo);輸出最優(yōu)路徑及長(zhǎng)度。

2 實(shí)驗(yàn)比較

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

2.1 參數(shù)設(shè)置

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

2.2 實(shí)驗(yàn)結(jié)果

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

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

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

3 結(jié) 論

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

［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］.計(jì)算機(jī)工程與應(yīng)用，2011，47(32):246-248.

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

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

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

［7］ 王超學(xué).遺傳算法和蟻群算法及其在TSP 問題和配電網(wǎng)重構(gòu)問題中的應(yīng)用研究［D］.西安:西安理工大學(xué)，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］ 陳亮，李暢. 一種基于知識(shí)的快速求解TSP 的蟻群算法［J］. 軍事交通學(xué)院學(xué)報(bào)，2013，15(3):78-81.