Research On Dynamic Vehicle Routing Problem With Soft Time Window And System Implementation

Vehicle Routing Problem(VRP)is widely used in the field of logistics enterprises and other areas.With the maturity of a variety of assistive technologies,such as satellite navigation technology can provide route information,Computing power and storage capacity increase,the completion of high-speed information network,vehicle path planning problem is becoming more and more intelligent and efficient,which can reduce the logistics cost of enterprises and improve the customer experience at the same time.In reality,the customer will propose random delivery needs,and hope to be served in a fixed time period.which is an elastic range,So it has practical significance to study the dynamic vehicle routing problem with soft time windows.Based on the actual demand,we resesarch the dynamic vehicle routing problem with soft time windows,and designed specific solutions for the constraints of soft time window and dynamic request.If vehicles arrvie at the begining of time window,it will increase the time cost of enterprises,so a linear penalty function is designed.When vehicles arrive at the latter,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 in order to solve the dynamic arrival problem of the request.This paper designs two Intelligent Heuristic Algorithm: improved large neighborhood search algorithm(iLNS)and hybrid particle swarm optimization algorithm(hPSO).the Algorithms will be calculate the requests collected from the last time slice,and leave the requests in this time slice to the next.As the soft time window constraint,a greedy algorithm is designed to generate the initial solution in iLNS,and then the insertion and deletion heuristic strategy is adopted to optimize the solution.Hybrid particle swarm optimization algorithm has design a special particle structure,and the Grasp algorithm is used to generate the initial solution.A particle velocity position heuristic function is applied to solve the iteration,and the final result is optimized by the PathRelinking algorithm.we use Solomon standard data,which is composed of six types according to the distribution of customer points,each type contains 9 to 12 data files,and each file contains 100 customer information.Since there is no research on the dynamic vehicle routing problem with soft time windows in current literature,so we will compare it with a paper which studies the dynamic vehicle routing problem with hard time windows.Penalty interval is set to 20,we will calculate the average results of the six types of data.From the results,the waste rate is significantly reduced.Meanwhile this paper will analysis relation between the penalty interval and the waste rate,relation between the range of punishment and distance,relation between dynamic degree and waste rate,relation between the dynamic degree and distance analysis.We can see the performance between the six different types of data in several variables,then get the relationship between different variables.In order to show the effect of path planning,a dynamic vehicle routing system based on Baidu map is designed.The Baidu maps API is used as a platform for the system,the JQuery technology is as the core in the front desk,while the background uses PHP which to implementation algorithm based on Python,and MySQL as database.The front desk can collect customer information including time window and demand information,which will be showed as the route in the front after processing,and at the same time various windows in front desk will display the entire path,the vehicle and the driver’s information in real time.