In this paper, we introduce the Glider Routing and Trajectory Optimisation Problem (GRTOP), the problem of finding simultaneously 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 simultaneously optimises the routes as well as the flight path along these routes, while flight dynamics are 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 and solvers 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.
Citation
Tech. Report 412745, University Road, Highfield, SO17 1BJ, 2017.