Hybrid genetic algorithm for the open capacitated arc routing problem

•A hybrid genetic algorithm is proposed for the open capacitated arc routing problem.•Solutions are encoded as permutations of required arcs, ignoring vehicle capacity.•Chromosomes are decoded into viable solutions by an optimal feasibilization method.•The genetic algorithm outperforms state-of-the-...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2018-02, Vol.90, p.221-231
Main Authors: Arakaki, Rafael Kendy, Usberti, Fábio Luiz
Format: Article
Language:English
Subjects:
Carp
Genetic algorithms
Hybrid genetic algorithm
Metaheuristic
Open capacitated arc routing problem
Operations research
Studies
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•A hybrid genetic algorithm is proposed for the open capacitated arc routing problem.•Solutions are encoded as permutations of required arcs, ignoring vehicle capacity.•Chromosomes are decoded into viable solutions by an optimal feasibilization method.•The genetic algorithm outperforms state-of-the-art methods w.r.t. optimality gaps.•Experiments show the feasibilization method had a substantial role on performance. The Open Capacitated Arc Routing Problem (OCARP) is an NP-hard arc routing problem where, given an undirected graph, the objective is to find the least cost set of routes that services all edges with positive demand (required edges). The routes are subjected to capacity constraints in relation to edge demands. The OCARP differs from the Capacitated Arc Routing Problem (CARP) since OCARP does not consider a depot and routes are not constrained to form cycles. A hybrid genetic algorithm with feasibilization and local search procedures is proposed for the OCARP. Computational experiments conducted on a set of benchmark instances reveal that the proposed hybrid genetic algorithm achieved the best upper bounds for almost all instances.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2017.09.020