Title: Discrete cuckoo search applied to capacitated arc routing problem

Authors: Badis Bensedira; Abdesslam Layeb; Zineb Habbas

Addresses: Department of Computer Science and Its Applications, Constantine 2 University, Route Ain El Bey, Constantine 25017, Algeria ' Department of Computer Science and Its Applications, Constantine 2 University, Route Ain El Bey, Constantine 25017, Algeria ' Department of Computer Science, Lorraine University, Ile du Saulcy, 57045, Metz Cedex, France

Abstract: Capacitated arc routing problem (CARP) is known as NP-hard combinatorial optimisation problem. Cuckoo search (CS) is a recent meta-heuristic algorithm inspired by breeding the behaviour of cuckoos. CS has proved to be very effective in solving continuous and discrete optimisation problems. In discrete CS for solving CARP (DCSARP), the solution is encoded as a sequence of integer numbers that are positioned according to the order between their components. This discretisation is the key for using CS for solving combinatorial optimisation problems. The experimental results showed that DCSARP can be better than some meta-heuristics in relation to the quality of solution and robustness.

Keywords: capacitated arc routing problem; CARP; combinatorial optimisation; cuckoo search; metaheuristics; discrete optimisation.

DOI: 10.1504/IJMHEUR.2017.083096

International Journal of Metaheuristics, 2017 Vol.6 No.1/2, pp.37 - 54

Received: 15 Mar 2016
Accepted: 20 Nov 2016

Published online: 20 Mar 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article