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

M H Akyüz, T Öncan and İ K Alt#x131;nel
Additional contact information
M H Akyüz: Galatasaray University, Ortaköy, İstanbul, Türkiye
T Öncan: Galatasaray University, Ortaköy, İstanbul, Türkiye
İ K Alt#x131;nel: Boğaziçi University, Bebek, İstanbul, Türkiye

Journal of the Operational Research Society, 2012, vol. 63, issue 6, 771-789

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.

Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.palgrave-journals.com/jors/journal/v63/n6/pdf/jors201181a.pdf Link to full text PDF (application/pdf)
http://www.palgrave-journals.com/jors/journal/v63/n6/full/jors201181a.html Link to full text HTML (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:63:y:2012:i:6:p:771-789

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().