A Column Generation Procedure for the Split Delivery Vehicle Routing Problem Using a Route-Based Formulation

The Split Delivery Vehicle Routing Problem (SDVRP) allows customers to be assigned to multiple routes. A column generation procedure using a route-based formulation is developed for the SDVRP and computational results are given for thirty-two data sets from previous literature. The SDVRP route-based formulation appears tighter (stronger) linear relaxation than a comparable SDVRP flow formulation. With respect to the total travel distance and computer time, the column generation procedure compares favorably versus previously published methods. The result is important for real-world since both the tractability and solution quality of larger (e.g., many vehicle routes, many customers) problems are both key issues when making vehicle routing decisions. The column generation method, along with the route-based formulation, provides an improved solution procedure that would be more appropriate for real-world problems than the previously published methods.