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

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

Full description

Saved in:
Bibliographic Details
Published in:The Journal of the Operational Research Society 2004-05, Vol.55 (5), p.513-520
Main Authors: LABBE, M, RODRIGUEZ-MARTIN, I, SALAZAR-GONZALEZ, J. J
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Branch & bound algorithms
Business and Management
Communications networks
Cost allocation
Customers
Exact sciences and technology
Heuristics
Integers
Linear programming
Management
Mathematical programming
Minimization of cost
Operational research and scientific management
Operational research. Management science
Operations research
Operations Research/Decision Theory
Optimal solutions
Optimization
Routing
Studies
Telecommunications
Telecommunications and information theory
Teleprocessing networks. Isdn
Theoretical Paper
Theoretical Papers
Valuation and optimization of characteristics. Simulation
Vehicles
Vertices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0160-5682
1476-9360
DOI:10.1057/palgrave.jors.2601692