Abstract
In some highway engineering work it is necessary to find a route between two points in a city's street and freeway network such that a function of time and distance is minimized. Such a route is called a “best” route, and finding such a route is not a difficult task. The Moore Algorithm1 accomplishes this quite nicely, and using that algorithm and a procedure developed by Hoffman and Pavley2 (programmed by them for the IBM 650) it is even possible to find the “Nth best path.”
- 1 MOORE, E. F. The shortest path through a maze. In Proceedings of an International Symposium on the Theory of Switching, Part II, April 2-5, 1957, The Annals of the Computation Laboratory of Harvard University 30, Harvard University, 1959.Google Scholar
- 2 HOFFMAN, WALTER, AND PAVLEY, RICHARD. A method for the solution of the Nth best path problems. J. Assoc. Comp. Mach. 6 (1959), 506-514. Google ScholarDigital Library
Index Terms
On finding minimum routes in a network with turn penalties
Recommendations
Quantifying the BGP routes diversity inside a tier-1 network
NETWORKING'06: Proceedings of the 5th international IFIP-TC6 conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications SystemsMany large ISP networks today rely on route-reflection [1] to allow their iBGP to scale. Route-reflection was officially introduced to limit the number of iBGP sessions, compared to the $\frac{n\times(n-1)}{2}$ sessions required by an iBGP full-mesh. ...
Network-wide prediction of BGP routes
This paper presents provably correct algorithms for computing the outcome of the BGP route-selection process for each router in a network, without simulating the complex details of BGP message passing. The algorithms require only static inputs that can ...
Two-phase bicriterion search for finding fast and efficient electric vehicle routes
SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsThe problem of finding an electric vehicle route that optimizes both driving time and energy consumption can be modeled as a bicriterion path problem. Unfortunately, the problem of finding optimal bicriterion paths is NP-complete. This paper studies ...
Comments