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

Thammarsat Visutarrom; Tsung Che Chiang

doi:10.1109/CEC.2019.8789946

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

Thammarsat Visutarrom, Tsung Che Chiang

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

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 language	English
Title of host publication	2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	673-680
Number of pages	8
ISBN (Electronic)	9781728121536
DOIs	https://doi.org/10.1109/CEC.2019.8789946
Publication status	Published - 2019 Jun
Event	2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Wellington, New Zealand Duration: 2019 Jun 10 → 2019 Jun 13

Publication series

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

Conference

Conference	2019 IEEE Congress on Evolutionary Computation, CEC 2019
Country/Territory	New Zealand
City	Wellington
Period	2019/06/10 → 2019/06/13

Keywords

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

ASJC Scopus subject areas

Computational Mathematics
Modelling and Simulation

Access to Document

10.1109/CEC.2019.8789946

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). Article 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 proceeding › Conference contribution

Visutarrom, T & Chiang, TC 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, 2019/06/10. https://doi.org/10.1109/CEC.2019.8789946

Visutarrom T, Chiang TC. 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). doi: 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{11e860e76755490d8dd95ffe89917ef5,

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 Chiang, {Tsung Che}",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE Congress on Evolutionary Computation, CEC 2019 ; Conference date: 10-06-2019 Through 13-06-2019",

year = "2019",

month = jun,

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

Y1 - 2019/6

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.

T2 - 2019 IEEE Congress on Evolutionary Computation, CEC 2019

Y2 - 10 June 2019 through 13 June 2019

ER -

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this