BRANCH-AND-PRICE FOR SPLIT DELIVERY VEHICLE ROUTING PROBLEM

In the basic vehicle routing problem (VRP), a customer’s demand should be satisfied by only one vehicle. On the other hand, split delivery vehicle routing problem (SDVRP) allows two or more vehicles to serve each customer. SDVRP has more feasible solutions than basic VRP, making it more difficult to enumerate feasible solutions. Column generation is a well-known method for VRP, and we can also efficiently solve SDVRP using Dantzig-Wolf decomposition. For integer programming, branch-and-price, which is a combination of column generation and branch-and-bound, is effective. In this research, we adopt branch-and-price for the solution method, and discuss the model and the solution process as an exact solution method for SDVRP. In addition, we compare the results of experiments for two solution methods and evaluate their relative performance.