车辆路径规划的数学模型及算法综述.pdfVIP

２０１５ 年３月 山东 师 范 大 学 学 报 （自然 科 学 版） Ｍａｒ．２０１５ 第３０卷　第１ 期 Ｊｏｕｒｎａｌ ｏｆＳｈａｎｄｏｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ） Ｖｏｌ．３０ Ｎｏ．１ 车辆路径规划的数学模型及算法综述 高晓菲 （山东外贸职业学院信息管理系，２６６１００，山东青岛 ） 摘要　车辆路径规划问题（Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ，ＶＲＰ）是一项研究热点．在运输过程中，对车辆进行合理的路径规划可以 在满足运输要求的基础上最大程度地节约人力物力，降低运输成本．在对车辆路径规划的研究过程中，模型和算法起着关键性作 用．目前已有的模型和算法还存在一些不足．为此，对车辆路径规划问题的数学模型和算法进行了探讨． 关键词　车辆路径规划；　数学模型；　启发式算法；　精确算法 中图分类号　ＴＰ３０１．６　　　　文献标识码　Ａ　　　　ｄｏｉ：　１０．３９６９／ｊ．ｉｓｓｎ．１００１ －４７４８．２０１５．０１．０１１ １　引　　言 随着社会的发展和科技的进步，我国已经成为汽车消费大国，汽车在交通运输中扮演着重要角色．对汽车的行车路线进 行合理规划不但能够节约人力物力，降低运输成本，给企业带来巨大的经济效益，还可以节能减排，减少交通拥堵，给社会带 来巨大的环境效益． ［１］ 车辆路径规划问题最早由Ｄａｎｔｚｉｇ和Ｒａｍｓｅｒ 于１９５９ 年提出，随后很快引起了广泛关注．该问题一般是指对于确定的配 ［２］ 送中心和客户点，在给定的约束条件下，合理安排配送车辆的行车路线，最终达到一定的配送目标 ．模型和算法是车辆路径 规划问题中最重要的组成部分．目前，对车辆路径规划问题求解的模型和算法很多，各具特点，但是对它们系统的归类分析还 比较少．为此，本文对车辆路径规划的数学建模过程进行了概述，对相关求解算法进行了分类探讨，对该问题的研究现状进行 了分析，指出了目前研究中存在的不足，并针对这些不足，对以后的研究方向进行了展望． ２　车辆路径规划问题的数学模型 目前车辆路径规划问题的研究模型主要分为网络图模型和数学模型两类．网络图模型容易理解，直观性强，但参数容纳 能力低，求解方法少．而数学模型灵活性高，通用性强，容量大，所以用途比较广．本文选用数学模型对该问题进行研究，以下 是数学建模的过程． 问题的简单描述：一个配送中心派出车辆，向多个客户点送货，然后车辆返回到该配送中心．要求合理安排行车路线，满 ［３］ 足各客户点需求 ． 已知条件：１）客户点数为ｎ，每个点的编号为ｉ，需货量为ｒ （ｉ＝１，２，…，ｎ）；２）配送中心拥有的车辆数为ｍ，每辆车的编ｉ 号为ｋ，载重量为ｗ （ｋ＝１，２，…，ｍ）；３）配送中心到各客户点的费用及各客户点之间的费用为ｃ （ｉ＝１，２，…，ｎ－１；ｊ＝１，２， ｋ ｉｊ …，ｎ；ｉ＜ｊ，ｉ＝０表示配送中心）． 约束条件：１）每辆车所装运的货物总重量不得超过自身所能承受的最大载重量；２）每个客户点只能由一辆车送货；３） ［４］ 每条路径的起点和终点都必须是配送中心 ． 建立模型的目标就是要使总的运输成本最小．通常，车辆的行驶路径越短，司机工作时间越少，车辆耗油量越低，总的运 输成本也就越小．因此以车辆行驶路径最短为目标函数建立数学模型． ｎ ｎ ｍ