带软时间窗的动态车辆路径规划问题研究与实现
发布时间：2018-10-10 20:19
【摘要】：车辆路径规划问题在很多领域包括物流行业运用广泛。随着各种辅助技术的成熟,比如卫星导航技术可以提供路线信息,计算机计算能力和存储能力的提高,高速信息网络的建成等都在促使车辆路径规划问题向更加智能更加高效方向发展。这样既能减少企业的物流成本同时能够提高顾客的体验。现实中顾客会随机提出送货需求,同时希望仓库能够在一个固定时间段将货物送达,此时间段是一个弹性区间,所以带软时间窗的动态车辆路径规划问题研究有现实意义。基于实际需求,本课题研究带软时间窗的动态车辆路径规划问题,针对问题中软时间窗和请求动态到达的约束条件设计了具体的解决方案。在软时间窗前一段到达会增加企业的时间成本,为此设计了一个线性惩罚函数;而在后一段到达会使顾客满意度降低,设计了一个指数惩罚函数。同时将车辆整个工作时间分解成一系列固定时间片来解决请求动态到达问题。本论文设计两个智能启发式算法:改进大领域搜索算法和混合粒子群算法。两个算法会对上个时间片到达的请求进行计算规划出路线,而将本时间片到达顾客点放在下一个时间片处理。改进大领域搜索算法针对软时间窗要求设计一个基于活动安排的贪心算法生成初始解,然后采用插入删除启发式策略进行优化。混合粒子群算法针对问题设计了针对性的粒子结构,并采用Grasp算法生成初始解,然后使用一个粒子速度位置启发式函数进行迭代求解,最后采用PathRelinking算法优化结果。本课题采用Solomon标准数据,该数据依据顾客点的分布分为六大类型,每个类型包含9到12个数据文件每个文件含有100个顾客信息。由于目前还没有研究相同问题的文献,所以将和一篇研究带硬时间窗的动态车辆路径规划问题文章进行对比。惩罚区间设定为20,同时计算六大类型数据平均结果。从结果来看废弃率很明显减少,能够服务的顾客数目增多。同时针对本论文提出两种算法分别在惩罚区间和废弃率,惩罚区间和路程,动态度和废弃率,动态度和路程四个方面进行分析。可以看到六大不同类型数据在几个变量之间的表现,进而得出变量之间的关系。为了直观的展示路径规划效果,本课题设计了基于百度地图的动态车辆路径规划系统。该系统分别采用百度地图API为平台,前端以JQuery技术为核心,后端以PHP和MySQL调用基于Python实现算法。前端可以采用顾客信息包括时间窗和需求等信息,经过处理之后会在前端展示规划好的路径,同时前端各个窗口也会实时显示整个路径,车辆以及司机的信息。
[Abstract]:Vehicle routing problem is widely used in many fields, including logistics industry. With the maturity of various assistive technologies, such as satellite navigation technology, which can provide route information, computer computing capacity and storage capacity, The establishment of high-speed information network has promoted the development of vehicle routing problem towards more intelligent and more efficient direction. This can not only reduce the logistics costs of enterprises, but also improve the customer experience. In reality, the customer will put forward the delivery demand at random, and hope that the warehouse can deliver the goods in a fixed time period, which is a flexible interval, so the study of dynamic vehicle routing with soft time window has practical significance. Based on the practical requirements, the dynamic vehicle routing problem with soft time window is studied in this paper, and a concrete solution is designed for the soft time window and the constraint condition of requesting dynamic arrival. The arrival in front of the soft time window will increase the time cost of the enterprise. For this reason, a linear penalty function is designed, while in the latter stage, the customer satisfaction is reduced, and an exponential penalty function is designed. At the same time, the whole working time of the vehicle is decomposed into a series of fixed time slices to solve the dynamic arrival problem. This paper designs two intelligent heuristic algorithms: improved large-domain search algorithm and hybrid particle swarm optimization algorithm. The two algorithms calculate and plan the route of the request from the last time slice, and the time slice arrives at the customer point to be processed in the next time slice. The improved large domain search algorithm designs a greedy algorithm based on activity scheduling for soft time window to generate the initial solution, and then optimizes the algorithm by inserting and deleting heuristic strategy. The hybrid particle swarm optimization algorithm is designed to solve the problem, and Grasp algorithm is used to generate the initial solution, then a particle velocity position heuristic function is used to iterate the solution. Finally, the PathRelinking algorithm is used to optimize the results. According to the distribution of customer points, the data is divided into six types. Each type contains 9 to 12 data files, and each file contains 100 customer information. Since there is no literature on the same problem at present, it will be compared with a study on dynamic vehicle routing with hard time window. The penalty interval is set to 20, and the average results of the six types of data are calculated at the same time. As a result, the wastage rate was significantly reduced and the number of customers able to serve increased. At the same time, the two algorithms are analyzed in four aspects: penalty interval and abandonment rate, penalty interval and distance, dynamic degree and abandonment rate, dynamic degree and distance. We can see the performance of six different types of data among several variables, and then get the relationship between variables. In order to show the effect of path planning, this paper designs a dynamic vehicle path planning system based on Baidu map. The system uses Baidu Map API as the platform, the front-end is based on JQuery technology, and the back-end is implemented by PHP and MySQL based on Python. The front end can use customer information, including time window and requirement information. After processing, the planned path will be displayed in the front end. At the same time, every front end window will also display the whole path, vehicle and driver information in real time.
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U116.2;TP301.6
本文编号：2263114
[Abstract]:Vehicle routing problem is widely used in many fields, including logistics industry. With the maturity of various assistive technologies, such as satellite navigation technology, which can provide route information, computer computing capacity and storage capacity, The establishment of high-speed information network has promoted the development of vehicle routing problem towards more intelligent and more efficient direction. This can not only reduce the logistics costs of enterprises, but also improve the customer experience. In reality, the customer will put forward the delivery demand at random, and hope that the warehouse can deliver the goods in a fixed time period, which is a flexible interval, so the study of dynamic vehicle routing with soft time window has practical significance. Based on the practical requirements, the dynamic vehicle routing problem with soft time window is studied in this paper, and a concrete solution is designed for the soft time window and the constraint condition of requesting dynamic arrival. The arrival in front of the soft time window will increase the time cost of the enterprise. For this reason, a linear penalty function is designed, while in the latter stage, the customer satisfaction is reduced, and an exponential penalty function is designed. At the same time, the whole working time of the vehicle is decomposed into a series of fixed time slices to solve the dynamic arrival problem. This paper designs two intelligent heuristic algorithms: improved large-domain search algorithm and hybrid particle swarm optimization algorithm. The two algorithms calculate and plan the route of the request from the last time slice, and the time slice arrives at the customer point to be processed in the next time slice. The improved large domain search algorithm designs a greedy algorithm based on activity scheduling for soft time window to generate the initial solution, and then optimizes the algorithm by inserting and deleting heuristic strategy. The hybrid particle swarm optimization algorithm is designed to solve the problem, and Grasp algorithm is used to generate the initial solution, then a particle velocity position heuristic function is used to iterate the solution. Finally, the PathRelinking algorithm is used to optimize the results. According to the distribution of customer points, the data is divided into six types. Each type contains 9 to 12 data files, and each file contains 100 customer information. Since there is no literature on the same problem at present, it will be compared with a study on dynamic vehicle routing with hard time window. The penalty interval is set to 20, and the average results of the six types of data are calculated at the same time. As a result, the wastage rate was significantly reduced and the number of customers able to serve increased. At the same time, the two algorithms are analyzed in four aspects: penalty interval and abandonment rate, penalty interval and distance, dynamic degree and abandonment rate, dynamic degree and distance. We can see the performance of six different types of data among several variables, and then get the relationship between variables. In order to show the effect of path planning, this paper designs a dynamic vehicle path planning system based on Baidu map. The system uses Baidu Map API as the platform, the front-end is based on JQuery technology, and the back-end is implemented by PHP and MySQL based on Python. The front end can use customer information, including time window and requirement information. After processing, the planned path will be displayed in the front end. At the same time, every front end window will also display the whole path, vehicle and driver information in real time.
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U116.2;TP301.6
【参考文献】
相关期刊论文 前3条
1 孙丽君;胡祥培;王征;;车辆路径规划问题及其求解方法研究进展[J];系统工程;2006年11期
2 郭耀煌,谢秉磊;一类随机动态车辆路径问题的策略分析[J];管理工程学报;2003年04期
3 谢秉磊,郭耀煌,郭强;动态车辆路径问题:现状与展望[J];系统工程理论方法应用;2002年02期
相关博士学位论文 前3条
1 饶卫振;大规模动态车辆路径问题优化方法研究[D];大连理工大学;2012年
2 潘立军;带时间窗车辆路径问题及其算法研究[D];中南大学;2012年
3 陆琳;不确定信息车辆路径问题及其算法研究[D];南京航空航天大学;2007年
，本文编号：2263114
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2263114.html
