求解CVRP問題的改進和聲算法

顏騰威，王麗俠，周 杰，王基一

(1.浙江師范大學數(shù)理與信息工程學院，浙江金華 321004; 2.浙江師范大學行知學院，浙江金華 321004)

求解CVRP問題的改進和聲算法

顏騰威1，王麗俠2，周 杰1，王基一1

(1.浙江師范大學數(shù)理與信息工程學院，浙江金華 321004; 2.浙江師范大學行知學院，浙江金華 321004)

車輛路徑問題是典型的NP難解問題，大多用啟發(fā)式算法求解。和聲搜索算法是一種新穎的啟發(fā)式算法，最近幾年得到了迅速發(fā)展，但是新提出的和聲算法在求解車輛路徑問題方面研究并不充分。針對現(xiàn)有的和聲算法在求解車輛路徑問題(CVRP)效率上的不足，提出了面向CVRP問題的改進的和聲算法，對帶有容量限制的CVRP，提出了一種改進的和聲搜索算法。該算法采用自然數(shù)編碼，在新和聲的生成過程中，對和聲音調(diào)的生成策略進行了改進，增加了和聲約束，避免了不可行解的生成，并利用2-opt算子對新的和聲進行了優(yōu)化，從而壓縮了搜索空間，提高了搜索效率。實驗結果表明，算法的效率優(yōu)于現(xiàn)有的CVRP求解算法。

車輛路徑優(yōu)化問題;容量約束的車輛路徑問題;和聲算法;組合優(yōu)化

0 引言

車輛路徑優(yōu)化問題(Vehicle Routing Problem，VRP)是著名的組合優(yōu)化問題，該問題的解決具有重要的理論和應用價值，廣泛存在于交通運輸、物流分發(fā)等領域。VRP問題可以描述為:一定數(shù)量的客戶，各自有不同數(shù)量的物流需求，配送中心根據(jù)客戶需求，規(guī)劃車隊行車路線，在滿足一定約束的條件下，達到諸如路程最短、成本最低、耗費時間最少等目標。VRP問題最初由Dantzig和Ramser于1959年提出［1］，經(jīng)過幾十年的發(fā)展，出現(xiàn)了許多分支，包括:帶時間窗車輛路徑問題、多配送中心車輛路徑問題、容量限制車輛路徑問題、基于站點的車輛路徑問題、開放式車輛路徑問題、同時取送貨車輛路徑問題等。其中，容量約束車輛路徑問題(Capacitated Vehicle Routing Problem，CVRP)具有更多的普適性，得到了學術界的廣泛關注［2］，并提出了許多求解算法。這些算法大體可分為三類［3］，即精確算法、啟發(fā)式算法和元啟發(fā)式算法。精確算法能求得最優(yōu)解，但CVRP是一個NP-Hard問題［4］，當問題規(guī)模增大到一定程度時，精確算法就無能為力了。因此，啟發(fā)式和元啟發(fā)式算法的研究更有意義。近年來涌現(xiàn)的一些智能算法，如遺傳算法［5］、禁忌搜索［6］、模擬退火［7］、蟻群算法［8］、粒子群算法［9］以及這些算法的混合算法，均被用來求解CVRP問題并取得了良好的效果。

和聲搜索(Harmony Search，HS)算法是由Geem［10］等提出的一種基于群體進化的元啟發(fā)式算法。HS算法模擬了音樂演奏的過程［11］，為了達到更好的和聲狀態(tài)，演奏中樂手們需要不斷調(diào)整各個樂器的音調(diào)，這是一個優(yōu)化過程。在生成一個新解時，和聲搜索會考慮和聲庫中的所有和聲，因此搜索的空間大。研究表明，利用經(jīng)典的和聲搜索算法求解CVRP問題可以得到更優(yōu)的解，然而其收斂速度較慢［12］。分析發(fā)現(xiàn)，經(jīng)典的和聲搜索算法的和聲庫中，存在大量的不可能是解的非法和聲。

