Title: A tabu search with vocabulary building approach for the vehicle routing problem with split demands

Authors: Rafael E. Aleman, Raymond R. Hill

Addresses: BIE Department, Wright State University, 3640 Colonel Glenn Hwy, Dayton, OH 45435, USA. ' Air Force Institute of Technology, Wright-Patterson AFB, Dayton OH 45433, USA

Abstract: In the vehicle routing problem (VRP) a fleet of vehicles with limited capacity is utilised to supply the demand of a set of customers located around a unique depot while minimising the total travelled distance. All customer demands are supplied and customers are visited by exactly one vehicle. In the split delivery vehicle routing problem (SDVRP), customers can be visited by more than one vehicle meaning their demands can be split among multiple vehicles. This paper presents a learning procedure, called tabu search with vocabulary building approach (TSVBA) for solving the SDVRP. TSVBA is a population-based search approach that uses a set of solutions to find attractive solution attributes with which to construct new solutions. As the search progresses, the solution set evolves; better solutions move into the set while bad solutions are removed. The proposed learning procedure was tested on benchmark instances and performed well when its solutions are compared to those reported in the literature. New best solutions are obtained on some benchmark problems available.

Keywords: vehicle routing; VRP; split delivery; vocabulary building; tabu search; route angle control; learning procedure; metaheuristics.

DOI: 10.1504/IJMHEUR.2010.033123

International Journal of Metaheuristics, 2010 Vol.1 No.1, pp.55 - 80

Published online: 08 May 2010 *

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