Parallel approaches for the the vehicle routing problem

Vehicle routing problems (VRPs) are known to be computationally intractable. The time required to solve a VRP increases significantly given a modest increase in problem size. Only small VRPs are optimally solved using existing solution approaches on single processor computers.

In recent years, multiprocessor computers have emerged as powerful tools for solving computationally difficult problems. Problems are decomposed into several smaller parts or modules that can be solved simultaneously, or in parallel, to decrease computation time. The degree of speedup depends on the particular system architecture and on the strategy for algorithmically decomposing the problem.

The objective of this doctoral research is the development of parallel techniques to solve the basic, capacity-constrained VRP. The research includes: (1) definition of an effective decomposition algorithm for the VRP, (2) development and implementation of parallel approaches for the decomposition algorithm, (3) metrics and analyses of their performance and efficiency, (4) observations of the convergence behavior of the decomposition algorithm, and (5) development and implementation of an end-game heuristic that can be used to obtain a feasible solution to the VRP in the event the decomposition algorithm fails to converge. The research presents a parallel approach that is as effective as the serial approach in terms of solutions to the VRP, but is computationally better with respect to performance yielding significant speedup over the serial implementation. It also presents alternative techniques that combine parallelization of the decomposition algorithm with alternative subproblem solvers and an end-game heuristic to improve computational time and quality of solutions.