车辆路径问题及其优化算法研究综述

《车辆路径问题及其优化算法研究综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、车辆路径问题及其优化算法研究综述摘要：车辆路径问题是物流管理与运输组织优化中的核心问题，是运筹学中一类经典的组合优化问题。文章比较系统地总结了常见的vrp问题的分类和基本的数学模型，并通过査阅学者们的研究状况，总结了求解vrp问题常用和高效的启发式算法及相应的研究现状；最后总结了研宄存在的问题，并对今后vrp问题的研究和求解方法进行了展望。关键词：车辆路径问题；启发式算法；优化中图分类号：U116.2文献标识码：a0引言随着科技的进步和电子商务的飞速发展，作为国民经济中一个重要行业的物流产业已成

2、为拉动国家经济发展与提高居民生活水平的重要动力源泉，而物流行业中的车辆路径问题(vehicleroutingproblem,vrp)是制约物流行业发展的一个关键要素，其研宄也受到人们的广泛关注。车辆路径问题是物流管理与运输组织优化中的核心问题之一，是指在满足一定的约束条件(如时间限制、车载容量限制、交通限制等)下，通过对一系列收货点与发货点客户合理安排行车路线，在客户的需求得到满足的前提下，达到配送车辆最少、配送时间最短、配送成本最低、配送路程最短等目标。该问题由dantzig和ramser[l

3、]于1959年在优化亚特兰大炼油厂的运输路径问题时首次提出，现已成为运筹学屮一类经典的组合优化问题，是典型的np-难题。企业通过选取恰当的配送路径，对运输车辆进行优化调度，可以明显提高配送效率，有效减少车辆的空驶率和行驶距离，降低运输成本，加快响应客户的速度从而提高客户服务质量，提高企业的核心竞争力。vrp作为物流系统优化环节中关键的一环，其研究成果己经应用到快递和报纸配送连锁商店线路优化以及城市绿化车线路优化等社会实际问题中，因而车辆路径问题的优化研究具有很好的现实意义。1车辆路径问题的分类与

4、基本模型vrp的构成要素通常包括车辆、客户点、货物、配送中心（车场）、道路网络、目标函数和约朿条件等，根据侧重点的不同，vrp可以分为不同的类型。根据运输车辆载货状况分类可分为非满载车辆路径问题和满载车辆路径问题；根裾任务特征可分为仅装货、仅卸货和装卸混合的车辆路径问题；根据优化目标的数量可分为单目标车辆路径问题和多目标车辆路径问题；根据配送车辆是否相同可分为同型车辆路径问题和异型车辆路径问题；根据客户对货物接收与发送有无时间窗约朿可分为不带时间窗的车辆路径问题和带时间窗的车辆路径问题；根据客户

5、需求是否可拆分可分为需求可拆分车辆路径问题和需求不可拆分车辆路径问题；根据客户是否优先可分为优先约束车辆路径问题和无优先约束车辆路径问题；根据配送与取货完成后车辆是否需要返回出发点可分为开放式车辆路径问题和闭合式车辆路径问题；还可以将上述两个或更多约朿条件结合起来，构成一些更复杂的车辆路径问题。由于vrp的约束条件不同引起了其分类多种多样，而不同类型的vrp其模型构造及求解算法有很大差别。vrp的一般数学模型为：在上述模型中，式（1）表示目标函数，式（2）表示约束条件。其他vrp模型大致都是在此

6、模型的基础上根据约束条件完善形成的。2vrp的求解算法与研究现状vrp的求解方法，基本上可分为精确算法和启发式算法两大类。由于精确算法的计算难度与计算量随着客户点的增多呈指数级增加，在实际中应用范围有限，而启发式算法则具有全局搜索能力强、求解效率高的特点，求出的解也具有较好的参考性，因此，目前大部分研宄者们主要把精力集中在如何构造高质量的启发式算法上，木文也主要讨论一些近年来研究比较多的启发式优化算法。针对vrp问题目前己提出了大量的启发式算法，其中研宄较多的主要包括以下算法：2.1遗传算法(g

7、eneticalgorithm,ga)2.2模拟退火算法(simulatedannealing,sa)sa同禁忌搜索算法一样，也属于局部搜素算法，但是模拟退火算法是模仿金属加工中退火的过程，通过一个温度函数作为0标函数，使其趋于最小值，是一种基于概率的算法。采用模拟退火算法研究vrp问题的研究现状包括：郎茂祥［5］研究了装卸混合车辆路径问题，并构造了模拟退火算法求解该问题；穆东等［6］提出丫一种并行模拟退火算法，并将该算法的应用领域扩展到其他车辆路径问题和组合优化问题；魏江宁和夏唐斌［7］以模拟

8、退火算法为基础，研究了单个集散点与多个客户之间的运输问题;mirabi和fatemighomi等［8］提出了一种基于模拟退火思想的三步启发式算法求解最小化配送时间的多配送屮心vrp模型。2.3蚁群算法(antcolonyoptimization,aco)蚁群算法是人们受蚂蚁可以快速找到食物的自然现象启发提出的。蚁群算法所建立的机制，主要包括蚂蚁的记忆、蚂蚁利用信息素进行交互通信及蚂蚁的集群活动三个方面。单个蚂蚁缺乏智能，但整个蚁群则表现为一种有效的智能行为。通过这种群体智能行为建立的路径选择机制