Path-flexible Vehicle Routing And Scheduling Problem With Inaccessible Arc Time Windows

In order to alleviate the increasingly severe traffic congestion and environmental pollution,various local governments in China have successively deployed temporal access restriction policies for urban freight vehicles,forbidding them to enter specific areas(or roads)during peak hours or the daytime of weekdays.These will definitely influence the urban logistics distribution efficiency and cost.In spite of this,research on urban logistics vehicle routing problem with such restrictions is very limited;and these limited research has routingly ignored some critical attributes(such as multiple paths between customers),making the resultant models and their algorithms lack theoretical and practical reference value.The paper addresses the vehicle routing and scheduling problem with inaccessible arc time windows and path flexibility,and conducts in-depth research on problem modeling,algorithm design,and numerical analyses under fuel and electric vehicles separately.It is expected that these works can provide a basis for decision-making to solve real-world problems and theoretical reference for subsequent research.The main work of this paper is as follows:(1)The paper addresses the path-flexible vehicle routing and scheduling problem with inaccessible arc time windows(PFVRSP-In ATW).In view of access restrictions and the fact that there are often multiple paths linking two diversely located sites for flexible selection,the paper establishes a mixed integer linear programming model with objective to minimize total cost(including vehicle fixed costs,travel cost and time cost)under a set of constaints,including,but not limit to,the load constraints,time window constraints,inaccessilbe time windows constraints.After that,a hybrid metaheuristic is developed to optimize the customers' visiting order.Under the framework of the hybrid algorithm,an iterative switching heuristics algorithm is designed for path selection;and a revised forward rime slack algorithm is proposed for vehicle scheduling decision by converting the travel time on restricted paths to time-dependent travel time which still satisfies the first-in-first-out property.Finally,extensive numerical experiments are performed on a newly constructed test problem set to demonstrate the efficiency and robustness of the algorithm.(2)Based on above PFVRSP-In ATW,the path-flexible electric vehicle routing and scheduling problem with inaccessible arc time windows(PFEVRSP-In ATW)is further studied;and a mixed linear integer programming model with the goal of minimizing the total cost is established.The model additionally considers the vehicle power constraints,and allows vehicles to charge outside(but it will induce extra cost).Then,based on the algorithmic framework developed for PFVRSP-In ATW,the charging plan is improved prior via a charging optimization precedure,and then optimized by a labeling method in further.Meanwhile,an iterative switching heuristics and a revised forward time slack algorithm are used for path selection and vehicle scheduling,so as to obtain a complete distribution plan covering distribution routes,path utilization and vehicle schedules.Finally,extensive numerical experiments are performed on a constructed test problem set to demonstrate the algorithmic efficiency and robustness.These research may provide scientific decision support for logistics companies to optimize the distribution plan under temporal acess restrictions,and then contribute to the sustainable development of urban society,economy and environment.