因此，針對CVRP問題，文中提出了高效的改進和聲搜索算法—和聲約束和優(yōu)化的和聲搜索(Constraint -Optimization Harmony Search，CO-HS)算法。

(1)在生成和聲時，通過增加和聲編碼約束，避免了不可行解的和聲的生成，壓縮了搜索空間。

(2)對每個新生成的和聲，采用2-opt算子，優(yōu)化了和聲，加快了搜索速度。

1 CVRP問題的形式化描述

CVRP問題是指為滿足一些特定位置的客戶需求，調(diào)度一定數(shù)量的車輛，從中心倉庫出發(fā)，選擇最優(yōu)的行車路線，使車輛有序地訪問每個客戶點，在滿足特定的約束條件(如客戶的需求、車輛的載重限制)下，使得貨物最快到達客戶點并使運輸費用最低。CVRP問題具有以下特點:

(1)所有配送車輛從配送中心出發(fā)，最后回到配送中心;

(2)每個客戶只被一輛車服務，每輛車只能走一條路線;

(3)每條運輸線路上，客戶總需求量不能超過車輛載重總和;

(4)車輛不能有重復的行駛路線。

為描述方便，引入以下符號:

D:所有車輛的總路徑長度;

cij=從客戶i到j的費用;

gi=第i個客戶的需求(i=1，2，…，n);

n=客戶總數(shù);

k=車輛總數(shù);

qs=第s輛車的容量;

s=車輛編號(1，2，…，k)。

令配送中心為編號為0號的節(jié)點，客戶編號為i(i =1，2，…，n)。基于以上符號，CVRP問題可以形式化為:

目標函數(shù):

其中，式(2)、(3)確保到達客戶的車必須離開該客戶;式(4)表示每條配送路線上的總客戶需求量不大于車輛的運載能力;式(5)則確保每個客戶只被一輛車服務，而發(fā)貨點則有k輛車經(jīng)過。

2 經(jīng)典的和聲搜索(HS)算法

經(jīng)典和聲搜索算法的基本過程是一個迭代過程:首先初始化生成和聲記憶庫;然后基于某種策略產(chǎn)生一個新和聲;計算新和聲的適應度，并基于更新策略更新和聲記憶庫;迭代這個過程，直到產(chǎn)生一個滿足條件的和聲為止。

HS算法中，一個解對應一個和聲，和聲的分量對應一個樂器的音調(diào)，即一個和聲由若干個音調(diào)組成。文中用p表示一個和聲，pd為和聲p的第d個音調(diào)，HM為和聲記憶庫，為和聲記憶庫中第r個和聲的第d個音調(diào)。

HS算法需要迭代地產(chǎn)生新的和聲，產(chǎn)生一個新和聲，就要生成該和聲的所有音調(diào)，音調(diào)生成規(guī)則如下:

(1)選自和聲記憶庫。

其中，d∈ {1 ，2，…，D}，D是和聲向量維度，r為隨機從和聲記憶庫中選擇的和聲編號。

(2)音調(diào)調(diào)整。

