An Improved Exact Algorithm Based On Discrete Time For Solving Time-Dependent Green Vehicle Routing Problem

With the progress of science and technology,vehicles have become an indispensable means of transportation in today’s society.In China,according to statistics,32.14 million new motor vehicles were registered in 2019,with a vehicle population of 348 million,including 220 million small passenger vehicles.The number of vehicles is huge,which causes the problem of road congestion.As a result,the carrying capacity of roads have become increasingly strained,especially during rush hours,when congestion becomes more pronounced.It adds an extra amount of travel time to the traffic jam,as well as the extra carbon emissions caused by the traffic jam.Therefore,how to reduce driving time cost and carbon emissions has become an urgent problem to be solved.In the actual situation,the driving speed cannot be constant due to the influence of traffic pressure and other factors.As the rush hour of the day varies from the idle hour on the road,so does the speed.Therefore,Time-dependent green vehicle routing problem(TDGVRP)has become the research direction of many scholars.It is more realistic to consider different speed of vehicle at different time.Different from the constant speed of traditional VRP,the travel cost can be calculated more accurately in the case of time dependence.Up to now,all the studies on TDGVRP have only carried out complete discretization of time for calculation.This thesis studies the vehicle routing problem under time dependence.Relevant research contents are as follows:(1)This thesis summarizes the related literature and the characteristics of TDGVRP.(2)According to the characteristics of time-dependence,the relevant definitions and principles in TDGVRP are proposed,and these principles are proved.(3)Based on the travel cost-time relation function of TDGVRP,the selection of vehicle’s departure time is improved.Only part of the departure time needs to be discretized and it can improve the accuracy of the solution.(4)In order to solve large scale of TDGVRP,branch-and-price algorithm is designed and developed.We set up the restricted master problem model of the algorithm,deduce the subproblem according to the master problem model,design the labeling algorithm to solve the subproblem.The benchmark example is used to verify the accuracy and scale of the algorithm.