×

Scheduling and routing of fly-in safari planes using a flow-over-flow model. (English) Zbl 1317.90118

Jünger, Michael (ed.) et al., Facets of combinatorial optimization. Festschrift for Martin Grötschel on the occasion of his 65th birthday. Berlin: Springer (ISBN 978-3-642-38188-1/hbk; 978-3-642-38189-8/ebook). 419-447 (2013).
Summary: 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.
For the entire collection see [Zbl 1282.90010].

MSC:

90B35 Deterministic scheduling theory in operations research
90B20 Traffic problems in operations research
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI