1

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

Improve this question
3
  • 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 Commented May 15, 2023 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 Commented May 15, 2023 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 Commented May 15, 2023 at 16:10
Related questions
0
Determining Eulerian Cycle in Multigraph for Christofides Algorithm
2
Show that 2 times optimal approximation algorithm for traveling salesman (TSP) does not compute an optimal solution
49
What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?
Load 4 more related questions Show fewer related questions

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.