A guided local search procedure for the multi-compartment capacitated arc routing problem

Luc Muyldermans, Gu Pang

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

Abstract

In this paper, we introduce and study the multi-compartment capacitated arc routing problem—an extension of the classical capacitated arc routing problem, but where the required edges have a demand for different products, and multi-compartment vehicles are available to co-distribute these commodities. We present a local search algorithm that exploits well-known moves (2-opt, re-insert, relocate, exchange and cross). We take advantage of speed up tricks such as marking and neighbour lists, and we combine the procedure with the guided local search meta-heuristic in order to reach high quality solutions. We report on results from extensive computational experiments. Our aim is to reveal in what situations co-distribution by partitioned vehicles saves in routing costs as compared with separate distribution with un-partitioned trucks. We explore sensitivities in key problem characteristics including, the number of commodities, the vehicle capacity, the location of the depot and required edges, the density of required edges, and the demand per commodity for the required edges.
Original languageEnglish
Pages (from-to)1662-1673
JournalComputers & Operations Research
Volume37
Issue number9
DOIs
Publication statusPublished - Sep 2010

Fingerprint

Dive into the research topics of 'A guided local search procedure for the multi-compartment capacitated arc routing problem'. Together they form a unique fingerprint.

Cite this