Solving the multi-commodity capacitated multi-facility Weber problem using Lagrangean relaxation and a subgradient-like algorithm

M. Hakan Akyüz, Temel Öncan (Corresponding author), Kuban Altinel

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

Abstract

The Multi-commodity Capacitated Multi-facility Weber Problem (MCMWP) is concerned with locating I-capacitated facilities in the plane in order to satisfy the demands of J customers for K commodities so that the total transportation cost is minimized. We propose a Lagrangean relaxation scheme and a subgradient-like algorithm based on the relaxation of the capacity and commodity bundle constraints. The resulting subproblem is a variant of the well-known Multi-facility Weber Problem and it can be solved by using column generation and branch-and-price on an equivalent set covering formulation, which is accurate but extremely inefficient. Therefore, we devise different strategies to increase the efficiency. They mainly benefit from the effective usage of the lower and upper bounds on the optimal value of the Lagrangean subproblem. On the basis of extensive computational tests, we can say that they increase the efficiency considerably and result in accurate Lagrangean heuristics.
Original languageEnglish
Pages (from-to)771-789
Number of pages19
JournalJournal of the Operational Research Society
Volume63
Issue number6
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint Dive into the research topics of 'Solving the multi-commodity capacitated multi-facility Weber problem using Lagrangean relaxation and a subgradient-like algorithm'. Together they form a unique fingerprint.

Cite this