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