An Efficient Forest-Based Tabu Search Algorithm for the Split-delivery Vehicle Routing Problem

The defining characteristic the SDVRP, where vehicle capacity and customer demands of the SDVRP that distinguishes it from the classical are not required to be integer numbers, the number of vehicles vehicle routing problem (VRP) is that each customer is not limited to the minimum possible number, and can be served by more than one vehicle. Obviously, when the customer demands may exceed the vehicle capacity. The the demand of a customer is lager than the vehicle capacity, main contributions are threefold. First, we find a novel way it has to be split and the customer has to be visited more to represent the solutions of the SDVRP, which is the combination than once. As shown by (Dror and Trudeau 1989), when all of a set of vehicle routes and a forest. Second, based customer demands are less than or equal to the vehicle capacity, on this solution representation, we propose three classes of split delivery can also lead to substantial cost savings.