Hello, I have a variant on the classic 'shortest path' problem and I don't know how to approach it. My graph topology is as such: There is one source and one sink. Other nodes are designated by a letter and subscript integer (e.g., A1,B1,C1,A2,B2,C2,....A30,B30,C30). There is one node per possible letter/integer combination. There is one zero-cost directed edge from the source to each of A1, B1, C1. There is one zero-cost directed edge from each of the nodes with the largest integer to the sink (e.g., when the integers go up to 30, there is one zero-cost directed edge from A30 to the 'Final Destination Node', and an identical edge from B30 and from C30). From each node there is a directed, weighted edge to one other node of each of the other letters with a larger integer. For example, there may be a directed weighted edge from A1 to B3 and from A1 to C10; however you won't see edges from A1 to both B3 and B5 because the destinations are both 'B' edges. There are no edges that move from one node with a letter, to another node with a letter (e.g., no B3 to B10) and no edges that move from a node with a higher integer to one with a lower integer (e.g., no B30 to C10). I know that I can use Djikstra's algorithm to find a singular shortest path from origin to destination, but my goal is somewhat different. I want to: 1) Find a single shortest path from source to sink that visits each of the 'letters' once and only once. Any group of integers will work as long as I visit all the letters. Eg. visiting the node set A1, B22, and C27 between the source and sink is acceptable; visiting A10, A15, B22 is not. 2) Find two paths that, combined, visit each of the letters once and only once. If the 'letter set' was ABCDEF, one route could visit ABD and the other CEF; but we couldn't have one route visit ABCD and the other visit DEF, because D would overlap. The goal is to identify two paths that find the minimal longer route - I don't care about the total time as much as about this minimax. 3) Same question as #2 but with 3 paths, 4 paths, etc. I assume I could make a very complicated integer program but didn't know if there were shortest-path algorithms already available to solve this. Bonus points if it's ready-made in an R package. Thanks in advance for any help you can provide. Ralph
asked
kmwest |

Your first variant sounds exactly like the network formulation of the traveling baseball fan problem. See this blog post: http://blogs.sas.com/content/operations/2015/04/03/the-traveling-baseball-fan-problem/ and this paper: http://support.sas.com/resources/papers/proceedings14/SAS101-2014.pdf The side constraints (called Visit_Once_Network in the paper) are quite simple. The extension to multiple baseball fans is straightforward.
answered
Rob Pratt |