Online algorithm for dynamic dial a ride problem and its metrics

Abstract

In this paper, an online regret based dial-a-ride (OR-DARP) algorithm is introduced and its performance evaluated on an actual demand responsive transit (DRT) system. The innovative part of the algorithm is the design of the optimization engine. A signal communication scheme between the trip dispatcher and the algorithm is used to improve utilization of the available idle time that can then be devoted to the optimization engine. The basic concept is as follows: a. Every trip request is treated as an emergency request demanding an immediate answer, b. The optimization engine runs continuously, thereby consuming every idle time fragment unless interrupted by a new trip request. The trip data are real, and they are sourced from a DRT system operating at a municipality in northern Greece where a static dial-a-ride algorithm was used as the optimization engine. Given the fact that these trips data provide all trip details plus the show-up time (the most important feature for our study), these data are the ideal basis for an "a posteriori" evaluation of the proposed online approach. Another contribution of this paper is the identification of the critical parameters in the trade-off between benefits gained from continuing to optimize an online system versus the losses of non-served demands. This important issue when applying online algorithms has not been studied extensively in the literature so far (to the best of our knowledge). © 2016 The Authors. Published by Elsevier B.V.