《车辆路径问题的算法综述》-哲学论文-论文范文参考-科学狗论文网

标题

车辆路径问题的算法综述

范文

周祺森

摘要：物流与国民经济及生活的诸多领域密切相关，在物流成本方面，运输费用占大约50%，比重最大。因此，物流成了企业创造利润的重要途径。要降低配送成本，缩短并优化车辆路径是关键所在。然而，车辆路径问题（vRP）是物流领域中的一个强NP问题，国内外学者近年来不断提出多种车辆路径优化问题及求解方法以解决愈加复杂的问题。为进一步理清国内外研究现状，就VRP进行总结分析，然后对车辆路径求解方法进行了介绍，特别地对元启发式算法进行了较为详细的综述。

关键词：VRP;元启发式算法;文献综述

中图分类号：U116.2 文献标志码：A

0引言

随着电子商务的快速发展，物流业作为连接生产者与消费者的桥梁，发挥着越来越重要的作用。然而，物流在给人们生活带来极大便利的同时，也给相关企业带来了逐年增高的物流费用。伴随着竞争日益白热化的商业环境，降低物流成本成了物流企业存活和发展所必须重视的环节。在降低物流成本方面，最关键的途径之一是解决车辆路径问题（vehicle routing prob-lem，VRP）。

1VRP综述

车辆路径问题于1959年由丹齐格和拉姆泽提出，最早源于旅行商问题（TsP）的研究。TsP可以简单理解为在给定的m个城市里，从一个城市出发，经过每个城市，并且每个城市只经过一次，最后回到出发点，找出最短回程路径问题。

在TsP的研究基础上，出现了能力约束车辆路径问题（CVRP），CVRP相对于TsP的“一对多”，可以理解为“多对多”，如图1所示。

2VRP元启发式算法综述

基于车辆路径模型，其求解算法基本可分为精确式算法、启发式算法、元启发式算法和机器学习算法，如图2所示。

2.1遗传算法

遗传算法是由J.Holland教授在1975年首先提出，它借鉴了生物进化论中的遗传、杂交、变异以及自然选择等现象，利用计算机模拟生物进化的过程，根据优胜劣汰、适者生存的自然法则规定搜索方向，以此迭代，最终获得具有最大适应度个体，该个体就作为最优解输出。

遗传算法的优点是求解结果稳定，计算效率高，但是存在局部搜索能力很弱，在接近最优解后，达到最优解还需要一段时间的缺陷。另外，如果适应度函数選择不当，遗传算法常常收敛于局部最优，无法实现全局最优。

针对遗传算法的缺陷，国内外学者提出了很多优化方法。比如H.Bersini和G.Seront提出将遗传算法与单一方法结合起来，获得除母体以外的新个体，通过计算发现，三交叉算子的性能较原先两母体有了较大提升。

2.2蚁群算法

蚁群算法是由Dorigo和Maniezzo等人提出的仿生算法，他们发现单只或少量的蚂蚁在寻找食物路径时无特别技巧，但是当蚁群数量上升到一定程度时，他们却可以找到最优路径，甚至在认为改变环境后，他们仍能找到最优路径，如图3所示。

经过研究发现，蚂蚁在行进过程中会释放一定量的信息素，周围的蚂蚁在感知到该信息素时会优先选择该路径，当选择该路径的蚂蚁越来越多时，即单位时间内走过该路径的蚂蚁越来越多，则该路径上信息素的浓度也越来越高，就会有越来越多的蚂蚁选择该路径，形成正反馈，从而实现路径最优化。蚁群算法最大优点是对最优解具有强大的搜索能力，此外还有原理简单，具有并行性和鲁棒性，易于实现等优点。缺点是需要较长的搜索时间，计算效率低下，当应用于求解静态车辆路径问题时，求解耗时的长短对实际应用几乎不产生影响，但是，当应用于动态车辆路径时，求解耗时成了实用性的重要指标。此外，参数的设置（如信息素挥发因子）对结果有很大的影响，设置不当会使运行陷于局部最优，出现停滞现象，无法搜索最优解。

针对蚁群算法的这个缺陷，常见的优化策略是将遗传算法的遗传、杂交和变异等遗传算子引入蚁群算法，使得在满足迭代次数的情况下，仍能保持较快的计算效率，同时每次迭代后局部最优解也能逐步逼近全局最优解。除此之外，还能在每次搜索的过程中，用邻域算法对每只蚂蚁求出的最优解进行二次搜索，比如在迭代过程中发现选择同一条路径的蚂蚁数量超过了蚂蚁总数的1/4，则可以通过降低该路径上的信息素浓度，避免信息素浓度对算法的极端影响，从而提高原来最优解的质量。

