An Evolutionary Algorithm with Heuristic Longest Cycle Crossover for Solving the Capacitated Vehicle Routing Problem
- Resource Type
- Conference
- Authors
- Visutarrom, Thammarsat; Chiang, Tsung-Che
- Source
- 2019 IEEE Congress on Evolutionary Computation (CEC) Evolutionary Computation (CEC), 2019 IEEE Congress on. :673-680 Jun, 2019
- Subject
- Communication, Networking and Broadcast Technologies
Computing and Processing
General Topics for Engineers
Robotics and Control Systems
Biological cells
Optimization
Evolutionary computation
Vehicle routing
Search problems
Sociology
Statistics
evolutionary algorithm
capacitated vehicle routing problem
cycle crossover
cycle length
nearest neighbor
- Language
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.