采用不同算法求解车辆路径问题的对比分析

李 宁 馨

(合肥工业大学 管理学院，合肥 230009)

进入21世纪以来，物流产业作为一个新兴产业迅猛发展，被认为“降低资源消耗”和“提高劳动生产率”两大企业利润来源之后的“第三利润源泉”[1]。“十二五”规划指出要构建综合交通运输体系，大力发展现代物流业，大力推进节能降耗、实施区域物流总体发展战略、大力发展新一代信息技术等重点任务[2]。车辆路径问题作为物流管理领域关注的热点和重点问题之一，从提出开始就引起运筹学、管理学、计算机应用、组合数学、图论等学科的专家和学者的高度重视[3]。研究车辆路径问题不仅可以帮助企业提高服务水平，为顾客提供快捷、准时的服务，而且有助于企业降低运输成本，提高车辆利用效率，缩短生产周期，加速资金周转，实现资源的合理配置，对资源节约和环境保护都有重要意义[4]。

1 标准车辆路径问题的模型

标准车辆路径问题是最基本的车辆路径问题，其他不同类型的车辆路径问题都是在标准车辆路径问题的基础上扩展而来的。通常的标准车辆问题是指带装载能力车辆路径问题(Capacitated Vehicle Routing Problem，简称CVRP)，即每个车辆都有最大容量的限制。标准车辆路径问题表示为一个完备图G=(V，A)，V是顶点集，A是弧集。其中V={0，1，…，n}，0是仓库点；1，…，n是待服务的客户点；A={(i，j)|i，j∈V，i≠j}。

此外，为了说明问题，定义以下符号：cij，对A中的任意一条弧(i，j)赋予一个非负值cij作为它的权(weight)，它根据实际需要代表不同的含义，如距离，时间，费用等等。Q为车辆最大容量；qi为客户点i的货物需求。∀i∈V，i≠0，都有qi≤Q。R为车辆集，R={0，1，…，m}。

目标函数：

(1)

约束条件：

(2)

(3)

(4)

(5)

模型式(1)是目标函数，意义是实现总路程最小化；式(2)表示每个顾客点都被服务，且仅被服务一次；式(3)表示车辆k是否访问j是由其他点到j的总和；式(4)表示车辆是否k访问j是由j到其他点的总和；式(5)表示每辆车的货物重量不超过其载重。

车辆路径问题的解法大体分为两种：精确解法和启发式解法。Lenstra JK和Rinnooy Kan[5]证明了车辆路径问题是组合优化领域中的强NP-hard问题，精确算法只能有效求解的需求点数量和路段数较少的车辆路径问题[6]。Bruce L. Golden等指出[7]，对于客户点超过50个的车辆路径问题，无法利用精确解法得到一致最优解，因此采用启发式算法来寻求车辆路径问题的满意解就成为车辆路径问题研究的重点。现把常见的车辆路径问题的解法归纳如图1所示[8]。

图1车辆路径问题的解法分类

2 节约法

2.1 基本概念

节约法是Clark和Wright于1964年提出来求解标准车辆路径问题的，又称节约里程法或CW算法，它基于节约原则逐步构造车辆路线，是解决车辆路径问题的一种经典启发式算法。节约法的基本原理很简单：三角形任意两边之和大于第三边。节约法核心思想是依次将车辆路径问题中的两条路径合并为一条路径，使得合并后的运输距离能够当前最大幅度的节约，直到不能再进行下去，此时对剩余的客户重复相同的过程，直至所有的边都被考虑。节约法原理简单，易于实现，车辆路径问题很多启发式算法利用节约法来产生初始解。

2.2 算法流程

算法的初始路线是n条(n是顾客点数目)仅含仓库和一个客户点的路线集：

Ru={Ri|Ri=(0，j，0)}，j=1，2，…，n，i∈R.

Step 1：计算各边节约值sij=ci0+c0j-cij，i，j=1，2，…，n且i≠j；

Step 2：将Step 1中计算出来的节约值按从大到小的顺序降序排列；

Step 3：按照Step 2中排列出来的顺序，从大到小依次检查各边，若删去(i，0) 和(0，j)并以(i，j)代替仍能够保持解的可行性，则选择满足条件的两条路线进行合并。

Step 4：操作Step 3直到没有可合并的路线，现在得到的路线就是最终路线。

2.3 评 价

节约法是一种简便而且易行的算法，形象体现出了优化运输的过程而且思路简单清晰、便于执行，因此在国内外物流配送过程中受到青睐。节约法也有它的缺点：利用节约法来决定配送路线的方法只考虑了运输距离，而完全没有考虑其他因素。 节约法适合应用于那些客户需求固定而且对于送货时间不急迫的场合，这显然与现在有较大不确定性的市场不符，这就限制了节约法的使用范围[9]。

3 遗传算法

3.1 基本概念

1975年，Holland出版了第一本系统论述遗传算法的学术专著“Adaptation in and Artificial Systems”[10]，书中将达尔文的“优胜劣汰，适者生存”的思想应用到人工系统的自适应行为中，此后Holland将这种算法加以发展和推广，并正式命名为遗传算法。1992年出版的“Genetic algorithms+Data Structures = Evolution Programs”[11]一书推动了最优化问题中遗传算法的应用。1996年，J.Lawrence最先将遗传算法应用到车辆路径问题的研究。学者们通过对编码方式、选择方式、交叉方式、变异方式进行深入研究，在简单遗传算法基础上提出了多种改进的遗传算法，改进的遗传算法提高了遗传算法的运行效率和求解质量。现就遗传算法中的基本概念[12]介绍如下：

(1) 编码方法。解的编码是遗传算法的基础工作之一，常见的编码方式有二进制编码、格雷码编码、实数编码等[13]。具体在某一问题中选择何种编码方式，应充分考虑到问题的复杂度、解的连续性、空间大小等因素[14]。

(2) 初始群体的生成和群体大小的确定[15]。初始群体通常采取随机生成的方式或其他生成方式，通过有效方式产生的初始解可能会有助于减少进化次数，但也可能会导致程序过早陷入局部最优群体中。群体中个体的个数越多，进化到最优解的可能性越大，但复杂度也会增大。

(3) 适应度函数。对于无约束的优化问题，可直接选取为目标函数或目标函数的简单变形。对于有约束的优化问题，适应度函数要由目标函数和约束条件共同决定。因此，适应度函数是为了在满足约束条件的解中，使能够让目标函数越优的解越有可能保留下来。

(4) 选择算子。常见的选择算子主要有赌盘轮转法、波尔兹曼选择法、排序选择方法、联赛方法、精英选择方法、稳态选择方法等。其中最常用的是赌盘轮转法，赌盘轮转法先计算每个个体的适应度，再计算每个个体适应度的比例，比例越大的个体越容易被选择，但不意味着适应度高的个体一定被选择。

(5) 交叉算子。需要先选择两个个亲体，再进行配对产生新的个体。一般都是随机配对，交叉规则有双亲遗传法、主个体规则、单亲遗传规则等。为了保证产生的个体是可行解，采用如下方法步骤来实现：对第二个亲体做一个拷贝；从第一个亲体选择任一部分；在后代里做最小的变化以完成所选模式。

(6) 变异算子。变异操作是模拟自然界的基因突变，得到新个体的过程。变异方法也有多种，本文采用的是交叉变异，即随机选择个体的两个基因并将其交换，用新得到的个体代替旧的个体。

(7) 终止准则。终止准则有设定最大遗传次数，检测收敛程度，精英策略保留最佳个体等方法。

3.2 算法流程[16]

(1) 确定编码方法、适应度函数、群体大小、选择算子、交叉算子、变异算子、交叉概率、变异概率等算法参数；

(2) 随机产生解的初始群体；

(3) 计算群体中每个个体的适应度；

(4) 选择，按(1)中确定的选择算子，从旧群体中选出个体组成群体1，群体1的规模与旧群体相同，用群体1代替旧群体，旧群体中的个体可能在群体1中多次出现，也可能不出现；

(5) 交叉，根据(1)中确定的交叉算子和交叉概率，在群体1上反复随机选择两个个体发生交叉，获得规模与群体1相同的群体2，用群体2代替旧群体；

(6) 突变，根据(1)中确定的变异算子和变异概率，群体2中每个个体发生突变，获得群体3，用群体3代替旧群体；

(7) 如果满足终止准则，则算法停止，输出群体中适应度最高的个体作为结果；否则，返回(3)。

3.3 评 价

遗传算法是模拟自然界中优胜劣汰和生物个体中染色体的交叉和变异来处理现实中优化问题的一类新方法。遗传算法适应性强，且是全局优化[17]。另外，遗传算法能用较少的数字串来搜索大量区域，这是遗传算法优于其他优化方法的最主要原因。遗传算法通用性强，易于移植，鲁棒性强，因此在优化领域得到广泛应用。另外，若变异概率0

4 禁忌搜索算法

4.1 基本概念

Osman、Gendreau、Taillard、Xu和Kelly等人都曾研究过利用禁忌搜索算法来求解车辆路径问题。禁忌搜索算法是一种全局搜索算法，禁忌搜索算法从一个初始可行解作为当前解，在它的邻域范围内进行试探，选择让目标函数值趋于最优的方向移动。为了避免陷入局部最优，禁忌搜索算法采用建立禁忌表的方法，把近几次移动的反方向移动存入禁忌表，以避免迂回搜索。此外，为了尽可能不错过产生最优解的移动，禁忌搜索算法还采用了破禁策略，因此处在禁忌表中的移动并非是绝对禁止的[18，19]。

4.2 算法流程

(1) 初始化禁忌表为空，初始解为节约法产生的解，初始化当前得到的最优目标函数值为初始解对应的目标函数值；

(2) 在当前解的邻域内搜索，根据选择策略决定移动方向，并更新禁忌表和当前最优目标函数值；

(3) 重复(2)，直到满足终止准则为止；

(4) 现在得到的最优解就是最终的最优解。

4.3 评 价

在启发式算法中禁忌搜索算法的求解质量最高，是目前最为有效的求解车辆路径问题的方法，在多个标准测试集上取得了令人兴奋的结果。在算法实施过程中发现，禁忌搜索算法的搜索速度快，但是禁忌搜索算法对于初始解具有较强依赖性，较差的初始解会使得收敛过程放慢。此外禁忌搜索算法的搜索过程是从点到点的，因此全局搜索能力有待提高[20]。

5 结 论

5.1 实验结果

上述4种算法采用matlab语言编写了相应程序，在同一Intel Core i3、2G RAM、计算机上进行，选取了10个标准数据测试集合来进行试验。实验结果分别如表1、表2、表3所示。

表1 节约法在标准数据测试集上的实验结果

表2 遗传算法在标准数据测试集上的实验结果

表3 禁忌搜索算法在标准数据测试集上的实验结果

5.2 实验分析

图2 实验结果对比图

用折线图表示上述3种算法的实验结果对比如图2所示。

从图2可以看出，禁忌搜索算法的结果大体优于遗传算法。由于本文中把节约法的解作为遗传算法和禁忌搜索算法的初始解，因此它的结果与其他两种算法的结果没有可比性。在实验中发现，尽管节约法与其他两种算法表示解的数据结构不同，在其他算法中节约法的解可能与原解代表的意义不同，但这样的初始解仍能明显改进遗传算法和禁忌搜索算法的解的质量和缩短迭代次数。

节约法在3种算法中所需要的运行时间最少，求解结果几乎也是最差的。但是经过对比可以发现，节约法的结果和其他两种算法相比，结果相差不多。因此，在对解的质量要求不是很高的情况下，节约法是首选。遗传算法是一种随机性算法，想要得到理想的结果可能要经过多次试验才能得到；禁忌搜索算法是一种确定性算法，但在迭代次数达到一定程度之后，即使增加迭代次数，也并不能起到明显改善结果的作用。禁忌搜索算法在大部分情况下得到的结果优于遗传算法，但这是以花费更多的计算时间为代价的。禁忌搜索算法适合结点数目较少的情况，随着结点数目增长，计算时间大幅增长，且结果不甚理想。

参考文献：

[1] 李永先.车辆路径问题的仿真模型及优化方法研究[D].大连：大连理工大学管理学院，2008

[2] 国家发展和改革委员会经济运行调节局，南开大学现代物流研究中心.中国现代物流发展报告[M].北京：中国物资出版社，2011：87-88

[3] 李相勇.车辆路径问题模型及算法研究[D].上海：上海交通大学安泰经济管理学院，2007

[4] 钟石泉.物流配送车辆路径优化方法研究[D].天津：天津大学经济与管理学院，2007

[5] LENSTRA J, RINNOOY K.Complexity ofvehicle routingand schedulingproblem.Networks，1981(11)：221-227

[6] 邱月.交叉熵方法在车辆路径问题中的应用研究[J].计算机工程与应用，2010，46(34)：242-248

[7] BRUCE L，EDWARD A，JAMES P.Kelly，I-Ming Chao. Fleet Management and Logistics [M].London：Kluwer Academic Publishers，1998

[8] 符卓，陈斯卫.车辆路径问题的研究现状与发展趋势[A]. 王建方.中国运筹学会第七届学术交流会论文集[C].香港：Global-Link出版社，2004：997-1002

[9] 陈晓伟，张悟移，耿继武.节约法在配送路线选择中的应用[J].昆明理工大学学报：自然科学版，2003，28(4)：140-143

[10] HOLLAND J. Adaptation in Natural and Artificial Systems [M].Massachusetts：MIT Press，1975

[11] Michalewicz Z. Genetic algorithms+Data Structures = Evolution Programs[M].Berlin：Springer-Verlag，1994

[12] 柳林，朱建荣.基于遗传算法的物流配送路径优化问题的研究[J].计算机工程与应用，2005，41(27)：227-229

[13] 邢文训，谢金星.现代优化计算方法[M].2版.北京：清华大学出版社，2005：52-53，113-130

[14] 王飞朝.遗传算法编程分析[J].火控雷达技术，2005，34(6)：63-66

[15] 张华庆，张喜.改进遗传算法在车辆路径问题中的应用[J].交通信息与安全，2012，30(5)：81-86

[16] 刘峡壁.人工智能导论：方法与系统[M].北京：国防工业出版社，2008：233-244，263-266

[17] 金菊良，杨晓华，丁晶.标准遗传算法的改进方案-加速遗传算法[J].系统工程与实践，2001，21(4)：8-13

[18] 张颖，刘艳秋.软计算方法[M].北京：科学出版社，2002：134-139

[19] 郎茂祥，胡思继. 车辆路径问题的禁忌搜索算法研究[J].管理工程学报，2004，18(1)：81-84

[20] 张德东.物流配送中车辆路径问题研究[D].天津：天津大学经济与管理学院，2006