Dynamic Reoptimization of Transportation for Elderly and Disabled

Abstract

In this master thesis, we address the challenge of dynamically replanning transportation services for individuals with reduced mobility in the context of Valys: a paratransit agency in the Netherlands. High financial costs and the need for reducing greenhouse gas emissions have put pressure on paratransit agencies to improve their operational efficiency of transport services. Dynamic replanning can prevent changes from rendering the schedule created a day in advance inefficient, thereby averting delays, missed deliveries, and additional expenses. Furthermore, it can enhance flexibility for paratransit users, allowing same-day bookings instead of a day or more in advance.

We propose a Greedy Randomized Adaptive Search Procedure (GRASP) with evolutionary Path Relinking as a solution to the challenges of dynamic replanning. To the best of our knowledge, we are the first to apply GRASP in this field. Therefore, we provide numerical evidence for our GRASP in comparison with a widely used simulated annealing (SA) method. Comparative analysis with an SA approach demonstrates that our GRASP outperforms SA significantly in the setting of limited computation time, typically encountered in real-time planning scenarios. Our GRASP approach relies on high-quality start solutions for better overall solutions, and we provide qualitative insight into the influence of the start solution on the performance. At last, we demonstrate that our GRASP approach is better at frequent real-time replanning than an SA approach. Overall, our findings highlight the effectiveness of our GRASP in addressing the challenges of dynamic replanning.

Furthermore, we assess the opportunity gap of dynamic rescheduling with respect to not rescheduling, quantifying the potential improvement based on the cumulative number of changes. Our results show predictable gains ranging from 3.0 to 16.8 depending on the number of changes. These gains correspond to a decrease in service time from 150 to 600 hours per day. Our GRASP algorithm can effectively close the opportunity gap, improve service delivery, and enhance customer satisfaction.