簡易檢索 / 詳目顯示

回結果列表
研究生： 王聖儒
Wang, Seng-Ju
論文名稱： 以節點為基礎的路網偵測器佈設模型：路徑流量重組之應用
A node-based network sensor location model for path flow reconstruction
指導教授： 胡守任
Hu, Shou-Ren
學位類別： 碩士
Master
系所名稱： 管理學院 - 交通管理科學系
Department of Transportation and Communication Management Science
論文出版年： 2018
畢業學年度： 106
語文別： 英文
論文頁數： 93
中文關鍵詞： 路網偵測器佈設問題 、頂點覆蓋法 、路徑流量重組 、旅次起訖量估計
外文關鍵詞： Network sensor location problem, Vertex cover method, Path flow reconstruction, O-D demand estimation
相關次數： 點閱：88  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 車輛偵測器是道路交通管理系統中不可或缺的一環，不僅用於蒐集道路交通相關參數資料，同時也可以做為交通監測的主要憑藉。然而，實務上交通管理部門基於預算限制，不可能在路網中廣泛的佈設偵測器，因此在特定的年度預算或空間範圍限制條件之下，如何決定最佳的車輛偵測器佈設數量與位置，以蒐集主要的交通流等相關資料進行線上交通管理，乃為現代化交通管理的重要課題之一。上述問題一般稱為路網偵測器佈設問題(Network Sensor Location Problem, NSLP)，在NSLP的相關文獻中，主要著眼於如何在特定路網中求解佈設於節點或節線的最小偵測器數量組合，或者利用既有的偵測器佈設組合推估旅次起訖需求量或其他流量資訊。隨著物聯網的興起，以及資通訊技術的迅速發展，以先進的偵測器蒐集車流相關資料變得日益可行。針對NSLP，本研究假設某種佈設於路網節點的虛擬智慧型偵測器，透過雙向通訊可以偵測車輛通過路口的身分，接著利用頂點覆蓋法尋找最小數量的節點組合，最後假設路網中每對旅次起訖點間有限條的最短路徑軌跡可被追蹤，據以發展數學規劃模型，進行路徑與旅次起訖流量的推估。在數值分析方面，主要分為兩部分：以點覆蓋法求得路網中最佳偵測器佈設位置並據以估計全路網的節線流量，以及根據前述偵測器最佳佈設位置以數學規劃模型推估路徑流量與旅次起訖量。經由數值分析可發現，以點覆蓋法可求得多組的最佳偵測器佈設位置，以及在多數的實際路徑軌跡已知的情況下，有助於路徑流量與旅次起訖流量的推估。本研究以前瞻性的觀點，提出創新的先進偵測器佈設策略，據以估計道路交通路網的相關流量資訊。展望未來，隨著車輛偵測器技術功能日益完備與成本下降，透過先進偵測器蒐集基礎車流資料將日益普遍；應用本研究所發展的NSLP模式與相關演算法推估車流相關資訊，對於線上交通管理與控制，將有實質的助益。

    Vehicle detectors or traffic sensors play an indispensable role in modern traffic management systems. They can not only collect traffic parameters in a vehicular network but also can be used for traffic monitoring and/ or control purposes. However, traffic management agencies are not able to comprehensively deploy a larger number of sensors in practice due to an annual budget constraint. It drives the need to address the problem of optimal sensor locations under a budget constraint and/ or within a specific region. This problem and its variants is called the network sensor location problem (NSLP). In the previous studies of NSLP, they mainly aimed at finding a smallest subset of the links or nodes for sensor deployment by minimizing the flow estimation errors, or focused on the estimation of network origin-destination (O-D) demands given a set of prior deployed sensors. With the advent of internet of things (IoT) and the rapid development of information and communication technologies (ICTs), application of advanced sensors for traffic data collection becomes feasible. For the NSLP, this study assumes a node-based smart virtual sensor is able to detect vehicle trajectories in a given network via two-way communications. We seek to identify the smallest subset of nodes for the NSLP by using the vertex cover method. Finally, we develop mathematical models by under the limited shortest paths between each O-D pair can be recognized to estimate path flows and O-D demand. Then the numerical analysis is divided into two parts: first part is to find optimal location(s) for sensor deployment by vertex cover method in order to detect all link flows in the network; second part is to construct mathematical models to estimate path flows and O-D demand under sensors are optimally located. The results of numerical analysis show that there are multiple optimal locations for sensor deployment by the vertex cover method, and it helps to estimate path flows and O-D demands when the partial path trajectories are captured by virtual smart sensors. Addressed from a frontier viewpoint, this study proposes an innovative idea for the NSLP. Looking into the future, collecting traffic information via advanced sensor technologies becomes popular due to matured technologies and decreasing costs. In addition, the developed models and solution algorithm proposed in this study are beneficial to traffic agencies for on-line traffic control and management purposes.

    中文摘要 II ABSTRACT III 誌謝 V TABLE OF CONTENTS VI LIST OF TABLES IX LIST OF FIGURES XI CHAPTER 1 INTRODUCTION 1 1.1 Research background 1 1.2 Research motivation 2 1.3 Research objectives 4 1.4 Research content with flow chart 5 CHAPTER 2 LITERATURE REVIEW 7 2.1 Definition of the NSLP 7 2.2 Classification of the NSLP 8 2.2.1 Sensor location flow-observability problem 8 2.2.2 Sensor location flow-estimation problem 10 2.3 Subclass of the NSLP studies according to the sensor deployment, sensor types and used methods 11 2.4 Graph-based approaches for the NSLP 18 2.4.1 Graphical approach address to the NSLP previously 18 2.4.2 Background of the vertex cover method 19 2.5 Summary 23 CHAPTER 3 METHODOLOGY 25 3.1 Problem statement and notations 25 3.2 The vertex cover method 29 3.2.1 Definitions and rules 29 3.2.2 Algorithm 31 3.3 Path flow reconstruction 40 3.4 Summary 42 CHAPTER 4 NUMERICAL ANALYSIS 43 4.1 Experimental setup 43 4.2 Results of link flow observability by the vertex cover method 44 4.2.1 Dharwadker’s solver 44 4.2.2 Parallel highway network 47 4.2.3 Fishbone network 50 4.2.4 Nguyen-Dupuis network 53 4.2.5 Yang’s network 58 4.2.6 NCKU network 61 4.2.7 Insights 65 4.3 Results of path flow reconstruction 67 4.3.1 Fishbone network 67 4.3.2 Nguyen-Dupuis network 74 4.3.3 Insights 79 4.4 Comparative analysis: the node-based method versus the link-based method 80 4.4.1 Cost comparison 80 4.4.2 Estimation performance comparison 83 4.5 Summary 85 CHAPTER 5 CONCLUSIONS AND RECOMMENDATIONS 86 5.1 Conclusions 86 5.2 Contributions 86 5.3 Future research 87 LIST OF REFERENCES 89

    1. Al-Naima, F.M. & Al-Any, H. (2011). Vehicle location system based on RFID. Proc. of the IEEE Developments in E-systems Engineering, 473-478.
    2. Alom, B.M., Das, S. & Rouf, M.A. (2011). Performance evaluation of vertex cover and set cover problem using optimal algorithm. DUET Journal, 1(2), 8-13.
    3. Angel, E., Campigotto, R. & Laforest, C (2010). Algorithm for the vertex cover problem on large graphs. IBISC Research report.
    4. Bianco, L., Confessore, G. & Gentili, M. (2006). Combinatorial aspects of the sensor location problem. Annals of Operations Research, 144, 201–234.
    5. Castillo, E., Calviño, A., Lo, H.K., Menéndez, J.M., & Grande, Z. (2014). Non-planar hole-generated networks and link flow observability based on link counters. Transportation Research Part B, 68, 239–261.
    6. Castillo, E., Calviño, A., Menéndez, J.M., Jiménez, P., & Rivas, A. (2013b). Deriving the upper bound of the number of sensors required to know all link flows in a traffic network. IEEE Transactions on Intelligent Transportation Systems, 14(2), 761-771.
    7. Castillo, E., Conejo, A.J., Menéndez, J.M., & Jiménez, P. (2008a). The observability problem in traffic network models. Computer-Aided Civil and Infrastructure Engineering, 23(3), 208–222.
    8. Castillo, E., Jiménez, P., Menéndez, J.M., & Conejo A.J. (2008b). The observability problem in traffic models: algebraic and topological methods. IEEE Transactions on Intelligent Transportation Systems, 9(2), 275-287.
    9. Castillo, E., Menéndez, J.M. & Jiménez, P. (2008d). Trip matrix and path flow reconstruction and estimation based on plate scanning and link observations. Transportation Research Part B, 42(5), 455-481.
    10. Castillo, E., Menéndez, J.M. & Sanchez-Cambronero, S. (2008c). Traffic estimation and optimal counting location with path enumeration using Bayesian networks. Computer-Aided Civil and Infrastructure Engineering, 23(3), 189–207.
    11. Castillo, E., Nogal, M., Rivas, A., & Sanchez-Cambronero, S. (2013a). Observability in traffic networks. Optimal location of counting and scanning devices. Transportmetrica B, 1(1), 68-102.
    12. Chattaraj, A., Bansal, S., & Chandra, A. (2009). An intelligent traffic control system using RFID, IEEE Potentials, 28(3), 40-43.
    13. Chootinan, P., Chen A. & Yang, H. (2005). A bi-objective traffic counting location problem for origin-destination trip table estimation. Transportmetrica, 1(1), 65-80.
    14. Clarkson, K.L. (1983). A modification of the greedy algorithm for vertex cover. Information Processing Letters, 16, 23-25.
    15. Cormen, T.H., Leiserson, C.E., Rivest, R.L. & Stein, C. (2009). Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill.
    16. Dharwadker, A. (2011). The Vertex Cover Algorithm. Createspace.
    17. Eisenman, S.M., Fei, X., Zhou, X. & Mahmassani, H.S. (2006). Number and location of sensors for real-time network traffic estimation and prediction: a sensitivity analysis. Transportation Research Record, 1964, 260–269.
    18. Fei, X. & Mahmassani, H.S. (2011). Structural analysis of near-optimal sensor locations for a stochastic large-scale network. Transportation Research Part C, 19, 440–453.
    19. Filiol, E. & Gallais, C. (2016). Combinatorial optimization of operational (cyber) attacks against large-scale critical infrastructures: the vertex cover approach. Proc. of the 11th International Conference on Cyber Warfare and Security, 129-139.
    20. Fu, C., Zhu, N., Ling, S., Ma, S. & Huang, Y. (2016). Heterogeneous sensor location model for path reconstruction. Transportation Research Part B, 91(5), 77-97.
    21. Gentili, M. & Mirchandani, P.B. (2012). Locating sensors on traffic networks: models, challenges and research opportunities. Transportation Research Part C, 24, 227-255.
    22. Gubbi, J., Buyya, R., Marusic, S., & Palaniswami, M. (2013). Internet of things (IoT): a vision, architectural elements, and future directions. Future Generation Computer Systems, 29(7), 1645–1660.
    23. He, S. (2013). A graphical approach to identify sensor locations for link flow inference. Transportation Research Part B, 55, 65-76.
    24. Horiguchi, R., Kuwahara, M. & Akahane, H. (2001). The optimal arrangement of infrared beacons on a road network to collect vehicle trajectories-pattern analysis using schema theory. Journal of the Eastern Asia Society for Transportation Studies, 4(4), 219-228.
    25. Hu, S.R. & Liou, H.T. (2014). A generalized sensor location model for the estimation of network origin-destination matrices. Transportation Research Part C, 40(3), 93-110.
    26. Hu, S.R., Peeta, S. & Liou, H.T. (2016). Integrated determination of network origin-destination trip matrix and heterogeneous sensor selection and location strategy. IEEE Transactions on Intelligent Transportation Systems, 17(1) 195-205.
    27. Hu, S.R., Peeta, S., & Chu, C.H. (2009). Identification of vehicle sensor locations for link-based network traffic applications. Transportation Research Part B, 43(8-9), 873-894.
    28. Karp, R. (1972). Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, ed. Advances in Computing Research. Plenum Press, 85–103.
    29. Kolassa, S. & Schütz, W. (2007). Advantages of the MAD/mean ratio over the MAPE. Foresight: The International Journal of Applied Forecasting, 6, 40–43.
    30. Lewis, C.D. (1982). Industrial and business forecasting methods: a practical guide to exponential smoothing and curve fitting. Butterworth Scientific, London.
    31. Li, C.H. (2010). Automatic vehicle identification AVI system based on RFID. Proc. of the IEEE Anti-Counterfeiting Security and Identification in Communication (ASID), International Conference on, 281-284.
    32. Mínguez, R., Sánchez-Cambronero, S., Castillo, E. & Jiménez, P. (2010). Optimal traffic plate scanning location for OD trip matrix and route. Transportation Research Part B, 44(2), 282-298.
    33. Ng, M.W. (2012). Synergistic sensor location for link flow inference without path enumeration: a node-based approach. Transportation Research Part B, 46(6), 781-788.
    34. Ng, M.W. (2013). Partial link flow observability in the presence of initial sensors: solution without path enumeration. Transportation Research Part E, 51, 62-66.
    35. Nguyen, S. & Dupuis, C. (1984). An efficient method for computing traffic equilibria in networks with asymmetric transportation costs. Transportation Science, 18(2), 185-202.
    36. Patel, K. & Patel, J. (2017). Computational analysis of different vertex cover algorithms of various graphs. International Conference on Intelligent Computing and Control Systems, 730-734.
    37. Prestwich, S., Rossi, R., Armagan Tarim, S., & Hnich, B. (2014). Mean-based error measures for intermittent demand forecasting. International Journal of Production Research, 52(22), 6782–6791.
    38. Wang, C.Y. & Hu, S.R. (2013). Estimation of time-dependent origin-destination matrices using the path flow proportion method. Journal of the Eastern Asia Society for Transportation Studies, 10, 776-795.
    39. Wang, N. & Mirchandani, P. (2013). Sensor location model to optimize origin-destination estimation using a Bayesian statistical procedure. Transportation Research Record, 2334, 29-39.
    40. Xing, T., Zhou, X. & Taylor, J. (2013). Designing heterogeneous sensor networks for estimating and predicting path travel time dynamics: An information-theoretic modeling approach. Transportation Research Part B, 57, 66–90.
    41. Xu, X., Lo, H.K., Chen, A., & Castillo, E. (2016). Robust network sensor location for complete link flow observability under uncertainty. Transportation Research Part B, 88, 1-20.
    42. Yang, H. & Zhou, J. (1998). Optimal traffic counting locations for origin-destination matrix estimation. Transportation Research Part B, 32(2), 109-126.
    43. Yang, H., Iida, Y. & Sasaki, T. (1991). An analysis of the reliability of an origin-destination trip matrix estimated from traffic counts. Transportation Research Part B, 25(5), 351-363.
    44. Yang, H., Yang, C. & Gan, L. (2006). Models and algorithms for the screen line-based traffic-counting location problems. Computers & Operations Research, 33(3), 836-858.
    45. Yen, J.Y. (1971). Finding the k shortest loopless paths in a network. Management Sciences, 17(11), 712-716.
    46. Zhou, X. & List, G. (2010). An information-theoretic sensor location model for traffic origin-destination demand estimation applications. Transportation Science, 44(2), 254-273.

    下載圖示 校內：2023-08-31公開
    校外：2023-08-31公開
    QR CODE