A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem

, , and

BibTeX reference

We describe a tabu search algorithm for the vehicle routing problem with split deliveries. At each iteration, a neighbour solution is obtained by removing a customer from a set of routes where it is currently visited, and by inserting it either into a new route, or into an existing route which has enough residual capacity. The algorithm also considers the possibility of inserting a customer into a route without removing it from another route. The insertion of a customer into a route is done by means of the cheapest insertion method. Computational experiments are reported for a set of benchmark problems, and the results are compared with those obtained by the algorithm proposed by Dror and Trudeau.

, 18 pages

Research Axis

Research application


A Tabu search algorithm for the split delivery vehicle routing problem
, , and
Transportation Science, 40(1), 64–73, 2006 BibTeX reference