A Time-Indexed Generalized Vehicle Routing Model and Stabilized Column Generation for Military Aircraft Mission Planning
2015 (English)In: OPTIMIZATION, CONTROL, AND APPLICATIONS IN THE INFORMATION AGE: IN HONOR OF PANOS M. PARDALOSS 60TH BIRTHDAY, SPRINGER , 2015, Vol. 130, 299-314 p.Conference paper (Refereed)Text
We introduce a time-indexed mixed-integer linear programming model for a military aircraft mission planning problem, where a fleet of cooperating aircraft should attack a number of ground targets so that the total expected effect is maximized. The model is a rich vehicle routing problem and the direct application of a general solver is practical only for scenarios of very moderate sizes. We propose a Dantzig-Wolfe reformulation and column generation approach. A column here represents a specific sequence of tasks at certain times for an aircraft, and to generate columns a longest path problem with side constraints is solved. We compare the column generation approach with the time-indexed model with respect to upper bounding quality of their linear programming relaxations and conclude that the former provides a much stronger formulation of the problem.
Place, publisher, year, edition, pages
SPRINGER , 2015. Vol. 130, 299-314 p.
, Springer Proceedings in Mathematics & Statistics, ISSN 2194-1009
Aircraft mission planning problem; Time-indexed mixed-integer linear program; Vehicle routing problem; Dantzig-Wolfe method; Column generation
IdentifiersURN: urn:nbn:se:liu:diva-130685DOI: 10.1007/978-3-319-18567-5_15ISI: 000380540400015ISBN: 978-3-319-18567-5; 978-3-319-18566-8OAI: oai:DiVA.org:liu-130685DiVA: diva2:954050
conference on Optimization Control and Applications in the Information Age