A Least-Expected Cost Vehicle Routing Problem With Pickup And Delivery With Time Window Based On Stochastic Time-Space-State Network

In recent years,the rapid development of mobile payment and the continuous expansion of the size of the city have led to the rapid rise of online car-hailing,which has played a important role in the urban transportation system due to its convenient booking,convenient payment,strong accessibility,diverse services and long business hours.Among them,the car-sharing service is popular because of its characteristics of multi-person sharing,cost sharing,and discount sharing.It is strongly advocated by the government for its advantages of easing traffic congestion and energy consumption.However,in the online car sharing scenario,due to the influence of many complex factors(such as bad weather,car breakdown,road construction,traffic accidents,etc.),the link travel time is highly uncertain,and the link travel time cannot be accurately measured.On the one hand,for the same link,the difference in the moment when the vehicle enters the link may cause the difference in the travel time.On the other hand,in different historical dates,even if the moment of entering the link is the same,the travel time of the link may be different.If the vehicle routing is based on single-day data without considering the comprehensive situation of multiple days,it will inevitably cause the shortest path planned to deviate from the actual shortest path,and increase the phenomenon of vehicle detours and empty vehicle travel,resulting in a waste of vehicle passenger space,increasing the cost of the enterprise and affect the stability of the dispatch system,and even increase traffic congestion.Therefore,under the existing traffic conditions,how to provide optimized routes to improve the efficiency and quality of drivers picking up passengers has become a key functional part of the carpool service information system,and has also become an important scientific issue in the field of transportation.From the perspective of the enterprise,effectively improving the service quality and operating efficiency of the enterprise while minimizing the operating cost is its core appeal.This paper carried out optimization research on vehicle routing in the online car sharing scenario.Based on a large amount of historical travel data,a 0-1 integer programming model is constructed,the objective function is the minimum expected travel cost,and the complex model is reconstructed at the same time,then the model is relaxed using the Lagrangian relaxation method,and then the model is solved using an improved dynamic programming algorithm.Finally,the effectiveness of the model and algorithm are evaluated by using different scenarios of calculation examples.It is designed to provide vehicles with highly robust routing guidance to ensure that they can pick up passengers within the designated boarding time window of multiple passengers,and deliver passengers to their destinations within the passenger’s designated boarding time window.Finally,the vehicle returns to the warehouse within the driving time window.The research has certain theoretical significance and practical value for improving user satisfaction,operating efficiency of online carpooling system,and ability to match supply and demand.The specific content of this article is detailed as follows:Describe the stochastic time-space-state network.This paper constructs a stochastic time-space-state network,where each day corresponds to a time-space-state network.This paper will elaborate on the minimum expected vehicle routing problem in the online car sharing scenario,and will use a simple example to elaborate on this problem.Subsequently,this paper will introduce the transition of the state,the number of vehicle carrying states.Construct a stochastic time-space-state minimum expected travel cost routing model.In order to build a more accurate model of the problem under study,this paper adds corresponding virtual nodes and virtual links on the basis of the constructed time-space-state network.Then a mathematical model with the objective function as the minimum expected travel cost is constructed.The model constraints include the traffic conservation constraints of each node;each passenger’s ride request must be satisfied,and there is only one vehicle service constraint;the same physical path constraint across different dates;and binary variable constraints.Reformulate the model.Since this study considers a large amount of historical travel data,the same physical path constraint across different dates is constructed in the above model.This constraint is based on multiple equation constraints and needs to be reconstructed.Make the new constraint easy to be absorbed into the objective function by Lagrangian relaxation method.The Lagrangian relaxation method relaxes the original model.According to the complexity of the model built in this paper,it faces computational challenges when dealing with large-scale data sets.Therefore,this paper introduces Lagrange multipliers to relax the complex constraints into the objective function,and then decomposes the relaxation model into a series of time-dependent shortest path sub-problems.Algorithm for solving relaxation model.Since this paper considers data from different dates in history,when solving sub-problems after decomposition,the dynamic programming algorithm needs to be improved to make it suitable for solving the model in this paper.Example analysis.This research constructs several different scenarios for simple network and real network respectively to prove the correctness of the model and the effectiveness of the algorithm.