Discrete equal-capacity p-median problem

Discrete equal-capacity p-median problem

0.00 Avg rating0 Votes
Article ID: iaor200185
Country: United States
Volume: 47
Issue: 2
Start Page Number: 166
End Page Number: 183
Publication Date: Mar 2000
Journal: Naval Research Logistics
Authors: ,
Keywords: -median problem
Abstract:

This paper examines the discrete equal-capacity p-median problem that seeks to locate p new facilities (medians) on a network, each having a given uniform capacity, in order to minimize the sum of distribution costs while satisfying the demand on the network. Such problems arise, for example, in local access and transport area telecommunication network design problems where any number of a set of p facility units can be constructed at the specified candidate sites (hence, the net capacity is an integer multiple of a given unit capacity). We develop various valid inequalities, a separation routine for generating cutting planes that are specific members of such inequalities, as well as an enhanced reformulation that constructs a partial convex hull representation that subsumes an entire class of valid inequalities via its linear programming relaxation. We also propose suitable heuristic schemes for this problem, based on sequentially rounding the continuous relaxation solutions obtained for the various equivalent formulations of the problem. Extensive computational results are provided to demonstrate the effectiveness of the proposed valid inequalities, enhanced formulations, and heuristic schemes. The results indicate that the proposed schemes for tightening the underlying relaxations play a significant role in enhancing the performance of both exact and heuristic solution methods for this class of problems.

Reviews

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