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

《车辆路径规划的数学模型及算法综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、２０１５年３月山东师范大学学报（自然科学版）Ｍａｒ．２０１５第３０卷第１期ＪｏｕｒｎａｌｏｆＳｈａｎｄｏｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅ）Ｖｏｌ．３０Ｎｏ．１车辆路径规划的数学模型及算法综述高晓菲（山东外贸职业学院信息管理系，２６６１００，山东青岛）摘要车辆路径规划问题（ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍ，ＶＲＰ）是一项研究热点．在运输过程中，对车辆进行合理的路径规划可以在满足运输要求的基础上最大程度地节约人力物力，降低运输成本．在对车辆路径规划的研究过程中，模型和算法起着关键性作用．目

2、前已有的模型和算法还存在一些不足．为此，对车辆路径规划问题的数学模型和算法进行了探讨．关键词车辆路径规划；数学模型；启发式算法；精确算法中图分类号ＴＰ３０１．６文献标识码Ａｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－４７４８．２０１５．０１．０１１１引言随着社会的发展和科技的进步，我国已经成为汽车消费大国，汽车在交通运输中扮演着重要角色．对汽车的行车路线进行合理规划不但能够节约人力物力，降低运输成本，给企业带来巨大的经济效益，还可以节能减排，减少交通拥堵，给社会带来巨大的环境效益．［１］车辆路径规划问题最早由Ｄａｎｔｚｉｇ和

3、Ｒａｍｓｅｒ于１９５９年提出，随后很快引起了广泛关注．该问题一般是指对于确定的配［２］送中心和客户点，在给定的约束条件下，合理安排配送车辆的行车路线，最终达到一定的配送目标．模型和算法是车辆路径规划问题中最重要的组成部分．目前，对车辆路径规划问题求解的模型和算法很多，各具特点，但是对它们系统的归类分析还比较少．为此，本文对车辆路径规划的数学建模过程进行了概述，对相关求解算法进行了分类探讨，对该问题的研究现状进行了分析，指出了目前研究中存在的不足，并针对这些不足，对以后的研究方向进行了展望．２车辆路径规划问题的数学模型目前车辆路径

4、规划问题的研究模型主要分为网络图模型和数学模型两类．网络图模型容易理解，直观性强，但参数容纳能力低，求解方法少．而数学模型灵活性高，通用性强，容量大，所以用途比较广．本文选用数学模型对该问题进行研究，以下是数学建模的过程．问题的简单描述：一个配送中心派出车辆，向多个客户点送货，然后车辆返回到该配送中心．要求合理安排行车路线，满［３］足各客户点需求．已知条件：１）客户点数为ｎ，每个点的编号为ｉ，需货量为ｒｉ（ｉ＝１，２，…，ｎ）；２）配送中心拥有的车辆数为ｍ，每辆车的编号为ｋ，载重量为ｗｋ（ｋ＝１，２，…，ｍ）；３）配送中心到各客

5、户点的费用及各客户点之间的费用为ｃｉｊ（ｉ＝１，２，…，ｎ－１；ｊ＝１，２，…，ｎ；ｉ＜ｊ，ｉ＝０表示配送中心）．约束条件：１）每辆车所装运的货物总重量不得超过自身所能承受的最大载重量；２）每个客户点只能由一辆车送货；３）［４］每条路径的起点和终点都必须是配送中心．建立模型的目标就是要使总的运输成本最小．通常，车辆的行驶路径越短，司机工作时间越少，车辆耗油量越低，总的运输成本也就越小．因此以车辆行驶路径最短为目标函数建立数学模型．ｎｎｍｍｉｎｚ＝∑∑∑ｃｉｊｘｉｊｋ，（１）ｉ＝０ｊ＝０ｋ＝１ｎｓ．ｔ．∑ｒｉｙｉｋ≤ｗｋ，ｋ＝１，

6、２，…，ｍ，（２）ｉ＝１ｍ∑ｙｉｋ＝１，ｉ＝１，２，…，ｎ，（３）ｋ＝１ｍ∑ｘｉｊｋ＝ｙｊｋ，ｊ＝０，１，２，…，ｎ；ｋ＝１，２，…，ｍ，（４）ｋ＝１ｍ∑ｘｉｊｋ＝ｙｉｋ，ｉ＝０，１，２，…，ｎ；ｋ＝１，２，…，ｍ，（５）ｋ＝１收稿日期：２０１４－０６－１３４４第１期高晓菲：车辆路径规划的数学模型及算法综述第３０卷ｙｉｋ＝１或０，ｉ＝０，１，２，…，ｎ；ｋ＝１，２，…，ｍ，（６）ｘｉｊｋ＝１或０，ｉ，ｊ＝０，１，２，…，ｎ；ｋ＝１，２，…，ｍ．（７）在上述模型中：（１）式为目标函数．（２）式是为了保证每辆车装载的货运总量不得超过

7、自身的最大承重量．（３）式表示每个需求点由且仅由一辆车送货．（４）式表示若客户点ｊ由车辆ｋ送货，则车辆ｋ必由某点ｉ到达点ｊ．（５）式表示若客户点ｉ由车辆ｋ送货，则车辆ｋ送完该点的货后必到达另一点ｊ．（６）式中ｙｉｋ表示客户点ｉ的货运任务由车辆ｋ来完成．当事件发生时取１，否则取０．（７）式中ｘｉｊｋ表示车辆ｋ由点ｉ驶向点ｊ，当事件发生时取１，否则取０．３车辆路径规划问题算法目前，车辆路径规划问题的算法总体可分为精确算法和启发式算法两大类．精确算法主要是利用数学方法求解；启发式算法主要是利用一些条件，使得求解的过程不断向着最优解的方

8、向进行．３．１精确算法精确算法主要运用线性规划、非线性规划、整数规划等数学规划技术来描述系统的数量关系，求出最优策［５］略．它包括：分枝定界法，割平面法，网络流算法，动态规划算法等．精确算法引入严格的数学方法解决问题，一般适用于解决结构清晰、边界清楚、各元素之间