摘要:

AbstractThis paper considers the problem of locating an obnoxious facility on a Euclidean network that could inflict damage within a λ distance of its location point. The objective is to find a location point that minimizes the sum of weights within the circle of radius λ centered at the location point, where each weight (assigned to a point on the network) represents a numerical scale that typically signifies the extent of the undesirability (or the damage cost) due to the facility located near the weighted point. The weights are assumed discretely distributed over all the nodes but uniformly distributed on all the links of the network. In the problem analysis, some optimal solution properties are found, e.g., the objective function is lower semicontinuous piecewise concave and there is at least one optimal location point in a finite set of candidate points. Using these properties, an efficient solution algorithm is derived and tested with several numerical problems. © 1994 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230240102

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractWe consider thek‐CARD TREE problem, i.e., the problem of finding in a given undirected graphGa subtree withkedges, having minimum weight. Applications of this problem arise in oil‐field leasing and facility layout. Although the general problem is shown to be strongly NP hard, it can be solved in polynomial time ifGis itself a tree. We give an integer programming formulation ofk‐CARD TREE and an efficient exact separation routine for a set of generalized subtour elimination constraints. The polyhedral structure of the convex hull of the integer solutions is studied. © 1994 by John Wiley&Son

ISSN:0028-3045    

DOI:10.1002/net.3230240103

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractA new characterization of tree medians is presented: We show that a vertexmis a median of a treeTwithnvertices iff there exists a partition of the vertex set into [n/2] disjoint pairs (excludingmwhennis odd), such that all the paths connecting the two vertices in any of the pairs pass throughm. We show that in this case the sum of the distances between these pairs of vertices is the largest possible among all such partitions, and we use this fact to discuss lower bounds on the message complexity of the distributed sorting problem. We show that, given a network of a tree topology, choosing a median and then routing all the information through it is the best possible strategy, in terms of worst‐case number of messages sent during any execution of any distributed sorting algorithm. We also discuss the implications for networks of a general topology and for the distributed ranking problem. © 1994 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230240104

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractConsider a network on which one or more facilities are already located. We examine how the network can be modified most efficiently in order to improve the location of the facility when the measure of facility performance is the minimax objective. The types of possible network modifications fall into two categories: reductions in the length of existing arcs or additions of some new arcs that are not currently in the network. A set of reduction and addition problems is introduced for which exact or heuristic algorithms are presented. The principal objective of the paper is in defining and formulating the problems and not in testing the efficacy of the proposed solution methodologies. © 1994 by John Wiley&Sons, Inc

ISSN:0028-3045    

DOI:10.1002/net.3230240105

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractThis paper creates and tests a vehicle routing heuristic that combines features of continuous space modeling and discrete modeling. The goals of the paper were (1) to determine whether exploiting continuous space approximations in the formation of an initial partition of customers into districts produces significant improvements in solution quality and (2) to test the validity of Daganzo's route‐length approximation in cases where shipment sizes are either identical or variable. The initial partition is created by dividing the service region into multiple annuli and then partitioning the annuli with a modified sweep algorithm. The initial solution is iteratively updated with a generalized assignment algorithm, which employs a new method for approximating the cost of inserting a stop into a tour. Computational tests have been systematically performed on over 500 sample problems with up to 170 stops and 70 districts. Unlike prior research, sample problems are sufficiently large to exhibit the multiple‐annuli phenomenon studied in Daganzo's work. Results show that continuous space models can provide substantial improvements in the initial customer partition compared to single‐annulus methods. However, after repeated application of a generalized assignment algorithm, the initial advantage of the continuous space solution tends to evaporate. Results also show that Daganzo's model provides accurate predictions of average distance between stops, especially on large problems with identical shipment sizes. © 1994 by John Wiley&Son

ISSN:0028-3045    

DOI:10.1002/net.3230240106

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230240101

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY