一种基于图论与布尔代数的机动车尾气遥测设备布点方法

技术领域

本发明涉及一种基于图论与布尔代数的机动车尾气遥测设备布点方法，属于机动车尾气遥测设备的布点技术领域，以实时高效监测公交车尾气排放情况为目标，根据图论与布尔代数相关理论，进行数学建模与求解，进而研究机动车尾气遥测设备在城市交通路网中的布设问题。

背景技术

随着社会发展和城市进步，随着高污染工厂逐渐迁至郊区，远离城市，而城市中机动车数量持续增加。汽车在促进经济繁荣、给人民生活带来方便的同时，也带来了能源和环保问题。其中对环境影响最大的，莫过于随着机动车总量的飞速增长而日益严重的汽车尾气污染。

公交车作为公共交通的重要组成部分，为市民出行提供了极大的便利，在人们生活中具有重要的意义。然而随着城市不断发展，公交车数量迅速增加，每到起步、加速、转弯或上坡时，这些柴油车免不了冒出黑烟，对环境造成了很大污染。同时新能源公交车成本高，买得起也修不起让很多公交公司望而却步。因此，公交车污染的治理迫在眉睫，而实时有效的公交尾气监控则是治理的第一步。在投资有限的情况下，如何将有限数量的检测器安装在路网中的合适道路上，以检测到尽可能多的公交车，是监测系统组建的一个核心问题。

发明内容

本发明技术解决问题：克服现有技术的不足，提供一种基于图论与布尔代数的机动车尾气遥测设备布点方法，以公交车尾气排放情况为监测目标，根据图论相关理论与布尔代数进行建模与求解，进而研究尾气遥测设备在城市交通路网中布设问题，以实现实时高效监测公交车尾气排放情况为目标。

本发明技术解决方案：在城市公交车尾气监测研究中，由于成本有限、机动车尾气遥感监测设备数量有限，研究目标是用尽可能少的设备监测尽可能多的公交车。因此，尾气遥测设备应布设在多条公交线路重合的路段上，且每条公交线路上至少有一个布设点，进而使监测范围覆盖城市所有公交路线。

基于以上分析，同时考虑到图论在描述处理离散数学系统方面有着强大功能，可以为任何一个包含了一种二元关系的系统提供一个形象而直观数学模型，本发明采用图论相关理论对道路建模，得到公交路线超图模型，在此基础上将尾气遥测设备的布点问题转化为公交车路线超图最小横贯的求解问题，再用布尔代数理论求出最小横贯集，即最小检测路段集合，也就是实际中需要布设尾气遥测设备的路段。

具体包括以下步骤：

(1)将公交车行驶路线抽象为公交路线超图模型。根据图论中超图的概念，以城市实际的交通道路网络为基础，将公交车行驶线路中经过的各路段抽象为超图顶点，将整条线路抽象为超边，得到公交路线超图。

(2)求公交路线超图的全部极小横贯。公交路线超图中每一个顶点都有布尔变量x_i与之对应，x_i表示路段i是否布设尾气遥感监测设备，若x_i＝1则表示此路段需要布设监测设备。首先对公交路线超图每条边中所有顶点进行布尔加法，得到表示第j条公交运行路线中包含的路段；然后对公交路线超图所有边进行布尔乘法，得到表示整个公交路线网中所有线路所含路段的全体；再将代入对展开化简，得到最简的多项式和的形式：Φ(H)＝σ₁+σ₂+…+σ_t+…，σ_t对应的顶点集是公交路线超图的一个极小横贯，Φ(H)表示与公交车每条运行路线都相交的路段全体。

(3)求公交路线超图的最小横贯。比较上一步所得的极小横贯的技术，即所含元素的个数，取基数最小的极小横贯为最小横贯，最小横贯中的元素所对应的路段即为需要布设尾气遥测设备的路段，进而得到了基于图论与布尔代数的机动车尾气遥测设备的布点方案。

本发明与现有技术相比的优点在于：

(1)本发明特别针对公交车设计尾气遥测设备布点方法，由于现在暂时没有以公交车为应用背景的布点方法的研究，故本发明填补了现有技术在该应用背景下的技术空白。

(2)本发明基于图论与布尔代数理论，将尾气遥测设备的布点问题转化为公交路线超图的最小横贯求解问题，再运用布尔运算的方法求出最小横贯即得到布点方案。算法简单，更易操作，具有很大的实践意义。

附图说明

图1为布点方法流程图；

图2为公交路线超图的极小横贯、最小横贯求解流程图。

具体实施方式

本发明提出的基于图论与布尔代数的机动车尾气遥测设备布点方法，以实时高效监测公交车尾气排放情况为目标，根据图论与布尔代数相关理论，进行数学建模与求解，进而研究机动车尾气遥测设备在城市交通路网中的布设问题。

如图1所示，本发明具体实施步骤如下：

(1)将公交车行驶路线抽象为公交路线超图。

