本站小編為你精心準備了給定數量線圈的網絡布局參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《系統工程雜志》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共六條路段的流量無法推出。比較以上構建不同支撐樹而得到的結果，很顯然第一種基礎支撐樹的選擇優于第二種。

作者：何勝學潘紅向樂佳王芳單位：上海理工大學管理學院