Research On Iterated Local Search For The Split Delivery Vehicle Routing Problem

The split delivery vehicle routing problem (SDVRP) is a variant of the capacitated vehicle routing problem (CVRP). SDVRP relaxes the constraint that the demand of one customer can only be serviced by a car. A multi-restart iterated local search (MRSILS) algorithm is introduced for SDVRP.Firstly, the GENIUS algorithm is used to get a large traveling salesman problem (TSP) solution according to the data set, The TSP solution is divided into several routes to meet the vehicle capacity constraint, namely to meet CVRP, to construct the initial solution. Secondly, the local search is done by nodes and the order of the nodes is arranged by their remove savings. In the local search program, the demand of node is deleted from the current solution and then reinserted it into the best locations. The re-insertion proposed is a greedy algorithm that we take account of the demand split strategy that the demand of node may be provided by one or more vehicles in the process of insertion. Try to get a better solution through this simple re-insertion algorithm. Finally, the perturbation is applied while certain predefined continuous no improvement local search steps are occurred. In order to extend the search space and keeping the quality of the restart solution, a method is designed for the perturbation that the perturbed solution is chosen from an elite solution set, while the best solution is preferred.The object of this work is to minimize the total travel distance. The two parameters, perturbation limits and the size of solution pool in MRSILS, are discussed by experiment and set reasonable numbers for them. The analysis presented in this paper for the node sorting algorithm, the experiment proves it is rationality. Experimental results on a benchmark set show that the MRSILS is competitive with a state of the art algorithm.