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 language | English |
---|---|
Pages (from-to) | 1138-1154 |
Number of pages | 17 |
Journal | European Journal of Operational Research |
Volume | 274 |
Issue number | 3 |
Early online date | 8 Nov 2018 |
DOIs | |
Publication status | Published - 1 May 2019 |
Funding
The authors would like to thank Jodie Walshe from RNLI and Dr. Andràs Sóbester from the Engineering Department at the University of Southampton for suggesting this problem. We also would like to thank Dr. Christopher Crispin for his support and Mrs. Fatine Mrabet for creating the UK instances. The first author received grants from CNPq [Grant no. 202241/2041-9 ]. Appendix A
Keywords
- OR in disaster relief
- Routing
- Trajectory optimisation
- Unmanned gliders
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research
- Information Systems and Management
Profiles
-
Maria Battarra
- Management - Professor
- Information, Decisions & Operations - Director of Studies MSc in Management suite
- Made Smarter Innovation: Centre for People-Led Digitalisation
- IAAPS: Propulsion and Mobility
- Centre for Climate Adaptation & Environment Research (CAER)
- Centre for Digital, Manufacturing & Design (dMaDe)
Person: Research & Teaching, Affiliate staff