Open AccessTHE TRAVELING SALESMAN PROBLEM WITH MULTI-VISIT DRONE
Author(s) -
Quang Minh Ha,
Duy Manh Vu,
Xuan Thanh Le,
Minh Ha Hoang
Publication year - 2021
Publication title -
journal of computer science and cybernetics (vietnam academy of science and technology)/journal of computer science and cybernetics
Language(s) - English
Resource type - Journals
eISSN - 2815-5939
pISSN - 1813-9663
DOI - 10.15625/1813-9663/37/4/16180
Subject(s) - travelling salesman problem , drone , benchmark (surveying) , mathematical optimization , iterated local search , computer science , metaheuristic , iterated function , integer programming , class (philosophy) , linear programming , mathematics , artificial intelligence , geodesy , biology , geography , mathematical analysis , genetics
This paper deals with the Traveling Salesman Problem with Multi-Visit Drone (TSP-MVD) in which a truck works in collaboration with a drone that can serve up to q > 1 customers consecutively during each sortie. We propose a Mixed Integer Linear Programming (MILP) formulation and a metaheuristic based on Iterated Local Search to solve the problem. Benchmark instances collected from the literature of the special case with q = 1 are used to test the performance of our algorithms. The obtained results show that our MILP model can solve a number of instances to optimality. This is the first time optimal solutions for these instances are reported. Our ILS performs better other algorithms in terms of both solution quality and running time on several class of instances. The numerical results obtained by testing the methods on new randomly generated instances show again the effectiveness of the methods as well as the positive impact of using the multi-visit drone.