1 概述
车辆路径规划问题（Vehicle Routing Problem,VRP）是现代物流配送过程中的关键环节,而且其在众多领域中都有广泛的应用,因此它的提出引起了不同学科的专家和物流管理者的极大重视,目前VRP已经成为研究的热点。但是如何找到一种高效的算法使其在较短的时间内找到比较满意的全局解仍然是研究的重点。
1.1研究背景
中国快递业业务量快速增长的同时也涌现出一批问题。比如价格竞争、快递车辆违规上路、快件安全问题、受到快递企业运输能力的限制,持续增长的快递运输需求得不到及时满足等等。其中供需矛盾成为亟待解决的焦点问题。作为运输管理研究中的核心问题之一,车辆调度问题（VRP）受到专家学者们的高度关注,一度成为研究热点。本文着重研究有障碍域的快递车辆动态调度问题（Vehicle Routing Problem with Obstacle Area,VRPOA）,通过基于蚁群算法的二维路径规划算法解决快递车辆线路安排和车辆指派问题,以期丰富蚁群算法解决车辆调度问题的应用场景,为快递企业进行车辆路径规划提供决策依据。本文以VRPOA问题为研究对象,关键在于集合蚁群算法和路径规划算法,使求解结果更快、更好。主要研究工作如下:首先,挖掘研究问题。通过阅读大量文献,对车辆路径问题的定义、分类、复杂度、求解算法做了详尽的总结,发现车辆路径问题的理论型研究已渐趋成熟,而考虑实际应用场景的应用型研究还有待拓展。其次,确定研究方法。通过文献阅读的积累,发现求解车辆路径问题这一类NP-hard问题需要使用智能启发式方法。蚁群算法现已成为求解离散优化问题的有效工具,且优势明显。MAKLINK图论可生成二维路径规划的可行空间,而Dijkstra算法是解决有向图中最短路径问题的有效算法,可以用于局部车辆路径调优。再次,模型构建。针对快递车辆路径问题,构建了以行驶总距离最短为目标的单目标数学模型,设计了算法和求解策略。最后,参照Benchmark Problems设计了算例。
2 运行结果
3 Matlab代码实现
[代码说明] 蚁群算法解决VRP问题 [算法说明] 首先实现一个ant蚂蚁类，用此蚂蚁类实现搜索。 算法按照tsp问题去解决，但是在最后计算路径的时候有区别。 比如有10个银行网点,网点1是银行中心，蚂蚁搜索的得到的路径是1,3,5,9,4,10,2,6,8,7。 计算路径的时候把网点依次放入派送线路中, 每放入一个网点前，检查该网点放入后是否会超过运钞车最大载重 如果没有超过就放入 如果超过，就重新开始一条派送路线 …… 直到最后一个网点运送完 就会得到多条派送路线 %} %清除所有变量和类的定义 clear; clear classes; %蚁群算法参数(全局变量) global ALPHA; %启发因子 global BETA; %期望因子 global ANT_COUNT; %蚂蚁数量 global CITY_COUNT; %网点数量 global RHO; %信息素残留系数!!! global IT_COUNT; %迭代次数 global DAry; %两两网点间距离 global TAry; %两两网点间信息素 global CITYWAry; %网点货物需求量 global VW; %运钞车最大载重 %=================================================================== %设置参数变量值 ALPHA=1.0; BETA=2.0; RHO=0.95;
4 结语
本文给出了一种基于改进人工蜂群算法的航路规划方法实现。该方法将规划空间的预处理和人工蜂群算法相结合，通过建立地形安全曲面和量化威胁信息,简化规划空间。在传统人工蜂群算法的基础上,改进了算法中食物产生的方式，将航迹规划分解为各节点的规划，并引入双向规划机制，大大提高了产生航迹的质量。同时应用我们给出的路径规划算法,对多无人机的两种协同模型做出初步实现，仿真结果表明，算法可以快速规划出满足约束条件的三维航路,并能有效实现多无人机的初步协同，具有较强的工程可实现性。.
5 参考文献
[1]秦固.基于蚁群优化的多物流配送中心选址算法[J].系统工程理论与实践,2006(04):120-124.
[1]石华瑀. 改进的蚁群算法在实际VRP中的应用研究[D].山东大学,2012.
部分理论来源于网络，如有侵权请联系删除。
