Advanced

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. © 2000 Elsevier Science B.V. All rights reserved.

(Less)
Please use this url to cite or link to this publication:
author
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?
no
id
f62157f1-7ef3-4dbc-89cc-4aaae22669c6
date added to LUP
2016-10-03 19:09:44
date last changed
2017-02-26 04:41: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. © 2000 Elsevier Science B.V. All rights reserved.</p>},
  author       = {Lagerholm, Martin and Peterson, Carsten and Söderberg, Bo},
  issn         = {0377-2217},
  keyword      = {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},
}