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 show that, for the considered problem instances, 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 gaps on the average.
Citation
Koç University, 2020