An asymmetric vehicle routing problem arising in the collection and disposal of special waste

In this paper we consider a particular pick-up and delivery vehicle routing problem, with unit vehicle capacity and possible compatibility constraints between consecutive operations. The problem arises in the collection and disposal of bulky recyclable waste, where containers of different types, used to collect different waste materials, must be picked-up to be emptied at suitable disposal plants and replaced by empty containers alike. Disposal plants depend on the material and are located in different sites. Here we provide a graph model based on an Asymmetric Vehicle Routing formulation and discuss heuristic algorithms. Preliminary computational results obtained on real data are reported. © 2004 Elsevier B.V. All rights reserved.