An Efficient Insertion Heuristic for On-Demand Ridesharing Services

In recent years, several ridesharing operators have launched their services across the globe. For these services, mobility requests arrive dynamically and have to be realized with a limited number of vehicles. The problem of request acceptance and route planning can be modeled as Dynamic Dial-a-Ride Problem (DDRP). Due to the limited transportation capacity of the shared vehicles, an important objective of the new service operators is to maximize the number of accepted requests. Since not all requests can be fulfilled, it is necessary to inform passengers immediately about the acceptance or rejection of their request. One way to achieve this is via feasibility check of the DDRP, which in this case must be performed within a very short computing time. The aim of this contribution is to examine the trade-off between computing time and solution quality as well as the effects of rescheduling during the feasibility check under realistic conditions of a typical urban on-demand ridesharing service. For this purpose, a Large Multiple-Neighborhood Search is proposed as an efficient approach to solve the DDRP. The analysis of different computing time limitation’s as well as the performance evaluation of the developed heuristic is based on computational simulation.