0

Can anyone provide assistance to the problem I'm facing? I'm working on implementing a delivery system algorithm. I have attempted to solve it using a graph, where addresses are represented as nodes and the distance between nodes as the weight of the edges. One approach I'm currently exploring involves adapting the Traveling Salesman Problem using Christofides' algorithm(https://www.youtube.com/watch?v=dNCwtFJLsKI&t=211s), which utilizes a Minimum Spanning Tree and Eulerian Cycle algorithm. However, this approach is not accurate enough for my needs. The TSP finds the Shortest Hamiltonian Cycle, whereas I only require the Shortest Hamiltonian Path.

I have come across suggestions to introduce a "dummy" node with a weight of zero, but this causes my approximation algorithm to lose context, resulting in paths that are far from optimal.

Has anyone encountered a similar problem and can provide assistance?

Example of paths. keep in mind that this algorithm creates the shortest paths for 4 different routes

enter image description here

Optimal paths

IlayAsayag
  • 1
  • 1
  • My algorithm constructs a Minimum Spanning Tree (T) from a given graph and identifies a Perfect Matching (M) for all nodes with odd degrees. By combining M and T, I obtain an Eulerian Circuit and record the nodes in the order they appear to create a Hamiltonian Path. I am facing a significant challenge with the Minimum Spanning Tree, as it takes the shape of a Star Graph with the dummy node at the center for obvious reasons. This leads to a significant loss of distance context between the nodes, resulting in highly inaccurate paths – IlayAsayag May 15 '23 at 10:20
  • The diagram is showing 4 different paths that every one of them is inaccurate on its own. Look at the blue route for example. its route is obviously not the shortest path, right? I added to the question a screen shot of the optimal paths if it helps – IlayAsayag May 15 '23 at 13:25
  • I don't think its a matter of implementation to be honest. Just to be clear I do not understand how the 0-weight dummy node would help my algorithm find the shortest path because it looses a lot of information about the distance between nodes. I need someone who is familiar with this approach and can help me understand it – IlayAsayag May 15 '23 at 16:10

0 Answers0