CODEWITHSUNDEEP
algorithmgraph-theorycombinatoricstraveling-salesman
AReubens
AReubens

Reputation: 159

Traveling Salesman Problem with Edge Weights Paid by Node

I have a variant of the Asymmetric TSP problem I'm trying to solve.

The graph is fully connected, edges are directional, and nodes can be visited multiple times.

The variation is edge weights between nodes must be paid by the node it goes to, reducing the node's money. If a node's money is less than the edge weight to the node, those edges can no longer be travelled. A solution which visits all nodes and minimises costs is required.

This only solution currently implemented is, for each node, to calculate all possible permutations of incident edges which result keep the node positive, and then to run TSP without consideration of node costs (since only valid edges are initially considered). This however means that TSP is being run on many, many graphs.

ie. Graph (only edges to node X shown):

 B    C
  \   |
   \  |
   10 8
     \|
A--9--X(20)

If the node X has a value of 20, then only 2 of the possible 3 incident edges are possible. For this single node, there are 3 possible permutations which work, meaning the current solution runs TSP 3 times. When multiple nodes are limited, and there are more edges, the amount of valid graphs explodes meaning TSP needs to be run many times.

Is there a variant which is able to consider such edge-node costs in a single run, or a better approach to creating the graphs?

Upvotes: 1

Views: 38

Answers (0)

Related Questions