Calculate alternative paths in road network

Question

I'm working on an alternative paths finding problem recently and trying to enhance route result's diversity. But there seems to have little material on the internet (or maybe I miss something), what I get is algorithms like remove or add penalty cost for segments on an path already found, which require re-routing multiple times.

Currently we are using bidirectional A* algorithm to construct forward and backward shortest path tree, and each meet points of these two trees will produce an alternative path.

However, since there only exist one optimal path from the root to each meet point, the diversity of alternative paths is still limited. I'm trying to add second parent(may be sub-optimal parent) for each node in road network to tackle this problem, but I have no idea whether this method can solve the problem.

Does anybody have any idea about algorithms to find alternative paths used in industrial map productions, like google map or baidu map. Any suggestion or reference link will be appreciated.

Answer 1

You have multiple ways to implement this.

You can:

• Artificially increase the cost of the optimal path so that if an another path is only slightly slower it will appear first, thus you have an alternative route.
• You can "disable" the best path (or part of it) then compute the optimal path again to force an alternative road to be taken.
• Use advanced techniques such as these presented in this paper. These thechnique are more adapted for industrial usage.