6

I am looking for a solution to derive the shortest route that touches all the points using Python. Please note that

  1. This is not a Travelling salesman problem (TSP), in which the route should end where it started (salesman reaches his origin point).
  2. No need to consider the road availability or any such parameters.

I have tried TSP solution that makes a circular path instead of the shortest path. Also, I tried routing-py that considers the road network and finds the optimal road route rather than the shortest path. I am looking for the shortest route that can start from any point, end at any point, and touches all the points.

Can you provide any suggestions in terms of code/ theoretical possibility?

Consider the code below as the input points.

import random
from shapely.geometry import Point
import matplotlib.pyplot as plt

minx, miny, maxx, maxy = 100, 500, 200, 600
ptList = []
for _ in range(50):
    pnt = Point(random.uniform(minx, maxx), random.uniform(miny, maxy))
    ptList.append(pnt)

xs = [point.x for point in ptList]
ys = [point.y for point in ptList]
plt.scatter(xs, ys)

Sample input points

I also tried TSP without the last point and it didn't help. The derived route isn't efficient since it moves in one direction and comes back in the same direction, making the route longer. The image below represents that scenario.
TSP without last point

Got an update! I understand that what I am looking for is termed 'shortest Hamilton path'. It is a modified TSP algorithm, in which the cyclic coming back is not forced. I got a solution using it, and below is the code. However, the result is not effective in a few nodes. The misrouting is marked in black circles in the figure below. Correcting this misrouting could provide a better solution to this kind of problem in terms of hardcoding, speed, and effectiveness.

import networkx as nx
g = nx.Graph()
# A distance matrix is made that have distance btwn each points
# A loop that creates all the edges  
for i in range(len(distance_matrix)):
    source = i
    curr_pt_dist = distance_matrix[i]
    for j in range(len(curr_pt_dist)):
        dest = j 
        # eucl -> Distance btwn source and destination point
        eucl = curr_pt_dist[j]   
        g.add_edge(source, dest, weight = eucl)
# Finding the route
solved_path = nx.approximation.traveling_salesman_problem(g, weight='weight', cycle=False)
# Getting the points in the calculated order and ploting them as lines.
path = []
for item in solved_path:
    path.append(ptList[item])
route_polyline = LineString([z for z in path])
route_geo = gpd.GeoSeries(route_polyline)
route_geo.plot

Sample of faulty route derived using networkx module

8
  • can you not just use the TSP result with the last link removed?
    – Ian Turton
    Jan 13 at 8:59
  • Thanks for the response @IanTurton. I have tried that already. A sample of that is added in the description for reference.
    – rmj
    Jan 13 at 9:35
  • @BERA Thaks for the response. I have tried the minimum_spanning_edges function but it only gives weights between the points such as 1, 28, {'weight': 4}), 20, 46, {'weight': 21}). However, the library seems promising. I tried a few ways and failed. Now I am trying to understand the functions and also I have tried their google group for an answer. Let me come back to you if I could derive a solution.
    – rmj
    Jan 13 at 12:51
  • Hi @BERA, I might be wrong, but as much I understand from networkx library, those functions are made to identify the best route from A to B, ignoring all unwanted nodes. In that route, most nodes are ignored to get the least cost path. I wanted a route that touches all the nodes, which I could not find in networkx library. Pls correct me if I am wrong. Thank you
    – rmj
    Jan 13 at 14:04
  • Try with minimum number of points (7 ?) and use permutations with fixed 1st point. Compare route to one produced by TCP. For now you have no proof that it is not working. The one on 2nd picture looks correct to me
    – FelixIP
    Jan 13 at 19:19

2 Answers 2

0

This is a python codebase which tries to draw the shortest network possible connecting points: https://github.com/facebookresearch/many-to-many-dijkstra

The only limitation is that the output will be a raster, so you will have to vectorize the output into lines.

0

I have not enough reputation to comment, so I will give you my idea as an answer :

Beware the wheel

I think that everytime you try to re invent the wheel nowadays it is not because it does not exist, but because you do not know it exists. What I propose here is kind of re inventing the wheel so... just a warning regarding my own idea.

The idea

enter image description here

  1. Perform a Delaunay triangulation. I think it is a good start as it preserves local relationship between points.

enter image description here

  1. Choose a starting point

  2. Then travel the points cloud by shortest path among the remaining direct connected points (you'll have to track what points are already in the path so that you do not connect a point twice).You will obviously forget some points this way.

enter image description here

  1. Wherever you forget a point, find the closest connected point and redirect one connection to join him

enter image description here

The issues I see : this is not THE shortest path to travel through all the points. More precisely, this method depends on the starting point. But if you have a small amount of points, it should be quick to test all starting points and find the shortest solution overall.
There might also be issues regarding forgotten "islands" of points. This could happen if your points are spread in groups. In that case you could:

  1. simplify the point cloud by clustering (you link an island of points to a virtual center point obtained by clustering)

  2. you perform the preceding method per island and then on the simplified point cloud.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.