liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Solving the flight perturbation problem with meta heuristics
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.ORCID iD: 0000-0002-5868-2388
2006 (English)In: Journal of Heuristics, ISSN 1381-1231, Vol. 12, no 1-2, 37-53 p.Article in journal (Refereed) Published
Abstract [en]

When there is a perturbation in a carefully constructed aircraft schedule, e.g. an aircraft breakdown, it is important to minimize the negative consequences of this disturbance. Here, a tabu search and a simulated annealing approach to the flight perturbation problem are presented. The heuristics use a tree-search algorithm to find new schedules for the aircraft, and utilize a path relinking strategy to explore paths between structurally different solutions. The computational results indicate that the solution strategies, especially the tabu search, can be successfully used to solve the flight perturbation problem.

Place, publisher, year, edition, pages
2006. Vol. 12, no 1-2, 37-53 p.
Keyword [en]
Aircraft recovery - Irregular operations - Operational airline scheduling - Simulated annealing - Tabu search - Path relinking
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-17062DOI: 10.1007/s10732-006-4833-4OAI: diva2:201519
The original publication is available at Tobias Andersson Granberg, Solving the flight perturbation problem with meta heuristics, 2006, Journal of Heuristics, (12), 1-2, 37-53. Copyright: Springer Science Business Media Available from: 2009-03-04 Created: 2009-03-04 Last updated: 2013-10-15
In thesis
1. Decision support tools for dynamic fleet management: applications in airline planning and ambulance logistics
Open this publication in new window or tab >>Decision support tools for dynamic fleet management: applications in airline planning and ambulance logistics
2005 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this work, decision support tools for dynamic fleet management problems are developed. The operational management tasks include dispatching, supervising and sometimes reconstructing the vehicle schedule. These tasks are often complex, while the time available to complete them is short. Therefore, decision support tools assisting the controller can be of great service.

Two studies on dynamic fleet management problems are presented. The first concerns airline planning and the problem of how to handle schedule perturbations. The second study is within the field of ambulance logistics, with focus on operational ambulance control.

For an airline, the flight perturbation problem arises when it is impossible to continue executing the original aircraft schedule, e.g. due to an aircraft breakdown. The flight controller then has to decide whether some flights have to be delayed or cancelled, or perhaps flights have to be reassigned to new aircraft. This is done in order to find an attainable, cost effective solution, where the airline can continue to serve the passengers. In this work, a decision support tool that can repair the aircraft schedule is suggested. The tool is based on a multicommodity network flow model with side constraints. A number of different solution strategies are suggested for the model, including heuristics based on column generation and meta heuristics utilizing path relinking. Computational tests show that several of the solution algorithms find near optimal solutions within a few seconds.

Ambulance logistics comprises most aspects of managing an efficient ambulance health care. This involves both emergency medical services and patient transportations. Controlling a fleet of ambulances includes deciding which ambulance to dispatch to a call. The controller also has to ensure that most or all parts of the area of responsibility can be reached by an ambulance in a short time. This is referred to as maintaining an adequate level of preparedness in the area. In this work, a way of calculating the preparedness is presented. It is incorporated into a number of decision support tools, including a dispatch tool and a relocation tool. The dispatch tool can suggest which ambulance to assign to a new call. The relocation tool suggests a way of relocating the ambulances, i.e. sending them to new locations, to increase the level of preparedness in the area. A simulation tool is also developed and used to study the effect of dynamically relocating ambulances. Furthermore, it is used to test if new locations for the ambulance stations will affect the waiting periods for the patients. The results show that the decision support tools have a positive effect on the system performance.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2005. 64 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 942
National Category
Engineering and Technology
urn:nbn:se:liu:diva-28405 (URN)13541 (Local ID)91-85297-91-7 (ISBN)13541 (Archive number)13541 (OAI)
Public defence
2005-05-20, K3, Kåkenhus, Campus Norrköping, Linköpings universitet, Norrköping, 13:15 (English)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2013-10-15Bibliographically approved

Open Access in DiVA

fulltext(544 kB)352 downloads
File information
File name FULLTEXT02.pdfFile size 544 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Andersson Granberg, Tobias
By organisation
Department of Science and TechnologyThe Institute of Technology
In the same journal
Journal of Heuristics
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 353 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 174 hits
ReferencesLink to record
Permanent link

Direct link