求解CVRP问题的改进和声算法

颜腾威，王丽侠，周 杰，王基一

(1.浙江师范大学数理与信息工程学院，浙江金华 321004; 2.浙江师范大学行知学院，浙江金华 321004)

求解CVRP问题的改进和声算法

颜腾威1，王丽侠2，周 杰1，王基一1

(1.浙江师范大学数理与信息工程学院，浙江金华 321004; 2.浙江师范大学行知学院，浙江金华 321004)

车辆路径问题是典型的NP难解问题，大多用启发式算法求解。和声搜索算法是一种新颖的启发式算法，最近几年得到了迅速发展，但是新提出的和声算法在求解车辆路径问题方面研究并不充分。针对现有的和声算法在求解车辆路径问题(CVRP)效率上的不足，提出了面向CVRP问题的改进的和声算法，对带有容量限制的CVRP，提出了一种改进的和声搜索算法。该算法采用自然数编码，在新和声的生成过程中，对和声音调的生成策略进行了改进，增加了和声约束，避免了不可行解的生成，并利用2-opt算子对新的和声进行了优化，从而压缩了搜索空间，提高了搜索效率。实验结果表明，算法的效率优于现有的CVRP求解算法。

车辆路径优化问题;容量约束的车辆路径问题;和声算法;组合优化

0 引言

车辆路径优化问题(Vehicle Routing Problem，VRP)是著名的组合优化问题，该问题的解决具有重要的理论和应用价值，广泛存在于交通运输、物流分发等领域。VRP问题可以描述为:一定数量的客户，各自有不同数量的物流需求，配送中心根据客户需求，规划车队行车路线，在满足一定约束的条件下，达到诸如路程最短、成本最低、耗费时间最少等目标。VRP问题最初由Dantzig和Ramser于1959年提出［1］，经过几十年的发展，出现了许多分支，包括:带时间窗车辆路径问题、多配送中心车辆路径问题、容量限制车辆路径问题、基于站点的车辆路径问题、开放式车辆路径问题、同时取送货车辆路径问题等。其中，容量约束车辆路径问题(Capacitated Vehicle Routing Problem，CVRP)具有更多的普适性，得到了学术界的广泛关注［2］，并提出了许多求解算法。这些算法大体可分为三类［3］，即精确算法、启发式算法和元启发式算法。精确算法能求得最优解，但CVRP是一个NP-Hard问题［4］，当问题规模增大到一定程度时，精确算法就无能为力了。因此，启发式和元启发式算法的研究更有意义。近年来涌现的一些智能算法，如遗传算法［5］、禁忌搜索［6］、模拟退火［7］、蚁群算法［8］、粒子群算法［9］以及这些算法的混合算法，均被用来求解CVRP问题并取得了良好的效果。

和声搜索(Harmony Search，HS)算法是由Geem［10］等提出的一种基于群体进化的元启发式算法。HS算法模拟了音乐演奏的过程［11］，为了达到更好的和声状态，演奏中乐手们需要不断调整各个乐器的音调，这是一个优化过程。在生成一个新解时，和声搜索会考虑和声库中的所有和声，因此搜索的空间大。研究表明，利用经典的和声搜索算法求解CVRP问题可以得到更优的解，然而其收敛速度较慢［12］。分析发现，经典的和声搜索算法的和声库中，存在大量的不可能是解的非法和声。

因此，针对CVRP问题，文中提出了高效的改进和声搜索算法—和声约束和优化的和声搜索(Constraint -Optimization Harmony Search，CO-HS)算法。

(1)在生成和声时，通过增加和声编码约束，避免了不可行解的和声的生成，压缩了搜索空间。

(2)对每个新生成的和声，采用2-opt算子，优化了和声，加快了搜索速度。

1 CVRP问题的形式化描述

