Abstract Shortest and/or longest path analysis is a major analytical component of quantitative models used by transportation planners. The importance of shortest path analysis in all phases of transportation planning has given rise to intensive research and software development over the last three decades for solving shortest path problems. This paper presents a new hybrid solution algorithm called THRESH, which integrates the features of label setting and label correcting algorithms, yet appears to have performance characteristics that transcend both. Preliminary computational results indicate that it is substantially more efficient than the methods determined to be best by previous studies.

Abstract This paper examines different algorithms for calculating the shortest path from one node to all other nodes in a network. More specifically, we seek to advance the state‐of‐the‐art of computer implementation technology for such algorithms and the problems they solve by exmining the effect of innovative computer science list structures and labeling techniques on algorithmic performance. The study shows that the procedures examined indeed exert a powerful influence on solution efficiency, with the identity of the best dependent upon the topology of the network and the range of the arc distance coefficients. The study further discloses, for the problems tested, that the lable‐setting shortest path algorithm previously documented as the most efficient is dominated for all problem structures examined by the new methods.

An in-depth study of the influence of problem structure on the computational efficiency of the primal simplex transportation algorithm is presented.The input for the study included over 1000 randomly generated problems with 185 different combinations of the number of sources, the number of destinations, and the number of variables.Objective function coefficients were generated using three different probability distributions to study the effects of variance and skewness in these parameters.Every problem was solved using three different starting procedures, and the following data were collected for each problem: (1) time required to obtain an optimal solution; (2) time required to obtain an initial basic solution; (3) number of artificial variables in the initial basic solution; (4) number of basis changes; (5) average time to perform a change of basis; (6) average number of basic variables in the "stepping stone path" in each change of basis; (7) average number of variables considered before selecting one to enter the basis.These measures of performance provide numerous insights into the effects of problem parameters on computation time.

Networks and network related problems occur with remarkable frequency in practical mathematical programming applications. This paper presents a variety of applications from industry and government that illustrate the scope and usefulness of network related formulations. In addition, recent breakthroughs in specialized methods and mathematical programming software systems that are capable of solving in only a few minutes problems that require many hours of computing time with commercial LP packages are reported. Finally, the latest developments in large scale applications are reported. These developments have made it possible to solve a manpower planning problem involving 450,000 variables in 26 minutes of central processing time on the IBM 360-65. Key Words and Phrases: network applications, transshipment algorithms, machine independent software, computational testing, network problem formulations, fixed charge mathematical programming CR Categorms: 3.25, 3.57, 5.25, 5.32 ~ 5.41

Abstract This paper presents extensive computational experience with a special purpose primal simplex algorithm. The performance is compared to that of several “state of the art” out‐of‐kilter computer codes. The computational characteristics of several different primal feasible start procedures and pivot selection strategies are also examined. The study discloses the advantages, in both computation time and memory requirements, of the primal approach over the out‐of‐kilter method. The test environment has the following distinguishing properties: (1) all of the codes are tested on the same machine and the same problems, (2) the test set includes capacitated and uncapacitated transhipment networks, transportation problems, and assignment problems, and (3) problem sizes ranging from 200 to 8,000 nodes with up to 35,000 arcs are examined.