Alternative method of counting the number of efficient paths in a transportation network

References

• Ahuja, R. 1993. Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice Hall.
   Google Scholar
• Ball, M. O. 1986. “Computational Complexity of Network Reliability Analysis: An Overview.” IEEE Transactions on Reliability 35 (3): 230–239.
   Google Scholar
• Ball, T., and J. R. Larus. 1997. “Efficient Path Profiling.” Proceedings of the 29th Annual International Symposium on Microarchitecture, 46–57. Paris, France.
   Google Scholar
• Ball, M. O., and J. S. Provan. 1983. “Calculating Bounds on Reachability and Connectedness in Stochastic Networks.” Networks 13 (2): 253–278.
   Google Scholar
• Bartholdi, L. 1999. “Counting Paths in Graphs.” Enseignement Mathématique 45 (1–2): 83–131.
   Google Scholar
• Bell, M. G. H. 1995. “Alternatives to Dial’s Logit Assignment Algorithm.” Transportation Research Part B 29 (4): 287–295.
   Google Scholar
• Bianco, L., G. Confessore, and P. Reverberi. 2001. “A Network Based Model for Traffic Sensor Location with Implication in O-D Matrix Estimates.” Transportation Science 35 (1): 50–60.
   Google Scholar
• Boer, C., M. Snelder, R. Van Nes, and B. Van Arem. 2017. “The Impact of Route Guidance, Departure Time Advice and Alternative Routes on Door-to-Door Travel Time Reliability: Two Data-Driven Assessment Methods.” Journal of Intelligent Transportation Systems 21 (6): 465–477.
   Google Scholar
• Brumbaugh-Smith, J. P., and D. R. Shier. 2002. “Minimax Models for Diverse Routing.” INFORMS Journal on Computing 14 (1): 81–95.
   Google Scholar
• Cartwright, D., and T. C. Gleason. 1966. “The Number of Paths and Cycles in a Digraph.” Psychometrika 31 (2): 179–199.
   Google Scholar
• Castillo, E., Z. Grande, A. Calviño, W. Y. Szeto, and H. K. Lo. 2015. “A State-of-the-Art Review of the Sensor Location, Flow Observability, Estimation, and Prediction Problems in Traffic Networks.” Journal of Sensors 2015: 1–26.
   Google Scholar
• Chan, H. Y., A. Chen, G. Li, X. Xu, and W. H. K. Lam. 2021. “Measuring Route Diversity for Urban Rail Transit Networks.” Journal of Transport Geography 91, 102945.
   Google Scholar
• Chen, A., P. Chootinan, and S. Pravinvongvuth. 2004. “Multiobjective Model for Locating Automatic Vehicle Identification Readers.” Transportation Research Record 1886 (1): 49–58.
   Google Scholar
• Chen, A., S. Pravinvongvuth, and P. Chootinan. 2010. “Scenario-Based Multiobjective AVI Reader Location Models Under Different Travel Demand Patterns.” Transportmetrica 6 (1): 53–78.
   Google Scholar
• Chen, A., S. Pravinvongvuth, P. Chootinan, M. Lee, and W. Recker. 2007. “Strategies for Selecting Additional Traffic Counts for Improving O-D Trip Table Estimation.” Transportmetrica 3 (3): 191–211.
   Google Scholar
• Chen, J., Z. Zang, X. Xu, and C. Yang. 2018. “Identifying Critical Links in Transportation Networks Based on Route Diversity Redundancy.” Proceedings of the 17th COTA International Conference of Transportation Professionals, Shanghai, China, 3965–3977.
   Google Scholar
• Chootinan, P., A. Chen, and H. Yang. 2005. “A Bi-Objective Traffic Counting Location Problem for Origin-Destination Trip Table Estimation.” Transportmetrica 1 (1): 65–80.
   Google Scholar
• Cormen, T. H., C. E. Leiserson, and R. L. Rivest. 2009. Introduction to Algorithms. Cambridge, MA: MIT Press.
   Google Scholar
• Crawford, F., D. P. W. Watling, and R. D. Connors. 2018. “Identifying Road User Classes Based on Repeated Trip Behaviour Using Bluetooth Data.” Transportation Research Part A 113: 55–74.
   Google Scholar
• Dial, R. B. 1971. “A Probabilistic Multipath Traffic Assignment Model Which Obviates Path Enumeration.” Transportation Research 5 (2): 83–111.
   Google Scholar
• Dias, F. C., M. Campêlo, C. Souza, and R. Andrade. 2017. “Min-Degree Constrained Minimum Spanning Tree Problem with Fixed Centrals and Terminals: Complexity, Properties and Formulations.” Computers & Operations Research 84: 46–61.
   Google Scholar
• Floyd, R. W. 1962. “Algorithm 97: Shortest Path.” Communications of the ACM 5 (6): 345.
   Google Scholar
