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

详细信息    查看全文

• 作者：Claudio Contardo ; Jean-Fran莽ois Cordeau ; Bernard Gendron
• 关键词：90C27 ; 90C57
• 刊名：Discrete Optimization
• 出版年：November, 2013
• 年：2013
• 卷：10
• 期：4
• 页码：263-295
• 全文大小：583 K

文摘

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.