2.3禁忌搜索算法

TS，也被称为爬山启发式算法，不同于蚁群算法，TS通过模拟人的记忆和经验，通过禁忌表记忆之前进行的优化过程，禁忌某些解，以避免走回头路和剔除某些极端解，从而避免陷入局部最优解。

其基本思路如下：假设一群兔子要寻找珠穆朗玛峰，它们在寻找过程中遇到了泰山，它们就会留一只在泰山，其余兔子继续寻找，最终找到珠穆朗玛峰。当兔子们再次寻找珠穆朗玛峰时，因为有一只兔子留守泰山，它们就会避开泰山，这就是禁忌解。但是，当它们搜寻的地方是平原时，泰山就成了不可避开的存在，这就是“特赦准则”。

然而，当禁忌表范围过小时，容易陷入循环搜索;当禁忌表范围过大时，容易陷入局部最优化，所以合理确定禁忌表范围是使用Ts的关键。通常可以采用邻域变换规则（neighborhoods changed rules，NCR）来决定禁忌搜索算法的禁忌解范围和解的质量，或者将遗传算法和禁忌搜索算法混合，通过遗传算法的交叉算子扩大搜索的范围。

2.4粒子群算法

粒子群算法是由Kenndv和Eberhart提出的新型进化算法，不同于遗传算法，粒子群算法没有交叉、变异算子，以及复杂多样的编码方式，他是通过个体位置和速度信息的不断更新，通过个体之间的相互联系和影响在解空间中不断进行搜索，最终求得全局最优解。该算法受到了鸟群捕食的启法，假设一群鸟在随机搜索食物，每只鸟都为一个粒子，它们与食物的距离已知，则搜寻食物最优的策略就是搜寻离食物最近的鸟的周围区域，这只鸟就是当前最优解，其他鸟通过追寻它来找寻食物，以此获得全局最优解。

该算法的优点是结构构造简单、需要调节的参数较少、涉及的专业知识少、容易实现，所以常被国内外大量研究人员应用于许多实际问题中。但是，粒子群算法解的可行性处理不好，其结果往往无法收敛或者结果为空集。常见的优化方法有：一是采用多层Pareto排序机制来产生优良粒子，利用这些优良的粒子来决定其他粒子的搜索范围和方向，从而提高搜索效率;二是通过混合遗传算法，引入自然选择机制，基本思路为：首先计算粒子的适应度值，并由该指标对粒子进行排序。然后由排序的结果，选出原来粒子个体的最优位置信息，再用粒子群中最好的一半粒子替换粒子群中最差的另一半粒子;三是通过混合模拟退火算法，引入模拟退火机制，基本的思路是随着迭代次数的增加，温度会逐渐下降，接受不良解的概率也会逐渐下降，从而改良粒子群算法收敛性差的缺陷，并且也在很大程度上提高了解的精度。

2.5模拟退火算法

模拟退火算法最早是由N.Metropolis等人基于固体退火原理提出，其基本思路为，当固体加热至充分高的温度，随着温度的升高固体内部的粒子变为无序状，内能增大，再让其徐徐冷却，在冷却过程中粒子重新变得有序，这样就令每个温度都能达到了平衡态，最后在常温时达到基态，内能减为最小。在1983年，s.Kirk-patrick等人基于Monte-Carlo迭代求解策略將退火思想引入到组合优化领域，也就是在“产生新解一计算新解—计算新解与原解的差值—是否接受”的重复迭代过程中，接受部分不好的解，这样就可以从整体上考虑，求出最优解，跳出局部最优的陷阱。所以，模拟退火算法的优点是全局搜索能力较强、原理简单、运算效率高、受到初始条件的约束较少、具有并行性等。缺点是求解精度低，尤其是当降温系数过低时，而当降温系数过大时，求解精度高但求解效率低，算法运行时间较长。

针对其求解精度低的缺点，国内外专家常采用求解精度高的蚁群算法与其混合。组合算法的思想是先使用模拟退火算法获得相对最优解，并将最优解作为蚁群的初始信息素，设置蚁群算法参数，然后使用蚁群算法找出精确解。

3结束语

元启发式算法不借助于某种问题的特有条件，从而能够运用于更广泛的方面。本论述主要选取了元启发式算法中4种经典的算法，对它们的基本含义、优点以及改进方案等进行了概述。希望能给研究学者提供参考，给物流行业人员提供知识框架和指导方法。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。