Monte Carlo Tree Search for TSP

In this repo, I made different heuristic solutions for the TSP written in OCaml. My main goal is to study the effectiveness of the Monte Carlo Tree Search to solve the TSP. I'm not using any neural network in this project.

My implementation of the monte carlo tree search is in this module

Available heuristics

• 2-opt : classic 2-opt algorithm, which makes a locally optimized solution from any tour.
• Monte-Carlo tree search or MCTS
• Simulated annealing or SA
• Genetic algorithm : maybe one day... For now, I only did it in python
• Greedy Random : try to find a solution by generating bunch of random solutions (with or without heuristics). It as not meant to be good, it's just to compare with the MCTS performances

Objectives

My point with MCTS is to use the approach described in this paper and try to see if adding some 2-opt in playouts and doing some other modifications, can end up in a better result.

How can I test it ?

If you don't want to use dune you can still run an old version of the project online - see toplevel release. Note that it's a very old release and that a lot of things changed

If you have dune, be sure that the Graphics library is installed in your opam switch

• Open and build the project using dune build.
• Then chose an example from the example directory and run it using dune exec ./examples/example_name.exe

Ressources

• TSPLIB a library which contains different cities configuration used in most of the papers related to TSP
• World a set of tsp instances based on the location of real world countries
• Hard TSP instances a set of instances which are designed to be very hard to solve for exact solvers as concorde

Where can I ask my questions or look for help ?

You can open an issue in this repo, contact me by email or join my discord server