Multiobjective heuristic search in road maps

被引：23
作者：
Machuca, E. [1 ]
Mandow, L. [1 ]
机构：
[1] Univ Malaga, Dpto Lenguajes & Ciencias Computac, E-29071 Malaga, Spain
来源：
EXPERT SYSTEMS WITH APPLICATIONS | 2012年 / 39卷 / 07期
关键词：
Multiobjective shortest path problem; Best-first search; Heuristic search; Artificial intelligence; Road networks;
D O I：
10.1016/j.eswa.2011.12.022
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
This article considers the application of exact multiobjective techniques to search in large size realistic road maps. In particular, the NAMOA* algorithm is successfully applied to several road networks from the DIMACS shortest path implementation challenge with two objectives. An efficient heuristic function previously proposed by Tung and Chew is evaluated. Heuristic values are precalculated with search. The precalculation effort is shown to pay off during the multiobjective search stage. An improvement to the calculation procedure is also proposed, resulting in added improved time performance in many problem instances. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码：6435 / 6445
页数：11
相关论文
共 34 条
  • [1] [Anonymous], 1979, P 3 C MULT CRIT DEC
  • [2] [Anonymous], 1984, Heuristics
  • [3] Bauer R, 2010, LECT NOTES COMPUT SC, V6078, P359, DOI 10.1007/978-3-642-13073-1_32
  • [4] On the selection of k routes in multiobjective hazmat route planning
    Caramia, Massimiliano
    Giordani, Stefano
    Iovanella, Antonio
    [J]. IMA JOURNAL OF MANAGEMENT MATHEMATICS, 2010, 21 (03) : 239 - 251
  • [5] Pattern databases
    Culberson, JC
    Schaeffer, J
    [J]. COMPUTATIONAL INTELLIGENCE, 1998, 14 (03) : 318 - 334
  • [6] GENERALIZED BEST-1ST SEARCH STRATEGIES AND THE OPTIMALITY OF A
    DECHTER, R
    PEARL, J
    [J]. JOURNAL OF THE ACM, 1985, 32 (03) : 505 - 536
  • [7] On finding dissimilar Pareto-Optimal paths
    Dell'Olmo, P
    Gentili, M
    Scozzari, A
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 162 (01) : 70 - 82
  • [8] Delling D, 2009, LECT NOTES COMPUT SC, V5515, P117, DOI 10.1007/978-3-642-02094-0_7
  • [9] Delling D, 2009, LECT NOTES COMPUT SC, V5526, P125, DOI 10.1007/978-3-642-02011-7_13
  • [10] Dijkstra E. W., 1959, NUMER MATH, V1, P269
1234