Premium
A variable neighborhood descent algorithm for a real waste collection problem with mobile depots
Author(s) -
Pia Alberto,
Filippi Carlo
Publication year - 2006
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2006.00539.x
Subject(s) - arc routing , variable (mathematics) , computer science , heuristic , feature (linguistics) , descent (aeronautics) , variable neighborhood search , generalization , set (abstract data type) , mathematical optimization , vehicle routing problem , duration (music) , algorithm , routing (electronic design automation) , artificial intelligence , mathematics , metaheuristic , engineering , computer network , mathematical analysis , linguistics , philosophy , literature , aerospace engineering , art , programming language
We consider a waste collection problem encountered in Due Carrare, a town located in Northern Italy. The original feature of the problem consists in the need for arranging appointments between vehicles along their routes so that small vehicles can dump their contents in the large ones and continue their work. This feature identifies the problem as a generalization of the well‐known Capacitated Arc Routing Problem (CARP). We propose a local search heuristic obtained from a variable neighborhood procedure suggested by Hertz and Mittaz (2001) for the CARP. In the Due Carrare instance, the proposed algorithm decreases the total route duration, apart from the required time for any feasible set of routes, of about 30% with respect to the routes so far adopted.