A branch-and-cut algorithm for vehicle routing problems |
| |
| Authors: | J. R. Araque G G. Kudva T. L. Morin J. F. Pekny |
| |
| Affiliation: | (1) School of Industrial Engineering and Program in Computational Combinatorics, Purdue University, 47907 West Lafayette, Indiana, USA;(2) School of Chemical Engineering, Purdue University, 47907 West Lafayette, Indiana, USA |
| |
| Abstract: | We present a branch-and-cut algorithm for the identical customer Vehicle Routing Problem. Transforming the problem into an equivalent Path-Partitioning Problem allows us to exploit its polyhedral structure and to generate strong cuts corresponding to facet-inducing inequalities. By using cuts defined by multistars, partial multistars and generalized subtour elimination constraints, we are able to consistently solve 60-city problems to proven optimality and are currently attempting to solve problems involving a hundred cities. We also present details of the computer implementation and our computational results. |
| |
| Keywords: | Vehicle routing branch-and-cut algorithm scientific computation combinatorial optimization polyhedral theory facets |
| 本文献已被 SpringerLink 等数据库收录！ |
|
