Research on Optimization of Vehicle Routing Problem for Ride-sharing Taxi

In order to improve transportation efficiency of taxi and mitigate urban traffic congestion, it is necessary to carry out ride-sharing strategy which contributes to reducing operating cost and saving road resources. This study focuses on the routing optimization of ride-sharing taxis, in which interests of both taxi drivers and passengers are taken into account. Minimization of operating cost and maximization of customer satisfaction are considered as the objective, and travel mileage, waiting time and extra riding time due to ride-sharing are used to quantify them respectively. Routing optimization model for ride-sharing taxis is established and then appropriate simulated annealing algorithm satisfying constraints of the model proposed is designed. At last, a computational experiment is conducted to verify the model and the result shows that this method is able to save 19% mileage as well as 66% taxis available.