Research On Green Vehicle Routing Problems Considering Time Factors In Urban Scenarios

Vehicle routing problem is a class of optimization problems,which aim is to construct a set of feasible routes and arrange schedules of the routes to minimize transportation cost.The correlative theories and methods have great application values for reducing logistic cost.The vehicle routing problem has been widely applied to many aspects in production and real life,such as goods delivery,ride-sharing service and school bus routing and great benefit has been gained.With the advance of the urbanization process and the increase of urban car ownership,traffic congestion has become the social focus of the cities in China.Meanwhile,environmental impact is also taken into account to arrange the routes and schedules.Hence,this dissertation studies the extensions of vehicle routing problem with time windows in urban scenarios,including problems considering factors of time-dependent travel speed,environmental cost,electric vehicles for goods distribution,and congestion tolls.The major results of this dissertation contain the following six aspects:(1)The current researches in the relative fields are surveyed by reviewing a large number of domestic and international monographs,journals,conference proceedings and technical reports.Firstly,the basic vehicle routing problems are summarized.Secondly,we focus on the status quo of time-dependent vehicle routing problems,especially the ones of vehicles under regular travel speed and uncertain travel time.Thirdly,the green vehicle routing problems from the perspective of low carbons and electric vehicles are introduced briefly.Finally,we introduce the status quo and model of adjustable robust optimization.(2)An algorithm is designed for checking the feasibility of a given route with complex constraints such as time windows for the problems in the dissertation.Firstly,based on temporal and spatial factors with insertion-removal-reinsertion operators,a parallel insertion algorithm is proposed to settle a dial-a-ride problem.The algorithm introduces the concept of decentralized factor between two requests,inserts the requests based on their time windows and geographical positions and determines the feasibility of a path when inserting a request to the path.Several experiments with randomly generated instances are conducted to show the effectiveness of the proposed algorithm.Moreover,due to the complex multiple scheduling constraints of dial-a-ride problems,it is hard to determine the feasibility of a given route.The feasibility testing algorithm of a given route is studied with time-dependent travel speeds and constraints of time windows,capacity,maximum ride time and maximum route duration.The feasibility testing algorithm has three phases,accompany with quadratic time complexity in the worst case.Finally,the algorithm is extended to checking the feasibility of the general vehicle routing problems in this dissertation.(3)For the routing problems in urban scenarios where customers having the same destination,the vehicle routing problem with gathering place which considers congestion periods,is proposed.The objective function of the problem accounts for the amount of green-house emissions,fuel,travel times and their costs.A two-phased algorithm based on set-partition method is developed.In the algorithm,the schedule of a fixed route is mainly studied.For a given route,a mixed integer linear program is formulated and a departure time and speed optimization heurisitic is described with comprehensive consideration of maximum ride time and time window constraints.Several experiments with randomly generated instances are conducted to show the effectiveness of the proposed algorithm.Finally,the effect of congestion and maximum ride time constraint is analyzed.(4)For the urban electric vehicle routing problem with congestion periods,a mixed integer linear programing formulation is presented and an adaptive large neighborhood search(ALNS)algorithm is designed.The proposed algorithm involves the removal and insertion strategies of customers and stations,mainly discusses the determination of recharge amount and the calculation of route cost.Finally,numerical experiment is designed using the data sets of instances with small and large scale generated from the benchmark instances.The performance of the ALNS is tested by comparing with the exact solutions of commercial software.Moreover,the computational results show that time-based congestion tolls significantly lead to fewer vehicles entering the morning and evening rush,which illustrates the outcome of the charge mode to relieve congestion.(5)Urban electric vehicle routing problems with waiting for recharging are studied.Two problems considering tolls based on congestion periods and congestion zones are proposed-The mixed integer linear programing formulations and the ALNS algorithms of the two problems are designed.Based on the ALNS algorithm proposed in Content(4),several new mechanisms including the removal and insertion operators,which consider the distance factor and time factor respectively,are applied to the ALNS of the congestion-zone-based model.Tests performed by comparing with the exact solutions as well as benchmark results of related problems demonstrate the performance of the ALNS.Finally,on the numerical experiment,the effect of waiting for recharging along with different charging modes is analyzed.(6)An adjustable robust electric vehicle routing problem under travel time uncertainty is studied.Considering the polyhedron uncertainty set,an exact algorithm based on row generation and set partitioning is designed to solve the model.Finally,on the numerical experiment,the performance of the designed algorithm is verified.Meanwhile,the price of robustness is tested under different levels of uncertainty as well as the effect of uncertainty on routing path is analyzed.