Model And Algorithm For Multiple-depot Vehicle Routing Problem With Different Supply Costs And Time Windows

In some huge product and logistics industries,due to the different cost of productive process or logistics and distribution method,the supply cost can be different to different distribution centers.In order to consider both the supply and transport costs in vehicle scheduling problem,and make the logistics cost minimization,carry out the multiple depot vehicle routing problem with the supply cost and time windows.The research includes of building the multiple depot vehicle routing problem based on the distribution production and marketing systems;Then in order to solve the mathematical model,considering the nature and characteristics of the multi-depot vehicle routing problem with supply cost and time windows,design the modified variable neighborhood search algorithm(VNS)by combining several neighborhoods and local improvement method.Finally,an example was given to test the model and algorithm.The specific research works are as follows:(1)Describing background and significance of the research,overview the status of vehicle routing problem,and show the main work content and technical route of this paper.(2)Analyzing the multiple depot vehicle routing optimization problem with different price and time windows.Giving the optimization objective and constraints,building the corresponding mathematical models and verifying the correctness of the model with a simple example.(3)Designing the improved variable neighborhood search algorithm to solve the model,giving the algorithm flow diagram,detailing the generation of initial solution,neighborhood design,Shaking process,Local Search process,the acceptance of principles and guidelines for termination processes.(4)Relax some constraints of the original problem,construct the Lagrangian relaxation problem,and design the lower bound gradient method to get the lower bound of the problem.Finally,giving some standard examples,calculating the lower bounds of the Lagrangian relaxation problem,and the optimal value of the original problem,analyzing the validity of the algorithm.