• Freeman, L. C., S. P. Borgatti, and D. R. White. 1991. “Centrality in Valued Graphs: A Measure of Betweenness Based on Network Flow.” Social Networks 13 (2): 141–154.
   Google Scholar
• Gentili, N., and P. B. Mirchandani. 2012. “Locating Sensors on Traffic Networks: Models, Challenges and Research Opportunities.” Transportation Research Part C 24: 227–255.
   Google Scholar
• Gessel, I. 1993. “Counting Paths in Young’s Lattice.” Journal of Statistical Planning and Inference 34 (1): 125–134.
   Google Scholar
• Havlin, S., and R. Cohen. 2010. Complex Networks: Structure, Robustness, Function. Cambridge: Cambridge University Press.
   Google Scholar
• He, D., A. N. Arslan, Y. He, and X. Wu. 2007. “Iterative Refinement of Repeat Sequence Specification using Constrained Pattern Matching.” Proceedings of the 2007 IEEE 7th International Symposium on BioInformatics and BioEngineering, Boston, MA, 1199–1203.
   Google Scholar
• Hochberg, R. 2012. Matrix Multiplication with CUDA – a Basic Introduction to the CUDA Programming Model. SHODOR Technical Document.
   Google Scholar
• Huang, H. J., and M. G. H. Bell. 1998. “A Study on Logit Assignment Which Excludes All Cyclic Flows.” Transportation Research Part B 32 (6): 401–412.
   Google Scholar
• Hung, M. S., and J. J. Divoky. 1988. “A Computational Study of Efficient Shortest Path Algorithms.” Computers & Operations Research 15 (6): 567–576.
   Google Scholar
• Ip, W. H., and D. Wang. 2009. “Resilience Evaluation Approach of Transportation Networks.” Proceedings of the International Joint Conference on Computational Sciences and Optimization, Sanya, China, 681–622.
   Google Scholar
• Jing, W., X. Xu, and Y. Pu. 2019. “Route Redundancy-Based Network Topology Measure of Metro Networks.” Journal of Advanced Transportation 2019: 1–12.
   Google Scholar
• Jing, W., X. Xu, and Y. Pu. 2020. “Route Redundancy-Based Approach to Identify the Critical Stations in Metro Networks: A Mean-Excess Probability Measure.” Reliability Engineering & System Safety 204: 107204.
   Google Scholar
• Kim, J., and H. S. Mahmassani. 2015. “Spatial and Temporal Characterization of Travel Patterns in a Traffic Network Using Vehicle Trajectories.” Transportation Research Part C 59: 375–390.
   Google Scholar
• Kirchhoff, G. 1958. “On the Solution of the Equations Obtained from the Investigation of the Linear Distribution of Galvanic Currents.” IRE Transactions on Circuit Theory 5 (1): 4–7.
   Google Scholar
• Kurauchi, F., N. Uno, A. Sumalee, and Y. Seto. 2009. “Network Evaluation Based on Connectivity Vulnerability.” Proceedings of the 18th International Symposium on Transportation and Traffic Theory, Boston, MA, 637–649.
   Google Scholar
• Lam, W. H. K., and K. S. Chan. 1998. “A Link-Based Alternative to Bell’s Logit Assignment Algorithm.” HKIE Transactions 5 (2): 11–18.
   Google Scholar
• Larsson, T., J. T. Lundgren, and A. Peterson. 2010. “Allocation of Link Flow Detectors for Origin-Destination Matrix Estimation – a Comparative Study.” Computer-Aided Civil and Infrastructure Engineering 25 (2): 116–131.
   Google Scholar
• Leurent, F. M. 1997. “Curbing the Computational Difficulty of the Logit Equilibrium Assignment Model.” Transportation Research Part B 31 (4): 315–326.
   Google Scholar
• Li, Y., L. Sun, H. Z. Zhu, and Y. X. Wu. 2012. “A Nettree for Simple Paths with Length Constraint and the Longest Path in Directed Acyclic Graphs.” Chinese Journal of Computers 35 (10): 2194.
   Google Scholar
• Liu, F., G. Qi, and H. Che. 2006. “Research on Algorithm for Detecting Simple Path in Complex Network and Its Application.” System Engineering Theory and Practices 26 (4): 9–13.
   Google Scholar
• Meng, Q., D. H. Lee, and R. L. Cheu. 2005. “Counting the Different Efficient Paths for Transportation Networks and Its Applications.” Journal of Advanced Transportation 39 (2): 193–220.
   Google Scholar
• Miller-Hooks, E., X. Zhang, and R. Faturechi. 2012. “Measuring and Maximizing Resilience of Freight Transportation Networks.” Computers & Operations Research 39 (7): 1633–1643.
   Google Scholar
• Prato, C. G. 2009. “Route Choice Modeling: Past, Present and Future Research Directions.” Journal of Choice Modelling 2 (1): 65–100.
   Google Scholar
• Prato, C. G., and S. Bekhor. 2006. “Applying Branch & Bound Technique to Route Choice set Generation.” Transportation Research Record 1985 (1): 19–28.
   Google Scholar
• Roberts, B., and D. P. Kroese. 2007. “Estimating the Number of s-t Paths in a Graph.” Journal of Graph Algorithms & Applications 11 (1): 195–214.
   Google Scholar
• Ross, I. C., and F. Harary. 1952. “On the Determination of Redundancies in Sociometric Chains.” Psychometrika 17 (2): 195–208.
   Google Scholar
• Sanjeev, A., and B. Boaz. 2009. Computational Complexity: A Modern Approach. Cambridge: Cambridge University Press.
   Google Scholar
• Schäfer, L., S. García, A. Mitschke, and V. Srithammavanh. 2018. “Redundancy System Design for an Aircraft Door Management System.” Computers & Operations Research 94: 11–22.
   Google Scholar
• Sheffi, Y. 1985. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Englewood Cliffs, NJ: Prentice Hall.
   Google Scholar
• Si, B., M. Zhong, H. Zhang, and W. Jin. 2010. “An Improved Dial’s Algorithm for Logit-Based Traffic Assignment Within a Directed Acyclic Network.” Transportation Planning and Technology 33 (2): 123–137.
   Google Scholar
• Stanley, R. P. 1996. “A Matrix for Counting Paths in Acyclic Digraphs.” Journal of Combinatorial Theory Series A 74 (1): 169–172.
   Google Scholar
• Tagliacozzo, F., and F. Pirzio. 1973. “Assignment Models and Urban Path Selection Criteria: Results of a Survey of the Behaviour of Road Users.” Transportation Research 7 (3): 313–329.
   Google Scholar
• Tong, C. 1990. “Modification of Dial's Algorithm by Redefining Path Efficiency.” Traffic Engineering & Control 31 (9): 483–486.
   Google Scholar
• Valiant, L. G. 1979a. “The Complexity of Computing the Permanent.” Theoretical Computer Science 8 (2): 189–201.
   Google Scholar
• Valiant, Leslie G. 1979b. “The Complexity of Enumeration and Reliability Problems.” SIAM Journal on Computing 8 (3): 410–421.
   Google Scholar
• Wang, I., E. L. Johnson, and J. S. Sokol. 2005. “A Multiple Pairs Shortest Path Algorithm.” Transportation Science 39 (4): 465–476.
   Google Scholar
• Wiener, H. 1947. “Structural Determination of Paraffin Boiling Points.” Journal of the American Chemical Society 69 (1): 17–20.
   Google Scholar
• Wong, S. C. 1999. “On the Convergence of Bell’s Logit Assignment Formulation.” Transportation Research Part B 33 (8): 609–616.
   Google Scholar
• Wu, Y., X. Wu, F. Min, and Y. Li. 2010. “A Nettree for Pattern Matching with Flexible Wildcard Constraints.” Proceedings of the IEEE International Conference on Information Reuse & Integration, Las Vegas, ND, 109–114.
   Google Scholar
• Xu, X., A. Chen, S. Jansuwan, C. Yang, and S. Ryu. 2018. “Transportation Network Redundancy: Complementary Measures and Computational Methods.” Transportation Research Part B 114: 68–85.
   Google Scholar
• Xu, X., A. Chen, and C. Yang. 2018. “An Optimization Approach for Deriving Upper and Lower Bounds of Transportation Network Vulnerability Under Simultaneous Disruptions of Multiple Links.” Transportation Research Part C 94: 338–353.
   Google Scholar
• Xu, X., H. K. Lo, A. Chen, and E. Castillo. 2016. “Robust Network Sensor Location for Complete Link Flow Observability Under Uncertainty.” Transportation Research Part B 88: 1–20.
   Google Scholar
• Yang, X., A. Chen, B. Ning, and T. Tang. 2017. “Measuring Route Diversity for Urban Rail Transit Networks: A Case Study of the Beijing Metro Network.” IEEE Transactions on Intelligent Transportation Systems 18 (2): 259–268.
   Google Scholar
• Young, C., and M. D. Smith. 1999. “Static Correlated Branch Prediction.” ACM Transactions on Programming Languages and Systems 21 (5): 1028–1075.
   Google Scholar
• Zhou, C., X. Chu, and C. Nie. 2007. “Predicting Thermodynamic Properties with a Novel Semiempirical Topological Descriptor and Path Numbers.” The Journal of Physical Chemistry B 111 (34): 10174–10179.
   Google Scholar
• Zhou, X., and G. List. 2010. “An Information-Theoretic Sensor Location Model for Traffic Origin-Destination Demand Estimation Applications.” Transportation Science 44 (2): 254–273.
   Google Scholar