An Evolutionary Algorithm with Heuristic Longest Cycle Crossover for Solving the Capacitated Vehicle Routing Problem

被引:0
|
作者
Visutarrom, Thammarsat [1 ]
Chiang, Tsung-Che [1 ]
机构
[1] Natl Taiwan Normal Univ, Dept Comp Sci & Informat Engn, Taipei, Taiwan
来源
2019 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) | 2019年
关键词
evolutionary algorithm; capacitated vehicle outing problem; cycle crossover; cycle length; nearest neighbor; GENETIC ALGORITHM; OPTIMIZATION; SEARCH;
D O I
10.1109/cec.2019.8789946
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
Crossoveris one of the most important parts of an evolutionary algorithm (EA) for solving optimization problems. Many crossover operators have been proposed for solving the capacitated vehicle routing problem (CVRP), a classical NP-hard problem in the field of operations research. This paper aims to improve the search ability of the cycle crossover (CX). The longest cycle selection and the nearest neighbor heuristic are utilized to improve the performance. Experimental results show that the proposed heuristic longest cycle crossover (HLCX) outperforms the original CX and four other operators. Additionally, we apply a search reduction strategy in the local refinement procedure to reduce the computation time at a little cost of solution quality.
引用
收藏
页码:673 / 680
页数:8
相关论文
共 50 条
  • [21] Nearest Neighbor Insertion Algorithm for Solving Capacitated Vehicle Routing Problem
    Joshi, Sourabh
    Kaur, Sarabjit
    2015 2ND INTERNATIONAL CONFERENCE ON COMPUTING FOR SUSTAINABLE GLOBAL DEVELOPMENT (INDIACOM), 2015, : 86 - 88
  • [22] Solving capacitated vehicle routing problem by artificial bee colony algorithm
    Gomez, Alberto
    Salhi, Said
    2014 IEEE SYMPOSIUM ON COMPUTATIONAL INTELLIGENCE IN PRODUCTION AND LOGISTICS SYSTEMS (CIPLS), 2014, : 48 - 52
  • [23] Solving Capacitated Vehicle Routing Problem Based on Improved Genetic Algorithm
    Wang Jie-sheng
    Liu Chang
    Zhang Ying
    2011 CHINESE CONTROL AND DECISION CONFERENCE, VOLS 1-6, 2011, : 60 - 64
  • [24] A Meta-Genetic Algorithm for Solving the Capacitated Vehicle Routing Problem
    Wink, Stefan
    Back, Thomas
    Emmerich, Michael
    2012 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2012,
  • [25] An evolutionary algorithm for solving Capacitated Vehicle Routing Problems by using local information
    Jiang, Hao
    Lu, Mengxin
    Tian, Ye
    Qiu, Jianfeng
    Zhang, Xingyi
    APPLIED SOFT COMPUTING, 2022, 117
  • [26] An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem
    Ilhan, Ilhan
    SWARM AND EVOLUTIONARY COMPUTATION, 2021, 64
  • [27] Edge assembly crossover for the capacitated vehicle routing problem
    Nagata, Yuichi
    Evolutionary Computation in Combinatorial Optimization, Proceedings, 2007, 4446 : 142 - 153
  • [28] Genetic Crossover Operators for the Capacitated Vehicle Routing Problem
    Ahmed, Zakir Hussain
    Al-Otaibi, Naif
    Al-Tameem, Abdullah
    Saudagar, Abdul Khader Jilani
    CMC-COMPUTERS MATERIALS & CONTINUA, 2023, 74 (01): : 1575 - 1605
  • [29] An evolutionary algorithm with repeated mutations for solving the vehicle routing problem
    Puljic, K
    Manger, R
    ITI 2005: Proceedings of the 27th International Conference on Information Technology Interfaces, 2005, : 507 - 512
  • [30] Adaptive Artificial Bee Colony Algorithm for solving the Capacitated Vehicle Routing Problem
    Mingprasert, S.
    Masuchun, R.
    2017 9TH INTERNATIONAL CONFERENCE ON KNOWLEDGE AND SMART TECHNOLOGY (KST), 2017, : 23 - 27