A comparison of heuristic best-first algorithms for bicriterion shortest path problems

► Three heuristic multiobjective best-first (label setting) algorithms are compared. ► The influence of solution depth and correlation between objectives is considered. ► Heuristic algorithm NAMOA ∗ is generally the best alternative. ► A class of problems is analysed where heuristics do not improve...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2012-02, Vol.217 (1), p.44-53
Main Authors: Machuca, E., Mandow, L., Pérez de la Cruz, J.L., Ruiz-Sepulveda, A.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Artificial intelligence
Best-first search
Combinatorial optimization
Comparative studies
Computer science
control theory
systems
Degradation
Exact sciences and technology
Flows in networks. Combinatorial problems
Heuristic
Heuristic search
Information retrieval. Graph
Mathematical problems
Multiobjective shortest path problem
Operational research
Operational research and scientific management
Operational research. Management science
Search theory
Searching
Shortest path algorithms
Shortest-path problems
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:► Three heuristic multiobjective best-first (label setting) algorithms are compared. ► The influence of solution depth and correlation between objectives is considered. ► Heuristic algorithm NAMOA ∗ is generally the best alternative. ► A class of problems is analysed where heuristics do not improve time performance. ► A very bad time performance of heuristic algorithm MOA ∗ is observed and analysed. A variety of algorithms have been proposed to solve the bicriterion shortest path problem. This article analyzes and compares the performance of three best-first (label-setting) algorithms that accept heuristic information to improve efficiency. These are NAMOA ∗, MOA ∗, and Tung & Chew’s algorithm (TC). A set of experiments explores the impact of heuristic information in search efficiency, and the relative performance of the algorithms. The analysis reveals that NAMOA ∗ is the best option for difficult problems. Its time performance can benefit considerably from heuristic information, though not in all cases. The performance of TC is similar but somewhat worse. However, the time performance of MOA ∗ is found to degrade considerably with the use of heuristic information in most cases. Explanations are provided for these phenomena.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2011.08.030