BibTex

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

Enrique Machuca, Lawrence Mandow, J.L. Pérez de la Cruz, and A. Ruiz-Sepulveda.
A comparison of heuristic best-first algorithms for bicriterion shortest path problems.
European Journal of Operational Research, 217(1):44-53, 2012.

Abstract

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 H W, MOA H W, and Tung & Chew @ Ys all gorithm (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 H W is the best option for difficult problems. Its time pp erformance 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 H W is found to degrade considerably with the use of heuristt ic information in most cases. Explanations are provided for these phenomena.

BibTex

@article{MAC:2012:R,
  doi={10.1016/j.ejor.2011.08.030},
  issn={0377-2217},
  journal={European Journal of Operational Research},
  keywords={Artificial intelligence},
  url={http: //www.sciencedirect.com/science/article/pii/S0377221711008010},
  author={Machuca, Enrique and Mandow, Lawrence and P{\'e}rez de la Cruz, J.L. and Ruiz-Sepulveda, A.},
  title={A comparison of heuristic best-first algorithms for bicriterion shortest path problems},
  volume={217},
  number={1},
  year={2012},
  pages={44--53},
}
Redmine Appliance - Powered by TurnKey Linux