Balancing Accuracy and Efficiency:The ε-Multi-objective Dijkstra Algorithmfor Large-Scale Optimization Problems

Multi-objective optimization problems with large underlying networks arise in many critical transportation,logistics, and infrastructure applications. However, conventional multi-objective shortest path algorithmsstruggle to scale due to the combinatorial explosion of the search space as problem size increases. This paperproposes a novel approximation algorithm called the ε-Multi-objective Dijkstra Algorithm (ε-MDA) thatleverages an ε-dominance technique to enable efficient, near-optimal solutions for large problem instances.Extensive experiments on grid and network graphs demonstrate that ε-MDA achieves over ۱۰,۰۰۰x speed upcompared to the exact Multi-objective Dijkstra Algorithm while still providing high-quality approximatePareto fronts. This work represents a significant advance in overcoming the scalability challenges of multiobjectiveoptimization for real-world network-based decision problems across transportation, logistics,emergency services, and more. The proposed ε-MDA algorithm and empirical results lay the algorithmicfoundation and evidence needed to tackle large-scale multi-objective combinatorial optimization problemswhere conventional methods fail.

Keywords:

Multi-objective Optimization , ε-Multi-objective Dijkstra Algorithm , Multi-objectiveShortest Path , Computational Complexity , Approximation Algorithm , Computational Efficiency , Algorithmic Innovation , Optimization Challenges , Shortest Path Algorithms , Label SettingAlgorithms , Performance Analysis , Empirical Evaluation