A branch and bound algorithm for the capacitated vehicle routing problem

Abstract

This paper considers a version of the vehicle routing problem in which a non-negative weight is assigned to each city to be visited and where all vehicles are identical and have the same capacityD. The weight assigned to a vehicle on a given route may not exceed this capacity. The problem is formulated as an integer program: integrality is obtained by means of a branch and bound procedure; capacity constraints are first relaxed, and introduced only when they are found to be violated. Three variants of this basic algorithm are examined. Exact solutions are obtained for problems ranging from 15 to 50 cities. Diese Arbeit befaßt sich mit einer Variante des Fahrzeugroutenproblems, bei der jeder zu besuchenden Stadt ein nichtnegatives Gewicht zugeordnet ist und bei der alle Fahrzeuge gleich sind und die gleiche KapazitätD haben. Das Problem wird als ganzzahliges lineares Programm formuliert: Ganzzahligkeit wird über ein Branch und Bound-Verfahren erreicht. Dabei werden die Kapazitätsbeschränkungen zunächst relaxiert und nur dann wieder einbezogen, wenn sie verletzt werden. Drei Varianten dieses Basisverfahrens werden untersucht. Exakte Lösungen werden für Probleme mit 15 bis 50 Städten erhalten.