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

Zack Rubinstein, Stephen Smith, and Laura Barbulescu
Proceedings 26th Annual Conference of the Association for the Advancement of Artificial Intelligence (AAAI 2012), Montreal CA, July 2012., July, 2012.


Download
  • Adobe portable document format (pdf) (115KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Notes
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory
Associated Project(s): Real-Time Scheduling of ACCESS Paratransit Transportation

Text Reference
Zack Rubinstein, Stephen Smith, and Laura Barbulescu, "Incremental Management of Oversubscribed Vehicle Schedules in Dynamic Dial-A-Ride Problems," Proceedings 26th Annual Conference of the Association for the Advancement of Artificial Intelligence (AAAI 2012), Montreal CA, July 2012., July, 2012.

BibTeX Reference
@inproceedings{Rubinstein_2012_7048,
   author = "Zack Rubinstein and Stephen Smith and Laura Barbulescu",
   title = "Incremental Management of Oversubscribed Vehicle Schedules in Dynamic Dial-A-Ride Problems",
   booktitle = "Proceedings 26th Annual Conference of the Association for the Advancement of Artificial Intelligence (AAAI 2012), Montreal CA, July 2012.",
   month = "July",
   year = "2012",
   number= "CMU-RI-TR-",
}