ICTEAM - Soutenance publique de thèse - Minh Quang HA

The Travelling Salesman Problem with drones

Over the past few years, unmanned aerial vehicles (UAV), also known as drones, have been adopted as part of a new logistic method in the commercial sector called "last-mile delivery". In this novel approach, they are deployed alongside trucks to deliver goods to customers to improve the quality of service and reduce the transportation cost. This approach gives rise to a new variant of the traveling salesman problem (TSP), called TSP with drone (TSP-D). A variant of this problem that aims to minimize the time at which truck and drone finish the service (or, in other words, to maximize the quality of service) was studied in the work of Murray and Chu (2015).

In this thesis, we propose two new variants of the TSP-D: the Min-Cost TSP-D and the Multi-Visits TSP-D. With each of this variant, a mathematical model – a MIP formulation – is presented. Furthermore, with the development of three metaheuristics (GRASP, HGA, ILS) based on local search, we can solve the problem in both min-time and min- cost objective efficiently under an acceptable time.

The computational results show that our proposed methods could outperform the ones in the previous work and could significantly improve the solution quality when comparing to the optimal TSP solution. Furthermore, the extensive analysis of the components of the heuristic as well as the parameters of the variants, we can understand more about the algorithm’s sensitivity as well as the nature of the problem.

Jury members :

• Prof. Yves Deville (UCLouvain), supervisor
• Prof. Quang Dung Pham (SOICT – HUST, Vietnam), supervisor
• Prof. Charles Pecheur (UCLouvain), chairperson
• Prof. Pierre Schaus (UCLouvain), secretary
• Prof. Birger Raa (Ghent University, Belgium)
• Prof. Christine Solnon (INSA Lyon, France)

Télécharger l'annonce