其中，d∈ {1 ，2，…，D};φ是一個符合均勻分布的隨機數(shù)，范圍為［-1，1］;bw表示一個適當?shù)恼{(diào)整距離。

(3)隨機選擇。

其中，ubd和lbd是音調(diào)d的上界和下界;r為［0，1］之間的隨機數(shù)。

和聲生成方式可以通過和聲庫取值概率(HMCR)和音調(diào)調(diào)整概率(PAR)兩個參數(shù)來確定。HS算法的步驟如下:

算法1:HS算法。

輸入:Max_Iterations，HMCR，PAR，bw;

輸出:最優(yōu)解和聲。

步驟:

1:初始化和聲記憶庫HM

2:評價和聲庫中的解

3:Iter_number=1

4:while Iter_number≤Max_iterations do

5:for each dimension d do

6:if U(0，1)≤HMCR then

7:隨機選擇和聲庫中的音調(diào)

8:else if U(0，1)≤PAR then

9:按式(7)調(diào)整選自和聲庫的音調(diào)

10:else

11:按式(8)隨機選擇音調(diào)

12:end for

13:評價生成的新和聲

14:if新和聲比和聲記憶庫中最差的解更好then

15:用新和聲代替和聲庫中最差解

16:Iter_number=Iter_number+1

17:end while

18:return best harmony

設和聲維度為n，迭代次數(shù)為d，則易知經(jīng)典和聲算法的時間復雜度為O(n*d)。

3 求解CVRP的改進和聲算法—CO－HS算法

3.1 和聲的編碼與和聲庫的初始化

CO-HS算法的和聲庫中每個和聲采用自然數(shù)編碼，一個和聲對應n(1～n)個自然數(shù)的一個不重復排列(n為客戶個數(shù))，即所有客戶編號的排列對應1種配送方案。該配送方案依據(jù)客戶編號排列次序安排車輛，即按照客戶的編碼順序依次將其納入1條車輛路徑中，直到超過該車的最大裝載量限制，再依次安排第2輛車的路徑。例如，配送中心有3輛車，載重都是4噸，客戶有8個，需求分別為2，1，1，1，2，2，1，1。則一個可行的配送方案是1，2，3，4，5，6，7，8，第一輛車的路徑是0-1-2-3-0;第二輛車的路徑是0-4-5-0;第三輛車的路徑是0-6-7-8-0。

配送路徑總長度可以用來評估該方案的優(yōu)劣，HS算法采用配送路徑總長度來度量和聲的適應度。

初始化和聲庫首先要確定和聲庫大小—HMS，然后隨機生成HMS個和聲向量(n個數(shù)的不同排列)放入和聲庫，初始化和聲庫為:

3.2 音調(diào)約束域

為提高CVRP的搜索效率，CO-HS算法在和聲生成上增加了面向問題的約束，以壓縮搜索空間。設CVRP問題有n個客戶，即和聲維度為n，則可行解的和聲應滿足:

約束1:和聲每個音調(diào)取值范圍為1，2，…，n;

約束2:若和聲已生成i個音調(diào)，即Xnew=(，，…，)，i＜n，則i+1個音調(diào)的取值應滿足:not in Xnew=(，…)。

引入了音調(diào)約束域的概念。

定義1(音調(diào)約束域):在生成和聲的音調(diào)過程中，將滿足約束1和約束2的音調(diào)所有可選值構成的集合定義為該音調(diào)的音調(diào)約束域，用Xrc表示。

若和聲已生成i個音調(diào)，即Xnew=(，x，…，)，i＜n，則i+1個音調(diào)的音調(diào)約束域Xrc的構造算法為:

算法2:音調(diào)約束域Xrc的構造算法。

步驟:

1:Initial Xrc=?，range=滿足約束1的所有音調(diào)

2:for each d in range do

3:if d not in Xnewthen

4:Xrc.append(d)

5:end if

6:end for

7:return Xrc

設和聲為n維向量，則音調(diào)約束域Xrc的構造算法的復雜度為O(n)。

3.3 改進的和聲音調(diào)生成策略

在3.2的基礎上，改進了和聲的3種生成策略:

1)選自和聲記憶庫。

生成第i+1個音調(diào)的步驟:

2)音調(diào)調(diào)整。

(2)生成Xrc;

(4)end if。

3)隨機選擇。

CO-HS算法將音調(diào)隨機選擇算法修改為:

(1)range=(1，2，…，n);

(2)按算法2生成Xrc;

3.4 基于2－opt算法的和聲優(yōu)化

為了加快算法的收斂速度，CO-HS在每次生成一個新的和聲時，首先對其進行優(yōu)化，然后再開始和聲算法迭代。優(yōu)化采用2-opt算子［13］，假設i和j是當前解中同一路徑上的互不相鄰的兩個客戶，i*和j*分別是i和j在路徑中的直接后繼節(jié)點。2-opt是指刪去弧(i，i*)、(j，j*)，添加弧(i，j)、(j*，i*)，從而得到一條更優(yōu)的路徑。

3.5 CO－HS算法步驟

