Two- and three-index formulations of the minimum cost multicommodity k-splittable flow problem

Mette Gamst, Peter Neergaard Jensen, David Pisinger and Christian Plum

European Journal of Operational Research, 2010, vol. 202, issue 1, 82-89

Abstract: 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.

Keywords: Network; flows; Transportation; Decomposition; Multicommodity; flow (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00318-X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:202:y:2010:i:1:p:82-89

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().