Airtravel scheduling

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 loads and fuel also must be satisfied. Moreover the refueling of the planes, which can only be done in certain locations, must be scheduled.

We introduce a mixed-integer linear programming based formulation for this problem. For its solution we develop a primal heuristic based on randomized local search. 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 use a set-covering based reformulation, where new columns are generated on demand by heuristics and exact methods. We further use a reformulation where the time windows are relaxed, and later reintroduced by cutting planes and branching.


  • Georgia Institute of Technology

Related talks

  1. A Time-Free Relaxation for a Mixed-Integer Dynamic Optimization Problem, GOR Workshop on Technical Operations Research, Asselheim, Germany, 4.3.2014.
  2. Optimizing Discrete and Continuous Problems Over Time, Magdeburg Lectures on Optimization and Control (MALOC), Magdeburg, Germany, 14.11.2013.
  3. Optimizing Discrete and Continuous Problems Over Time, Discrete Optimization Seminar, Georgia Institute of Technology, Atlanta, Georgia, USA, 2.8.2013.
  4. Scheduling and routing of fly-in safari airplanes, EURO/Informs 26th European Conference on Operational Research, Rome, 2.7.2013.
  5. Scheduling and routing of fly-in safari airplanes, International Symposium on Mathematical Programming ISMP 2012, Berlin, Germany, 24.8.2012.

Related publications

  1. Armin Fügenschuh, George Nemhauser, Yulian Zeng, Scheduling and Routing of Fly-in Safari Planes Using a Flow-Over-Flow Model , In: M. Jünger, G. Reinelt (Eds.), Facets of Combinatorial Optimization, Series Algorithms and Combinatorics, Springer Verlag, Heidelberg, pp. 419-447, 2013.

This website uses cookies. There are two types of cookies: The first type supports the basic functionality of our website. The second allows us to improve our content for you by saving and analyzing pseudonymised user data. Since this second type is technically not required to run the website, you can withdraw your consent to those cookies at any time. For more information please visit our pages on data protection.


These cookies are needed for a smooth operation of our website.


For statistical reasons, we use the platform Matomo to analyse the user flow with the help of website users‘ pseudonymised data. This allows us to optimize website content.

Name Purpose Lifetime Type Provider
_pk_id Used to store a few details about the user such as the unique visitor ID. 13 months HTML Matomo
_pk_ref Used to store the attribution information, the referrer initially used to visit the website. 6 months HTML Matomo
_pk_ses Short lived cookie used to temporarily store data for the visit. 30 minutes HTML Matomo