A proposed multiagent model for bus crew scheduling

ABSTRACT

Bus crew scheduling is a complex problem to solve because of the large number of resources that need to be managed, complexity of allocating crew shifts, rising cost of crew and unpredictability of traffic and crew availability. This causes a difficulty to maintain an optimal schedule. Existing systems are excellent in producing optimal or near optimal schedules. However, to maintain such optimality for day-to-day operations, crew scheduling systems need to extend their capabilities by enabling crew reassignment, a feature that is not currently available in currently existing automated scheduling systems. The aim of this research is to model the crew reassignment process using agents and simulate agents' behavior in order to establish ways of automating management of unpredictable events. The model should assist supervisor in managing everyday bus operations. The paper presents agents analysis and design using Gaia methodology.

References

1. Cheng, J. H., and Y. H. Chang. 1999. Application of a fuzzy knowledge base on bus operations under uncertainty. In Proceeding of the Fuzzy Systems Conference. 1355--1360. IEEE International.
2. Copley, G., J. Dodgson, M. Bright, D. Coombe, B. Davidson, and G. Barrett. 2003. Second assessment report: 10 year transport plan monitoring strategy. Hertfordshire, UK: Commission for Integrated Transport.
3. Desaulniers, G. 2002. Bus and driver scheduling in urban transit systems, {online}. Available via <http://www.ima.umn.edu/talks/workshops/11-11-15.2002/desaulniers/desaulniers.pdf>. {accessed June 13, 2004}.
4. Fores, S., L. Proll, and A. Wren. 2002. TRACS II: a hybrid IP/heuristic driver scheduling system for public transport. Operational Research Society, 53: 1093--1100.
5. Kwan, A. S. K., M. E. Parker, R. S. K. Kwan, S. Fores, L. Proll, and A. Wren. 2004. Recent advances in TRACS. In Preprints of the 9th International Conference on Computer-Aided Scheduling of Public Transport; San Diego, California, USA.
6. Rousseau J. M., and J. Y. Blais. 1985. HASTUS: an interactive system for buses and crew scheduling. In Proceedings on Computer-Aided Scheduling of Public Transport, ed. J. M. Rousseau, 45--60. North-Holland.
7. Shibghatullah, A. S., T. Eldabi, and G. Rzevski. 2006. The requirements for a dynamic bus crew scheduling system. In Proceedings of the 10th International Conference on Computer-Aided Scheduling of Public Transport, Leeds, UK.
8. Wooldridge, M., N. R. Jennings, and D. Kinny. 2000. The Gaia methodology for agent-oriented analysis and design. Autonomous Agents and Multi-Agent Systems. 3: 285--312.
9. Wren A, B. M. Smith, and A. J. Miller. 1985. Complementary approaches to crew scheduling. In Proceedings on Computer-Aided Scheduling of Public Transport, ed. J. M. Rousseau, 263--278. North-Holland.
10. Yunes, T. H., A. V. MOURA, and C. C. D. SOUZA. 2000. Solving very large crew scheduling problems to optimality. In Proceedings of the 2000 ACM symposium on Applied computing, 446--451. ACM Press.
11. Zambonelli, F., N. R. Jennings, M. J. Wooldridge. 2003. Developing multiagent systems: the Gaia methodology. ACM Transactions on Software Engineering and Methodology. 12: 317--370.

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making