Balancing Accuracy and Efficiency:The ε-Multi-objective Dijkstra Algorithmfor Large-Scale Optimization Problems
سال انتشار: 1402
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 53
فایل این مقاله در 13 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ICTBC07_020
تاریخ نمایه سازی: 26 اسفند 1402
چکیده مقاله:
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.
کلیدواژه ها:
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
نویسندگان
Amaneh Mollaei
Master's student in Computer Engineering, Urmia University,
Asghar Asgharian Sardroud
Ph.D. in Computer Engineering, Assistant Professor, Urmia University,