CO-HS算法對經(jīng)典的和聲算法進行了兩點改進:首先在新和聲生成時，添加了約束，避免了不可行解的生成;其次，基于2-opt算子對新生成的和聲進行了優(yōu)化，提高了算法速度。算法描述如下:

步驟1:初始化和聲算法(包括參數(shù)和記憶庫);

步驟2:采用改進算法產(chǎn)生一個符合約束的和聲;

步驟3:對新和聲進行2-opt算子的優(yōu)化;

步驟4:計算新和聲適應度，并基于更新策略，更新和聲記憶庫;

步驟5:檢查是否滿足停止條件，若不滿足，轉(zhuǎn)2;

步驟6:輸出和聲記憶庫中的當前最優(yōu)解。

設客戶個數(shù)為n，迭代次數(shù)為d，則算法的復雜度與HS算法類似，也為O(n*d)。

4 實驗結果與分析

將提出的CO-HS算法與現(xiàn)有的CVRP問題的求解算法進行比較分析。實驗環(huán)境:InDel(R)Core (DM)i3-2120 CPU@3.30 GHz;3 GB內(nèi)存;Windows 7操作系統(tǒng)，Eclipse+pydev，解釋器版本:pypy3-2.4.0。CO-HS算法的參數(shù)設置:和聲記憶庫大小=20;HMCR =0.9;PAR=0.25。每類算法運行20次，迭代次數(shù)為50。

實驗數(shù)據(jù)選用很多研究工作中都采用的一個小規(guī)模數(shù)據(jù)，包括了8個顧客和2輛車，每輛車容量為8，客戶需求數(shù)據(jù)見表1。

CO-HS算法運行20次的結果如下:67.5，67.5，67. 5，68，67.5，67.5，67.5，67.5，68，67.5，67.5，67.5，67.5，67.5，68，67.5，68.5，68，67.5，67.5。與現(xiàn)有算法的比較見表2。

從表2可以看出，所提出的CO-HS算法在求解CVRP問題時，從最大值、最小值、平均值以及得到最優(yōu)解的次數(shù)上，都優(yōu)于現(xiàn)有算法。

文中同時對VRPLIB的5個標準測試數(shù)據(jù)進行了測試，實驗結果見表3。

從表3可以看出，所提出的CO-HS算法獲得的最優(yōu)解比傳統(tǒng)遺傳算法和粒子群算法更優(yōu)。

5 結束語

CVRP問題在實際生活中有許多應用，如收集和運送貨物、校車路線、街道清潔、垃圾收集等。文中研究了和聲算法，提出了CO-HS算法。實驗結果表明，提出算法在效率上優(yōu)于現(xiàn)有的CVRP算法。

［1］ Dantzig G B，Ramser J H.The truck dispatching problem［J］. Management Science，1959，6(1):80-91.

［2］ Montoya-Torres J，Alfonso-Lizarazo E，F(xiàn)ranco E，et al.Using randomization to solve the deterministic single and multiple vehicle routing problem with service time constraints［C］// Proc of winter simulation conference.［s.l.］:［s.n.］，2009: 2989-2994.

［3］ Toth P，Vigo D.An overview of vehicle routing problem［M］. Philadelphia:Society for Industrial and Applied Mathematics，2002.

［4］ En A，BülbüL K.Survey on multi trip vehicle routing problem ［C］//Proc of international logistics and supply chain congress.Istanbul，Turkiye:［s.n.］，2008.

［5］ Baker B M，Ayechew M A.A genetic algorithm for the vehicle routing problem［J］.Computers＆Operations Research，2003，30:787-800.

［6］ Semet F，Taillard E D.Solving real-life vehicle routing problems efficiently using taboo search［J］.Annals of Operations Research，1993，41:469-488.

［7］ Osman I H.Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem［J］.Annals of Operations Research，1993，41:421-451.

［8］ Yu B，Yang Z Z，Yao B.An improved ant colony optimization for vehicle routing problem［J］.European Journal of Operational Research，2009，196:171-176.

［9］ Chen A L，Yang G K，Wu Z M.Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem ［J］.Journal of Zhejiang University SCIENCE A，2006，7(4): 607-614.

