Home  About us  Contact
 

Demand Points (demand + point)

Distribution by Scientific Domains
Mathematics and Statistics100%

Selected Abstracts

The gradual covering problem

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 6 2004
Zvi Drezner
Abstract In this paper we investigate the gradual covering problem. Within a certain distance from the facility the demand point is fully covered, and beyond another specified distance the demand point is not covered. Between these two given distances the coverage is linear in the distance from the facility. This formulation can be converted to the Weber problem by imposing a special structure on its cost function. The cost is zero (negligible) up to a certain minimum distance, and it is a constant beyond a certain maximum distance. Between these two extreme distances the cost is linear in the distance. The problem is analyzed and a branch and bound procedure is proposed for its solution. Computational results are presented. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004 [source]

Efficient algorithms for centers and medians in interval and circular-arc graphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2002
Sergei Bespamyatnikh
Abstract The p -center problem is to locate p facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The p -median problem is to locate p facilities on a network so as to minimize the average distance from a demand point to its closest facility. We consider these problems when the network can be modeled by an interval or circular-arc graph whose edges have unit lengths. We provide, given the interval model of an n vertex interval graph, an O(n) time algorithm for the 1-median problem on the interval graph. We also show how to solve the p -median problem, for arbitrary p, on an interval graph in O(pn log n) time and on a circular-arc graph in O(pn2 log n) time. We introduce a spring representation of the objective function and show how to solve the p -center problem on a circular-arc graph in O(pn) time, assuming that the arc endpoints are sorted. © 2002 Wiley Periodicals, Inc. [source]

A nested benders decomposition approach for telecommunication network planning

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 6 2010
Joe Naoum-Sawaya
Abstract Despite its ability to result in more effective network plans, the telecommunication network planning problem with signal-to-interference ratio constraints gained less attention than the power-based one because of its complexity. In this article, we provide an exact solution method for this class of problems that combines combinatorial Benders decomposition, classical Benders decomposition, and valid cuts in a nested way. Combinatorial Benders decomposition is first applied, leading to a binary master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition. The algorithm is enhanced using valid cuts that are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem. The valid cuts proved efficient in reducing the number of times the combinatorial Benders master problem is solved and in reducing the overall computational time. More than 120 instances of the W-CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010 [source]

Exploiting self-canceling demand point aggregation error for some planar rectilinear median location problems

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 6 2003
R.L. Francis
When solving location problems in practice it is quite common to aggregate demand points into centroids. Solving a location problem with aggregated demand data is computationally easier, but the aggregation process introduces error. We develop theory and algorithms for certain types of centroid aggregations for rectilinear 1-median problems. The objective is to construct an aggregation that minimizes the maximum aggregation error. We focus on row-column aggregations, and make use of aggregation results for 1-median problems on the line to do aggregation for 1-median problems in the plane. The aggregations developed for the 1-median problem are then used to construct approximate n -median problems. We test the theory computationally on n -median problems (n , 1) using both randomly generated, as well as real, data. Every error measure we consider can be well approximated by some power function in the number of aggregate demand points. Each such function exhibits decreasing returns to scale. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 614,637, 2003. [source]