[發明專利]一種基于圖論與布爾代數的機動車尾氣遙測設備布點方法

有效

• 申請號: 201611267906.5
• 申請日: 2016-12-31
• 公開（公告）號: CN106846222B
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 康宇;楊鈺瀟;李澤瑞;昌吉
• 申請（專利權）人: 中國科學技術大學
• 主分類號: G06Q50/26
• 分類號: G06Q50/26
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 楊學明;顧煒

本發明涉及一種基于圖論與布爾代數的機動車尾氣遙測設備布點方法，針對城市公交車，尋找機動車尾氣遙測設備在城市路網中合適的布設位置，以實現實時高效監測公交車尾氣排放情況的目標：首先基于圖論中超圖相關原理，將公交車運行路線轉化為公交路線超圖，并根據圖論中極小橫貫、橫貫超圖概念，將公交車尾氣遙測設備的布點問題轉化為公交路線超圖的最小橫貫求解問題；然后用布爾代數相關原理，解出公交路線超圖所有極小橫貫集；最后求出公交路線超圖的最小橫貫集，即最小監測路段集，確定出公交車尾氣遙測設備在城市路網中的布設位置。相比于已有的監測器布點方案，本發明專門針對城市公交系統，更具獨特性，且求解算法簡單易實現，操作性更強。

技術領域

本發明涉及一種基于圖論與布爾代數的機動車尾氣遙測設備布點方法，屬于機動車尾氣遙測設備的布點技術領域，以實時高效監測公交車尾氣排放情況為目標，根據圖論與布爾代數相關理論，進行數學建模與求解，進而研究機動車尾氣遙測設備在城市交通路網中的布設問題。

背景技術

隨著社會發展和城市進步，隨著高污染工廠逐漸遷至郊區，遠離城市，而城市中機動車數量持續增加。汽車在促進經濟繁榮、給人民生活帶來方便的同時，也帶來了能源和環保問題。其中對環境影響最大的，莫過于隨著機動車總量的飛速增長而日益嚴重的汽車尾氣污染。

公交車作為公共交通的重要組成部分，為市民出行提供了極大的便利，在人們生活中具有重要的意義。然而隨著城市不斷發展，公交車數量迅速增加，每到起步、加速、轉彎或上坡時，這些柴油車免不了冒出黑煙，對環境造成了很大污染。同時新能源公交車成本高，買得起也修不起讓很多公交公司望而卻步。因此，公交車污染的治理迫在眉睫，而實時有效的公交尾氣監控則是治理的第一步。在投資有限的情況下，如何將有限數量的檢測器安裝在路網中的合適道路上，以檢測到盡可能多的公交車，是監測系統組建的一個核心問題。

發明內容

本發明技術解決問題：克服現有技術的不足，提供一種基于圖論與布爾代數的機動車尾氣遙測設備布點方法，以公交車尾氣排放情況為監測目標，根據圖論相關理論與布爾代數進行建模與求解，進而研究尾氣遙測設備在城市交通路網中布設問題，以實現實時高效監測公交車尾氣排放情況為目標。

本發明技術解決方案：在城市公交車尾氣監測研究中，由于成本有限、機動車尾氣遙感監測設備數量有限，研究目標是用盡可能少的設備監測盡可能多的公交車。因此，尾氣遙測設備應布設在多條公交線路重合的路段上，且每條公交線路上至少有一個布設點，進而使監測范圍覆蓋城市所有公交路線。

基于以上分析，同時考慮到圖論在描述處理離散數學系統方面有著強大功能，可以為任何一個包含了一種二元關系的系統提供一個形象而直觀數學模型，本發明采用圖論相關理論對道路建模，得到公交路線超圖模型，在此基礎上將尾氣遙測設備的布點問題轉化為公交車路線超圖最小橫貫的求解問題，再用布爾代數理論求出最小橫貫集，即最小檢測路段集合，也就是實際中需要布設尾氣遙測設備的路段。

具體包括以下步驟：

(1)將公交車行駛路線抽象為公交路線超圖模型。根據圖論中超圖的概念，以城市實際的交通道路網絡為基礎，將公交車行駛線路中經過的各路段抽象為超圖頂點，將整條線路抽象為超邊，得到公交路線超圖。

(2)求公交路線超圖的全部極小橫貫。公交路線超圖中每一個頂點都有布爾變量x_i與之對應，x_i表示路段i是否布設尾氣遙感監測設備，若x_i＝1則表示此路段需要布設監測設備。首先對公交路線超圖每條邊中所有頂點進行布爾加法，得到表示第j條公交運行路線中包含的路段；然后對公交路線超圖所有邊進行布爾乘法，得到表示整個公交路線網中所有線路所含路段的全體；再將代入對展開化簡，得到最簡的多項式和的形式：Φ(H)＝σ₁+σ₂+…+σ_t+…，σ_t對應的頂點集是公交路線超圖的一個極小橫貫，Φ(H)表示與公交車每條運行路線都相交的路段全體。