Traveling Salesman Problem¶

traveling_salesman_problem(points, return_to_start=True, distances=None)[source]

Get the shortest path visiting all points.

Parameters:

points (GeoDataFrame | GeoSeries) – An iterable of point geometries.
return_to_start (bool) – If True (default), the path will make a full circle to the startpoint. If False, a dummy node will be added to make the salesman focus only on getting to the last node. Not guaranteed to work, meaning the wrong edge might be removed.
distances (DataFrame | None) – Optional DataFrame of distances between all points. If not provided, the calculation is done within this function. The DataFrame should be identical to the DataFrame created from sgis.get_all_distances from and to the points.

Return type:

list[Point]

Returns:

List of Points making up the traveling salesman’s path.

Examples:¶

>>> import sgis as sg
>>> from shapely.geometry import LineString
>>> points = sg.to_gdf(
...     [
...         (0, 0),
...         (10, -10),
...         (10, 10),
...         (0, 10),
...         (0, -10),
...         (10, 0),
...         (20, 0),
...         (0, 20),
...     ]
... )
>>> roundtrip = sg.traveling_salesman_problem(points)
>>> roundtrip
[<POINT (0 0)>, <POINT (10 -10)>, <POINT (0 -10)>, <POINT (10 0)>, <POINT (20 0)>, <POINT (10 10)>, <POINT (0 10)>, <POINT (0 20)>, <POINT (0 0)>]

>>> LineString(roundtrip)
LINESTRING (0 0, 10 -10, 0 -10, 10 0, 20 0, 10 10, 0 10, 0 20, 0 0)

>>> oneway_trip = sg.traveling_salesman_problem(points, return_to_start=False)
>>> oneway_trip
[<POINT (0 0)>, <POINT (10 0)>, <POINT (20 0)>, <POINT (10 -10)>, <POINT (0 -10)>, <POINT (10 10)>, <POINT (0 10)>, <POINT (0 0)>]

>>> LineString(oneway_trip)
LINESTRING (0 20, 0 10, 10 10, 0 0, 10 0, 20 0, 10 -10, 0 -10)