Glider Routing and Trajectory Optimisation in disaster assessment

Walton Pereira Coutinho, Jörg Fliege, Maria Battarra

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

In this paper, we introduce the Glider Routing and Trajectory Optimisation Problem (GRTOP), the problem of simultaneously finding optimal routes and trajectories for a fleet of gliders with the aim of surveying a set of locations. We propose a novel Mixed-Integer Nonlinear Programming (MINLP) formulation for the GRTOP, which optimises the routes as well as the trajectories along these routes, while flight dynamics is modelled as constraints. We avoid solving a non-convex problem by linearising the gliders’ flight dynamics, converting the proposed MINLP into a Mixed-Integer Second-order Cone Programming (MISOCP) problem. To allow for a more tractable formulation, the dynamical constraints are relaxed and a penalisation is added to the objective function. Several different discretisation techniques are compared. The formulation is tested on instances inspired by risk maps of flooding-prone cities across the UK and on 180 randomly generated instances.

Original languageEnglish
Pages (from-to)1138-1154
Number of pages17
JournalEuropean Journal of Operational Research
Volume274
Issue number3
Early online date8 Nov 2018
DOIs
Publication statusPublished - 1 May 2019

Keywords

  • OR in disaster relief
  • Routing
  • Trajectory optimisation
  • Unmanned gliders

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this

Glider Routing and Trajectory Optimisation in disaster assessment. / Pereira Coutinho, Walton; Fliege, Jörg; Battarra, Maria.

In: European Journal of Operational Research, Vol. 274, No. 3, 01.05.2019, p. 1138-1154.

Research output: Contribution to journalArticle

Pereira Coutinho, Walton ; Fliege, Jörg ; Battarra, Maria. / Glider Routing and Trajectory Optimisation in disaster assessment. In: European Journal of Operational Research. 2019 ; Vol. 274, No. 3. pp. 1138-1154.
@article{b6c23affd6ee4cfbbef11fd032fe7d4d,
title = "Glider Routing and Trajectory Optimisation in disaster assessment",
abstract = "In this paper, we introduce the Glider Routing and Trajectory Optimisation Problem (GRTOP), the problem of simultaneously finding optimal routes and trajectories for a fleet of gliders with the aim of surveying a set of locations. We propose a novel Mixed-Integer Nonlinear Programming (MINLP) formulation for the GRTOP, which optimises the routes as well as the trajectories along these routes, while flight dynamics is modelled as constraints. We avoid solving a non-convex problem by linearising the gliders’ flight dynamics, converting the proposed MINLP into a Mixed-Integer Second-order Cone Programming (MISOCP) problem. To allow for a more tractable formulation, the dynamical constraints are relaxed and a penalisation is added to the objective function. Several different discretisation techniques are compared. The formulation is tested on instances inspired by risk maps of flooding-prone cities across the UK and on 180 randomly generated instances.",
keywords = "OR in disaster relief, Routing, Trajectory optimisation, Unmanned gliders",
author = "{Pereira Coutinho}, Walton and J{\"o}rg Fliege and Maria Battarra",
year = "2019",
month = "5",
day = "1",
doi = "10.1016/j.ejor.2018.10.057",
language = "English",
volume = "274",
pages = "1138--1154",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

TY - JOUR

T1 - Glider Routing and Trajectory Optimisation in disaster assessment

AU - Pereira Coutinho, Walton

AU - Fliege, Jörg

AU - Battarra, Maria

PY - 2019/5/1

Y1 - 2019/5/1

N2 - In this paper, we introduce the Glider Routing and Trajectory Optimisation Problem (GRTOP), the problem of simultaneously finding optimal routes and trajectories for a fleet of gliders with the aim of surveying a set of locations. We propose a novel Mixed-Integer Nonlinear Programming (MINLP) formulation for the GRTOP, which optimises the routes as well as the trajectories along these routes, while flight dynamics is modelled as constraints. We avoid solving a non-convex problem by linearising the gliders’ flight dynamics, converting the proposed MINLP into a Mixed-Integer Second-order Cone Programming (MISOCP) problem. To allow for a more tractable formulation, the dynamical constraints are relaxed and a penalisation is added to the objective function. Several different discretisation techniques are compared. The formulation is tested on instances inspired by risk maps of flooding-prone cities across the UK and on 180 randomly generated instances.

AB - In this paper, we introduce the Glider Routing and Trajectory Optimisation Problem (GRTOP), the problem of simultaneously finding optimal routes and trajectories for a fleet of gliders with the aim of surveying a set of locations. We propose a novel Mixed-Integer Nonlinear Programming (MINLP) formulation for the GRTOP, which optimises the routes as well as the trajectories along these routes, while flight dynamics is modelled as constraints. We avoid solving a non-convex problem by linearising the gliders’ flight dynamics, converting the proposed MINLP into a Mixed-Integer Second-order Cone Programming (MISOCP) problem. To allow for a more tractable formulation, the dynamical constraints are relaxed and a penalisation is added to the objective function. Several different discretisation techniques are compared. The formulation is tested on instances inspired by risk maps of flooding-prone cities across the UK and on 180 randomly generated instances.

KW - OR in disaster relief

KW - Routing

KW - Trajectory optimisation

KW - Unmanned gliders

UR - http://www.scopus.com/inward/record.url?scp=85057059170&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2018.10.057

DO - 10.1016/j.ejor.2018.10.057

M3 - Article

VL - 274

SP - 1138

EP - 1154

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -