An Auction-Based Method for Decentralized Train Scheduling
Ungar, Lyle H.
MetadataShow full item record
CitationParkes, 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.
AbstractWe 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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4101015
- FAS Scholarly Articles