.png){kind=icon}
.png){kind=icon}
返回
A learning based algorithm for drone routing
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eer.2021.105524.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We introduce a learning-based algorithm to solve the drone routing problem with recharging stops that arises in many applications such as precision agriculture, search and rescue, and military surveillance. The heuristic algorithm, namely Learn and Fly (L&F), learns from the features of high-quality solutions to optimize recharging visits, starting from a given Hamiltonian tour that ignores the recharging needs of the drone. We propose a novel integer program to formulate the problem and devise a column generation approach to obtain provably high-quality solutions that are used to train the learning algorithm. Results of our numerical experiments with four groups of instances show that the classification algorithms can effectively identify the features that determine the timing and location of the recharging visits, and L&F generates energy feasible routes in a few seconds with around 5% optimality gap on the average.
Keyword:
Drone routing
Learning based algorithm
Column generation
Machine learning