Route Optimisation For Mobility-On-Demand Systems With Ride-Sharing

Abstract

Privately owned cars are an unsustainable mode of transportation, especially in cities. New Mobility on Demand (MoD) services should offer a convenient and sustainable alternative to privately owned cars. Notable in this field is the recent uprise of ride-sharing services such as offered by companies like Uber and Grab. Such services, especially when allowing for multiple passengers to share a vehicle, could potentially be a valuable addition to existing modes of transport to offer fast and sustainable door-to-door transportation.

The optimisation of vehicle routes for a MoD fleet is a complex task, especially when allowing for multiple passengers to share a vehicle. Recent studies have presented algorithms that can optimise routes in real-time for large scale ride-sharing systems, but have left opportunities to further enhance fleet performance. The redistribution of idle vehicles towards areas of high demand and the utilisation of high capacity vehicles in a heterogeneous fleet has received little attention. This work presents a method to continuously redistribute idle vehicles towards areas of expected demand and an analysis of fleets with both buses and regular vehicles. Furthermore, a method is proposed to optimise vehicle routes while taking into account vehicle capacities and the future locations of vehicles in anticipation to predicted demand.

In simulations with historical taxi data of Manhattan, 99.8% of transportation requests can be served with a fleet of 3000 vehicles with an average waiting time of 57.4 seconds, and an average in-car delay of 13.7 seconds. Compared to earlier work, a decrease in walk-aways of 95% is obtained for 3000 vehicles, with a 86% decrease in average in-car delay and a 37% decrease in average waiting time. For a small fleet of 1000 small busses of capacity 8 still 84.6% of requests can be served with an average waiting time of 141 seconds and an average in-car delay of 269 seconds. In comparison to prior work, a decrease in walk-aways of 15% is obtained, with a 14% decrease in average in-car delay and a 2% decrease in average waiting time. A heterogeneous fleet of 1000 vehicles consisting of 500 buses and 500 regular vehicles using this new approach can serve approximately the same number of passengers as a homogeneous fleet of 1000 buses using earlier presented algorithms.