ATTENTION/WARNING - NE PAS DÉPOSER ICI/DO NOT SUBMIT HERE

Ceci est la version de TEST de DIAL.mem. Veuillez ne pas soumettre votre mémoire sur ce site mais bien à l'URL suivante: 'https://thesis.dial.uclouvain.be'.
This is the TEST version of DIAL.mem. Please use the following URL to submit your master thesis: 'https://thesis.dial.uclouvain.be'.
 

Designing a high-performance exact solver for the Travelling Salesman Problem in Java

Valkenberg, Louis
(2023)

Files

Valkenberg_40601800_2023.pdf
  • UCLouvain restricted access
  • Adobe PDF
  • 768.77 KB

Details

Supervisors
Schaus, Pierre
Faculty
Ecole polytechnique de Louvain
Degree label
Master [120] : ingénieur civil en informatique, à finalité spécialisée
Abstract
In this paper, we focus on the construction of an effective, exact solver for the Travelling Salesman Problem (TSP), a classical, NP-hard problem in computer science and operational research. The TSP, despite its deceptive simplicity, has a wide array of applications, ranging from vehicle routing to genome sequencing. Given its importance, we strive to design a solver that primarily minimizes execution time. Drawing inspiration from various approaches in operational research and constraint programming, we develop our solver in the Java programming language as a part of a comprehensive library. At its core, the solver implements a branch-and-bound framework combined with a Lagrangian relaxation technique to provide a robust lower bound estimation for optimal tour cost. The performance and implementation details of the solver are meticulously evaluated and presented, along with future research directions and potential enhancements.