Skip to main content
Research Article
01 December 2012

Metaheuristic algorithms for the simultaneous slot allocation problem

Abstract

In this study, the authors propose the formalisation of the Simultaneous Slot Allocation Problem (SSAP), that extends, in two directions, the current way of allocating airport slots in Europe. The SSAP requires, first, to perform the slot allocation at all airports simultaneously and, second, to respect airspace sector capacities. The authors solve the SSAP with two algorithms based on metaheuristics, namely Iterated Local Search and Variable Neighborhood Search, and with an algorithm based on an integer linear programming model. They compare these algorithms on randomly generated instances and show that for small instances metaheuristics are competitive with the integer linear programming model. Nevertheless, the integer linear programming model is unable to solve medium or large instances because of memory and computation time requirements. Metaheuristics, instead, can deal with large instances, allocating slots to more than 99.8% of flights.

Get full access to this article

View all available purchase options and get full access to this article.

References

1.
Barnhart C., Belobaba P., and Odoni A. Applications of operations research in the air transport industry Transp. Sci. 37 4 368-391 2003
2.
Eurocontrol Experimental Centre: Long-Term Forecast: IFR Flight Movements 2008–2030, v1.0. Forecast prepared as part of the Challenges of Growth 2008 project, Brussels, Belgium, 2008
3.
Brooker P. SESAR and NextGen: investing in new paradigms J. Navig. 61 195-208 2008
4.
ACI Europe position on the proposed revision of the Council Regulation (EEC) No 95/93 on common rules for the allocation of slots at Community airports Presentation on the TRAN Meeting at the European Parliament 25 March 2009 Strasbourg, France
5.
European Commission. Council Regulation (EEC)oNo 95/93 of 18 January 1993 on common rules for the allocation of slots at Community airports, 1993
6.
Bennell J.A., Mesgarpour M., and Potts C.N. Airport runway scheduling 4OR, Q. J. Oper. Res. 4 2 115-138 2011
7.
D'Ariano A., D'Urgolo P., Pacciarelli D., and Pranzo M. Optimal sequencing of aircrafts take-off and landing at a busy airport 2010 13th Int. IEEE Conf. on Intelligent Transportation Systems (ITSC) 2010 1569-1574
8.
D'Ariano A., Pistelli M., and Pacciarelli D. Aircraft retiming and rerouting in vicinity of airports Proc. Second Int. Conf. on Models and Technology for Intelligent Transportation Systems (MT-ITS 2011) 2011 1-5
9.
Zografos K.G., Salouras Y., and Madas M.A. Dealing with the efficient allocation of scarce resources at congested airports Transp. Res. C, Emerg. Technol. 21 1 244-256 2012
10.
Kösters D.: Study on the usage of declared capacity at major German airports, 2007, available at http://www.eurocontrol.int/prc/gallery/content/public/Docs/FINAL_REPORT_Study_Capacity_Usage.pdf
11.
NERA Economic ConsultingoStudy to assess the effects of different slot allocation schemes, 2004, available at http://www.nera.com/67_4921.htm
12.
DotEcon Ltd.: Alternative allocation mechanisms for slots created by new airport capacity, 2006, available at http://www.dft.gov.uk/pgr/aviation/airports/alternativeallocationmechani.pdf
13.
Fukui H. An empirical analysis of slot trading in the Unites States Transp. Res. B 44 330-357 2010
14.
Verhoef E.T. Congestion pricing, slot sales and slot trading in aviation Transp. Res. B 44 320-329 2010
15.
de Wit J., Burghouwt G.: The impact of secondary slot trading at Amsterdam Airport Schiphol, 2007, available at http://www.seo.nl/binaries/publicaties/rapporten/2007/957.pdf
16.
Holt D., Meaney A., Noble R., Riley C., and Shaw A. Assessing the welfare impact of the introduction of secondary slot trading at community airports European Transport Conf. 2007 2007
17.
Mott MacDonald Limited: Study on the impact of the introduction of secondary trading at community airports, 2006, available at http://www.euaca.org/documents/2006_slots_final_report.pdf_211108_054651.pdf
18.
Rassenti S.J., Smith V.L., and Bulfin R.L. A combinatorial auction mechanism for airport time slot allocation Bell J. Econ. 13 2 402-417 1982
19.
Castelli L., Pellegrini P., and Pesenti R. Airport slot allocation in Europe: economic efficiency and fairness Int. J. Revenue Manage. 6 1/2 28-44 2012
20.
Bertsimas D., Lulli G., and Odoni A. An integer optimization approach to large-scale air traffic flow management Oper. Res. 59 1 211-227 2011
21.
Chen B. and Cheng H.H. A review of the applications of agent technology in traffic and transportation systems IEEE Trans. Intell. Transp. Syst. 11 2 485-497 2010
22.
Pellegrini P., Castelli L., and Pesenti R. Secondary trading of airport slots as a combinatorial exchange Transp. Res. E, Logist. Transp. Rev. 48 5 1009-1022 2012
23.
Lourenço H.R., Martin O., and Stützle T. Iterated local search 321-353 Kluwer Academic Publishers 2003
24.
Hansen P. and Mladenović N. Variable neighborhood search: Principles and applications Eur. J. Oper. Res. 130 3 449-467 2001
25.
Pellegrini P., Castelli L., Pesenti R.: ‘Metaheuristic algorithms for the simultaneous slot allocation problem’. Working Papers 9/2011, Department of Management, Università Ca' Foscari Venezia, Italy, 2011, available at http://ideas.repec.org/p/vnm/wpdman/9.html
26.
Hoos H.H. and Stützle T. Stochastic local search. foundations and applications Morgan Kaufmann Publishers San Francisco, CA, USA 2004
27.
EUROCONTROL Performance Review Commission: ‘An assessment of air traffic management in europe during the calendar year 2009 – performance review report’. Brussels, Belgium, May 2010
28.
Birattari M. On the estimation of the expected performance of a metaheuristic on a class of instances. How many instances, how many runs? IRIDIA, Université Libre de Bruxelles Brussels, Belgium 2004 Technical Report TR/IRIDIA/2004-01
29.
López-Ibáñez M., Dubois-Lacoste J., Stützle T., and Birattari M. The irace package, iterated race for automatic algorithm configuration IRIDIA, Université Libre de Bruxelles Brussels, Belgium 2011 Technical Report 2011-04

