Partial evaluation in aircraft crew planning

ABSTRACT

In this paper we investigate how partial evaluation and program transformations can be used on a real problem, namely that of speeding up airline crew scheduling.Scheduling of crews is subject to many rules and restrictions. These restrictions are expressed in a rule language. However, in a given planning situation much is known to be fixed, so the rule set can be partially evaluated with respect to this known input.The approach is somewhat novel in that it uses truly static input data as well as static input data where the values are known only to belong to a set of values.The results of the partial evaluation is quite satisfactory: both compilation and running times have decreased by using it. The partial evaluator is now part of the crew scheduling system that Carmen Systems AB markets and which is in use at most of the major European airlines and in daily production.

REFERENCES

• AGPT91: R. Anbil, E. Gelman, B. Patty, and R. Tanga. Recent Advances in Crew-Pairing Optimization at American Airlines. Interlaces, 21(1):62-74, 1991.
• AHKW97: E. Andersson, E. Housos, N. Kohl, and D. Wedelin. Crew Pairing Optimization. In OR in Airline Industry. Kluwer Academic Press, 1997.
• Aug93: L. Augustsson. HBC User's Manual. Programming Methodology Group, Department of Computer Sciences, Chalmers, S-412 96 GSteborg, Sweden, 1993. Distributed with the HBC compiler.
• Has90: Erik Hasselberg. The Carmen Rule Language. Technical report, Carmen Systems AB, 1990.
• Hud92: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• Jon96a: Mark P. Jones. Hugs 1.3 user manual. Technical Report NOTTCS-TR-96-2, Department of Computer Science, University of Nottingham, August 1996.
• Jon96b: Mark P. Jones. The Hugs distribution. Currently available from http://www.cs.nott.ac.uk/ Department/Staff/mpj/hugs. htrd, 1996.
• RW93: Colin Runciman and David Wakeling. Heap profiling of lazy functional programs. Journal o/F, nctional Programming, 3(2):217-245, April 1993.
• TE96: E. Housos T. Elmroth. Automatic Subproblem Optimisation for Airline Crew Scheduling. Interlaces(to appear), 1996.
• Wed95: D. Wedelin. An algorith for large scale 0-1 integer programming with application to airline crew scheduling. Annals of Operations Research, 57:283-301, 1995.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

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

General Terms:
Design, Human Factors, Languages, Measurement, Performance, Theory

Keywords:
airline crew scheduling, generalized constant propagation, partial evaluation, program transformation