CVRP问题是指为满足一些特定位置的客户需求，调度一定数量的车辆，从中心仓库出发，选择最优的行车路线，使车辆有序地访问每个客户点，在满足特定的约束条件(如客户的需求、车辆的载重限制)下，使得货物最快到达客户点并使运输费用最低。CVRP问题具有以下特点:

(1)所有配送车辆从配送中心出发，最后回到配送中心;

(2)每个客户只被一辆车服务，每辆车只能走一条路线;

(3)每条运输线路上，客户总需求量不能超过车辆载重总和;

(4)车辆不能有重复的行驶路线。

为描述方便，引入以下符号:

D:所有车辆的总路径长度;

cij=从客户i到j的费用;

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

n=客户总数;

k=车辆总数;

qs=第s辆车的容量;

s=车辆编号(1，2，…，k)。

令配送中心为编号为0号的节点，客户编号为i(i =1，2，…，n)。基于以上符号，CVRP问题可以形式化为:

目标函数:

其中，式(2)、(3)确保到达客户的车必须离开该客户;式(4)表示每条配送路线上的总客户需求量不大于车辆的运载能力;式(5)则确保每个客户只被一辆车服务，而发货点则有k辆车经过。

2 经典的和声搜索(HS)算法

经典和声搜索算法的基本过程是一个迭代过程:首先初始化生成和声记忆库;然后基于某种策略产生一个新和声;计算新和声的适应度，并基于更新策略更新和声记忆库;迭代这个过程，直到产生一个满足条件的和声为止。

HS算法中，一个解对应一个和声，和声的分量对应一个乐器的音调，即一个和声由若干个音调组成。文中用p表示一个和声，pd为和声p的第d个音调，HM为和声记忆库，为和声记忆库中第r个和声的第d个音调。

HS算法需要迭代地产生新的和声，产生一个新和声，就要生成该和声的所有音调，音调生成规则如下:

(1)选自和声记忆库。

其中，d∈ {1 ，2，…，D}，D是和声向量维度，r为随机从和声记忆库中选择的和声编号。

(2)音调调整。

其中，d∈ {1 ，2，…，D};φ是一个符合均匀分布的随机数，范围为［-1，1］;bw表示一个适当的调整距离。

(3)随机选择。

其中，ubd和lbd是音调d的上界和下界;r为［0，1］之间的随机数。

和声生成方式可以通过和声库取值概率(HMCR)和音调调整概率(PAR)两个参数来确定。HS算法的步骤如下:

算法1:HS算法。

输入:Max_Iterations，HMCR，PAR，bw;

输出:最优解和声。

步骤:

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:随机选择和声库中的音调

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

9:按式(7)调整选自和声库的音调

10:else

11:按式(8)随机选择音调

12:end for

13:评价生成的新和声

14:if新和声比和声记忆库中最差的解更好then

15:用新和声代替和声库中最差解

16:Iter_number=Iter_number+1

17:end while

18:return best harmony

设和声维度为n，迭代次数为d，则易知经典和声算法的时间复杂度为O(n*d)。

3 求解CVRP的改进和声算法—CO－HS算法

3.1 和声的编码与和声库的初始化

CO-HS算法的和声库中每个和声采用自然数编码，一个和声对应n(1～n)个自然数的一个不重复排列(n为客户个数)，即所有客户编号的排列对应1种配送方案。该配送方案依据客户编号排列次序安排车辆，即按照客户的编码顺序依次将其纳入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。

配送路径总长度可以用来评估该方案的优劣，HS算法采用配送路径总长度来度量和声的适应度。

初始化和声库首先要确定和声库大小—HMS，然后随机生成HMS个和声向量(n个数的不同排列)放入和声库，初始化和声库为:

3.2 音调约束域

为提高CVRP的搜索效率，CO-HS算法在和声生成上增加了面向问题的约束，以压缩搜索空间。设CVRP问题有n个客户，即和声维度为n，则可行解的和声应满足:

约束1:和声每个音调取值范围为1，2，…，n;

约束2:若和声已生成i个音调，即Xnew=(，，…，)，i＜n，则i+1个音调的取值应满足:not in Xnew=(，…)。

