An improved tabu search for the Split Delivery VRP

This paper describes the split deliveries vehicle routing problem briefly and presents an improved tabu search algorithm. At each iteration, a neighbor solution at each iteration by removing a customer from a set of routes where it is currently visited and inserting it either into a new route or into an existing route that 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. The experimental results show that the improved algorithm is feasible and valid for the split delivery VRP.