Scheduling and Routing of Fly-in Safari Planes Using a Flow-over-Flow Model

Armin Fügenschuh (), George Nemhauser () and Yulian Zeng ()
Additional contact information
Armin Fügenschuh: Helmut-Schmidt-Universität, Universität der Bundeswehr Hamburg, Fakultät für Maschinenbau
George Nemhauser: Georgia Institute of Technology, H. Milton Stewart School of Industrial and Systems Engineering
Yulian Zeng: Georgia Institute of Technology, H. Milton Stewart School of Industrial and Systems Engineering

A chapter in Facets of Combinatorial Optimization, 2013, pp 419-447 from Springer

Abstract: Abstract The scheduling and routing of small planes for fly-in safaris is a challenging planning problem. Given a fleet of planes and a set of flight requests with bounds on the earliest departure and latest arrival times, the planes must be scheduled and routed so that all demands are satisfied. Capacity restrictions on the load and fuel also must be satisfied. Moreover the refueling of the planes, which can only be done in certain locations, must be scheduled. We present a mixed-integer linear programming based formulation for this problem. For its solution we develop a primal heuristic based on randomized local search. We try to enhance the local search by using exact methods to solve subproblems that only involve a small number of planes. Using a branch-and-cut solver, the MILP formulation can be solved to proven optimality only for small instances. To achieve better dual bounds we present a set partitioning based formulation, where new columns are generated on demand by heuristics and exact methods. We also present a new formulation where the time windows are relaxed, and later reintroduced by incumbent branching. Numerical results on real-world instances show that this time-free approach gives the best results.

Keywords: Local Search; Travel Salesman Problem; Column Generation; Valid Inequality; Column Generation Approach (search for similar items in EconPapers)
Date: 2013
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:sprchp:978-3-642-38189-8_17

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

DOI: 10.1007/978-3-642-38189-8_17

Access Statistics for this chapter

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