A memetic algorithm for the open capacitated arc routing problem

被引：22
|
作者：
Fung, Richard Y. K. [1 ]
Liu, Ran [2 ]
Jiang, Zhibin [2 ]
机构：
[1] City Univ Hong Kong, Dept Mfg Engn & Engn Management, Kowloon, Hong Kong, Peoples R China
[2] Shanghai Jiao Tong Univ, Sch Mech Engn, Dept Ind Engn & Logist Management, Shanghai 200240, Peoples R China
来源：
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW | 2013年 / 50卷
基金：
中国国家自然科学基金;
关键词：
Open capacitated arc routing problem; Lower bound; Memetic algorithm; RURAL POSTMAN PROBLEM; SUBTOUR ELIMINATION CONSTRAINTS; TABU SEARCH ALGORITHM; HEURISTIC ALGORITHM; SCATTER SEARCH; FLEET SIZE; FORMULATIONS; EXTENSIONS; VEHICLES;
D O I：
10.1016/j.tre.2012.11.003
中图分类号：
F [经济];
学科分类号：
02 ;
摘要：
In this paper, an open capacitated arc routing problem (OCARP) is defined and considered. The OCARP seeks to find a set of minimum-cost open routes that can serve the tasks (i.e., required arcs) of a given graph, subject to the vehicle capacity and travel distance. A mathematical programming formulation and a lower bound are established. An effective memetic algorithm is developed for solving the OCARP. Computational experiments demonstrate that the proposed algorithm can produce high quality solutions within a reasonable computational time span, and the proposed memetic algorithm is superior to the classical genetic algorithm in solution quality. (C) 2012 Elsevier Ltd. All rights reserved.
引用
收藏
页码：53 / 67
页数：15
相关论文
共 50 条
  • [1] Improved Memetic Algorithm for Capacitated Arc Routing Problem
    Mei, Yi
    Tang, Ke
    Yao, Xin
    2009 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-5, 2009, : 1699 - +
  • [2] A Memetic Algorithm for Periodic Capacitated Arc Routing Problem
    Mei, Yi
    Tang, Ke
    Yao, Xin
    IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 2011, 41 (06): : 1654 - 1667
  • [3] Memetic algorithm with route decomposing for periodic capacitated arc routing problem
    Zhang, Yuzhou
    Mei, Yi
    Tang, Ke
    Jiang, Keqin
    APPLIED SOFT COMPUTING, 2017, 52 : 1130 - 1142
  • [4] Memetic Algorithm with adaptive Local Search for Capacitated Arc Routing Problem
    Yao, Tingting
    Yao, Xin
    Han, Shuangshuang
    Wang, Yingchun
    Cao, Dongpu
    Wang, Feiyue
    2017 IEEE 20TH INTERNATIONAL CONFERENCE ON INTELLIGENT TRANSPORTATION SYSTEMS (ITSC), 2017,
  • [5] A memetic algorithm with iterated local search for the capacitated arc routing problem
    Liu, Tiantang
    Jiang, Zhibin
    Geng, Na
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2013, 51 (10) : 3075 - 3084
  • [6] Decomposition-Based Memetic Algorithm for Multiobjective Capacitated Arc Routing Problem
    Mei, Yi
    Tang, Ke
    Yao, Xin
    IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2011, 15 (02) : 151 - 165
  • [7] Towards Probabilistic Memetic Algorithm: An Initial Study on Capacitated Arc Routing Problem
    Feng, Liang
    Ong, Yew-Soon
    Quang Huy Nguyen
    Tan, Ah-Hwee
    2010 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2010,
  • [8] Memetic Algorithm with Heuristic Candidate List Strategy for Capacitated Arc Routing Problem
    Fu, Haobo
    Mei, Yi
    Tang, Ke
    Zhu, Yanbo
    2010 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2010,
  • [9] Memetic algorithm with non-smooth penalty for capacitated arc routing problem
    Li, Rui
    Zhao, Xinchao
    Zuo, Xingquan
    Yuan, Jianmei
    Yao, Xin
    KNOWLEDGE-BASED SYSTEMS, 2021, 220
  • [10] A Memetic Algorithm for Uncertain Capacitated Arc Routing Problems
    Wang, Juan
    Tang, Ke
    Yao, Xin
    2013 IEEE WORKSHOP ON MEMETIC COMPUTING (MC), 2013, : 72 - 79
12345