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

Muyldermans, Luc and Pang, Gu (2010) A guided local search procedure for the multi-compartment capacitated arc routing problem. Computers & Operations Research, 37 (9). pp. 1662-1673. ISSN 0305-0548

Full text not available from this repository. (Request a copy)

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.

Item Type:	Article
Uncontrolled Keywords:	Multi-compartment capacitated arc routing, meta-heuristics, guided local search, co-collection, separate collection
Subjects:	G200 Operational Research G900 Others in Mathematical and Computing Sciences
Department:	Faculties > Business and Law > Newcastle Business School
Depositing User:	EPrint Services
Date Deposited:	02 Aug 2010 13:43
Last Modified:	19 Nov 2019 09:52
URI:	http://nrl.northumbria.ac.uk/id/eprint/1508

Downloads