A computational comparison of flow formulations for the capacitated location-routing problem

作者：Contardo Claudio^*; Cordeau Jean Francois; Gendron Bernard

来源：Discrete Optimization, 2013, 10(4): 263-295.

DOI：10.1016/j.disopt.2013.07.005

• Location-routing
• Flow formulations
• Branch-and-cut

In this paper we present a computational comparison of four different flow formulations for the capacitated location-routing problem. We introduce three new flow formulations for the problem, namely a two-index two-commodity flow formulation, a three-index vehicle-flow formulation and a three-index two-commodity flow formulation. We also consider an existing two-index vehicle-flow formulation and extend it by considering new families of valid inequalities and separation algorithms. We introduce new branch-and-cut algorithms for each of the formulations and compare them on a wide number of instances. Our results show that compact formulations can produce tight gaps and solve many instances quickly, whereas three-index formulations scale better in terms of computing time.

• 出版日期2013-11