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

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

Joseph Hubert Wilck IV (Department of Engineering, East Carolina University, Greenville, NC, USA) and Tom M. Cavalier (The Harold and Inge Marcus Department of Industrial and Manufacturing Engineering, Pennsylvania State University, University Park, PA, USA)
DOI: 10.4018/ijoris.2014100103
OnDemand PDF Download:
List Price: $37.50


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.
Article Preview

1. Introduction And Literature Review

The primary research findings of this paper include combining a route-based formulation and a column generation procedure for the split delivery vehicle routing problem (SDVRP), including computational results compared to previously published methods. The Vehicle Routing Problem (VRP) is a prominent combinatorial optimization problem in distribution planning. Various forms of the VRP are studied for both theoretical and practical purposes. The solution quality of these problems is essential to the logistics industry when considering transportation costs. Dantzig and Ramser (1959) first exhibited these cost savings by providing a formulation and solution approach for gasoline distribution. Toth and Vigo (2002a) estimate that computer-generated solutions for distribution problems reduce transportation costs by 5%-20%, and this is a significant decrease since transportation costs represent between 10%-20% of the final cost of a delivered product or unit. Ellis et al. (2010) depicted this decrease to be approximately 10% within a manufacturing facility. Review literature for the VRP includes a survey by Toth and Vigo (2002b) for exact solution procedures, whereas Cordeau et al. (2002, 2005) survey heuristic procedures. Recent papers include Gutiérrez-Jarpa et al. (2009) and Jabali et al. (2009) which depict the single vehicle routing problem and time-dependent vehicle routing, respectively.

Dror and Trudeau (1989, 1990) formally introduced the SDVRP. The primary motivation to split a customer’s demand over multiple routes is to reduce the travel distance and the number of vehicle routes (or total number of vehicles). If each vehicle has the same capacity, then the minimum number of routes is the total demand divided by the vehicle capacity rounded up to the nearest integer. They proved, given that the distance between nodes follows the triangle inequality, there exists an optimal solution where no two routes can have more than one split demand point in common, and that there exists an optimal solution with no -split cycles (for any ). Based on these proofs, Dror and Trudeau (1990) devised a heuristic to solve the SDVRP given an initial capacitated VRP (CVRP) solution by splitting a node's demand to fill the routes to capacity. Dror et al. (1994) extended the formulation of Dror and Trudeau (1989, 1990) with additional constraints, and developed a constraint relaxation branch and bound algorithm. The results from Dror and Trudeau (1989, 1990) and Dror et al. (1994) show that the percent reduction in travel distance, when compared to the CVRP, is most prominent among problems where customers have high demands (i.e., more than 10% of the vehicle capacity). The results showed that the SDVRP solution used fewer routes than the CVRP solution; however, the SDVRP solution did not always use the minimum number of routes.

A graphical representation for an SDVRP solution is provided in Figure 1. In this example, there are three customers with demands of 100 units apiece and the vehicle capacity is 150 units. In the CVRP, the solution would be to visit each customer once and return to the depot. Whereas, in the SDVRP a single customer’s demand can be split over two vehicle routes; thus, saving a vehicle route.

Figure 1.

SDVRP solution for three customers and two vehicle routes

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing