No label defined (Q4955264)

In this work the static and deterministic basic version of the Vehicle Routing Problem (VRP), known as the Capacited VRP (CVRP) is considered. Its aim is to provide an update of that survey, describing the algorithms recently proposed for the exact solution of CVRP both for the case with symmetric and asymmetric cost matrices. Up to the end of the last decade the most effective exact approaches for the CVRP were mainly branch-and-bound algorithms using basis relaxations. Recently, more sophistical bounds were proposed, as those based on Lagrangian relaxations or on the additive approach, which increased the size of the problems that can be solved to optimality by branch-and-bound. There are treated separately problems with symmetric and asymmetric cost matrices. The work consists of eight sections. The first section is an introduction. In Sections 1.2 and 1.3 a detailed description of CVRP as a graph theoretic problem is given and also, some basic reduction rules are described. In Section 1.4 the case is considered where the cost matrix is asymmetric, illustrating some branch-and-bound algorithms. Some exact methods for the more widely studied CVRP with symmetric cost matrix are presented. Section 1.5 examines the algorithms based on branch-and-bound. In Section 1.6 the main ingredients of the branch-and-cut algorithm proposed by \textit{G. Cornuéjols} and \textit{F. Harche} [Math. Program. 60 A, 21-51 (1993; Zbl 0790.90029)] and some recent results in this field are discussed. In Section 1.7 some exact approaches based on set-partitioning formulations are examined. In 1.8 some conclusions are given and some future directions of research are proposed. For the entire collection see [Zbl 0933.00021].