OpenGrey (Institut de l'Information Scientifique et Technique) · 1998 · 372 citations · 0 references
BusinessIndustrial EngineeringOperations ManagementOptimizationTransportTransportationAssignment ProblemsCombinatorial OptimizationInteger ProgrammingOptimization TheoryRoutingTransportation ProblemsCapacity ConstraintsCutting PlanesHeuristic AlgorithmsOptimization HeuristicsRouting ProblemsValid InequalitiesVehicle RoutingVehicle Routing Problems
In this paper, we present a branch-and-cut algorithm to solve the Capacitated Vehicle Routing Problem (CVRP) to optimality, which is based on the partial polyhedral description of the cor-responding polytope. The valid inequalities used in the algorithm are proposed and described in Cornuéjols and Harche (1993), De Vitis, Harche, and Rinaldi (1999), and in Naddef and Rinaldi (1999) where also unpublished inequalities of Augerat and Pochet can be found. We concen-trated mainly on the design of separation procedures for several classes of valid inequalities. The capacity constraints (generalized subtour elimination inequalities) happen to play a crucial role in the development of a cutting plane algorithm for the CVRP. A number of separation heuristics have been implemented and compared for these inequalities. We also implemented heuristic separation algorithms for other classes of valid inequalities that also lead to significant improvements: comb, capacity strengthened comb, and generalized capacity inequalities. The resulting cutting plane algorithm has been applied to a set of instances taken from the literature. The lower bounds obtained are better than the ones previously known. Some branch-ing strategies have been implemented to develop a branch-and-cut algorithm that has been able