路网多样化替代路径求解技术咨询：算法选型与优化建议

Hey there! Let me break down some practical approaches and insights that might help with your alternative route research, including what industrial-grade mapping platforms like Google Maps or Baidu Maps tend to use, plus feedback on your proposed multi-parent node idea.

1. Your Suboptimal Parent Node Idea: Feasible and Worth Testing #

Your thought of adding a second (or even top-k) suboptimal parent nodes to each node is definitely a valid direction—it falls into the realm of k-shortest path trees and multi-parent path generation. Here’s why it works and what to watch out for:

• When extending your bidirectional A* to track top-k parent nodes per node, you can combine paths from the forward tree’s top-k paths and reverse tree’s top-k paths at intersection points, which immediately creates more diversified routes than just using the single optimal parent.
• Key caveats: Control the value of k (start with k=2 or 3 first) to avoid exponential computation overhead. Also, add loop detection logic to filter out paths that revisit nodes unnecessarily—this keeps your alternative routes practical.

2. Industrial-Grade Platform Strategies for Alternative Routes #

Big players like Google Maps and Baidu Maps don’t rely on a single algorithm; they combine multiple techniques to balance diversity, efficiency, and user relevance:

• Preference-Driven Multi-Objective Optimization: Instead of just penalizing existing paths, they generate routes optimized for different user priorities—e.g., fastest time, shortest distance, least traffic, or even "scenic routes". Each of these priorities acts as a separate constraint, naturally producing distinct alternative paths.
• Precomputed Route Corridors: They precompute parallel route corridors in high-traffic areas (like urban downtowns or major highways). These corridors are sets of interconnected roads that offer viable alternatives to the main optimal path, allowing quick retrieval instead of real-time full computation.
• Data-Driven Path Generation: They leverage historical user trajectory data and traffic patterns to learn which alternative paths are actually used by drivers. This means some recommended routes might not be the "algorithmically optimal" ones, but they’re more aligned with real-world driver behavior (e.g., avoiding a short but frequently congested street).
• Dynamic Penalty Adjustment: When generating alternatives, they dynamically adjust weights for roads already included in the primary path—but not just a fixed penalty. The penalty might vary based on road type (e.g., higher penalty for major highways to push towards side roads, lower for local streets to keep options realistic).

3. Practical Recommendations for Your Research #

• Start Small with k-Shortest Paths: Implement a simplified version of Yen’s algorithm or Eppstein’s algorithm alongside your bidirectional A*—these are classic academic algorithms for generating k distinct shortest paths, which can serve as a baseline for diversity.
• Integrate Multi-Objective Metrics: Add more cost dimensions beyond distance (e.g., estimated travel time, number of intersections, road speed limits). Use Pareto optimality to select routes that are optimal for at least one dimension—this ensures your alternatives aren’t just minor variations of the main path.
• Test Deviation Constraints: Define a maximum deviation threshold (e.g., alternative paths can’t be more than 20% longer than the shortest path) to keep routes practical while maintaining diversity. This prevents generating overly detoured paths that users won’t actually take.

内容的提问来源于stack exchange，提问作者Wang Yudong