Publication Type
Journal
Journal Name
INFORMS Journal on Computing
Publication Date
Page Numbers
315 to 330
Volume
23
Issue
2
Abstract
The vehicle routing problem (VRP) is a dicult and well-studied combinatorial optimization
problem. We develop a parallel algorithm for the VRP that combines a heuristic local search
improvement procedure with integer programming. We run our parallel algorithm with
as many as 129 processors and are able to quickly nd high-quality solutions to standard
benchmark problems. We assess the impact of parallelism by analyzing our procedure's
performance under a number of di erent scenarios.