Investigating edge-reordering procedures in a tabu search algorithm for the capacitated arc routing problem

Padungwech, Wasin ORCID: https://orcid.org/0000-0002-4842-5222, Thompson, Jonathan and Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X 2016. Investigating edge-reordering procedures in a tabu search algorithm for the capacitated arc routing problem. Presented at: HM 2016: International Workshop on Hybrid Metaheuristics, Plymouth, UK, 8-10 June 2016. Published in: Blesa, Maria J., Blum, Christian and Cangelosi, Angelo eds. Hybrid Metaheuristics: 10th International Workshop, HM 2016, Plymouth, UK, June 8-10, 2016, Proceedings. Lecture Notes in Computer Science. Lecture Notes in Computer Science , vol.9668 Cham: Springer, pp. 62-74. 10.1007/978-3-319-39636-1_5

Preview

PDF - Accepted Post-Print Version Download (392kB) | Preview

Abstract

This paper presents two ideas to guide a tabu search algorithm for the Capacitated Arc Routing Problem to a promising region of the solution space. Both ideas involve edge-reordering, although they work in different ways. One of them aims to directly tackle deadheading cycles, and the other tries to reorder edges with the aim of extending a scope of solutions that can be reached from a given solution. Experiments were performed on 134 benchmark instances of various sizes, and the two ideas were shown to have an ability to guide the search to good solutions. Possible issues that may arise when implementing these ideas are also discussed.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Additional Information:	PDF uploaded in accordance with publisher's policies at http://www.sherpa.ac.uk/romeo/issn/0302-9743/ (accessed 9.6.16).
Publisher:	Springer
ISBN:	978-3-319-39636-1
ISSN:	0302-9743
Date of First Compliant Deposit:	9 June 2016
Last Modified:	08 Jan 2025 12:00
URI:	https://orca.cardiff.ac.uk/id/eprint/91665

Actions (repository staff only)

Edit Item