Building the shortest route through all points in QGIS

Question

How to build the shortest route through all selected points, starting from a given point? Which plugin to use?

There is a point layer and a linear layer for all routes between points.

Answer 1

What you're looking for is called "Travelling salesman problem".

Let's assume there is a point and a line layers, see the image below.

There are several approaches available:

Approach 1 : qgis-grass-plugin

v.net.salesman

Creates a cycle connecting given nodes (Traveling salesman problem). Note that TSP is NP-hard, heuristic algorithm is used by this module and created cycle may be sub optimal

This geoalgorithm takes a layer nd a point layer as an input.

Approach 2 : pyqgis

Find a corresponding Python package and install it via OSGeo4W Shell. In this example I used the tsp_solver2 library.

⚠️ The last update to this package was done in July 2020.

In the below script, you do not need a line layer.

# imports
import geopandas as gpd
from qgis import processing
from qgis.core import QgsProject
from tsp_solver.greedy import solve_tsp
referring to a layer by its name
point_layer = QgsProject.instance().mapLayersByName("YOUR_LAYER_NAME")[0]
creating a GeoDataFrame from a QgsVectorLayer
gdf = gpd.read_file(point_layer.source())
calculating a distance matrix
dm = gdf.geometry.apply(lambda g: gdf.distance(g))
convertign a distance matrix to a NumPy array
dm = dm.to_numpy()
applying the TSP solver
min_path = solve_tsp(dm, endpoints=(0,2)) # change endpoints ids accordingly
if one wants an enclosing line, please modify the above list
min_path.insert(len(min_path), min_path[0])
converting previous output to a real path
params = {
    'INPUT' : point_layer,
    'CLOSE_PATH' : False,
    'GROUP_EXPRESSION' : '',
    'NATURAL_SORT' : True,
    'ORDER_EXPRESSION' : f"array_get(min_path, $id)",
    'OUTPUT' : 'TEMPORARY_OUTPUT'
    }
result = processing.run("native:pointstopath", params)
adding result to the project
QgsProject.instance().addMapLayer(result['OUTPUT'])

or if one prefers pure PyQGIS:

# imports
import geopandas as gpd
from qgis.core import QgsProject, QgsVectorLayer, QgsGeometry, QgsPoint, QgsFeature
from tsp_solver.greedy import solve_tsp
referring to a layer by its name
point_layer = QgsProject.instance().mapLayersByName("YOUR_LAYER_NAME")[0]
creating a GeoDataFrame from a QgsVectorLayer
gdf = gpd.read_file(point_layer.source())
calculating a distance matrix
dm = gdf.geometry.apply(lambda g: gdf.distance(g))
convertign a distance matrix to a NumPy array
dm = dm.to_numpy()
applying the TSP solver
min_path = solve_tsp(dm, endpoints=(0, 2))  # change endpoints ids accordingly
if one wants an enclosing line, please modify the above list
min_path.insert(len(min_path), min_path[0])
creating a PolyLine geometry
min_path_geom = QgsGeometry.fromPolyline(
    [QgsPoint(point_layer.getFeature(node).geometry().asPoint()) for node in min_path])
creating an empty vector layer
vlayer = QgsVectorLayer(f"LineString?query=SELECT ST_GeomFromText('{min_path_geom.asWkt()}',"
                        f"{point_layer.crs().postgisSrid()})", "vlayer", "virtual")
adding output layer to the canvas
QgsProject.instance().addMapLayer(vlayer)

Approach 3 : qgis-plugins

The ORS Tools Plugin

openrouteservice routing, isochrones and matrix calculations for QGIS

An API Key is required. It has a Fix Start.

Approach 4 : qgis-plugins

The MTSP Routing Plugin

Either plugin or Python library currently is not available.

It requires additional installation in QGIS of the Python package mtsp-routing.

---

References:

• YouTube | Traveling Salesman Problem Visualization
• wiki.gis.com | Travelling salesman problem
• Why Travelling Salesman Problem plugin is not working in QGIS 3?

Answer 2

You can also use networkx together with pyqgis:

from itertools import combinations
import networkx as nx
layer = QgsProject.instance().mapLayersByName("building")[0]
all_features = [f for f in layer.getSelectedFeatures()] #List all selected features
edgelist = [] #A list to hold all pairs of features and the distance between them: [(feature1, feature2, distance), (feature2, feature3, distance) ...]
for featurepair in combinations(all_features, 2):
    f1, f2 = featurepair
    edgelist.append((f1.id(), f2.id(), f1.geometry().distance(f2.geometry())))
#print(edgelist[0])
#(37780, 37859, 4570.112717970702) "(id of feature 1, id of feature 2, distance between 1 and 2)
#Create a graph from the list of edges
G = nx.Graph()
G.add_weighted_edges_from(edgelist)
tsp = nx.approximation.traveling_salesman_problem
route = tsp(G=G, nodes=G.nodes, weight="weight")
#The best route is:
#[37780, 41930, 41928, 41926, 41923, 41929, 41933, 41931, 41932, 41936, 37955, 42667, 42664, 42661, 42653, 41918, 41917, 42848, 42850, 42853, 42043, 42042, 42046, 41916, 41915, 42132, 41925, 41938, 37859, 37780]
#Create a line layer of the route
all_geometries = {f.id():f.geometry().asPoint() for f in all_features} #Dictionary of each features id and its geometry
vl = QgsVectorLayer("LineString?crs={}&index=yes&field=id:integer".format(layer.crs().authid()), 
"shortest_path", "memory")
provider = vl.dataProvider()
for featurepair in zip(route, route[1:]):
    f1, f2 = featurepair
    new_feature = QgsFeature(fields)
    line_geometry = QgsGeometry(QgsLineString([all_geometries[f1],all_geometries[f2]]))
    new_feature.setGeometry(line_geometry)
    provider.addFeature(new_feature)
QgsProject.instance().addMapLayer(vl)