Does a TSP variant exist in which edge costs depend on the vertices already visited?
For instance, if you already visited vertices A, B, and then C, in that order, then now the cost to traverse CD = 5, whereas if you visited B, A, and then C, then the cost to traverse CD would be 8 or something like that.

It doesn't have to depend on the whole visit order so far, it can only depend on the last vertex visited. In a more general sense, if one knows of any TSP variant in which edge costs vary based on some choice made before traversing the edge, please state them here. They might be helpful.

I found the following post, in which the edge costs can depend on the "state" of the visiting entity, which is not unlike my own question : Path finding on graph with state dependent edge costs
Unfortunately, it doesn't have any answer yet.



Your Answer

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

Browse other questions tagged or ask your own question.