基于蚁群算法的快递车辆动态调度研究

发布时间：2018-07-12 12:53

  本文选题：快递车辆调度 + 蚁群算法　； 参考：《杭州电子科技大学》2017年硕士论文

【摘要】：中国快递业业务量快速增长的同时也涌现出一批问题。比如价格竞争、快递车辆违规上路、快件安全问题、受到快递企业运输能力的限制,持续增长的快递运输需求得不到及时满足等等。其中供需矛盾成为亟待解决的焦点问题。作为运输管理研究中的核心问题之一,车辆调度问题(VRP)受到专家学者们的高度关注,一度成为研究热点。本文着重研究有障碍域的快递车辆动态调度问题(Vehicle Routing Problem with Obstacle Area,VRPOA),通过基于蚁群算法的二维路径规划算法解决快递车辆线路安排和车辆指派问题,以期丰富蚁群算法解决车辆调度问题的应用场景,为快递企业进行车辆路径规划提供决策依据。本文以VRPOA问题为研究对象,关键在于集合蚁群算法和路径规划算法,使求解结果更快、更好。主要研究工作如下:首先,挖掘研究问题。通过阅读大量文献,对车辆路径问题的定义、分类、复杂度、求解算法做了详尽的总结,发现车辆路径问题的理论型研究已渐趋成熟,而考虑实际应用场景的应用型研究还有待拓展。其次,确定研究方法。通过文献阅读的积累,发现求解车辆路径问题这一类NP-hard问题需要使用智能启发式方法。蚁群算法现已成为求解离散优化问题的有效工具,且优势明显。MAKLINK图论可生成二维路径规划的可行空间,而Dijkstra算法是解决有向图中最短路径问题的有效算法,可以用于局部车辆路径调优。再次,模型构建。针对快递车辆路径问题,构建了以行驶总距离最短为目标的单目标数学模型,设计了算法和求解策略。最后,参照Benchmark Problems设计了算例。实验证明本文提出的基于蚁群算法的二维路径规划算法对于求解VRPOA问题行之有效。
[Abstract]:China express industry business volume of rapid growth at the same time also emerged a number of problems. For example, price competition, express delivery vehicles on the road, express security problems, by express transport capacity constraints, continuous growth of express transport demand can not be met in time, and so on. Among them, the contradiction between supply and demand has become the focus problem to be solved. As one of the core issues in the research of transportation management, vehicle scheduling problem (VRP) has been highly concerned by experts and scholars. This paper focuses on the vehicle routing problem with stacle area VRPOA (vehicle routing problem), and solves the routing and assignment problems of express delivery vehicles by means of a two-dimensional path planning algorithm based on ant colony algorithm. The purpose of this paper is to enrich the application scenario of ant colony algorithm to solve the vehicle scheduling problem and to provide the decision basis for the express delivery enterprise to plan the vehicle route. In this paper, we take VRPOA problem as the research object, the key lies in the set ant colony algorithm and the path planning algorithm to make the solution result faster and better. The main research work is as follows: first, mining research problems. Through reading a lot of literature, the definition, classification, complexity and algorithm of vehicle routing problem are summarized in detail, and it is found that the theoretical research of vehicle routing problem has gradually matured. But the application research considering the practical application scene still needs to be expanded. Secondly, the research method is determined. Through the accumulation of literature, it is found that an intelligent heuristic method is needed to solve the NP-hard problem of vehicle routing problem. Ant colony algorithm (ACA) has become an effective tool for solving discrete optimization problems and has obvious advantages. MAKLINK graph theory can generate feasible space for two-dimensional path planning. Dijkstra algorithm is an effective algorithm for solving the shortest path problem in directed graphs. Can be used for local vehicle routing tuning. Again, the model is built. Aiming at the route problem of express delivery vehicle, a single objective mathematical model aiming at the shortest total distance is constructed, and the algorithm and solution strategy are designed. Finally, an example is designed with reference to benchmark problems. Experiments show that the proposed two-dimensional path planning algorithm based on ant colony algorithm is effective for solving VRPOA problem.
【学位授予单位】：杭州电子科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;F259.2

【参考文献】

中国期刊全文数据库 前10条

1 任志刚;赵松云;黄姗姗;梁永胜;;求解多维背包问题的蚁群-拉格朗日松弛混合优化算法[J];控制与决策;2016年07期

2 李洋;刘艳娜;;蚁群算法信息素更新方式的评价研究[J];科技创新与生产力;2016年03期

3 张婷;赖平仲;何琴飞;靳志宏;;基于实时信息的城市配送车辆动态路径优化[J];系统工程;2015年07期

4 田宇;伍炜勤;吴其震;;基于标签算法的异车型混合集送多属性车辆路径问题研究[J];管理工程学报;2015年03期

5 韩娟娟;李永先;;动态车辆路径问题研究综述[J];绿色科技;2015年05期

6 张勇;;基于改进蚁群算法物流配送路径优化的研究[J];控制工程;2015年02期

7 费腾;张立毅;孙云山;;基于DNA-蚁群算法的车辆路径优化问题求解[J];计算机工程;2014年12期

8 侯玲娟;周泓;;基于离散差分进化算法的随机车辆路径问题[J];工业工程;2014年03期

9 李成兵;郭瑞雪;李敏;;改进蚁群算法在旅行商问题中的应用[J];计算机应用;2014年S1期

10 叶仕通;万智萍;;一种基于改进全局信息素更新效率的蚁群算法及仿真[J];计算机应用与软件;2014年01期

中国博士学位论文全文数据库 前2条

1 孙中悦;车辆路径问题的仿真优化方法研究[D];北京交通大学;2012年

2 钟石泉;物流配送车辆路径优化方法研究[D];天津大学;2007年

中国硕士学位论文全文数据库 前1条

1 白磊;蚁群算法的改进及其应用研究[D];安徽大学;2015年

，

本文编号：2117222