A branch-and-cut algorithm for the plant-cycle location problem

M Labbé (), I Rodríguez-Martin and J J Salazar-González
Additional contact information
M Labbé: ISRO and SMG, Université Libre de Bruxelles
I Rodríguez-Martin: DEIOC, Universidad de La Laguna, La Laguna
J J Salazar-González: DEIOC, Universidad de La Laguna, La Laguna

Journal of the Operational Research Society, 2004, vol. 55, issue 5, 513-520

Abstract: Abstract The Plant-Cycle Location Problem (PCLP) is defined on a graph G=(I∪J, E), where I is the set of customers and J is the set of plants. Each customer must be served by one plant, and the plant must be opened to serve customers. The number of customers that a plant can serve is limited. There is a cost of opening a plant, and of serving a customer from an open plant. All customers served by a plant are in a cycle containing the plant, and there is a routing cost associated to each edge of the cycle. The PCLP consists in determining which plants to open, the assignment of customers to plants, and the cycles containing each open plant and its customers, minimizing the total cost. It is an NP-hard optimization problem arising in routing and telecommunications. In this article, the PCLP is formulated as an integer linear program, a branch-and-cut algorithm is developed, and computational results on real-world data and randomly generated instances are presented. The proposed approach is able to find optimal solutions of random instances with up to 100 customers and 100 potential plants, and of instances on real-world data with up to 120 customers and 16 potential plants.

Keywords: optimization; mathematical programming; telecommunications (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601692 Abstract (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:55:y:2004:i:5:d:10.1057_palgrave.jors.2601692

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

DOI: 10.1057/palgrave.jors.2601692

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 ().