期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 253, 期 1, 页码 25-39出版社
ELSEVIER
DOI: 10.1016/j.ejor.2016.02.015
关键词
Capacitated arc routing problem; Memetic search; Tabu thresholding
资金
- PGMO project from the Jacques Hadamard Mathematical Foundation [2014-0024H]
- National Natural Science Foundation of China [61473301, 71201171, 71501179]
The capacitated arc routing problem (CARP) is a difficult combinatorial optimization problem that has been intensively studied in the last decades. We present a hybrid metaheuristic approach (HMA) to solve this problem which incorporates an effective local refinement procedure, coupling a randomized tabu thresholding procedure with an infeasible descent procedure, into the memetic framework. Other distinguishing features of HMA include a specially designed route-based crossover operator for solution recombination and a distance-and-quality based replacement criterion for pool updating. Extensive experimental studies show that HMA is highly scalable and is able to quickly identify either the best known results or improved best known results for almost all currently available CARP benchmark instances. In particular, it discovers an improved best known result for 15 benchmark instances (6 classical instances and 9 large-sized instances whose optima are unknown). Furthermore, we analyze some key elements and properties of the HMA-CARP algorithm to better understand its behavior. (C) 2016 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据