A Review of Algorithms for Multi-objective Shortest PathProblems

The multi-objective shortest path (MOSP) problem is critical for optimizing real-world transportation,logistics, emergency response, and infrastructure networks involving multiple conflicting goals. However,conventional MOSP algorithms struggle to scale due to the combinatorial explosion of the search space. Thisreview synthesizes key developments in exact and approximation MOSP techniques. It analyzes theircapabilities and limitations. Exact methods like Martins' algorithm and Multi-objective Dijkstra providecomplete Pareto-optimal solution sets but face exponential complexity. Approximation algorithms includingε-dominance techniques trade optimality for dramatically improved performance in large networks.Enhancements like parallelization, bounding of suboptimality, and problem-specific customization offerpromising directions. Real-world applications in areas like transit network optimization, logistics planning,disaster response, and satellite trajectory optimization showcase the significance and challenges of multiobjectivepath finding. This review both surveys seminal MOSP algorithms and highlights emerginginnovations to balance accuracy and efficiency in solving multi-objective optimization problems on largescalenetworks.

Keywords:

Multi-objective Optimization , Shortest Path Problems , Exact Algorithms , ApproximationAlgorithms , ε-Dominance , Pareto-Optimal Paths , Transportation Optimization , Logistics , Environmental Management , Multi-Criteria Decision Making , Problem Complexity , AlgorithmicApproaches , Resource Allocation , Algorithm Comparison , Scalability Challenges , Real-WorldApplications , Dynamic Algorithms , Bounding Optimality Loss , Parallelization , InterdisciplinaryCollaboration , Review Article , Combinatorial Optimization , Algorithm Efficiency , Resource-Constrained Environments , Route Planning.