给定数量线圈的网络布局范文

《系统工程杂志》2014年第四期

1全网可测的基本线圈布局优化支撑树算法

交通的出行起点和终点统称形心点，而其他的节点则被称为非形心点或普通节点。假设网络中除了形心点外，不存在其他节点度为1或0的节点。为了更好的利用一般节点处的流量守恒条件，以及网络中总的出行产生量与吸引量之间的平衡关系，需对对一般交通网络进行转换。经转换的网络将只含一个虚拟的形心点。在构造只含一个虚拟形心点的网络时，如果在起点o处仅有向外发散的路段，那么将这些路段的起点转为新添加的虚拟形心点，但不改变路段的方向。然后将o从网络中删除。进一步来说，如果由该起点向外发散的路段数多于一条，为了附带获得该起点处的出行产生量，在把该起点转变为虚拟小区形心点之前，需要统计与其相关联路段上的流量。类似的方法也可以用于终点d，在此不再赘述。有时一个节点可能既是起点又是终点，因此在该节点处既有发散又有汇聚的路段。如果只有一条发散和一条汇聚路段，可以将这两条路段的端点与虚拟形心点相连；或者增加两条不同方向的路段来连接该节点与虚拟形心点。在只含有一个虚拟形心点的交通网络中，所有节点处都可以应用流量守恒方程。在只含有一个虚拟形心点的交通网络中，如果与某一节点相关联的路段中只有一条路段的流量未知，那么通过流量守恒条件可确定该未知流量。如果能依次在每个节点处应用流量守恒，一步一步获得各条路段上的流量信息，直至最后获取所有路段的流量信息，那么我们的全网路段流量观测问题即得以解决。可利用如下算法求解全网可测的线圈布局问题：step1：为只含有一个虚拟形心点的交通网络构建一个支撑树，将支撑树中所包含的路段标记为“不需要安装线圈的路段”，将其余的路段标记为“安装线圈的路段”。step2：搜索支撑树或该支撑树的余图，令S是度为1的节点的集合。执行如下操作：step2．1：如果S是空集，则算法终止；如果S不是空集，则需要进行如下步骤：从S中任意选取一个节点v，在节点v处，应用流量守恒计算出属于该支撑树并与节点v相关联路段的流量或支撑树的余图中流量未知路段的流量。step2．2：从集合S和支撑树（或支撑树的余图）中同时删除节点v．并从支撑树（或支撑树的余图）中删除连接节点v与支撑树（或支撑树的余图）的路段。如果此时集合S不是空集，返回step2．1；否则，再次搜索支撑树（或支撑树的余图）找到一个新的集合S，然后进入step2．1。由于利用了网络的支撑树，因此我们称上述算法为全网可测的支撑树算法。引理1如果图G是一个连通图，C是图G中的任意一个回路，删除C中的一条路段，图G仍是连通的［14］。定理1每一个连通图都有支撑树。证明设图G是连通图，如果G不含回路，那么G本身是一个树，从而G是它自身的一个支撑树；如果G含回路，任取一个回路C1．通过引理1可知从C1中任意去掉一条边，得到图G的子图是连通的，如果这个子图中不存在回路，那么其就是支撑树；如果这个子图中仍存在回路，那么至少存在一个回路C2，从C2中任意去掉一条边，得到图G的子图仍是连通的。重复上述步骤，直到最后得到的子图T中不含回路。因为在这一过程中并没有删除图G的节点，所以T包含了G的每一个节点。因此T是G的一个支撑树。定理2存在一个安装线圈数量最少的路段集合，基于该集合中的路段检测流量可推测出网络全部路段的流量，但是该路段集合并不唯一。证明由定理1可知，只含一个虚拟形心点的交通网络是连通的，因此该网络有支撑树。根据支撑树算法，支撑树的余图中所包含的路段就构成了安装线圈的路段集合（路段数最少），由此存在性得证。从只含一个虚拟形心点的交通网络的构建过程可知必然存在一条由连接原始网络的一OD对的一条路径（路段的起讫点可能变为了虚拟形心点）和可能新增的虚拟路段（与上述路径相连）构成的回路。由定理1的证明可知，在回路中选择不同的路段进行删除，从而可以得到不同的支撑树，由此解的多样性得证。定理3在只含有一个虚拟形心点的交通网络中，分别用m和n表示路网中的路段数和节点数。在满足可推测出全部路段流量的条件下，路网中需要安装线圈的路段数最少为m－n＋1条，不需要安装线圈的路段数最多为n－1条。证明给定正整数i，任意一个含有i个节点的树都包含i－1条路段［14］。由于支撑树包含了经改造后交通网络中的所有节点，并且有n－1条路段。如果增加任意一条路段到支撑树中，则至少形成一个回路。如果将回路中所有路段的流量都增加或减少一定量，那么在所有节点处流量守恒条件依然成立。但是这将使得一部分路段的流量无法被推断出来的。因此不需要安装线圈的路段数最多为n－1条。又因为该交通网络中有m条路段，因此在能够推断出全部路段流量的前提下，需要安装线圈的路段数最少为m－n＋1条。

2给定数量线圈的布局优化分析

