Research On Dynamic Vehicle Routing Problems:Modeling And Optimization Algorithms

Vehicle routing problem(VRP)is an important branch of combinational optimization problem.The algorithms about VRP have attracted much attention in computer science and OR communities,also play an important role in industrial areas.However,with the increasing complexity of traffic routes and the diversification and personalization of customer requirements,the basic VRP model is difficult to guide the logistics enterprises to carry out the distribution work.Modern logistics enterprises need to consider all aspects of the distribution route planning,such as customer dynamic request,time window,as well as the enterprise's own resources.The study of Dynamic VRP(DVRP)oriented for satisfying the customers' demands and optimizing the enterprise's own network has been paid more and more attention on theorists,and becomes a new hotspot.Based on the predecessors' research,this paper focuses on the research of DVRP including its extension and heuristic algorithm.The main researches are listed as follows:(1)The basic DVRP is discussed,and an improved monarch butterfly optimization algorithm is proposed.The algorithm uses natural number coding to continuously code the discrete problem for DVRP.A greedy strategy is adopted in the operation of the migration operator and the butterfly adjustment operator to accept the local solution;Whenever a new solution is generated,the 2-opt*perturb the new solution,to help the search process avoid falling into a local optimum,increase the diversity of searches,and speed up the search,resulting in a satisfactory solution.Experiments were performed on a the popular of 22 benchmark sets.The algorithm was able to update the best known solution for 12 instances,and the average performance was improved by at least 9.38%compared with the methods in the existing literature.The effectiveness of the algorithm,thus,is validated.(2)The DVRP with time windows(DVRPTW)is studied and a modified harmony search is proposed.The algorithm combines the advantages of the harmony search algorithm and the variable neighborhood descent algorithm.Compared with the classical harmony search,the coding method,the initial solution construction method,the improvisational new harmonic operation and the reception method are redefined;four kinds of neighborhood structures are designed to expand the search space;and information entropy is used to evaluate the quality of the population and prevent convergence prematurely;dynamically examine customer requests to improve search performance.The proposed method is compared with the existing algorithms on general benchmark test dataset.The experimental results show that the average rejection rate of the proposed algorithm is the least.Even under the same rejection rate,the vehicle travel distance and the number of vehicles used are better than the existing ones in most cases.Therefore,the effectiveness of the algorithm is verified.(3)The DVRPTW with limited vehicles is studied.An improved algorithm based on adaptive large neighborhood search is proposed.A series of special remove/repair strategies are designed;an initial score and weight is assigned for each strategy,and the score and weight is dynamically updated in the search process according to the current performance;and the remove/repair strategy is selected according to the weight by the roulette mechanism;A periodic perturbation speeds up the search speed.In addition,an ahead waiting strategy is designed for the insertion of dynamic customers.Finally,the performance of the algorithm is tested by the Lacker benchmark dataset.The minimum vehicles used in the 19 sets of instances is updated and the effectiveness of the algorithm is tested.(4)The DVRPTW under crowdsourcing is studied.In this problem,it is assumed that some of the customer's demands are transported by the logistics company's own fleet,and the other part is outsourcing to the third-party logistics platform,through the Occasional driver to receive the task to complete the transport distribution.To solve the problem,we propose a greedy randomized adaptive search procedure that involves the construction of initial solution by a greedy search,and the re-optimization by a local search based on variable neighborhood descent metaheuristics.Four neighbourhood structures are designed to escape from local optima and thus obtain a high quality solution.Also two kinds of compensation are proposed to verify the impact of different policies on transportation cost and customer satisfaction.The performance of the proposed procedure is extensively tested on the Lacker benchmarks and also on a real dataset by a delivery company.The computational results not only indicate the comparative effectiveness of the proposed method,but also the great potential of using occasional drivers to reduce delivery costs.(5)The parcel delivery platform based on crowdsourcing is developed.From the perspective of software development,the functional modules of the system are analyzed,the business process of package delivery under crowdsourcing conditions is designed,the related algorithm proposed in this paper is integrated,and the main interface and function modules of the package distribution platform are displayed.The platform can provide efficient logistics integration solutions for logistics companies using crowdsourcing for parcel distribution.