0

I'm trying to find a shortest path algorithm (which does not need to be optimal) for a path with intermediate destinations. Consider the following case: One wants to go from A to Z and in between wants to visit B and C. For both, B and C, there are multilocal options,b1 and b2, and c1 and c2. Just to make it more practical, I want to go from my place (A) to a friends place (Z), but on my way I want to visit a supermarket (B), of which there are two in the area (b1 and b2), and I want to go to a pharmacy, of which there are also two in the area (c1 and c2). The order of whether I first visit the supermarket or the pharmacy does not matter, but I favor the shortest path to my friend. Accordingly, I need the shortest path from A to Z with an (close to) optimal ordering of the intermediate destinations B and C. I hope this is understandable.

Now, I first thought I may first calculate all shortest paths between a certain option of an intermediate destination (let's consider here b1) and the start node (A), the destination node (Z) and the nodes of the options of the other intermediate destination (c1 and c2). Accordingly I would calcuate a shortest path (e.g. with Dijkstra) between:

b1 - A

b1 - Z

b1 - c1

b1 - c2

The algorithm would do this also for b2, c1, and c2, would order it then and select the shortest path which would include one option of B and one of C. However, with increasing options and as such an increasing network the peformance would be low. Therefore I thought to use the Yen's algorithm. This would lengthen the path between A and Z artificially, and I would include an iteration restriction (e.g. after calculating 100 paths, stop), then ordering the paths according to some priority. Accordingly, it should give out one shortest path between A and Z which would include at least one option (node) for B and one for C. However, here find a challenge to use it for my network. Have a look at the first image. red nodes = end nodes and target nodes
The red nodes are dangling nodes, but these nodes are also options for intermediate destinations. When I understand the Yen's correctly, dangling edges would cause the algorithm to stop iterating before it achieves the destination, and as such,no path would include intermediate destinations which are within a dangling branch. Instead of stop iterating, the algorithm would need to go the danling branch backwards and iterate further until it reaches node Z. Have a look at the arrows of the second image , which show which path it would need to calculate. arrows showing the path needed to be calulated. Those 'dead branches' need to be gone forwars AND backwards and, in the end, included in the path. Is this named to be a 'loop'? I hadn't had a look at Eppstein yet, but I think it includes the possibility of having also loops in the path. But... is this a loop?? If someone out there has experience with Yen's or Eppstein I would be glad to hear his/her opinion on this case! I also thought about merging the information of the nodes within the dead branch to the closest inbound node, or generate a new node on the closest, relevant edge. For example, in the first image, this would result in that the node a would get the information from node b, and the node c would get the information from the nodes d and e. However, I find this semioptimal as in some cases imprecise (example of such a case would be node e, as it is in a little distance from c).

  • This is a vehicle routing problem: en.wikipedia.org/wiki/Vehicle_routing_problem with optional locations – Karussell May 13 '18 at 15:50
  • @ Karussell I thought it is not a VRP, as the targets are not set, only one option of each selected intermediate destination will be included, and paths between two options of the same functional destination (so e.g. between b1 and b2) will not be calculated at all. Therefore I think this is not a VRP, or at least only partially? – mauegraus May 14 '18 at 11:54
  • Maybe this is more an application for the Floyd-Warshall? I'm a bit surprised that there is such low response. Is there something unclear? Please ask for more information if something is unclear. – mauegraus May 14 '18 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.