定理4对于图中任何一个由度大于或等于2的节点组成的连通子图（回路），其路段流量是无法确定的。证明将连通子图分成两类：第一类是由度等于2的节点构成；第二类是由度大于或等于2的节点构成，并且至少有一个节点的度大于2。假设C是任意一个属于第一类且至少含有2个节点的子图，考虑下面的算法：step1：从C中选择一条路段e，令v和v″是e的两个端点。step2：当v和v″不相同时，重复步骤2a，2b，2c．step2a：选择与v相关联的路段e′，并且e≠e′．step2b：令v′是路段e′的另一个端点。step2c：令e＝e′，v＝v′．该算法最终一定会终止，因为子图C是连通的并且节点的个数是有限的。当算法终止时，包含了C中所有节点的一个回路就出现了。事实上这个回路就是C本身。如果回路C中每条路段的流量均增加或减少一定量，由于流量守恒在所有节点处仍然成立，因此第一类子图的路段流量都是无法确定的。对于第二类子图，当利用节点流量守恒条件时，易知未知数数目大于方程数目，因此根据线性方程理论可知问题的解不唯一。这里方程数对应节点数目，未知数对应网络的路段数目。交通网络中对于给定数量的线圈的布局优化问题，其实质在于通过所安装的线圈能够推断出更多路段的流量。影响线圈布局的因素主要有两个：（1）给定线圈的数量；（2）线圈布局的拓扑特性。考虑上述两个因素，在交通网络G中，对于给定t个线圈的布局优化问题给出如下算法：step1：应用上节给出的支撑树算法，构造G的支撑树T．用H和W分别表示T和T的余图中路段的集合；用C表示T的子图中能够构成回路的路段集合。如果t≥m－n＋1，则转至step2；否则，转至step3。step2：在T中，选择任意的t＋n－m－1条路段，在其上安装线圈，然后将安装了线圈的路段从支撑树中删除，转至step5。step3：令Temp为图G的一个子图并且与T相同。用Htemp和Vtemp分别表示图Temp中路段和节点的集合，表示一个空的路段集合，图G中所有路段的权都分配为0。令Mtemp＝2｜Htemp｜，并且S∶＝（定义｜S｜为集合S的基数）。当Htemp≠时，反复执行如下步骤：step3a：仅考虑Temp中的路段并计算其节点度，将Temp中度为1的节点添加到集合S中。step3b：对于任意一个节点v∈S，都会存在一条连接节点v与Temp的余图的路段e，并将e的权设为Mtemp．step3c：令Mtemp∶＝Mtemp－2｜S｜。从Vtemp中删除集合S中的所有节点，并且从Htemp中删除连接集合S中节点与图Temp的所有路段。然后更新图Temp，令S∶＝．step4：反复执行下述步骤m－n－t＋1次：step4a：从W中选择一条路段e与从W中选择的其他路段进行比较，将e添加到T中，在此过程中会得到权最小的C．step4b：将e从W中删除，并添加到T中，更新C．Step5：除了最终得到的图T中包含的路段，其余的路段就构成了安装给定的t个线圈的路段集合，也就是对于给定t个线圈的优化布局。需要特别指出的是一个连通图能构建出多个支撑树。算法中用到的支撑树只是众多支撑树中的一个，因此线圈的优化布局也会多种方案。然而至今还没有有效的方法能够将一个图的支撑树全部都列举出来。例如一个含有l个节点的完全图，就能构建出ll－2个支撑树。因此，现实有效的方法就是将算法应用于不同的支撑树，综合比较产生的结果，进而选择一个最佳的线圈布局方案。根据定理3，如果t≥m－n＋1，则可以推断出交通网络中所有路段的流量；如果t＜m－n＋1，受到线圈数量的限制，部分路段的流量是无法推断出来的。由定理4的证明可知，如果一条路段处于回路中，那么其流量也是无法推断出来的。在使用支撑树算法时，可采取向支撑树中添加路段序列的方法来计算未安装线圈路段上的流量。当一条路段处于回路中时，该路段会阻碍接下来的路段流量推断，因此应该先计算出其流量。这就是为什么要使最终C的权重最小，并且当形成回路不可避免时，应尽量使新添路段处于已有回路或与已有回路中的路段形成新的回路。

3算例分析

图1所示交通网络中包含了4个形心点、30条路段和15个节点。节点1和2是出行起点，节点14和15是出行终点。图2中经转换后的网络仅含有一个标记为16的虚拟形心点，30条路段和12个节点。对于基本的NSLP问题，由于利用支撑树算法可以得到不同的安装策略。由路段1、4、7、10、11、14、15、19、23、24、30构成图2中网络的一个支撑树；路段3、8、9、13、18、19、22、24、26、28、29形成另一支撑树。上述任一支撑树包涵的路段均可作为不需要安装线圈的路段集合完成全网流量的检测。在图2所示的网络中，对于给定的16个线圈进行优化布局。根据定理3，为了能够推断出全部路段的流量，安装线圈的路段数最少应为：30－12＋1＝19条。很显然这个数字比16大，因此该网络中有部分路段的流量是无法推断出来的。利用第2节提出的算法，首先构建包含路段1、2、6、10、13、15、15、19、22、24、27的支撑树，然后添加路段序列5、7、8或3、4、5到以上不需要安装线圈的路段集合中，最后路段1、2、5、6、7、8、10、13、14、15、19、22、24、27（或1、3、3、4、5、6、10、13、14、15、19、22、24、27）构成了不需要安装线圈的路段集合。棋中1、2、3、4、5（或2、5、6、7、8）五条路段的流量是无法推断出来的。但是如果构建一个包含路段1、5、6、10、13、16、19、21、22、26、27的支撑树，并且添加路段序列17、20、23到以上路段集合中，最终会有16、17、20、21、22、23共六条路段的流量无法推出。比较以上构建不同支撑树而得到的结果，很显然第一种基础支撑树的选择优于第二种。

作者：何胜学潘红向乐佳王芳单位：上海理工大学管理学院