Advanced algorithmsAvailable algorithmstsp

tsp

TSP or “Travelling salesman problem” is one of the well-known problems in graph theory. The goal of the problem is to find the shortest route that visits each node once, starting and finishing from the same node, given the distance between each one of them. It is an NP-hard problem in optimization and therefore there exists no exact solution. Here implemented are trivial, greedy and k-approx methods that find the solution within a k-bound of the optimal one. That means that solution is not going to be more than k times worse than the best possible. The algorithm uses the distance calculator to determine the distance between points, and works only with geographical locations, meaning each node needs to have its lat and lng property.

(location:Location {lat: 44.1194, lng: 15.2314})
Source code
TraitValue
Module typemodule
ImplementationPython
Graph directionundirected
Edge weightsunweighted
Parallelismsequential

Too slow?

If this algorithm implementation is too slow for your use case, open an issue on Memgraph’s GitHub repository and request a rewrite to C++!

Procedures

You can execute this algorithm on graph projections, subgraphs or portions of the graph.

solve()

Use the procedure to solve the travelling salesman problem.

Input:

  • subgraph: Graph (OPTIONAL) ➡ A specific subgraph, which is an object of type Graph returned by the project() function, on which the algorithm is run. If subgraph is not specified, the algorithm is computed on the entire graph by default.

  • points: List[Vertex] ➡ List of points to calculate TSP on. Required to have lng and lat properties.

  • method: string (default=1.5_approx) ➡ Method used for optimization. Can be either 1.5_approx, 2_approx or greedy.

Output:

  • sources: List[Vertex] ➡ List of elements from 1st to (n-1)-th element.
  • destinations: List[Vertex] ➡ List of elements from 2nd to n-th element The pairs of them represent individual edges between 2 nodes in the graph.

Usage:

To solve the travelling salesman problem, use the following query:

MATCH (n:Location)
WITH COLLECT(n) as locations
CALL tsp_module.solve(points) YIELD sources, destinations;

Example

Database state

The database contains the following data:

Created with the following Cypher queries:

CREATE (location:Location {name: 'Zagreb', lat: 45.8150, lng: 15.9819});
CREATE (location:Location {name: 'Split', lat: 43.5081, lng: 16.4402});
CREATE (location:Location {name: 'Rijeka', lat: 45.3271, lng:  14.4422});
CREATE (location:Location {name: 'Osijek', lat: 45.5550, lng: 18.6955});
CREATE (location:Location {name: 'Zadar', lat: 44.1194, lng: 15.2314});

Solve the problem

Use the following query to solve the travelling salesman problem:

MATCH (n:Location)
WITH COLLECT(n) AS locations
CALL tsp.solve(locations, "1.5_approx") YIELD sources, destinations
WITH EXTRACT(i IN RANGE(0, SIZE(sources) - 1) | [sources[i], destinations[i]]) AS path
UNWIND path as edge
WITH edge[0] AS from, edge[1] AS to
CREATE (from)-[path:PATH]->(to)
RETURN from, to, path;

Result:

+----------------------------------------------------------+----------------------------------------------------------+----------------------------------------------------------+
| from                                                     | to                                                       | path                                                     |
+----------------------------------------------------------+----------------------------------------------------------+----------------------------------------------------------+
| (:Location {lat: 45.815, lng: 15.9819, name: "Zagreb"})  | (:Location {lat: 45.555, lng: 18.6955, name: "Osijek"})  | [:PATH]                                                  |
| (:Location {lat: 45.555, lng: 18.6955, name: "Osijek"})  | (:Location {lat: 43.5081, lng: 16.4402, name: "Split"})  | [:PATH]                                                  |
| (:Location {lat: 43.5081, lng: 16.4402, name: "Split"})  | (:Location {lat: 44.1194, lng: 15.2314, name: "Zadar"})  | [:PATH]                                                  |
| (:Location {lat: 44.1194, lng: 15.2314, name: "Zadar"})  | (:Location {lat: 45.3271, lng: 14.4422, name: "Rijeka"}) | [:PATH]                                                  |
| (:Location {lat: 45.3271, lng: 14.4422, name: "Rijeka"}) | (:Location {lat: 45.815, lng: 15.9819, name: "Zagreb"})  | [:PATH]                                                  |
+----------------------------------------------------------+----------------------------------------------------------+----------------------------------------------------------+
temporal_graph_networksunion_find