The Robotics Institute

Carnegie Mellon Robotics Institute

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 deﬁne a controlled iterative repair search procedure for ﬁnding an alterna-tive set of vehicle itineraries in which the overall so-lution has been feasibly extended to include newly re-ceived requests. We ﬁrst 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-",
}

The Robotics Institute

Menu