Program > By author > Chen Ping

Open vehicle routing problem (OVRP) is a variant of vehicle routing problem (VRP), which has hierarchical objectives, i.e., to minimize the number of routes, and to minimize the total travel distance. Although the split delivery vehicle routing problem (SDVRP) has been studied extensively recently, and has been demonstrated that it can reduce the cost by at most 50%, there are not many reports on how delivery split will affect the solution to the OVRP. In this paper, we study the OVRP with split delivery . Considering that it is not quite practical for one customer to be serviced more than twice, especially when demand is small, we focus on limiting the splits into two pieces. Firstly, we propose a priori split strategy based on the first-fit heuristic, by which each delivery is split into at most 2 (or 3) pieces in advance. Secondly, we propose an iterated local search algorithm for solving this problem. Computational experiments on 42 benchmark instances show that our algorithm is effective and efficient, and delivery split indeed improves solutions in terms of both the number of routes and the total travel distance. The results also demonstrate that to split delivery into 3 pieces will improve the solution just a little bit, but with much computing time increase, which indicates that to split each delivery into 2 pieces is more cost effective and appropriate for real-life applications.