1098. Close-enough multi-UAV general routing problem for monitoring
Invited abstract in session MD-17: Drone Routing, stream Combinatorial Optimization.
Monday, 14:30-16:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Michel Gendreau
|
| MAGI and CIRRELT, Polytechnique Montréal | |
| 2. | Huan Liu
|
| School of Traffic and Transportation Engineering, Central South University | |
| 3. | Guohua Wu
|
| School of Automation, Central South University |
Abstract
We introduce the Close-enough Multi-UAV General Routing Problem (CMUAVGRP), in which homogeneous UAVs perform monitoring tasks involving nodes with disk neighborhoods and edges, aiming to minimize the total travelled distance. A two-phase iterative method is proposed: first, a variable neighborhood descent is designed to generate routes excluding disk neighborhoods in a general routing phase, and, second, a second-order cone programming procedure is developed to optimize representative points for each required node in a close-enough routing phase. The two phases operate iteratively under an adaptive iterated local search framework until termination criteria are met. Extensive experiments demonstrate the efficiency of this two-phase algorithm and the superiority of disk neighborhoods.
Keywords
- Vehicle Routing
- Combinatorial Optimization
- Transportation
Status: accepted
Back to the list of papers