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

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

0.00 Avg rating0 Votes
Article ID: iaor20051249
Country: United Kingdom
Volume: 55
Issue: 5
Start Page Number: 513
End Page Number: 520
Publication Date: May 2004
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: programming: integer
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 with each edge of the cycle. The PCLP consists of 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.

Reviews

Required fields are marked *. Your email address will not be published.