Recovery management for a dial-a-ride system with real-time disruptions

The problem considered in this work stems from a non-profit organization in charge of transporting patients from their home to medical appointment locations and the other way around. The aim of this work is to propose a reactive algorithm for this dial-a-ride problem to adapt the planning in order to manage real-time disruptions, such as patient delays or appointment cancellations. Our work aims at adapting the current solutions so as to manage the disruptions while accounting for three potentially conflicting objectives, namely: satisfying all patient requests, to the best possible extent; limiting the planning changes, so as to avoid confusion for the drivers and patients; and minimizing the patient excess journey duration, as a measure of service quality. Moreover, the dispatcher should be able to react quickly, so as to take care of the patients as early as possible and to define the recourse action before the next disruption occurs.
The proposed reactive algorithm explores small neighborhoods of the current solution and very progressively enlarging these neighborhoods in order to restore feasibility when a perturbation occurs. As a secondary objective reflecting the quality of the modified plan, when feasibility is restored, we try to minimize the excess journey time ratio of the patients. Disruption scenarios have been generated and discrete event simulation has been used to observe the behavior of the algorithm on several types of instances.