摘要:

AbstractIn this paper, we are concerned with the problem of optimally covering a large region with rectilinear distances by many service facilities. We assume that the number of customers is proportional to the area that they occupy and that each customer patronizes the nearest facility. Our objective is to locate the facilities in such a manner that the maximal area any future competitor facility can capture will be minimized. For Euclidean distances, it has been conjectured that the best arrangement is a triangular grid, yielding hexagonal service areas (honeycomb). In this paper, we show that an analogous arrangement is optimal for rectilinear distances. Furthermore, as in the Euclidean case, it minimizes both the average and the maximal distance for all customers to their nearest facilities. The service areas under the optimal solution are rectilinear circles—which are shaped as Euclidean squares tilted at 45° to theX‐ andY‐axes. ©1993 by John Wiley&So

ISSN:0028-3045    

DOI:10.1002/net.3230230602

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

年代:1993

数据来源: WILEY

摘要:

AbstractGiven an undirected graphG=(N, E)with a cost associated with each edgeC:E→R+and a demand associated with each nodeA:N→R+. A special node is designated as thecenter. The capacitated minimum spanning tree (CMST) problem is to find a minimum spanning tree for graphGsuch that the sum of demands on each branch stem from the center does not exceed a given capacity. The CMST problem has many applications in network design, centralized telecommunications, and vehicle routing. In this paper, we present a new formulation and a full optimization algorithm by branch and bound. The lower bounds are generated by Lagrangean relaxation with tightening constraints. Computational results based upon the methodology presented are shown. ©1993 by John Wiley&Sons,

ISSN:0028-3045    

DOI:10.1002/net.3230230603

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

年代:1993

数据来源: WILEY

摘要:

AbstractWe present a new algorithm based upon network flows for finding all minimum‐size separating vertex sets in an undirected and unweighted graph. The sequential implementation of our algorithm runs in Θ(Mn+C) =O(2kn3) time, whereMis the number of minimum‐size separating vertex sets of the graph;n, the number of the vertices in the graph;m, the number of the edges in the graph;k, the connectivity of the graph, andC=knmin(k(m+n),A), whereAis the complexity of the best maximum flow algorithm for unit networks. The parallel implementation runs either inO(klogn) deterministic time or inO(log2n) randomized time using Θ(;M2n2+knNα) =O(4k(n6/k2)) processors on a PRAM, whereNαis the number of processors needed for parallel matrix multiplication inO(logn) time on PRAM. ©1993 by John Wiley&S

ISSN:0028-3045    

DOI:10.1002/net.3230230604

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

年代:1993

数据来源: WILEY

摘要:

AbstractThe study of “optimally” locating on a network a single facility of a given total length in the form of a path or a tree was initiated by several authors. We extend these results to the problem of locatingp(≥1) such facilities. We will consider “center”, “median”, “max eccentricity”, and “max distance sum” location type problems forp= 1 orp>1, for general networks and for tree networks, whether a facility contains partial arcs or not, and whether a facility is path‐shaped or tree‐shaped. These cases lead to 64 problems. We will determine the algorithmic complexity of virtually all these problems. We conclude with a result that may be viewed as a generalization of thep‐Median theorem. ©

ISSN:0028-3045    

DOI:10.1002/net.3230230605

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

年代:1993

数据来源: WILEY

摘要:

AbstractThis paper considers the problem of the competition among a finite number of players who must transport the fixed volume of traffic on a simple network over a prescribed planning horizon. Each player attempts to minimize his total transportation cost by making simultaneous decisions of departure time, route, and flow rate over time. The problem is modeled as aN‐person nonzero‐sum differential game. Two solution concepts are applied: [1] the open‐loop Nash equilibrium solution and [2]the feedback Nash equilibrium solution. Optimality conditions are derived and given an economic interpretation as a dynamic game theoretic generalization of Wardrop's second principle. Future extensions of the model are also discussed. The model promises potential applications to Intelligent Vehicle Highway Systems (IVHS) and air traffic control systems. ©1993 by John Wiley&Son

ISSN:0028-3045    

DOI:10.1002/net.3230230606

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

年代:1993

数据来源: WILEY

摘要:

AbstractLetD=(V, E)be a digraph withnvertices andmarcs. For eache∈Ethere is an associated costceand a transit timete;cecan be arbitrary, but we requireteto be a non‐negative integer. Thecost to time ratioof a cycleCis Λ(C)= ∑e∈cce/∑e∈c. LetE'⊆Edenote the set of arcsewithte>0, letTu= max{tuv:(u, v)∈E} for each vertexu, and letT= ∑u∈vTu. We give a new algorithm for finding a cycleCwith the minimum cost to time ratio Λ(C). The algorithm'sO(T(m+nlo gn)) running time is dominated byO(T)shortest paths calculations on a digraph with non‐negative arc lengths. Further, we consider early termination of the algorithm and a fasterO(Tm)algorithm in caseE–E'is acyclic, i.e., in case each cycle has a strictly positive transit time, which gives anO(n2) algorithm for a class of cyclic staffing problems considered by Bartholdi et al. The algorithm can be seen to be an extension of theO(nm)algorithm of Karp for the case in whichte= 1 for alle∈E, which is the problem of calculating a minimum mean cycle. Our algorithm can also be modified to solve the related parametric shortest paths problem inO(T(m+nlogn)) time. ©

ISSN:0028-3045    

DOI:10.1002/net.3230230607

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

年代:1993

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230230601

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

年代:1993

数据来源: WILEY