Vehicle Routing And System Implementation For Pickup And Delivery Problem With Time Windows

With the development of Internet and economic globalization,logistics plays an increasingly important role in manufacturing-related enterprises.How to improve the manufacturing speed and reduce the logistics cost is an important direction for enterprises to focus on.As a new logistics mode,milk-run can effectively reduce inventory,improve vehicle utilization rate and reduce transportation cost in small batch and multi-frequency material transportation.This topic studies the Pickup and Delivery Problem with Time Windows(PDPTW)in the milk-run mode from the perspective of vehicle routing.This Problem is a NP-hard problem with no polynomial time complexity solution.In reality,this problem is common in parts transportation,express delivery and other industries.At present,there are few researches on PDPTW at home and abroad,and even fewer combined with the milk-run mode.Therefore,it is of certain practical significance to study the vehicle routing of pickup and delivery problem with time windows under the milk-run mode.Aiming at the vehicle routing problem with pickup-delivery and time Windows,the improved algorithm of large neighborhood search is designed in this project.Multiple restart strategies are added externally to make the results more stable.The adaptive selection strategy between operators and the parameter vector adaptive strategy within operators are proposed to improve the search efficiency and neighborhood diversity.This algorithm obtains the optimal solution with the number of vehicles as the target under the Li?100 standard data set,and compared with the simulated annealing nested tabu search algorithm under the average loading rate as the second target,this algorithm can obtain better results on the regular distribution,random distribution and mixed distribution data sets.According to the actual scene,this paper further expands the use scene of the above improved large neighborhood search algorithm,and innovatively introduces the constraint of rest time window and white and night shift.For the constraint of the break time window,the path arrangement of the algorithm in this time period is optimized by means of piecewise discussion and setting up the linear penalty function.In view of the constraints of white shift and night shift,this algorithm adopts a time-based clustering method,first clustering orders according to the day shift and night shift,then solvingthe orders of each shift using the improved large neighborhood search algorithm,and finally optimizing the paths of each day shift and night shift.Compared with the genetic algorithm,this algorithm can achieve higher vehicle loading rate with the same number of vehicles.Combined with the above algorithms,the vehicle routing system for pickup and delivery problem with time windows is designed.The back-end of the system adopts SSM(Spring MVC,Spring,My Batis)framework,and the browser is based on Web GIS technology and uses baidu map API and Echarts library for path display and data display.The system mainly contains three functions,customer order information management,vehicle routing arrangement,map display.The execution process of the system is as follows: obtain valid orders in the background and display them in the front end to provide operations such as increase and query,etc.The server performs path planning on the vehicle routing module for all orders,and finally displays the route planning information of each vehicle in the front end.