Travelling Salesman Problem (TSP) in 2P-Kt

Brief example showing how Google's OR-Tools can exploited in Prolog, to solve the TSP problem. Our solution leverages the notion of primitives from the 2P-Kt Prolog implementation.

A standard Prolog solver can be extended with a predicate of the form:

tsp(?SetOfCities, ?Circuit, ?Cost)

which enumerates all minimally-Costly Circuits for any possible SetOfCities, provided that the Prolog solver's KB contains a number of path/3 facts describing the undirected edges of a city graph, like, e.g.:

path(city1, city2, cost12).
path(city2, city3, cost23).
path(city3, city1, cost31).
% etc...

To solve the TSP, 2P-Kt solvers treat Google OR-Tools solvers as producers of streams of solutions, to be lazily enumerated as part of a standard Prolog resolution strategy. Thus, users as well may lazily consume solutions to the TSP, via backtracking.

Furthermore, the tsp/3 predicate is fully relational, thus users may perform a wide range of queries.

For example, users may be willing to solve a particular instance of the TSP, involving e.g. cities city1, city2, and city3:

tsp({city1, city2, city3}, Circuit, Cost), Circuit = [city2 | OtherCities].

The query above enumerates all the minimally-Costly Circuits starting from city2 and involving exactly those 3 cities.

Conversely, the following query

tsp({city1, city2, city3, MoreCities}, Circuit, Cost), Circuit = [city2 | OtherCities].

enumerates all the the minimally-Costly Circuits starting from city2 and stepping through at least 3 cities, namely city1, city2, and city3.

Finally, the general query

tsp(Cities, Circuit, Cost).

enumerates all the the minimally-Costly Circuits involving all non-empty subsets of cities mentioned in the KB.

How to run the example

Prerequisites

• JDK 11+
• [Optionally] Gradle 6.7+
• [Alternatively] Docker

Walkthrough

1. Start a new command line Prolog interpreter by running

gradlew -q run --args="-T /path/to/your/map-theory.pl"`

for instance, you may use ./src/test/resource/mini-map.pl

0. Alternatively, you may start the interpreter by simply running

gradlew -q run

and later consult a graph theory via the query:

consult('file:/path/to/your/map-theory.pl').

for instance, you may write

consult('file:./src/test/resource/mini-map.pl').

0. Write your .-terminated Prolog query of the form tsp(Cities, Circuit, Cost). and press Enter

1. The first solution will appear: press ; and then Enter to show the next one

   • or just Enter to interrupt the solution stream and provide a new query

2. You may add new edges to the map graph by asserting new facts in the theory, e.g.:

assert(path(city3, city4, cost34)).

0. Terminate the interpreter by querying halt., or simply by pressing Ctrl+ D

In case of issues, try using Docker

1. You may dockerify this demo on your own machine by running:

docker build . -t pikalab/demos:2p-kt-tsp  

2. Then you may then start the dockerified interpreter by running:

docker run -it --rm pikalab/demos:2p-kt-tsp

(In presence of an Internet connection this step may also work without requiring the previous one, as the image pikalab/demos:2p-kt-tsp is publicly available on DockerHub)