| Article ID: | iaor20115097 |
| Volume: | 23 |
| Issue: | 2 |
| Start Page Number: | 315 |
| End Page Number: | 330 |
| Publication Date: | Mar 2011 |
| Journal: | INFORMS Journal on Computing |
| Authors: | Wasil Edward, Golden Bruce, Gror Chris |
| Keywords: | combinatorial optimization |
The vehicle routing problem (VRP) is a difficult 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 find high‐quality solutions to standard benchmark problems. We assess the impact of parallelism by analyzing our procedure's performance under a number of different scenarios.