Scientific Program > Talks by Speaker > Dollevoet Twan

In the vehicle routing literature, different types of formulations have been proposed to model a variety of routing problems. Most of these formulations can be classified into one of two classes: vehicle flow formulations on the one hand and set partitioning formulations on the other. Vehicle flow formulations have the advantage of being compact models that can straightforwardly be solved by commercial optimization packages. However, the models typically have many constraints and weak relaxations. Set partitioning models commonly lead to stronger relaxations, but have a huge number of variables. As a consequence, these models require sophisticated solution methods, commonly based on column generation with complicated pricing problems.

In this paper, we develop a generalized formulation for the capacitated vehicle routing problem. This formulation is based on the concept of partial vehicle routes, which we refer to as p-steps. These p-steps visit a fixed number of customers and take the limited vehicle capacity into account. We show that the vehicle flow formulation and the set partitioning formulation are special cases of our general p-step formulation. Varying the fixed number of customers to be visited in a p-step allows us to study the transition from vehicle flow to set partitioning models. We study this transition theoretically and perform computational experiments to analyse the strength of the relaxations. Finally, we explain how the generalized formulation can be adapted to include time windows.