Exact Algorithm Based On Discrete Time For Time-Dependent Green Vehicle Routing Problem With Time Windows

Air pollution is caused when certain substances are released into the atmosphere by human activities in sufficient concentrations to endanger the normal and comfortable life of human beings.Greenhouse effect is one of the hazards caused by air pollution.It causes the air temperature in the ground layer to increase,making the global climate change.The cause of the greenhouse effect is that the excessive carbon dioxide in the atmosphere absorbs the long-wave radiation from the ground.Reducing the carbon dioxide emission in life is an effective way to alleviate the greenhouse effect.In China,the carbon emission of transportation increased from 79.67Mt in 1985 to 887.34Mt in 2009,with an average annual increase of 10.56%.Road transportation has the highest carbon emission compared with air transportation,railway transportation and water transportation.It can be seen that reducing the carbon emission of highways transportation is of great significance to the control of air pollution.With the increasing awareness of environmental protection,more and more scholars begin to focus on the study of Green travel,and Green vehicle routing problem(GVRP)is one of them.In the actual operation of vehicles,the speed of vehicles is not fixed,but changes in a piecewise function according to different approximate Time periods in a day.Therefore,studies on time-dependent GVRP(TDGVRP)for green vehicles have emerged in recent years.In the case that the speed is time-dependent,the abstraction of the problem is more practical.The calculation of carbon emission is affected by the change of speed,and the carbon emission varies with the departure time of the vehicle.Therefore,the departure time of the vehicle is also within the scope of our decision.So far,all researches on TDGVRP have been solved by heuristic algorithm or meta-heuristic algorithm,and no corresponding exact algorithm has been developed.In this paper,the exact algorithm of time-dependent green vehicle routing problem with time Windows(TDGVRPTW)is studied.The main research contents of this paper are as follows:(1)This paper summarizes the related literature and the characteristics of TDGVRPTW.(2)On the premise that the speed is time-dependent,the green vehicle routing problem is analyzed.the TDGVRPTW is defined from the perspective of the relationship between carbon emission and vehicle departure time,and a new digraph is proposed to describe the TDGVRPTW problem.(3)An accurate algorithm for TDGVRPTW based on set partition model is developed.Combined with the characteristics of the problem,the feasible path was defined and the expansion of the feasible path was designed,and the dominance rules between the feasible paths were deduced for the elimination of non-optimal path.The set partition model was established to solve the problem and the accuracy of the algorithm was verified by theoretical proof and benchmark calculation experiment.(4)In order to solve large scale TDGVRPTW,branch-and-price algorithm is designed and developed.In this paper,we set up the restricted master problem model of the algorithm,deduce the pricing subproblem according to the master problem model,design the bidirectional labeling algorithm to solve the pricing subproblem,refer to the appropriate branch rules for solving the problem and conduct experiments with benchmark example to verify the accuracy and scale of the algorithm.