［10］Geem Z，Kim J，et al.A N new heuristic optimization algorithm:harmony search［J］.Simulation，2001，76(2):60-68.

［11］Lee K S，Geem Z W.A new meta-heuristic algorithm for continuous engineering optimization:harmony search theory and practice［J］.Computer Methods in Applied Mechanics and Engineering，2005，194:3902-3933.

［12］王 華.改進和聲搜索算法在車輛路徑問題中的應用研究［D］.阜新:遼寧工程技術大學，2011.

［13］姜昌華，戴樹貴，胡幼華.求解車輛路徑問題的混合遺傳算法［J］.計算機集成制造系統(tǒng)，2007，13(10):2047-2052.

［14］Jiang Dali，Yang Xilong，Du Wen.A study on the genetic algorithm for vehicle routing problem［J］.System Engineering Theory＆Practice，1999，19(6):44-46.

［15］Zhao Yanwei，Wu Bin，Jiang Li，et al.Double populations genetic algorithm for vehicle routing problem［J］.Computer Integrated Manufacturing Systems，2004，10(3):303-306.

［16］肖健梅，李軍軍，王錫淮.求解車輛路徑問題的改進微粒群優(yōu)化算法［J］.計算機集成制造系統(tǒng)，2005，11(4):577-581.

［17］Wang Z，Zhou M，Li J，et al.Research in capacitated vehicle routing problem based on modified hybrid particle swarm optimization［C］//Proc of IEEE international conference on intelligent computing and intelligent systems.Shanghai，China: IEEE，2009:289-293.

［18］Kou M，Ye C，Chen Z.A bee evolutionary particle swarm optimization algorithm for vehicle routing problem［C］//Proc of 2011 6th IEEE joint international information technology and artificial intelligence conference.Chongqing，China:IEEE，2011:398-401.

［19］鄭建茹.粒子群算法改進及在車輛路徑中問題的應用［D］.北京:華北電力大學，2013.

［20］ Wu Bin，Wang Wanliang，Zhao Yanwei，et al.A novel real number encoding method of particle swarm optimization for vehicle routing problem［C］//Proc of sixth world congress on intelligent control and automation.Piscataway，NJ，USA:［s. n.］，2006:3271-3275.

An Improved Harmony Search Algorithm for CVRP

YAN Teng-wei1，WANG Li-xia2，ZHOU Jie1，WANG Ji-yi1
(1.College of Mathematics Physics and Information Engineering，Zhejiang Normal University，Jinhua 321004，China; 2.Xingzhi College of Zhejiang Normal University，Jinhua 321004，China)

Vehicle routing problem is a typical NP-hard problem，mostly solved by a heuristic algorithm.Harmony search algorithm，as a novel heuristic algorithm，has been developing rapidly in recent years.However，the research on vehicle routing problem by the harmony search algorithm is not sufficient.The existing harmony search algorithms for CVRP have some defects on efficiency.To address the problem，an improved harmony search algorithm is proposed，which uses natural number coding.It adds constraints to new harmonies to avoid generating invalid solutions，and optimizes new harmonies by 2-opt algorithm，so that it can compress the search solution space and improve the efficiency.Compared with several improved GA，PSO，experiments show that the proposed algorithm outperforms the existing algorithms on efficiency.

vehicle routing problem;capacitated vehicle routing problem;harmony search algorithm;combinatorial optimization

TP31

A

1673-629X(2016)09-0187-05

10.3969/j.issn.1673-629X.2016.09.042

2015-02-27

2015-08-13< class="emphasis_bold">網(wǎng)絡出版時間:

時間:2016-08-23

國家自然科學基金資助項目(61170108，61402418);教育部人文社科研究項目(12YJCZH142);浙江省自然科學基金(LQ13F020007)

顏騰威(1989-)，男，碩士研究生，研究方向為智能計算;王麗俠，副教授，研究方向為智能計算。

http://www.cnki.net/kcms/detail/61.1450.tp.20160823.1112.006.html