Finding Optimal Routes For Ride Sahring Vehicles Based On State-space-time Network Representations

With the urbanization process,the number of urban residents and personal activities are increasing rapidly.Which renders the resource-constrained transportation systems still facing severe traffic congestion problems.Driving-alone is a common phenomenon in the current society.It occupies a large amount of traffic resources,leads to inefficient usage of vehicles and exacerbates traffic congestion.However,optimized and coordinated ride-sharing traffic modes can utilize limited vehicle and driver resources efficiently and meet the time-sensitive transport service requests at the same time.With the populartion of ride-sharing mode among the piblic,reducing the operation cost of service vehicles,meeting the traveling requirements,offering passengers a good traveling experience and improving passenger satisfaction could make great contributions to the sustainable development of ride-sharing mode and resource conservation and mitigation of the status of quo of urban traffic congestion.Vehicle routing problem has been obtained close attention by domestic and foreign experts and scholars since Dantzig and Ramser first proposed it in 1959.They have made a lot of contributions in this field from the aspects of models and solving algorithms.During the research,many variants have been brought up that extends the VRP problems.The study of vehicle routing problem can optimize the routes of service vehicles in order to minimize the operation costs and maximize the interests.It also can provide methods of the efficient use of existing transportation resources and ease traffic jam.Taking dynamic road tavel time and time windows of passengers and vehicles into consideration makes the studying situation more suitable for the real world and more accurate to simulate the ride-sharing vehicle routing problems.Vehicle routing problem is a combinatorial optimization problem,and it is a NP-hard problem.The general modelings are integer programming or mixed integer programming problem.The objective of the models could be minimize the total driving distance or cost.Branch-and-cut algorithm,cutting plane method and heuristic algorithm are applied to solving the problem generaly.In this paper,vehicle routing problem with time window with pickup and delivery based on the state-space-time network will be studied and Lagrangian relaxation solution framework will be applied to solve it.In this paper,state-space-time network is constructed as fundation.This network is added with a system state dimension based on the two-dimension space-time network,which can precisely represent the passenger-carring state and the state transition of sharing service vehicles.Based on the established state-space-timenetwork,a multi-commodity flow model is constructed aming at the specific research contents.Because of the complexity of the model,the computation processes face computational challenges when dealing with large data sets.Therfore,Lagrangian multipliers will be introduced to relax the complex constraint into the objective function to reformulate the problem to an easily-solved relaxation problem.The basic idea of Lagrangian relaxation is to move the difficult constraint into the objective function and keep the linear the objective function.As a result,an easily-solved problem could be obtained.And the relaxation problem can be solved by solving the Lagrangian dual problem by taking the Lagrangian multipliers as variables.Then Lagrangian decomposition will transform the primal problem into a series of time-dependent single vehicle routing problems.Dynamic programming will be utilized to solve the single vehicle routing problems.When solving the Lagrangian dual problem,subgradient algorithm will be applied to update the multipliers.Lagrangian relaxation algorithm consists of two parts,one is to provide the lower bound of the primal problem,and the other one is to evolve into the Lagrangian relaxation heuristic algorithm to obtain the upper bound.Some efficient rules are offered in the paper to reduce the research space during the computational process.Then,the simple scenarios and complex scenarios will be tested on the GAMS model system to test the effectiveness of the proposed algorithm.