Exploring a Favorable Tradeoff for Finding Every Efficient Path in Large-Scale Networks

Area of Science:

• Network Optimization
• Algorithm Development
• Computer Science

Background:

• The multiobjective shortest path problem (MSPP) is crucial for network optimization but faces challenges with diverse decision-maker preferences and high computational costs in large networks.
• Existing methods struggle to balance conflicting objectives and manage the spatiotemporal overhead inherent in solving MSPP for large-scale networks.

Purpose of the Study:

• To develop a generalized algorithm for MSPP in large-scale networks that accommodates diverse decision-maker preferences.
• To significantly reduce the spatiotemporal overhead associated with solving MSPP, making it more practical for real-world applications.

Main Methods:

• Introduction of a novel concept: the generalized dominance relation.
• Development of a generalized multiobjective shortest path algorithm using a generalized dynamic programming approach.
• Application of the H-reducible technique to accelerate algorithm convergence.

Main Results:

• The proposed algorithm successfully finds all efficient paths within a tolerable time frame.
• Rigorous proofs confirm the algorithm's ability to handle diverse preferences and achieve low spatiotemporal overhead.
• Experimental results on large-scale communication networks demonstrate the algorithm's effectiveness and competitiveness.

Conclusions:

• The developed generalized MSPP algorithm offers an effective solution for large-scale network optimization problems.
• The approach satisfies diverse decision-maker preferences while maintaining low computational complexity.
• The algorithm's potential for distributed implementation under mild assumptions further enhances its applicability.