Heuristic-Search Approaches for the Multi-Objective Shortest-Path Problem: Progress and Research Opportunities

In the multi-objective shortest-path problem we are interested in computing a path, or a set of paths that simultaneously balance multiple cost functions. This problem is important for a diverse range of applications such as transporting hazardous materials considering travel distance and risk. This family of problems is not new with results dating back to the 1970's. Nevertheless, the significant progress made in the field of heuristic search resulted in a new and growing interest in the sub-field of multi-objective search. Consequently, in this paper we review the fundamental problems and techniques common to most algorithms and provide a general overview of the field. We then continue to describe recent work with an emphasis on new challenges that emerged and the resulting research opportunities.

• Publication year

  2023

• Venue

  International Joint Conference on Artificial Intelligence

• Publication date

  2023-08-01

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.24963/ijcai.2023/757
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multi-objective Search via Lazy and Efficient Dominance Checks

  2023influential reference
• Exact algorithms for multiobjective linear optimization problems with integer variables: A state of the art survey

  2022cited by this paper
• Enhanced Multi-Objective A* with Partial Expansion

  2022cited by this paper
• Simple and efficient bi-objective search algorithms via fast dominance checks

  2022cited by this paper
• A*pex: Efficient Approximate Multi-Objective Search on Graphs

  2022cited by this paper
• Admissible Heuristics for Multi-Objective Planning

  2022influential reference
• Multi-Objective Safe-Interval Path Planning With Dynamic Obstacles

  2022cited by this paper
• Anytime Approximate Bi-Objective Search

  2022cited by this paper
• Bounded-Cost Bi-Objective Heuristic Search

  2022cited by this paper
• Enhanced Multi-Objective A* Using Balanced Binary Search Trees

  2022cited by this paper
• Subset Approximation of Pareto Regions with Bi-objective A

  2022cited by this paper
• Approximation Algorithms

  2021influential reference
• A practical guide to multi-objective reinforcement learning and planning

  2021cited by this paper
• An Improved Multiobjective Shortest Path Algorithm

  2021cited by this paper
• Computationally-Efficient Roadmap-based Inspection Planning via Incremental Lazy Search

  2021cited by this paper
• Multi-objective Conflict-based Search for Multi-agent Path Finding

  2021cited by this paper
• Multi-Objective Path-Based D* Lite

  2021cited by this paper
• Bi-objective Search with Bi-directional A

  2021cited by this paper
• Merge-and-Shrink: A Compositional Theory of Transformations of Factored Transition Systems

  2021cited by this paper
• Targeted multiobjective Dijkstra algorithm

  2021cited by this paper
• Research Challenges and Opportunities in Multi-Agent Path Finding and Multi-Agent Pickup and Delivery Problems

  2020cited by this paper
• A Scalable Many-Objective Pathfinding Benchmark Suite

  2020cited by this paper
• Data structures for non-dominated sets: implementations and empirical assessment of two decades of advances

  2020cited by this paper
• Approximate bi-criteria search by efficient representation of subsets of the Pareto-optimal frontier

  2020cited by this paper
• The 2 k Neighborhoods for Grid Path Planning

  2020cited by this paper
• Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

  2019cited by this paper
• A biobjective Dijkstra algorithm

  2019cited by this paper
• Toward Asymptotically-Optimal Inspection Planning via Efficient Near-Optimal Graph Search

  2019cited by this paper
• A tutorial on multiobjective optimization: fundamentals and evolutionary methods

  2018cited by this paper
• Multi-Objective Optimisation Based Planning of Power-Line Grid Expansions

  2018cited by this paper
• Multi-Objective Decision Making

  2017cited by this paper
• Many-objective stochastic path finding using reinforcement learning

  2017cited by this paper
• ND-Tree-Based Update: A Fast Algorithm for the Dynamic Nondominance Problem

  2016cited by this paper
• Analysis of FPTASes for the multi-objective shortest path problem

  2016cited by this paper
• Parametric search for the bi-attribute concave shortest path problem

  2016cited by this paper
• The 2014 International Planning Competition: Progress and Trends

  2015cited by this paper
• Dimensionality reduction in multiobjective shortest path search

  2015influential reference
• The maximin HAZMAT routing problem

  2015cited by this paper
• A Parallel Computing Framework for Finding the Supported Solutions to a Biobjective Network Optimization Problem

  2015cited by this paper
• A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem

  2015cited by this paper
• Parallel Bi-objective Shortest Paths Using Weight-Balanced B-trees with Bulk Updates

  2014cited by this paper
