The Vehicle Routing Problem

John E. Beasley, Abilio Lucena, and Marcus Poggi de Aragão

ABSTRACT

This article is concerned with mathematical models of the vehicle routing problem. Initially, three models are discussed for the simplest form of the problem. These models can be categorized, respectively, in the following classes: a polynomial number of variables and an exponential number of constraints; a polynomial number of variables and constraints; and an exponential number of variables and a polynomial number of constraints. The first model is a direct extension of the Dantzig, Fulkerson, and Johnson formulation of the traveling salesman problem. The second one is a two-commodity flow-based model, while the third model is based on a set partitioning reformulation of the problem. The models are then adapted to address a number of relevant extensions of the basic problem.