A new mixed-integer linear programming model for rescue path planning in uncertain adversarial environment

作者：Berger Jean^*; Boukhtouta Abdeslem; Benmoussa Abdelhamid; Kettani Ossama

来源：Computers & Operations Research, 2012, 39(12): 3420-3430.

DOI：10.1016/j.cor.2012.05.002

• Path planning
• Constrained shortest path
• Mixed-integer linear programming

Efficient vehicle path planning in hostile environment to carry out rescue or tactical logistic missions remains very challenging. Most approaches reported so far rely on key assumptions and heuristic procedures to reduce problem complexity. In this paper, a new model is proposed to solve the discrete rescue path planning problem for a single agent navigating in uncertain adversarial environment. It relies on a novel and simplified mathematical mixed-integer linear programming formulation aimed at minimizing traveled distance and threat exposure. Exploiting a user-defined survivability function approximation and survivability threshold, the approximate model allows constructing a solution providing an adjustable optimality gap interval on the optimal solution. Experimental results show the value of the proposed approach in computing near optimal solutions reasonably fast for various problem instances.

• 出版日期2012-12