• LP-Based Heuristics for Cost-Optimal Planning

  2014cited by this paper
• A Survey of Multi-Objective Sequential Decision-Making

  2013influential reference
• Parallel Label-Setting Multi-objective Shortest Path Search

  2013cited by this paper
• Multicriteria path and tree problems: discussion on exact algorithms and applications

  2012cited by this paper
• Route Planning for Bicycles - Exact Constrained Shortest Paths Made Practical via Contraction Hierarchy

  2012cited by this paper
• A comparison of multiobjective depth-first algorithms

  2012cited by this paper
• Data Structures in Multi-Objective Evolutionary Algorithms

  2012cited by this paper
• I and J

  2012cited by this paper
• Approximating the Pareto Front of Multi-criteria Optimization Problems

  2010cited by this paper
• Multiobjective A* search with consistent heuristics

  2010cited by this paper
• Agent

  2010cited by this paper
• A New Approach to Iterative Deepening Multiobjective A

  2009cited by this paper
• Near Admissible Algorithms for Multiobjective Search

  2008cited by this paper
• Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms

  2007cited by this paper
• Evolutionary Algorithms for the Multiobjective Shortest Path Problem

  2007cited by this paper
• Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications

  2006cited by this paper
• On the cardinality of the Pareto set in bicriteria shortest path problems

  2006cited by this paper
• A New Approach to Multiobjective A* Search

  2005cited by this paper
• D*lite

  2002cited by this paper
• Label Correcting Methods to Solve Multicriteria Shortest Path Problems

  2001cited by this paper
• On the approximability of trade-offs and optimal access of Web sources

  2000cited by this paper
• A* with Partial Expansion for Large Branching Factor Problems

  2000cited by this paper
• Admissible Heuristics for Optimal Planning

  2000cited by this paper
• Dijkstra's algorithm on-line: an empirical case study from public railroad transport

  1999cited by this paper
• Nonlinear multiobjective optimization

  1998cited by this paper
• Tools and Algorithms for the Construction and Analysis of Systems

  1996cited by this paper
• Multiobjective transportation network design and routing problems: Taxonomy and annotation

  1993cited by this paper
• Algorithms

  1992cited by this paper
• Multiobjective A*

  1991cited by this paper
• A parametric approach to solving bicriterion shortest path problems

  1991cited by this paper
• An empirical investigation of some bicriterion shortest path algorithms

  1989cited by this paper
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems

  1987cited by this paper
• Some Considerations about Computational Complexity for Multi Objective Combinatorial Problems

  1987cited by this paper
• On a special class of bicriterion path problems

  1984cited by this paper
• Bicriterion Path Problems

  1980cited by this paper
• Multiple Objective Decision Making - Methods and Applications: A State-of-the-Art Survey

  1979cited by this paper
• A New Approach to Multiple Criteria Decision-Making

  1976cited by this paper
• A Formal Basis for the Heuristic Determination of Minimum Cost Paths

  1968cited by this paper

• Parametric Traversal for Multi-Dimensional Cost-Aware Graph Reasoning

  2026cites this paper
• Intelligent Search and Multiobjective Path Planning With Application to Ship Routing

  2026cites this paper
• Planning with Minimal Disruption

  2025cites this paper
• EMOA*: A framework for search-based multi-objective path planning

  2025cites this paper
• User preferences in multi-objective routes: The role of gradient visualization and personality measures

  2025cites this paper
• Generalizing Multi-Objective Search via Objective-Aggregation Functions

  2025cites this paper
• Generalized Shortest Path Problem: An Innovative Approach for Non-Additive Problems in Conditional Weighted Graphs

  2024cites this paper
• OPMOS: Ordered Parallel Algorithm for Multi-Objective Shortest-Paths

  2024cites this paper
• The Multi-Objective Shortest Path Problem with Multimodal Transportation for Emergency Logistics

  2024cites this paper
• Offline Task Assistance Planning on a Graph:Theoretic and Algorithmic Foundations

  2024cites this paper
• Theoretical Study on Multi-objective Heuristic Search

  2024cites this paper
• Algorithmic Motion Planning Meets Minimially-Invasive Robotic Surgery

  2023cites this paper
• Field Testing of a Stochastic Planner for ASV Navigation Using Satellite Images

  2023cites this paper
• On the Algorithmic Foundations of Task Assistance Planning

  year unknowncites this paper
• Artificial Intelligence

  year unknowncites this paper