A Time-Flow Approach for Scheduling and Routing of Fly-in Safari Airplanes

Fabian Gnegel () and Armin Fügenschuh
Additional contact information
Fabian Gnegel: Brandenburg Technical University Cottbus-Senftenberg
Armin Fügenschuh: Brandenburg Technical University Cottbus-Senftenberg

A chapter in Operations Research Proceedings 2018, 2019, pp 339-345 from Springer

Abstract: Abstract A touristic company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of aircrafts in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time window. Furthermore the number of available seats, the consumption of fuel, the maximal takeoff weight, and restrictions on the detour of the individual groups have to be taken into account. A flow-over-flow formulation on the time expanded graph of the airports was used in the literature in combination with a so called time-free relaxation in order to solve this problem with a solver for MILP. We give an alternative MILP formulation of the problem, that still allows for similar relaxation techniques to be used. This formulation, however, also allows for the construction of graphs which can be interpreted as intermediate graphs between the time-free and the (totally) time-expanded graph and therefore yield stronger relaxations. With knowledge obtained from the solutions of these relaxations the number of vertices that have to be expanded in order to guarantee feasibility is reduced significantly. On the benchmark set this lead to a decrease of the average computation time and a significant reduction of the remaining optimality gaps.

Keywords: Mixed integer programming; Vehicle routing problem with time-windows; Airplane scheduling (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-030-18500-8_42

Ordering information: This item can be ordered from
http://www.springer.com/9783030185008

DOI: 10.1007/978-3-030-18500-8_42

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().