SOLVING THE SPLIT DELIVERY VEHICLE ROUTING PROBLEM
Open Access
Author:
Wilck, IV, Joseph Hubert
Graduate Program:
Industrial Engineering
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
October 08, 2009
Committee Members:
Tom Michael Cavalier, Dissertation Advisor/Co-Advisor Tom Michael Cavalier, Committee Chair/Co-Chair M Jeya Chandra, Committee Member Marc Eric Mcdill, Committee Member Tao Yao, Committee Member
The Split Delivery Vehicle Routing Problem (SDVRP) allows customers to be assigned to multiple routes. A flow formulation and a set-covering based formulation are presented for the SDVRP. A construction heuristic procedure is developed and used to build an initial population for a hybrid genetic algorithm. The construction heuristic, along with the set-covering based formulation, are used to develop a column generation procedure. These three procedures for the SDVRP are compared and computational results are given for data sets from previous literature. With respect to the total travel distance and computation time, the three procedures compare favorably versus previously published methods. The column generation procedure provides lower bounds (dual bounds), thereby reducing the Duality GAP to less than 5% within 5101.699 seconds of computer time for 32 test problems with up to 288 customers and 216 vehicle routes. These results represent a significant improvement when compared to previously published methods.
