摘要:

AbstractIn this paper, we discuss a computationally viable algorithm based on a set‐partitioning for‐mulation of the Vehicle Routing Problem (VRP). Implementation strategies based on theoretical as well as empirical results are developed. Some computational results are presented. It is shown that a set‐partitioning formulation to the VRP, although well known for a long time, deserves considerable research efforts beyond those we present

ISSN:0028-3045    

DOI:10.1002/net.3230190702

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

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper presents a general dynamic spatial price network equilibrium model with gains and losses, which contains as special cases both dynamic and static models studied earlier. This framework through the use of multipliers has the capability of handling directly agricultural markets for perishable commodities and financial markets. Alternative variational inequality formulations are given and then exploited (akin to the work for dynamic problems without gains and losses) to construct a Gauss–Seidel‐type decomposition scheme. Computational experience for this scheme and for an equilibration multiplier method is given for a variety of large‐scale pro

ISSN:0028-3045    

DOI:10.1002/net.3230190703

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

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper considers the following variation on the construction of a reliable communication network. Whenever a vertex is attacked, all vertices within distance 2 are also destroyed (or fail) indirectly. We are interested in designing a connected graph (undirected, all edges of length one) onpvertices such that when a random subset of the vertices are attacked the expected number of vertices that are destroyed (directly and indirectly) is minimized. It is assumed that any of the 2psubsets of vertices is equally likely to be attacked. The optimal structure is determined for allpand is shown to be one of five patterns depending onrwherep= 5t + r.

ISSN:0028-3045    

DOI:10.1002/net.3230190704

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

年代:1989

数据来源: WILEY

摘要:

AbstractWe investigate probabilistically the relative tightness of a linear programming relaxation bound for an integer programming formulation of the Steiner tree problem in networks. Under two different random modesl of the network, we show that the aggregate linear programming relaxation provides a rapidly diverging bound for the optimal Steiner tree and characterize the rates of divergence.

ISSN:0028-3045    

DOI:10.1002/net.3230190705

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

年代:1989

数据来源: WILEY

摘要:

AbstractBroadcasting is the process by which a message originated at one vertex is delivered to all other vertices of a network, subject to the restriction that a vertex may participate in only one message transfer during a given time unit. Akfault‐tolerant broadcasting scheme is a calling scheme that gurantees the completion of the broadcast in the presence of up toklink failures. LetTk(n) denote the minimum time required forkfault‐tolerant broadcasting in ann‐vertex network. Liestman [Networks15(1985) 159–171] showed that for everynandksuch thatn− 2 ≥ k ≥ 1, Tk(n) ⩾ [logn]+k. This paper establishes a matching upper bound, showing that for suchnandk,Tk(n) ϵ O (logn+k). In particular, we present various efficient broadcasting schemes achieving almost optimal multiplicative constants. Our best upper bound uses new partial results on a tree‐packing problem that may be of in

ISSN:0028-3045    

DOI:10.1002/net.3230190706

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

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190707

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

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190708

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

年代:1989

数据来源: WILEY