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'.
 

Solving the Traveling Salesman Problem with a locality hypothesis by subdividing the problem

Hennecart, Alexandre
(2024)

Files

Hennecart_64721700_2024.pdf
  • Open access
  • Adobe PDF
  • 1.75 MB
Download

Details

Supervisors
Schaus, Pierre
Faculty
Ecole polytechnique de Louvain
Degree label
Master [120] : ingénieur civil en informatique, à finalité spécialisée
Abstract
This master's thesis explores a new method for solving the traveling salesman problem. The idea comes from an article using deep learning to obtain a weight for each edge (weight which corresponds to the probability that this edge is in the final solution). This approach having several drawbacks, the idea arose that it might be possible to obtain a similar matrix by dividing the problem into a large number of sub-problems which would be simpler to solve by posing a hypothesis of locality, that is, by grouping nearby nodes together. The main assumption is that if an edge is taken in the sub-solution to one of these sub-problems, it has a high chance of being included in the final solution. This master's thesis therefore explores this hypothesis in order to prove/disprove it.