A Time-Indexed Generalized Vehicle Routing Model and Stabilized Column Generation for Military Aircraft Mission Planning

Quttineh, Nils-HassanLinköpings universitet,Optimeringslära,Tekniska fakulteten (författare)

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.

NATURVETENSKAP Matematik Beräkningsmatematik hsv//swe
NATURAL SCIENCES Mathematics Computational Mathematics hsv//eng
Aircraft mission planning problem; Time-indexed mixed-integer linear program; Vehicle routing problem; Dantzig-Wolfe method; Column generation

Larsson, TorbjörnLinköpings universitet,Optimeringslära,Tekniska fakulteten(Swepub:liu)torla64 (författare)
Van den Bergh, JorneKatholieke University of Leuven, Belgium (författare)
Belien, JeroenKatholieke University of Leuven, Belgium (författare)
Linköpings universitetOptimeringslära (creator_code:org_t)

Ingår i:OPTIMIZATION, CONTROL, AND APPLICATIONS IN THE INFORMATION AGE: IN HONOR OF PANOS M. PARDALOSS 60TH BIRTHDAYCham : SPRINGER, s. 299-31497833191856759783319185668

Av författaren/redakt...: Quttineh, Nils-H ...; Larsson, Torbjör ...; Van den Bergh, J ...; Belien, Jeroen

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.