Exploring a Favorable Tradeoff for Finding Every Efficient Path in Large-Scale Networks
针对大规模网络中多目标最短路径问题的高时空开销和决策者偏好多样性的瓶颈，提出一种广义动态规划算法，通过广义支配关系和H-reducible技术加速收敛，能在可容忍时间内找到所有有效路径。
Multiobjective shortest path problem (MSPP) is one of the most critical issues in network optimization, aimed at identifying all efficient paths across conflicting objectives. Nowadays, existing methods face substantial bottlenecks in addressing the diverse preferences of decision makers and high spatiotemporal overhead caused by the calculation process, particularly in cases with large-scale networks. To overcome these obstacles, a generalized MSPP in large-scale networks is investigated with the aim of solving it with diverse preferences of decision makers satisfied and low spatiotemporal overhead. Toward this end, with a novel concept, the generalized dominance relation is introduced, and the generalized multiobjective shortest path algorithm via the generalized dynamic programming approach is developed. Moreover, the H-reducible technique is further employed to accelerate the convergence of the proposed algorithm. Additionally, several rigorous proofs are provided for the conclusions that all efficient paths could be found within a tolerable time by the developed algorithm and the algorithm could be implemented in a distributed manner under mild assumptions. Finally, numerous routing experiments are conducted on large-scale communication networks for demonstrating the effectiveness and competitiveness of our approach.