摘要:

AbstractWe present a primal‐dual algorithm for solving the minimum average weighted length circuit problem. The algorithm solves the problem by solving a series of subproblems with more combinatorial aspects iteratively. We also prove that the complexity of the algorithm isO(n4max{tij}) and show that our algorithm is actually a generalization of the Karp–Orlin algorithm. Finally, the relationship between the two algorithms is discus

ISSN:0028-3045    

DOI:10.1002/net.3230210702

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

年代:1991

数据来源: WILEY

摘要:

AbstractGiven an undirected 0‐1 flow networkGwithnnodes, Gomory and Hu's algorithm solves the multiterminal maximum flow problem by constructing a cut‐tree forG. Their algorithm requires solvingn− 1 maximum flow problems. A perturbed network ofGis a network generated fromGby deleting or adding an edge toG. For a given networkGand an edge(s, t)to be deleted from (resp., added to)G, a marginal cut‐treeTis a cut‐tree forGfrom which a cut‐tree for the perturbed network can be generated easily by reducing (resp., increasing) by 1 the weight of every edge in the path betweensandtinT. Given an undirected 0‐1 flow networkG, a cut‐tree forG, and an edge to be deleted from or added toG, we present an algorithm to generate a cut‐tree for the perturbed network by first transforming the given cut‐tree forGinto a marginal cut‐tree and then transforming the marginal cut‐tree into a cut‐tree for the perturbed network. This algorithm also requires solving the maximum flow problem; depending on the input data, the number of such problems to be solved is between 0 andn− 2 for edge deletion and between 0 andn− 1 for edge addition. Properties on the input data that lead, respectively, to the best‐case and worst‐case complexities of the algorithm are identified, and n

ISSN:0028-3045    

DOI:10.1002/net.3230210703

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

年代:1991

数据来源: WILEY

摘要:

AbstractIn this article, we present a multiphase approach to the period routing problem. The period routing problem involves the design of effective vehicle routes that satisfy customer service frequencies over a specified planning horizon. The first phase of analysis consists of a generalized network approximation to achieve an efficient initial solution. The second phase involves an interchange heuristic that reduces distribution costs by solving a surrogate traveling salesman problem. The third phase consists of an interchange heuristic that further reduces the distribution costs by addressing the actual vehicle routes of the period routing problem. A fourth phase utilizes a 0–1 integer model to attempt further improvements. Computational results on test problems indicate that the multiphase approach yields improvements over previous best solution

ISSN:0028-3045    

DOI:10.1002/net.3230210704

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

年代:1991

数据来源: WILEY

摘要:

AbstractThe minimum flow problem in a network is to find a flow with the smallest value so that the flow on each arc is bounded from below by the arc capacity. We present a linear time algorithm for solving the problem in(s,t)planar directed networks.

ISSN:0028-3045    

DOI:10.1002/net.3230210705

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

年代:1991

数据来源: WILEY

摘要:

AbstractConsider a flow networkG= (

ISSN:0028-3045    

DOI:10.1002/net.3230210706

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

年代:1991

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230210701

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

年代:1991

数据来源: WILEY