Incremental Management of Oversubscribed Vehicle Schedules in Dynamic Dial-A-Ride Problems

Abstract

In this paper, we consider the problem of feasibly in-tegrating new pick-up and delivery requests into exist-ing vehicle itineraries in a dynamic, dial-a-ride problem (DARP) setting. Generalizing from previous work in oversubscribed task scheduling, we define a controlled iterative repair search procedure for finding an alterna-tive set of vehicle itineraries in which the overall so-lution has been feasibly extended to include newly re-ceived requests. We first evaluate the performance of this technique on a set of DARP feasibility benchmark problems from the literature. We then consider its use on a real-world DARP problem, where it is necessary to accommodate all requests and constraints must be relaxed when a request cannot be feasibly integrated. For this latter analysis, we introduce a constraint relax-ation post processing step and consider the performance impact of using our controlled iterative search over the current greedy search approach.