A Branch-and-Price Algorithm for a Team Orienteering Problem with Fixed-Wing Drones

arXiv1912.04353MaRDI QIDQ6330786FDOQ6330786

Christopher Montez, Kaarthik Sundar, Sujeevraja Sanjeevi

Publication date: 9 December 2019

Abstract: This paper formulates a team orienteering problem with multiple fixed-wing drones and develops a branch-and-price algorithm to solve the problem to optimality. Fixed-wing drones, unlike rotary drones, have kinematic constraints associated with them, thereby preventing them to make on-the-spot turns and restricting them to a minimum turn radius. This paper presents the implications of these constraints on the drone routing problem formulation and proposes a systematic technique to address them in the context of the team orienteering problem. Furthermore, a novel branch-and-price algorithm with branching techniques specific to the constraints imposed due to fixed-wing drones are proposed. Extensive computational experiments on benchmark instances corroborating the effectiveness of the algorithms are also presented.

Has companion code repository: https://github.com/kaarthiksundar/fairmtsp

This page was built for publication: A Branch-and-Price Algorithm for a Team Orienteering Problem with Fixed-Wing Drones

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330786)