On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm

The Multi-Compartment Vehicle Routing Problem involves clients with a demand for different products and vehicles with several compartments to co-transport these commodities. We present a local search procedure that explores well-known moves (2-opt, cross, exchange, relocate), and exploits the mechanisms of neighbour lists and marking to speed up the searches. We combine the procedure with the Guided Local Search meta-heuristic to improve solution quality. Extensive computational results are reported to uncover when co-distribution by vehicles with multiple compartments is better than separate distribution with un-partitioned trucks. Sensitivities in key problem parameters including, client density and location of the depot, vehicle capacity, client demand and number of commodities are investigated. (C) 2010 Elsevier B.V. All rights reserved.