進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-1608201814310900
論文名稱(中文) 以節點為基礎的路網偵測器佈設模型:路徑流量重組之應用
論文名稱(英文) A node-based network sensor location model for path flow reconstruction
校院名稱 成功大學
系所名稱(中) 交通管理科學系
系所名稱(英) Department of Transportation & Communication Management Science
學年度 106
學期 2
出版年 107
研究生(中文) 王聖儒
研究生(英文) Seng-Ju Wang
學號 R56051096
學位類別 碩士
語文別 英文
論文頁數 93頁
口試委員 指導教授-胡守任
口試委員-林東盈
口試委員-禇志鵬
口試委員-王中允
口試委員-邱裕鈞
中文關鍵字 路網偵測器佈設問題  頂點覆蓋法  路徑流量重組  旅次起訖量估計 
英文關鍵字 Network sensor location problem  Vertex cover method  Path flow reconstruction  O-D demand estimation 
學科別分類
中文摘要 車輛偵測器是道路交通管理系統中不可或缺的一環,不僅用於蒐集道路交通相關參數資料,同時也可以做為交通監測的主要憑藉。然而,實務上交通管理部門基於預算限制,不可能在路網中廣泛的佈設偵測器,因此在特定的年度預算或空間範圍限制條件之下,如何決定最佳的車輛偵測器佈設數量與位置,以蒐集主要的交通流等相關資料進行線上交通管理,乃為現代化交通管理的重要課題之一。上述問題一般稱為路網偵測器佈設問題(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起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw