TY - JOUR
T1 - Two- and three-index formulations of the minimum cost multicommodity k-splittable flow problem
AU - Gamst, Mette
AU - Jensen, Peter Neergaard
AU - Pisinger, David
AU - Plum, Christian Edinger Munk
PY - 2010
Y1 - 2010
N2 - The multicommodity flow problem (MCFP) considers the efficient routing of commodities from their origins to their destinations subject to capacity restrictions and edge costs. Baier et al. [G. Baier, E. Köhler, M. Skutella, On the k-splittable flow problem, in: 10th Annual European Symposium on Algorithms, 2002, 101–113] introduced the maximum flow multicommodity k-splittable flow problem (MCkFP) where each commodity may use at most k paths between its origin and its destination. This paper studies the -hard minimum cost multicommodity k-splittable flow problem (MCMCkFP) in which a given flow of commodities has to be satisfied at the lowest possible cost. The problem has applications in transportation problems where a number of commodities must be routed, using a limited number of distinct transportation units for each commodity. Based on a three-index formulation by Truffot et al. [J. Truffot, C. Duhamel, P. Mahey, Branch and price pour le problème du multiflot k-séparable de coût minimal, in: LIMOS, UMR 6158 – CNRS, ROADEF’05, 2005] we present a new two-index formulation for the problem, and solve both formulations through branch-and-price. The three-index algorithm by Truffot et al. is improved by introducing a simple heuristic method to reach a feasible solution by eliminating some symmetry. A novel branching strategy for the two-index formulation is presented, forbidding subpaths in the branching children. Though the proposed heuristic for the three-index algorithm improves its performance, the three-index algorithm is still outperformed by the two-index algorithm, both with respect to running time and to the number of solved test instances.
AB - The multicommodity flow problem (MCFP) considers the efficient routing of commodities from their origins to their destinations subject to capacity restrictions and edge costs. Baier et al. [G. Baier, E. Köhler, M. Skutella, On the k-splittable flow problem, in: 10th Annual European Symposium on Algorithms, 2002, 101–113] introduced the maximum flow multicommodity k-splittable flow problem (MCkFP) where each commodity may use at most k paths between its origin and its destination. This paper studies the -hard minimum cost multicommodity k-splittable flow problem (MCMCkFP) in which a given flow of commodities has to be satisfied at the lowest possible cost. The problem has applications in transportation problems where a number of commodities must be routed, using a limited number of distinct transportation units for each commodity. Based on a three-index formulation by Truffot et al. [J. Truffot, C. Duhamel, P. Mahey, Branch and price pour le problème du multiflot k-séparable de coût minimal, in: LIMOS, UMR 6158 – CNRS, ROADEF’05, 2005] we present a new two-index formulation for the problem, and solve both formulations through branch-and-price. The three-index algorithm by Truffot et al. is improved by introducing a simple heuristic method to reach a feasible solution by eliminating some symmetry. A novel branching strategy for the two-index formulation is presented, forbidding subpaths in the branching children. Though the proposed heuristic for the three-index algorithm improves its performance, the three-index algorithm is still outperformed by the two-index algorithm, both with respect to running time and to the number of solved test instances.
KW - network flows
KW - multicommodity flow
KW - decomposition
KW - transportation
U2 - 10.1016/j.ejor.2009.05.014
DO - 10.1016/j.ejor.2009.05.014
M3 - Journal article
SN - 0377-2217
VL - 202
SP - 82
EP - 89
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -