An Auction-Based Method for Decentralized Train Scheduling
Citation
Parkes, David C. and Lyle H. Ungar. 2001. An auction-based method for decentralized train scheduling. In AGENTS 2001: Proceedings of the Fifth International Conference on Autonomous Agents: May 28-June 1, 2001, Montreal, Canada, ed. J P Muller, Association for Computing Machinery, SIGGRAPH, SIGCH, ACM Special Interest Group on Artificial Intelligence, et al., 43-50. New York, N.Y.: ACM Press.Abstract
We present a computational study of an auction-based method for decentralized train scheduling. The method is well suited to the natural information and control structure of mod- ern railroads. We assume separate network territories, with an autonomous dispatch agent responsible for the ow of trains over each territory. Each train is represented by a self-interested agent that bids for the right to travel across the network from its source to destination, submitting bids to multiple dispatch agents along its route as necessary. The bidding language allows trains to bid for the right to enter and exit territories at particular times, and also to represent indifference over a range of times. Computational results on a simple network with straight-forward best-response bid- ding strategies demonstrate that the auction computes near- optimal system-wide schedules. In addition, the method appears to have useful scaling properties, both with the number of trains and with the number of dispatchers, and generates less extremal solutions than those obtained using traditional centralized optimization techniques.Other Sources
http://www.eecs.harvard.edu/econcs/pubs/trains01.pdfTerms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:4101015
Collections
- FAS Scholarly Articles [17828]
Contact administrator regarding this item (to report mistakes or request changes)