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

Thammarsat Visutarrom, Tsung-Che Chiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Crossover is 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.

Original languageEnglish
Title of host publication2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages673-680
Number of pages8
ISBN (Electronic)9781728121536
DOIs
Publication statusPublished - 2019 Jun 1
Event2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Wellington, New Zealand
Duration: 2019 Jun 102019 Jun 13

Publication series

Name2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings

Conference

Conference2019 IEEE Congress on Evolutionary Computation, CEC 2019
CountryNew Zealand
CityWellington
Period19/6/1019/6/13

Fingerprint

Long Cycle
Operations research
Vehicle routing
Vehicle Routing Problem
Evolutionary algorithms
Crossover
Mathematical operators
Evolutionary Algorithms
Computational complexity
Heuristics
Costs
Local Refinement
Crossover Operator
Operations Research
NP-hard Problems
Nearest Neighbor
Optimization Problem
Cycle
Experimental Results
Operator

Keywords

  • capacitated vehicle routing problem
  • cycle crossover
  • cycle length
  • evolutionary algorithm
  • nearest neighbor

ASJC Scopus subject areas

  • Computational Mathematics
  • Modelling and Simulation

Cite this

Visutarrom, T., & Chiang, T-C. (2019). An Evolutionary Algorithm with Heuristic Longest Cycle Crossover for Solving the Capacitated Vehicle Routing Problem. In 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings (pp. 673-680). [8789946] (2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CEC.2019.8789946

An Evolutionary Algorithm with Heuristic Longest Cycle Crossover for Solving the Capacitated Vehicle Routing Problem. / Visutarrom, Thammarsat; Chiang, Tsung-Che.

2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 673-680 8789946 (2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Visutarrom, T & Chiang, T-C 2019, An Evolutionary Algorithm with Heuristic Longest Cycle Crossover for Solving the Capacitated Vehicle Routing Problem. in 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings., 8789946, 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 673-680, 2019 IEEE Congress on Evolutionary Computation, CEC 2019, Wellington, New Zealand, 19/6/10. https://doi.org/10.1109/CEC.2019.8789946
Visutarrom T, Chiang T-C. An Evolutionary Algorithm with Heuristic Longest Cycle Crossover for Solving the Capacitated Vehicle Routing Problem. In 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2019. p. 673-680. 8789946. (2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings). https://doi.org/10.1109/CEC.2019.8789946
Visutarrom, Thammarsat ; Chiang, Tsung-Che. / An Evolutionary Algorithm with Heuristic Longest Cycle Crossover for Solving the Capacitated Vehicle Routing Problem. 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 673-680 (2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings).
@inproceedings{3204f57e2f7d430d80d3b7700fc7f6ea,
title = "An Evolutionary Algorithm with Heuristic Longest Cycle Crossover for Solving the Capacitated Vehicle Routing Problem",
abstract = "Crossover is 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.",
keywords = "capacitated vehicle routing problem, cycle crossover, cycle length, evolutionary algorithm, nearest neighbor",
author = "Thammarsat Visutarrom and Tsung-Che Chiang",
year = "2019",
month = "6",
day = "1",
doi = "10.1109/CEC.2019.8789946",
language = "English",
series = "2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "673--680",
booktitle = "2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings",

}

TY - GEN

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

AU - Visutarrom, Thammarsat

AU - Chiang, Tsung-Che

PY - 2019/6/1

Y1 - 2019/6/1

N2 - Crossover is 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.

AB - Crossover is 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.

KW - capacitated vehicle routing problem

KW - cycle crossover

KW - cycle length

KW - evolutionary algorithm

KW - nearest neighbor

UR - http://www.scopus.com/inward/record.url?scp=85071291244&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071291244&partnerID=8YFLogxK

U2 - 10.1109/CEC.2019.8789946

DO - 10.1109/CEC.2019.8789946

M3 - Conference contribution

AN - SCOPUS:85071291244

T3 - 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings

SP - 673

EP - 680

BT - 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

ER -