Parallelization of the set partitioning method for optimally solving the vehicle routing problem

This paper will present the Vehicle Routing Problem in its basic form as well as describe the particular type of problem the solution method addresses. The Set Partitioning method has been used to solve this problem optimally. The Set Partitioning method consists of three steps. The serial versions of code in each step could be parallelized to obtain a speedup at each step, and an overall speedup for the whole project. The second step, which this paper focuses on, has been parallelized for this project and will be described in greater detail. Parallelization strategies and considerations will also be discussed. The third step of the Set Partitioning method, which involves integer program-ming, may simply require the use of an efficient parallel integer program solver for speedup in this final step. Complexity of each step will be presented as well as ideas for future research.