Research On Intercity Ride-sharing Route Optimization Problem

With the rapid development of economy,short and medium distance intercity travel demand is increasing.In recent years,intercity ride-sharing has been developed as a new rapid transport mode in China.Intercity ride-sharing is becoming more and more accepted by the public.In order to build intercity ride-sharing platform,we need to solve among others the problems of ride-sharing service scope,ride-sharing fare,vehicle routing optimization in the operation process.This paper focuses on the intercity ride-sharing route optimization problem,that is,how to arrange vehicles to serve riders with predetermined service scope and ride-sharing fare.Firstly,this paper introduces traditional dial-a-ride problem and its mathematical model.The model aims at minimizing the total cost of route travel,and considers passengers’ ride time constraints and route duration constraints.In solving the dial-a-ride problem,heuristic algorithm is much better than the exact algorithm in efficiency and high precision.This paper uses the variable neighborhood search algorithm to solve the dial-a-ride problem and introduces the framework of the algorithm,the generation of the initial solution,shaking and local search.Then,this paper describes the intercity rider-sharing route optimization problem.Different from the dial-a-ride problem,intercity travelers start and end in different cities,which makes differences in network construction,mathematical model and algorithm.This paper constructs a network graph.The nodes in the network graph are composed of rider’s origin and destination and vehicle’s origin and destination.A mixed integer linear programming model is constructed to maximize the revenue of rider-sharing platform,considering the service constraints of passengers and rest constraints of drivers.This paper uses the framework of variable neighborhood search algorithm.Considering the complexity of the problem,we require that the initial solution generated is feasible,and the solution is required to maintain the feasibility in the process of shaking and local search,so as to avoid than the algorithm can not get a feasible solution al last.In the initial feasible solution,the method of constructing routes in sequence is adopted.Five kinds of neighborhood operators based on trips are designed to shake the current solution.In local search,four local search operators are designed to improve the shaked solution.The experimental results show that the proposed algorithm is fast and effective in solving the intercity rider-sharing route optimization problem.Finally,this paper introduces the daily intercity rider-sharing route optimization problem.Different from the intercity rider-sharing route optimization problem,due to the high cost of a trip,vehicles are not allowed to drive empty on each trip.This makes it necessary to adjust the network construction,mathematical model and algorithm.This paper constructs a new network graph,which lacks of three kinds of empty driving arcs.In the definition of variables,the round trip and daily intercity rider-sharing route are defined.In the mathematical model,the calculation method of intercity rider-sharing route revenue is adjusted.In the algorithm,this paper adjusts the generation method of initial feasible solution,introduces the generation method of round trip and the generation method of daily intercity rider-sharing route.This paper uses four neighborhood operators in the intercity rider-sharing route optimization problem,but designs more strictly in the insertion or exchange of trips.This paper also uses the first three local search operators in intercity rider-sharing route optimization problem.In this paper,the first three local search operators in the intercity rider-sharing route optimization are used,and the fourth local search operator is adjusted.This adjustment is to add a round trip to a route instead of adding a trip to a route.The experimental results show that the algorithm designed in this paper is powerful and efficient in solving the daily intercity rider-sharing route optimization problem.At the same time,the paper also analyzes the sensitivity of the algorithm and intercity rider-sharing system.