带时间约束的动态车辆路径问题算法设计与系统实现
发布时间：2018-10-30 10:41
【摘要】：随着近些年物流企业的快速发展,企业对减少成本的期望越来越强烈,非常需要针对车辆分派问题进行研究。车辆路径问题正是对此类问题进行研究,早期大多数研究主要集中在约束车辆路径问题,但是约束车辆路径问题的局限性抑制了它的实用性。动态车辆路径问题是在约束车辆路径问题的基础上,通过取消预知全部顾客需求的限制条件,从而更加符合实际情况,但同时也比约束车辆路径问题更难求解最优解。目前动态车辆路径问题的研究还不多,而针对更符合实际情况的带时间约束的动态车辆路径问题的研究更少,非常需要针对此类问题建立模型并设计高效的算法。本文通过对带时间约束的动态车辆路径问题建立相应数学模型,提出混合算法(模拟退火算法和遗传算法)的解决方案,并在此基础上,实现带时间约束的动态车辆调度系统的设计与开发。本文提出的混合算法将解决方案设置为两个阶段:第一个阶段发挥模拟退火算法的快速性,获取预备最优解集;第二个阶段发挥遗传算法的高效性,并使用第一个阶段的预备最优解集作为种群,在处理遗传算法中针对选择操作、交叉操作、变异操作提出了灵活的解决方案,最终获得最优解。通过与一般的遗传算法和模拟退火算法进行对比实验,证明了本论文算法的优越性。另外,基于本文混合算法开发的带时间约束的动态车辆调度系统包含了三个阶段,即前台数据输入,后台数据运算,以及通过结合百度地图应用程序界面来展示运算结果。
[Abstract]:With the rapid development of logistics enterprises in recent years, the expectation of cost reduction is becoming stronger and stronger, so it is very necessary to study the vehicle assignment problem. The vehicle routing problem is just to study this kind of problem. In the early years, most of the researches focused on the constrained vehicle routing problem, but the limitation of the constrained vehicle routing problem restrained its practicability. On the basis of constrained vehicle routing problem, dynamic vehicle routing problem (DMPS) is more in line with the actual situation by canceling the constraints that predict all customer needs, but at the same time, it is more difficult to solve the optimal solution than the constrained vehicle routing problem. At present, there are not many researches on dynamic vehicle routing problem, but there is less research on dynamic vehicle routing problem with time constraint, which is more suitable to the actual situation. It is very necessary to build a model and design efficient algorithm for this kind of problem. In this paper, the mathematical model of dynamic vehicle routing problem with time constraint is established, and the solution of hybrid algorithm (simulated annealing algorithm and genetic algorithm) is proposed. Design and development of dynamic vehicle scheduling system with time constraints. The hybrid algorithm proposed in this paper sets the solution into two stages: the first stage takes advantage of the rapidity of the simulated annealing algorithm to obtain the preparatory optimal solution set; In the second stage, the high efficiency of genetic algorithm is brought into play, and the preoptimal solution set of the first stage is used as the population. In dealing with genetic algorithm, a flexible solution is put forward for the selection operation, cross operation and mutation operation. Finally, the optimal solution is obtained. Compared with genetic algorithm and simulated annealing algorithm, the superiority of this algorithm is proved. In addition, the dynamic vehicle scheduling system with time constraints is developed based on the hybrid algorithm in this paper, which includes three stages: foreground data input, background data operation, and displaying the results by combining the Baidu map application program interface.
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.52;TP18
本文编号：2299773
[Abstract]:With the rapid development of logistics enterprises in recent years, the expectation of cost reduction is becoming stronger and stronger, so it is very necessary to study the vehicle assignment problem. The vehicle routing problem is just to study this kind of problem. In the early years, most of the researches focused on the constrained vehicle routing problem, but the limitation of the constrained vehicle routing problem restrained its practicability. On the basis of constrained vehicle routing problem, dynamic vehicle routing problem (DMPS) is more in line with the actual situation by canceling the constraints that predict all customer needs, but at the same time, it is more difficult to solve the optimal solution than the constrained vehicle routing problem. At present, there are not many researches on dynamic vehicle routing problem, but there is less research on dynamic vehicle routing problem with time constraint, which is more suitable to the actual situation. It is very necessary to build a model and design efficient algorithm for this kind of problem. In this paper, the mathematical model of dynamic vehicle routing problem with time constraint is established, and the solution of hybrid algorithm (simulated annealing algorithm and genetic algorithm) is proposed. Design and development of dynamic vehicle scheduling system with time constraints. The hybrid algorithm proposed in this paper sets the solution into two stages: the first stage takes advantage of the rapidity of the simulated annealing algorithm to obtain the preparatory optimal solution set; In the second stage, the high efficiency of genetic algorithm is brought into play, and the preoptimal solution set of the first stage is used as the population. In dealing with genetic algorithm, a flexible solution is put forward for the selection operation, cross operation and mutation operation. Finally, the optimal solution is obtained. Compared with genetic algorithm and simulated annealing algorithm, the superiority of this algorithm is proved. In addition, the dynamic vehicle scheduling system with time constraints is developed based on the hybrid algorithm in this paper, which includes three stages: foreground data input, background data operation, and displaying the results by combining the Baidu map application program interface.
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.52;TP18
【参考文献】
相关期刊论文 前6条
1 周慧;周良;丁秋林;;多目标动态车辆路径问题建模及优化[J];计算机科学;2015年06期
2 王仁民;闭应洲;刘阿宁;李杰;;改进变邻域搜索算法求解动态车辆路径问题[J];计算机工程与应用;2014年02期
3 戈军;周莲英;;面向动态车辆路径的改进变邻域搜索算法[J];计算机工程与应用;2013年23期
4 王君;李波;卢志刚;;带时间窗动态车辆路径问题的优化调度策略[J];计算机工程;2012年13期
5 张景玲;赵燕伟;王海燕;介婧;王万良;;多车型动态需求车辆路径问题建模及优化[J];计算机集成制造系统;2010年03期
6 谢秉磊,郭耀煌,郭强;动态车辆路径问题:现状与展望[J];系统工程理论方法应用;2002年02期
，本文编号：2299773
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2299773.html