引入了音调约束域的概念。

定义1(音调约束域):在生成和声的音调过程中，将满足约束1和约束2的音调所有可选值构成的集合定义为该音调的音调约束域，用Xrc表示。

若和声已生成i个音调，即Xnew=(，x，…，)，i＜n，则i+1个音调的音调约束域Xrc的构造算法为:

算法2:音调约束域Xrc的构造算法。

步骤:

1:Initial Xrc=ø，range=满足约束1的所有音调

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维向量，则音调约束域Xrc的构造算法的复杂度为O(n)。

3.3 改进的和声音调生成策略

在3.2的基础上，改进了和声的3种生成策略:

1)选自和声记忆库。

生成第i+1个音调的步骤:

2)音调调整。

(2)生成Xrc;

(4)end if。

3)随机选择。

CO-HS算法将音调随机选择算法修改为:

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

(2)按算法2生成Xrc;

3.4 基于2－opt算法的和声优化

为了加快算法的收敛速度，CO-HS在每次生成一个新的和声时，首先对其进行优化，然后再开始和声算法迭代。优化采用2-opt算子［13］，假设i和j是当前解中同一路径上的互不相邻的两个客户，i*和j*分别是i和j在路径中的直接后继节点。2-opt是指删去弧(i，i*)、(j，j*)，添加弧(i，j)、(j*，i*)，从而得到一条更优的路径。

3.5 CO－HS算法步骤

CO-HS算法对经典的和声算法进行了两点改进:首先在新和声生成时，添加了约束，避免了不可行解的生成;其次，基于2-opt算子对新生成的和声进行了优化，提高了算法速度。算法描述如下:

步骤1:初始化和声算法(包括参数和记忆库);

步骤2:采用改进算法产生一个符合约束的和声;

步骤3:对新和声进行2-opt算子的优化;

步骤4:计算新和声适应度，并基于更新策略，更新和声记忆库;

步骤5:检查是否满足停止条件，若不满足，转2;

步骤6:输出和声记忆库中的当前最优解。

设客户个数为n，迭代次数为d，则算法的复杂度与HS算法类似，也为O(n*d)。

4 实验结果与分析

将提出的CO-HS算法与现有的CVRP问题的求解算法进行比较分析。实验环境:InDel(R)Core (DM)i3-2120 CPU@3.30 GHz;3 GB内存;Windows 7操作系统，Eclipse+pydev，解释器版本:pypy3-2.4.0。CO-HS算法的参数设置:和声记忆库大小=20;HMCR =0.9;PAR=0.25。每类算法运行20次，迭代次数为50。

实验数据选用很多研究工作中都采用的一个小规模数据，包括了8个顾客和2辆车，每辆车容量为8，客户需求数据见表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。与现有算法的比较见表2。

从表2可以看出，所提出的CO-HS算法在求解CVRP问题时，从最大值、最小值、平均值以及得到最优解的次数上，都优于现有算法。

文中同时对VRPLIB的5个标准测试数据进行了测试，实验结果见表3。

从表3可以看出，所提出的CO-HS算法获得的最优解比传统遗传算法和粒子群算法更优。

5 结束语

CVRP问题在实际生活中有许多应用，如收集和运送货物、校车路线、街道清洁、垃圾收集等。文中研究了和声算法，提出了CO-HS算法。实验结果表明，提出算法在效率上优于现有的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，Franco 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］.计算机集成制造系统，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］肖健梅，李军军，王锡淮.求解车辆路径问题的改进微粒群优化算法［J］.计算机集成制造系统，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">网络出版时间:

时间:2016-08-23

国家自然科学基金资助项目(61170108，61402418);教育部人文社科研究项目(12YJCZH142);浙江省自然科学基金(LQ13F020007)

颜腾威(1989-)，男，硕士研究生，研究方向为智能计算;王丽侠，副教授，研究方向为智能计算。

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