The Determination of Critical Junctions for Transport Network

Abstract

By using the vertex cover algorithm in graph theory and network analysing techniques in GPS, the paper explores method in determining critical road network junctions for the optimum location of non-intrusive sensors for real-time traffic monitoring and data collection. The objective of the paper is to find the optimal location of junctions for placing sensors to maximally cover the road network under different budgets and requirements. Since the problem is NP-complete, a greedy-based heuristic method is proposed in finding the optimal junctions.

本文利用圖論中的頂點覆蓋算法和GIS中的網絡分析技術,對非嵌入式傳感器在路網中的最優定位問題,即關鍵路口點的選擇問題進行了探討。其目的在于選擇最少的路口點而覆蓋最大的路網范圍,從而最大限度地掌握交通流在路網上的分布和變化。由于頂點覆蓋是一個NP完全問題,本文將采用一個啟發式算法,并在一個模擬的路網結構上進行解算。