摘要:

AbstractLetG= (V, E) be an undirected graph withV=nperfectly reliable vertices andE=medges that work with probabilitypeand fail with probability qefor alle/inE. The network reliability problem considered here is to calculateRK[G] = Prob [there exists a path of working edges between every pair of a setKofkvertices]. Backtrack algorithms for this problem are presented. The complexity of these algorithms is discussed when applied to the all‐terminal network reliability problem whereK=V. Strategies are presented which minimize the size of the search structures generated. The main theorems state that when these strategies are used, the size of the search structures may be measured by counting spanning trees or acyclic orientation

ISSN:0028-3045    

DOI:10.1002/net.3230140402

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

年代:1984

数据来源: WILEY

摘要:

AbstractWe give a simple linear‐time algorithm for finding even‐length simple paths between two specified nodes of a given graph. We show that the same problem for directed graphs is NP‐com

ISSN:0028-3045    

DOI:10.1002/net.3230140403

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

年代:1984

数据来源: WILEY

摘要:

AbstractThis paper gives the Lagrangian dual coordinatewise maximization (LDCM) algorithm for network transportation problems with strictly convex quadratic costs (NTPQ). An explicit expression for the dual function associated with NTPQ is obtained. Some properties of the dual function are shown. Then, using these properties, a procedure which involves successively maximizing the dual function with respect to each of its dual coordinates is applied to obtain the optimal dual solution. Then the optimal primal solution is obtained by substituting the dual solution to the simple expression. Computational results for 200 randomly generated problems reveal the effectiveness of the algorithm. The key idea of applying the Lagrangian dual method to NTPQ is that the objective function of the network problems is strictly convex. This strict convexity allows one to finesse problems that occur in using Lagrangian methods with more general problems. In particular, because the optimal solution of the Lagrangian problem is unique, the dual function is differentiable and an optimal solution to the Lagrangian with optimal multipliers is optimal in the original primal problem. These are strong results that are not true in general.

ISSN:0028-3045    

DOI:10.1002/net.3230140404

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

年代:1984

数据来源: WILEY

摘要:

AbstractWe consider the following problem: Given an integerkand a networkGwith two distinct verticessandt, find a maximum number of vertex disjoint paths fromstotof length bounded byk. In a recent work [9] it was shown that for length greater than four this problem isNP‐hard. In this paper we present a polynomial heuristic algorithm for the problem for general length. The algorithm is proved to give optimal solution for length less than five. Experiments show very good results for the algorith

ISSN:0028-3045    

DOI:10.1002/net.3230140405

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

年代:1984

数据来源: WILEY

摘要:

AbstractConsider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost, and a time interval within which the trip must begin. The trips may include visits to one or more specific points. Our problem is to determine the number of vehicles required, together with their routes and schedules, so that each trip begins within its given time interval, while the fixed costs related to the number of vehicles, and the travel costs between trips, are minimized. The problem is a generalization of them‐traveling salesman problem. We use column generation on a set partitioning problem solved by simplex and branch‐and‐bound; columns are generated by a shortest path algorithm with time windows on the nodes. Numerical results for several school bus transportation problems with up to 151 trips are disc

ISSN:0028-3045    

DOI:10.1002/net.3230140406

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

年代:1984

数据来源: WILEY

摘要:

AbstractGiven a transportation flow network with two arcs in antiparallel, if the capacities of all other arcs are fixed and the demands at sinks are fixed, at least one of the two arcs will be irrelevant to the problem of flow feasibility. As a consequence, in a stochastic setting, two arcs in antiparallel whose capacities are independent of other network capacities and demands may be treated as having independent probability distributions regardless of their actual correlation.

ISSN:0028-3045    

DOI:10.1002/net.3230140407

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

年代:1984

数据来源: WILEY

摘要:

AbstractHierarchical vehicle routing problems, in which the decision to acquire a number of vehicles has to be based on imperfect (probabilistic) information about the location of future customers, allow a natural formulation as two‐stage stochastic programming problems, where the objective is to minimize the sum of the acquisition cost and the length of the longest route assigned to any vehicle. For several versions of this difficult optimization problem, we show that simple heuristics have strong properties of asymptotically optimal behavio

ISSN:0028-3045    

DOI:10.1002/net.3230140408

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

年代:1984

数据来源: WILEY

摘要:

AbstractThis article presents an informal discussion of the issue of asymptotic optimality of heuristics from the viewpoint of the operations research practitioner. It is suggested that certain heuristics belonging to the above class are likely to perform questionably in practice, with regard both to relative error and to computational tractability. Possible explanations of this phenomenon are offered and suggestions for further research toward a better understanding of this problem are presented.

ISSN:0028-3045    

DOI:10.1002/net.3230140409

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

年代:1984

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230140411

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

年代:1984

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230140401

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

年代:1984

数据来源: WILEY