Information & Authors

Information

Published in

History

Published in print: 01 December 2012
Published online: 31 March 2024

Inspec keywords

  1. airports
  2. integer programming
  3. iterative methods
  4. linear programming
  5. resource allocation
  6. search problems

Keywords

  1. metaheuristic algorithm
  2. simultaneous slot allocation problem
  3. SSAP
  4. airport slot allocation
  5. Europe
  6. airspace sector capacity
  7. iterated local search algorithm
  8. variable neighborhood search algorithm
  9. randomly generated instance
  10. integer linear programming model
  11. memory requirement
  12. computation time requirement
  13. large instance
  14. medium instance
  15. small instance

Authors

Affiliations

P. Pellegrini
IFSTTAR – Univ. Lille Nord de France, rue Élisée Reclus 20, Villeneuve d'Ascq, Lille, 59666, France
L. Castelli
DIA, Università degli Studi di Trieste, Via A. Valerio 10, Trieste, 34127, Italy
R. Pesenti
DM, Università Ca' Foscari Venezia, Cannaregio 873, Venice, Italy

Metrics & Citations

Metrics

Citations

If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.

View Options

Access content
Login options
Buy this article
Metaheuristic algorithms for the simultaneous slot allocation problem

View options

PDF

View PDF

Media

Figures

Other

Tables

Share

Share

Copy the content Link

Share on social media