摘要:

AbstractA new and much faster algorithm is presented for the problem of assigning buses to a large number of short trips in an urban area. The trips are grouped into chains, beginning and ending at the same bus depot, and a vehicle is assigned to each one of them. Fleet size costs and dead heading time are to be minimized. This problem has been already formulated as a transportation problem and more recently, as an assignment model. However, some difficulties, such as the zero pivot phenomenon, rising in many practical cases drastically affected computing times required to obtain the optimal solution. This is overcome by an algorithm based on the hungarian method and making full use of the sparsity of the assignment matrix for the bus scheduling problem. Computational results comparing the different methods are given in the last section of the paper. Significant reductions in computing time are obtained for either real case applications or random generated test problems.

ISSN:0028-3045    

DOI:10.1002/net.3230170302

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

年代:1987

数据来源: WILEY

摘要:

AbstractTwo bipartite matching problems arising in Vehicle Scheduling are considered: the capacitated matching and the multicommodity matching. For the former, given a reasonable cost structure, we can exhibit a polynomial time algorithm, while the general case is conjectured to be NP‐hard. The latter problem is shown to be NP‐hard. A heuristic algorithm based on Lagrangean relaxation for the capacitated version of the multicommodity matching is also presented together with experimental resu

ISSN:0028-3045    

DOI:10.1002/net.3230170303

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

年代:1987

数据来源: WILEY

摘要:

AbstractSince the introduction of the Chinese Postman Problem (CPP), many variations on the same theme have been developed. In this paper we examine still another variation. The arcs of the graph are partitioned and a precedence relation defined, specifying the order in which the elements of the partition have to be traversed. We first examine the conditions for a feasible solution to the problem. Next, we specify the graph properties of the precedence partition that insure a polynomial complexity solution ofO(N5), whereNis the number of nodes in the original graph. When the precedence relation on sets of arcs is general, we prove that the problem of finding the minimum length of feasible postman tour is NP‐complet

ISSN:0028-3045    

DOI:10.1002/net.3230170304

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

年代:1987

数据来源: WILEY

摘要:

AbstractWe construct a digraph with the maximum number of simple paths between two specified vertices, for a digraph with a given number of edges. The following cases are considered: digraphs with parallel edges, acyclic simple digraphs and general simple digraphs. The corresponding extremal digraphs are the tri‐chains, the (deficient) Fibonacci digraphs and (if our conjecture is true) the 3‐diamond strings, respectively. The similarity of these three families of digraphs is discussed. The related problem of digraphs with the maximum number of simple cycles for a given number of edges is considered

ISSN:0028-3045    

DOI:10.1002/net.3230170305

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

年代:1987

数据来源: WILEY

摘要:

AbstractWe develop a linear time algorithm to determine if a given planar triangulated graph has a rectangular dual.

ISSN:0028-3045    

DOI:10.1002/net.3230170306

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

年代:1987

数据来源: WILEY

摘要:

AbstractThe PARTAN variant of the linear approximation method is adapted for solving the network equilibrium problem. A simple and efficient algorithm is stated. Its properties are analyzed by using algebraic and geometric approaches. Its computational efficiency on small and large scale problems is compared to that of the linear approximation method.

ISSN:0028-3045    

DOI:10.1002/net.3230170307

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

年代:1987

数据来源: WILEY

摘要:

AbstractIn this paper, we examine the problem of findingk‐shortest paths between an origin and destination pair when distances are Euclidean. Two versions of a generalized Dijkstra algorithm are compared. Computational results show that the advantage of the adaptive version (measured by total number of permanent labels) grows with bothkand the network size. For large networks, the adaptive algorithm exhibits a 100:1 advantage in the number of permanent labels se

ISSN:0028-3045    

DOI:10.1002/net.3230170308

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

年代:1987

数据来源: WILEY

摘要:

AbstractThe Steiner Problem in Graphs (SP) is the problem of finding a set of edges with minimum total weight which connects a given subset of nodes in an edge‐weighted (undirected) graph. In the more general Node‐weighted Steiner Problem (NSP) also node weights are considered. A restricted minimum spanning tree model is adjusted for the NSP as well as for the Steiner Forest Problem, a newly introduced generalization. The NSP is related to the Directed Steiner Problem. Reduction tests for the SP, reducing the size of the problem graph, are adapted for these generalizations and some new tests are develo

ISSN:0028-3045    

DOI:10.1002/net.3230170309

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

年代:1987

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230170301

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

年代:1987

数据来源: WILEY