Title: A ring-based diversification scheme for routing problems

Authors: Rafael E. Aleman, Xinhui Zhang, Raymond R. Hill

Addresses: BIE Department, Wright State University, 207 Russ Engineering Center, 3640 Colonel Glenn Hwy, Dayton, OH 45435, USA. ' BIE Department, Wright State University, 207 Russ Engineering Center, 3640 Colonel Glenn Hwy, Dayton, OH 45435, USA. ' Department of Operational Sciences, 2950 Hobson Way, Bldg 641, Wright-Patterson AFB, OH 45433, USA

Abstract: The split delivery vehicle routing problem (SDVRP) relaxes the classical vehicle routing problem (VRP) by allowing multiple vehicles to supply the demand of individual customers thereby potentially reducing costs. This article provides an up-to-date review of the SDVRP literature and presents a new solution diversification scheme based on concentric rings centred at the depot that partitions the original problem. The resulting subproblems are then solved using a constructive approach. Different ring settings produce varied partitions and thus different solutions to the original problem are obtained and improved via a variable neighbourhood descent. Computational results on available test problems demonstrate the effectiveness of the proposed algorithm and present new best solutions to some of the tested problems.

Keywords: RAC; rings-based diversification scheme; route angle control; split delivery; vehicle routing; SDVRP; ring settings.

DOI: 10.1504/IJMOR.2009.022880

International Journal of Mathematics in Operational Research, 2009 Vol.1 No.1/2, pp.163 - 190

Published online: 31 Jan 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article