Abstract: As an important type of vehicle routing problem, split delivery vehicle routing problem, which can be divided into two subtypes, split deliveries without restriction (by unit) and split deliveries by order, has broad applications such as distribution vehicle routing optimization and so on. In most of the present research of split delivery vehicle routing problem, customers' demands can be split without restrictions. However, in practical, sometimes a customer order consists of several cargos and could not be split during deliveries. So the cargos in the same order can only be delivered by the same vehicle. In that condition, customers' demands can be split in orders while a specific order could not be split. In addition, more and more customers have time window requirement during the distribution process. Considering this two respects, the vehicle routing problem with soft time windows and split deliveries by the order and its optimization algorithm are presented. The problem allows that the same customer can be serviced by multiple vehicles and the customer demand can be split but not split a specific order. Customers can be served either in the specified time windows or out of the time windows with according punishment. A mixed integer programming model for the problem is constructed and a tabu search algorithm for the model is proposed. The proposed algorithm was coded and tested on the problems which are based on the benchmark problems generated by Solomn. The computational results are compared with the ones in related literatures. It shows that the algorithm converges well and effectively solves the problem.

Key words: vehicle routing problem, split deliveries by order, Soft time windows, tabu search algorithm