Memetic Algorithm with Heuristic Candidate List Strategy for Capacitated Arc Routing Problem

被引:0
作者
Fu, Haobo [1 ]
Mei, Yi [1 ]
Tang, Ke [1 ]
Zhu, Yanbo [2 ]
机构
[1] Univ Sci & Technol China, Nat Inspired Computat & Applicat Lab, Dept Comp Sci & Technol, Hefei 230027, Anhui, Peoples R China
[2] Beihang Univ, Sch Elect & Informat Engn, Beijing 100083, Peoples R China
来源
2010 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) | 2010年
关键词
OPTIMIZATION;
D O I
暂无
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
Capacitated Arc Routing Problem (CARP) has drawn much attention during the last few years because of its applications in the real world. Recently, we developed a Memetic Algorithm with Extended Neighborhood Search (MAENS), which is powerful in solving CARP. The excellent performance of MAENS is mainly due to one of its local search operators, namely the Merge-Split (MS) operator. However, the higher computational complexity of the MS operator compared to traditional local search operators remains as the major drawback of MAENS, especially when applying it to large-size instances. In this paper, we propose a heuristic candidate list strategy to sample the neighbors generated by the MS operator instead of enumerating or sampling them randomly, in order to avoid unnecessary callings of the MS operator during local search. Based on the strategy, an improved algorithm of MAENS, namely MAENS-II, is developed. Experimental results on benchmark instances showed that MAENS-II managed to obtain the same level of solution quality as MAENS with much less computational time. This should be credited to the utilization of the proposed heuristic strategy. On the other hand, in case both MAENS and MAENS-II were provided comparable computational time, MAENS-II outperformed MAENS in terms of solution quality.
引用
收藏
页数:8
相关论文
共 19 条
  • [1] AHR D, 2004, THESIS RUPERCHT KARL
  • [2] Baldacci R, 2006, NETWORKS, V47, P52, DOI [10.1002/net.20091, 10.1002/NET.20091]
  • [3] THE CAPACITATED ARC ROUTING PROBLEM - LOWER BOUNDS
    BENAVENT, E
    CAMPOS, V
    CORBERAN, A
    MOTA, E
    [J]. NETWORKS, 1992, 22 (07) : 669 - 690
  • [4] A deterministic tabu search algorithm for the capacitated arc routing problem
    Brandao, Jose
    Eglese, Richard
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (04) : 1112 - 1126
  • [5] DeArmon JS, 1981, THESIS U MARYLAND CO
  • [6] Dror M., 2000, Arc routing : Theory, solutions and applications
  • [7] ROUTEING WINTER GRITTING VEHICLES
    EGLESE, RW
    [J]. DISCRETE APPLIED MATHEMATICS, 1994, 48 (03) : 231 - 244
  • [8] COMPUTATIONAL EXPERIMENTS WITH ALGORITHMS FOR A CLASS OF ROUTING-PROBLEMS
    GOLDEN, BL
    DEARMON, JS
    BAKER, EK
    [J]. COMPUTERS & OPERATIONS RESEARCH, 1983, 10 (01) : 47 - 59
  • [9] CAPACITATED ARC ROUTING-PROBLEMS
    GOLDEN, BL
    WONG, RT
    [J]. NETWORKS, 1981, 11 (03) : 305 - 315
  • [10] Robust route optimization for gritting/salting trucks: A CERCIA experience
    Handa, Hisashi
    Chapman, Lee
    Yao, An
    [J]. IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE, 2006, 1 (01) : 6 - 9