图论中有如下超图的定义：

设V＝{v₁,v₂,…,v_n}是一个有限集，则V上的一个超图H＝{E₁,E₂,…,E_m}是指V上的一个有限子集簇，使得(1)E_i≠Φ(i＝1,2,…,m)(2)其中v_i为超图H的第i个顶点，V为顶点集合，E_i为超图H的第i个超边，Φ表示空集，H为超边集合，也就是超图。

结合城市交通路网，将公交车行驶线路中经过的各路段抽象为超图顶点，将整条线路抽象为超边，得到公交路线超图。

图论中超图横贯的定义为：

设H＝{E₁,E₂,…,E_m}是V上的一个超图，若顶点子集满足T∩E_i≠Φ(i＝1,2,…,m)，即T与H每条边都相交，则称T是超图H的一个横贯(集)。

如果一个横贯的任何一个真子集都不是横贯,则称这个横贯为极小横贯集。所有极小横贯集中基数最小的极小横贯集是最小横贯集。

基于以上横贯、极小横贯、最小横贯的定义，将公交线路抽象为超图模型后，尾气遥测设备的布点问题便转化为求公交路线超图的最小横贯集问题。

(2)求公交路线超图的极小横贯集。

在前两步的基础上，用布尔代数相关理论求公交路线超图的最小横贯。首先介绍布尔代数相关理论。

布尔变量的值只有0,1两种情况，用“+”和“·”表示布尔代数中的“布尔加法(逻辑或)”与“布尔乘法(逻辑与)”，也称为“析取”与“合取”，只含布尔加法的表达式称为析取式，只含布尔乘法的表达式称为合取式。

设a,b为布尔变量，布尔运算满足如下性质：

①交换律a+b＝b+a；a·b＝b·a

②结合律(a+b)+c＝a+(b+c)；(a·b)·c＝a·(b·c)

③分配率a·(b+c)＝(a·b)+(b·c)；a+(b·c)＝(a+b)·(a+c)

④幂等律a+a＝a；a·a＝a

⑤吸收率a·(a+b)＝a；a+(a·b)＝a

下面介绍求公交路线超图H所有极小横贯集的具体步骤：

设H＝{E₁,E₂,…,E_m}是顶点集V上的一个公交路线超图，由公交车行驶路线抽象而得。超图中顶点为超边为E_j(j＝1,2,...,m)。

本发明中用H表示公交路线超图，超图H的一个顶点v_i表示公交车线路中经过的一个路段；超图的一个超边E_j表示一条公交车运行线路。

①对每一个顶点v_i设布尔变量x_i与之对应，x_i表示路段i是否布设尾气遥感监测设备，若x_i＝1则表示此路段需要布设监测设备。

②对公交路线超图H的每一条边中的所有顶点v_ji进行布尔加法运算，得到每条边E_j对应的布尔析取式：表示第j条公交运行路线中包含的路段；

③对第②步得到的公交路线超图H中所有边的布尔析取式进行布尔乘法运算，得到整个公交路线超图H的布尔合取式：表示整个公交线路网中所有线路所含路段的全体；

④对先使用布尔分配律展开，再用结合律、交换律、幂等律进行化简，最终得到最简的析取式：Φ(H)＝σ₁+σ₂+…+σ_t+…，其中σ_t对应的顶点集是公交路线超图H的一个极小横贯集，所有σ_t构成公交路线超图H的所有极小横贯集，Φ(H)表示与公交车每条运行线路都相交的路段全体。

(3)求公交路线超图的最小横贯集。

比较横贯超图中所有极小横贯集的基数，基数最小的极小横贯集是最小横贯集，即最小监测路段集合，为实际中需要布设机动车尾气遥感监测设备的路段。

图2为公交路线超图极小横贯集、最小横贯集求解的流程图。首先，对公交路线超图中各顶点设布尔变量，变量值取0或1，取1时表示该顶点代表的路段要布设尾气检测设备；然后，对公交路线超图中每条边，根据该边所含的顶点进行布尔加法运算，得到对应于每条边的布尔析取式；接着将所有超边的布尔析取式进行布尔乘法运算，得到整个公交路线超图的布尔合取式；之后用布尔运算的性质对所得的合取式整理化简，得到最简的析取式，其中每个子式代表超图的一个极小横贯集；最后比较各个极小横贯集的基数，即所含元素的个数，取基数最小的极小横贯集为最小横贯集，最小横贯集中的元素所对应的路段即为需要布设尾气遥测设备的路段，进而得到了基于图论与布尔代数的机动车尾气遥测设备的布点方案。

总之，相比于已有的监测器布点方案，本发明专门针对城市公交系统，更具独特性，且求解算法简单易实现，操作性更强。

提供以上实施例仅仅是为了描述本发明的目的，而并非要限制本发明的范围。本发明的范围由所附权利要求限定。不脱离本发明的精神和原理而做出的各种等同替换和修改，均应涵盖在本发明的范围之内。