Airline crew scheduling using Potts mean field techniques

Summary, in English

A novel method is presented and explored within the framework of Potts neural networks for solving optimization problems with a non-trivial topology, with the airline crew scheduling problem as a target application. The key ingredient to handle the topological complications is a propagator defined in terms of Potts neurons. The approach is tested on artificial problems generated with two real-world problems as templates. The results are compared against the properties of the corresponding unrestricted problems. The latter are subject to a detailed analysis in a companion paper (M. Lagerholm, C. Peterson, B. Söderberg, submitted to European Journal of Operational Research). Very good results are obtained for a variety of problem sizes. The computer time demand for the approach only grows like (number of flights)³. A realistic problem typically is solved within minutes, partly due to a prior reduction of the problem size, based on an analysis of the local arrival/departure structure at the single airports. To facilitate the reading for audiences not familiar with Potts neurons and mean field (MF) techniques, a brief review is given of recent advances in their application to resource allocation problems.

• Författare: Martin Lagerholm; Carsten Peterson; Bo Söderberg
• Avdelning/ar: Computational Biology and Biological Physics
• Publiceringsår: 2000-01-01
• Språk: Engelska
• Sidor: 81-96
• Publikation/Tidskrift/Serie: European Journal of Operational Research
• Volym: 120
• Issue: 1
• Dokumenttyp: Artikel i tidskrift
• Förlag: Elsevier
• Nyckelord: Neural networks; Optimization; Transportation
• Aktiv: Published
• ISBN/ISSN/Övrigt: ISSN: 0377-2217