A weight-coded genetic algorithm for the capacitated arc routing problem

Morgan, Matthew J. W. and Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272 2009. A weight-coded genetic algorithm for the capacitated arc routing problem. Presented at: GECCO 2009 Genetic and Evolutionary Computation Conference, Montreal, Canada, 8-12 July 2009. Published in: Rothlauf, F. ed. GECCO '09 Proceedings of the 11th Annual conference on Genetic and evolutionary computation, Montreal, Québec, Canada, 8-12 July, 2009. New York, NY: ACM, pp. 325-332. 10.1145/1569901.1569947

Full text not available from this repository.

Abstract

In this paper we present a weight coded genetic algorithm (GA) based approach to the capacitated arc routing problem (CARP). In comparison to metaheuristic algorithms, simple constructive heuristic algorithms often produce poor quality solutions to the CARP. Using a novel weight coding model in conjunction with a series of standard CARP heuristics, acting as a solution engine, we demonstrate how these simple heuristic procedures can be `duped' into producing better solutions to the CARP. The algorithm is tested on a set of problem instances drawn from the literature. Initial results for our GA show that it is possible to reliably produce an uplift in solution quality of between 7.3% and 14.3% above the standard heuristics, the GA identifying 47 optimum or best known solutions from the 57 problem instances tested.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Publisher:	ACM
ISBN:	9781605583259
Last Modified:	18 Oct 2022 13:31
URI:	https://orca.cardiff.ac.uk/id/eprint/14174

Citation Data

Cited 4 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item