BTU overview
Faculty 1
Chair of Engineering Mathematics and Numerical Optimization Prof. Dr. rer. nat. habil. Armin Fügenschuh

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.

Partners

  • 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.