An auction-based method for decentralized train scheduling

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.

REFERENCES

• 1: A. Andersson, M. Tenhunen, and F. Ygge. Integer programming for auctions with bids for combinations. In Proc. 4th Int. Conf. on Multi-Agent Systems (ICMAS-00), 2000.
• 2: Craig Boutilier , Moisés Goldszmidt , Bikash Sabata, Sequential Auctions for the Allocation of Resources with Complementarities, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.527-523, July 31-August 06, 1999
• 3: P. J.Brewer and C. R. Plott. A binary con ict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks. Int. Journal of Industrial Organization, 14:857-886, 1996.
• 4: M. M. Bykowsky, R. J. Cull, and J. O. Ledyard. Mutually destructive bidding: The FCC auction design problem. J. of Regulatory Economics, 2000.
• 5: S. F. Hallowell. Optimal Dispatching Under Uncertainty: With Application to Railroad Scheduling. PhD thesis, The Wharton School, University ofPennsylvania, 1993. OPIM TR 93-12-02.
• 6: D. R. Kraay andP. T. Harker. Real-time scheduling of freight railroads. Transportation Research-B, 29B(3):213-229, 1995.
• 7: David Kraay , Patrick T. Harker , Bintong Chen, Optimal pacing of trains in freight railroads: model formulation and solution, Operations Research, v.39 n.1, p.82-99, Jan./Feb. 1991 [doi>10.1287/opre.39.1.82]
• 8: P. Kreuger, M. Carlsson, and J. Olsson. The TUFF train scheduler- trip scheduling on single-track networks. In CP97 Workshop on Industrial Constraint-Directed Scheduling, Linz, Austria, 1997.
• 9: Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
• 10: David C. Parkes, iBundle: an efficient ascending price bundle auction, Proceedings of the 1st ACM conference on Electronic commerce, p.148-157, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337032]
• 11: S. J. Rassenti, V. L. Smith, and R. L. Bulfin. A combinatorial mechanism for airport time slot allocation. Bell Journal of Economics, 13:402-417, 1982.
• 12: M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason. Auction protocols for decentralized scheduling. Games and Economic Behavior, 2000. To appear.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory