Research On The Electric Vehicle Routing Problem With Simultaneous Pickup And Delivery Using Space-Time-State Network

Electric vehicles(EVs)are environmental emerging transportation modes that have advantages of less noise pollution,less air pollution and energy saving.With the improvement of charging facilities and the introduction of relevant national friendly policies,more and more logistics companies have increased the proportion of electric vehicles in logistics links.Compared with fuel vehicles,the charging of electric vehicles is quite time-consuming.Even using fast charging technology,it will take several hours to fully charge,which brings range anxiety to drivers.To ensure the energy efficiency,logistics companies need to incorporate the impacts of customer service models and charging strategies into the optimization of electric logistics resource.The electric Vehicle Routing Problem with Simultaneous Pickup and Delivery(EVRPSPD)proposed by this paper integrates the optimization of vehicle routing,customer service modes of Simultaneous pickup and delivery and recharging strategies of parital charging for the EVs.This problem allows customers to have both pickup and delivery requests.The vehicle must serve the customer within the corresponding time window,and can detour to a recharging station to ensure that the power can maintain the remaining route.To minimize the total transportation cost by rational route planning,the specific research work is as follows:(1)To describe the vehicle routing problem more comprehensively,this paper introduces the benefits of using high-dimensional networks to study VRPs by comparing the characteristics and usage scenarios of the space network,the space-time network and the space-time-state network.Based on this,this paper constructs a space-time-state network for the EVRPSPD.The hyperdimensional network takes discrete battery’s remaining electricity and continuous remaining pickup and delivery capacity as the state dimension.Based on the constructed network,the state transition rules when vehicles travel different types of links will be introduced.The construction method of the hyperdimensional network will also be mentioned.The space–time-state network can be utilized to optimize the resource allocation of the power logistics network operation effectively in both the time and space dimensions at the same time.(2)A multi-commodity network flow model for EVRPSPD will be established based on the hyperdimensional network.The objective function of this model is to minimize the total transportation cost.Constraints include vehicle routing constraints,customer’s request satisfaction constraints,limited recharging station capacity constraints,and binary variable constraints.When modeling under the space-time-state network,time-related constraints(such as customer time window constraints)and state-related constraints(such as power constraints,capacity constraints)have been embedded in the underlying network,so the optimization model is more streamlined.This paper will also analyze the complexity of the constraints of the given model.(3)The proposed model will be decomposed into a sequence of resource constrained least cost path subproblems by using the alternating direction multiplier method(ADMM)decomposition framework.The decomposition framework includes Lagrangian Relaxation technique(LR)and Augmented Lagrange Multiplier method(ALR),where the solution of LR is to obtain the lower bound of the problem,and the solution of ALR is to obtain the upper bound of the problem.The subproblem will be solved effectively by using improved dynamic programming algorithm.The solution quality can be guaranteed by calculating the optimality gap between the best lower bound and upper bound for each iteration.(4)In this paper,several different scenarios are constructed to test the effectiveness of the proposed model and algorithm.The effect of the quadratic penalty parameter will be tested on the example of a simple 7-node network.The influence of the input parameters related to the charging strategy will also be tested on the simple 7-node network.Based on the Sioux Falls network and the Chicago Sketch network,the feasibility of the algorithm in solving different scale networks and service modes will be tested.two different service scenarios will be tested.Finally,The effectiveness of the model and algorithm will be verified based on the real network of old town in Suzhou.