ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

An effective memetic algorithm for heterogeneous vehicle CARP

  • School of Computer and Information,Anqing Normal University,Anqing 246133,China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2017.07.006
  • Received Date: 30 December 2016
  • Rev Recd Date: 11 April 2017
  • Publish Date: 31 July 2017
    Abstract

  • Abstract

    In view of wider application background，heterogeneous vehicle capacitated arc routing problem (HVCARP) and approach for it are investigated in this paper. First, the cost of any route in HVCARP is divided into two parts, i.e., variable cost and fixed cost, and penalty coefficients for vehicles keep the routes and their vehicles close. In view of the characteristic of HVCARP, we propose a local search operator, namely exchanging vehicles among same group routes (EVSGR) for the vehicle，which adjusts the vehicles for routes based on the loads and vehicles of the routes so as to minimize the cost. Then，the EVSGR operator is integrated into memetic algorithm (MA), and the resultant algorithm is used to solve HVCARP. Finally, the proposed algorithm is run on the instances modified from the instances of the benchmark data sets for CARP, and a large number of experimental results show that the EVSGR operator based memetic algorithm is effective for HVCARP.

    Abstract

    In view of wider application background，heterogeneous vehicle capacitated arc routing problem (HVCARP) and approach for it are investigated in this paper. First, the cost of any route in HVCARP is divided into two parts, i.e., variable cost and fixed cost, and penalty coefficients for vehicles keep the routes and their vehicles close. In view of the characteristic of HVCARP, we propose a local search operator, namely exchanging vehicles among same group routes (EVSGR) for the vehicle，which adjusts the vehicles for routes based on the loads and vehicles of the routes so as to minimize the cost. Then，the EVSGR operator is integrated into memetic algorithm (MA), and the resultant algorithm is used to solve HVCARP. Finally, the proposed algorithm is run on the instances modified from the instances of the benchmark data sets for CARP, and a large number of experimental results show that the EVSGR operator based memetic algorithm is effective for HVCARP.
    • FullText(HTML)
  • loading
    • References(22)
  • [1]
    梅一. 基于元启发式方法对限量弧路由问题的求解[D]. 合肥：中国科学技术大学, 2010.
    [2]
    GOLDEN B L, DEARMON J S, BAKER E K. Computational experiments with algorithms for a class of routing problems[J]. Computers & Operations Research, 1983, 10(1): 47-59.
    [3]
    ULUSOY G. The fleet size and mix problem for capacitated arc routing[J].European Journal of Operational Research, 1985, 22(3): 329-337.
    [4]
    LPEZ E B, AUCEJO V C, SALVADOR A C, et al. The capacitated arc routing problem: A heuristic algorithm[J]. 1990, 14(1): 107-122.
    [5]
    HERTZ A, LAPORTE G, MITTAZ M. A tabu search heuristic for the capacitated arc routing problem[J]. Operations Research, 2000, 48(1): 129-135.
    [6]
    GREISTORFER P. A tabu scatter search metaheuristic for the arc routing problem[J]. Computers & Industrial Engineering, 2003, 44(2): 249-266.
    [7]
    BRANDO J, EGLESE R. A deterministic tabu search algorithm for the capacitated arc routing problem[J]. Computers & Operations Research, 2008, 35(4): 1112-1126.
    [8]
    HERTZ A, MITTAZ M. A variable neighborhood descent algorithm for the undirected capacitated arc routing problem[J]. Transportation Science, 2001, 35(4): 425-434.
    [9]
    BEULLENS P, MUYLDERMANS L, CATTRYSSE D, et al. A guided local search heuristic for the capacitated arc routing problem[J]. European Journal of Operational Research, 2003, 147 (3): 629-643.
    [10]
    LACOMME P. Competitive memetic algorithms for arc routing problems[J]. Annals of Operations Research, 2004, 131(1): 159-185.
    [11]
    ZHANG Y Z, MEI Y, TANG K, et al. Memetic algorithm with route decomposing for periodic capacitated arc routing problem[J]. Applied Soft Computing, 2017, 52: 1130-1142.
    [12]
    TANG K, MEI Y, YAO X. Memetic algorithm with extended neighborhood search for capacitated arc routing problems[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 1151-1166.
    [13]
    MEI Y, TANG K, YAO X. A memetic algorithm for periodic capacitated arc routing problem[J]. IEEE Transactions on Systems Man & Cybernetics, Part B: Cybernetics, 2011, 41(6): 1654-1667.
    [14]
    MEI Y, LI X D, YAO X. Cooperative coevolution with route distance grouping for large-scale capacitated arc routing problems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 435-449.
    [15]
    MEI Y, TANG K, YAO X. A global repair operator for capacitated arc routing problem[J]. IEEE Transactions on Systems Man & Cybernetics, Part B: Cybernetics, 2009, 39(3): 723-734.
    [16]
    HANDA H, CHAPMAN L, YAO X. Robust route optimization for gritting/salting trucks: A CERCIA experience[J]. IEEE Computational Intelligence Magazine, 2006, 1(1): 6-9.
    [17]
    刘天堂, 江志斌, 耿娜, 等. 带有异质固定车队的能力约束弧路径问题[J]. 上海交通大学学报, 2012, 46(11): 1759-1763.
    LIU T T, JIANG Z B, GENG N, et al. The heterogeneous fixed fleet capacitated arc routing problem[J]. Journal of Shanghai Jiaotong University, 2012, 46(11): 1759-1763.
    [18]
    胡珊，林丹. 求解CARP-RP-ML 问题的改进算法[J]. 计算机工程, 2012, 38(7): 168-170.
    HU Shan, LIN Dan. Algorithms for solving CARP-RP-ML problem[J]. Computer Engineering, 2012, 38(7): 168-170.
    [19]
    金倩倩, 林丹. 求解UCARPP问题的变邻域搜索算法[J]. 计算机工程, 2012, 38(21): 290-292.
    JIN Q Q, LIN D. Variable neighborhood search algorithm for solving UCARPP problem[J]. Computer Engineering, 2012, 38(21): 290-292.
    [20]
    徐凯, 朱征宇. 改进遗传算法对带服务时间约束的弧路径问题的求解[J]. 微机处理, 2010, 31(5): 58-62.
    [21]
    朱征宇, 杨永, 邓欣. 一种求解多车型CARP问题的高效进化算法[J]. 计算机工程与应用, 2008, 44(8): 212-216.
    ZHU Z Y, YANG Y, DENG X，et al. High efficient evolutionary computing method for solving multi-vehicle CARP[J]. Computer Engineering & Applications, 2008, 44(8): 212-216.
    [22]
    MOSCATO P. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms[R]. Pasadena, CA, CalTech Concurrent Computation Program, 1989: 158-179.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    梅一. 基于元启发式方法对限量弧路由问题的求解[D]. 合肥：中国科学技术大学, 2010.
    [2]
    GOLDEN B L, DEARMON J S, BAKER E K. Computational experiments with algorithms for a class of routing problems[J]. Computers & Operations Research, 1983, 10(1): 47-59.
    [3]
    ULUSOY G. The fleet size and mix problem for capacitated arc routing[J].European Journal of Operational Research, 1985, 22(3): 329-337.
    [4]
    LPEZ E B, AUCEJO V C, SALVADOR A C, et al. The capacitated arc routing problem: A heuristic algorithm[J]. 1990, 14(1): 107-122.
    [5]
    HERTZ A, LAPORTE G, MITTAZ M. A tabu search heuristic for the capacitated arc routing problem[J]. Operations Research, 2000, 48(1): 129-135.
    [6]
    GREISTORFER P. A tabu scatter search metaheuristic for the arc routing problem[J]. Computers & Industrial Engineering, 2003, 44(2): 249-266.
    [7]
    BRANDO J, EGLESE R. A deterministic tabu search algorithm for the capacitated arc routing problem[J]. Computers & Operations Research, 2008, 35(4): 1112-1126.
    [8]
    HERTZ A, MITTAZ M. A variable neighborhood descent algorithm for the undirected capacitated arc routing problem[J]. Transportation Science, 2001, 35(4): 425-434.
    [9]
    BEULLENS P, MUYLDERMANS L, CATTRYSSE D, et al. A guided local search heuristic for the capacitated arc routing problem[J]. European Journal of Operational Research, 2003, 147 (3): 629-643.
    [10]
    LACOMME P. Competitive memetic algorithms for arc routing problems[J]. Annals of Operations Research, 2004, 131(1): 159-185.
    [11]
    ZHANG Y Z, MEI Y, TANG K, et al. Memetic algorithm with route decomposing for periodic capacitated arc routing problem[J]. Applied Soft Computing, 2017, 52: 1130-1142.
    [12]
    TANG K, MEI Y, YAO X. Memetic algorithm with extended neighborhood search for capacitated arc routing problems[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 1151-1166.
    [13]
    MEI Y, TANG K, YAO X. A memetic algorithm for periodic capacitated arc routing problem[J]. IEEE Transactions on Systems Man & Cybernetics, Part B: Cybernetics, 2011, 41(6): 1654-1667.
    [14]
    MEI Y, LI X D, YAO X. Cooperative coevolution with route distance grouping for large-scale capacitated arc routing problems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 435-449.
    [15]
    MEI Y, TANG K, YAO X. A global repair operator for capacitated arc routing problem[J]. IEEE Transactions on Systems Man & Cybernetics, Part B: Cybernetics, 2009, 39(3): 723-734.
    [16]
    HANDA H, CHAPMAN L, YAO X. Robust route optimization for gritting/salting trucks: A CERCIA experience[J]. IEEE Computational Intelligence Magazine, 2006, 1(1): 6-9.
    [17]
    刘天堂, 江志斌, 耿娜, 等. 带有异质固定车队的能力约束弧路径问题[J]. 上海交通大学学报, 2012, 46(11): 1759-1763.
    LIU T T, JIANG Z B, GENG N, et al. The heterogeneous fixed fleet capacitated arc routing problem[J]. Journal of Shanghai Jiaotong University, 2012, 46(11): 1759-1763.
    [18]
    胡珊，林丹. 求解CARP-RP-ML 问题的改进算法[J]. 计算机工程, 2012, 38(7): 168-170.
    HU Shan, LIN Dan. Algorithms for solving CARP-RP-ML problem[J]. Computer Engineering, 2012, 38(7): 168-170.
    [19]
    金倩倩, 林丹. 求解UCARPP问题的变邻域搜索算法[J]. 计算机工程, 2012, 38(21): 290-292.
    JIN Q Q, LIN D. Variable neighborhood search algorithm for solving UCARPP problem[J]. Computer Engineering, 2012, 38(21): 290-292.
    [20]
    徐凯, 朱征宇. 改进遗传算法对带服务时间约束的弧路径问题的求解[J]. 微机处理, 2010, 31(5): 58-62.
    [21]
    朱征宇, 杨永, 邓欣. 一种求解多车型CARP问题的高效进化算法[J]. 计算机工程与应用, 2008, 44(8): 212-216.
    ZHU Z Y, YANG Y, DENG X，et al. High efficient evolutionary computing method for solving multi-vehicle CARP[J]. Computer Engineering & Applications, 2008, 44(8): 212-216.
    [22]
    MOSCATO P. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms[R]. Pasadena, CA, CalTech Concurrent Computation Program, 1989: 158-179.
    Recommended articles
    TrendMD
    Volume 47 Issue 7 page: 583-593
    Cover

    Article Metrics

    Article views (548) PDF downloads(180)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return