Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Airline crew scheduling using Potts mean field techniques

Lagerholm, Martin LU ; Peterson, Carsten LU and Söderberg, Bo LU (2000) In European Journal of Operational Research 120(1). p.81-96
Abstract

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.... (More)

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)3. 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.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
keywords
Neural networks, Optimization, Transportation
in
European Journal of Operational Research
volume
120
issue
1
pages
16 pages
publisher
Elsevier
external identifiers
  • scopus:0004654743
ISSN
0377-2217
language
English
LU publication?
yes
id
f62157f1-7ef3-4dbc-89cc-4aaae22669c6
date added to LUP
2016-10-03 19:09:44
date last changed
2024-01-04 13:37:32
@article{f62157f1-7ef3-4dbc-89cc-4aaae22669c6,
  abstract     = {{<p>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)<sup>3</sup>. 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.</p>}},
  author       = {{Lagerholm, Martin and Peterson, Carsten and Söderberg, Bo}},
  issn         = {{0377-2217}},
  keywords     = {{Neural networks; Optimization; Transportation}},
  language     = {{eng}},
  month        = {{01}},
  number       = {{1}},
  pages        = {{81--96}},
  publisher    = {{Elsevier}},
  series       = {{European Journal of Operational Research}},
  title        = {{Airline crew scheduling using Potts mean field techniques}},
  volume       = {{120}},
  year         = {{2000}},
}