給定數(shù)量線圈的網(wǎng)絡(luò)布局范文
本站小編為你精心準(zhǔn)備了給定數(shù)量線圈的網(wǎng)絡(luò)布局參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。
《系統(tǒng)工程雜志》2014年第四期
1全網(wǎng)可測的基本線圈布局優(yōu)化支撐樹算法
交通的出行起點(diǎn)和終點(diǎn)統(tǒng)稱形心點(diǎn)，而其他的節(jié)點(diǎn)則被稱為非形心點(diǎn)或普通節(jié)點(diǎn)。假設(shè)網(wǎng)絡(luò)中除了形心點(diǎn)外，不存在其他節(jié)點(diǎn)度為1或0的節(jié)點(diǎn)。為了更好的利用一般節(jié)點(diǎn)處的流量守恒條件，以及網(wǎng)絡(luò)中總的出行產(chǎn)生量與吸引量之間的平衡關(guān)系，需對對一般交通網(wǎng)絡(luò)進(jìn)行轉(zhuǎn)換。經(jīng)轉(zhuǎn)換的網(wǎng)絡(luò)將只含一個虛擬的形心點(diǎn)。在構(gòu)造只含一個虛擬形心點(diǎn)的網(wǎng)絡(luò)時，如果在起點(diǎn)o處僅有向外發(fā)散的路段，那么將這些路段的起點(diǎn)轉(zhuǎn)為新添加的虛擬形心點(diǎn)，但不改變路段的方向。然后將o從網(wǎng)絡(luò)中刪除。進(jìn)一步來說，如果由該起點(diǎn)向外發(fā)散的路段數(shù)多于一條，為了附帶獲得該起點(diǎn)處的出行產(chǎn)生量，在把該起點(diǎn)轉(zhuǎn)變?yōu)樘摂M小區(qū)形心點(diǎn)之前，需要統(tǒng)計與其相關(guān)聯(lián)路段上的流量。類似的方法也可以用于終點(diǎn)d，在此不再贅述。有時一個節(jié)點(diǎn)可能既是起點(diǎn)又是終點(diǎn)，因此在該節(jié)點(diǎn)處既有發(fā)散又有匯聚的路段。如果只有一條發(fā)散和一條匯聚路段，可以將這兩條路段的端點(diǎn)與虛擬形心點(diǎn)相連；或者增加兩條不同方向的路段來連接該節(jié)點(diǎn)與虛擬形心點(diǎn)。在只含有一個虛擬形心點(diǎn)的交通網(wǎng)絡(luò)中，所有節(jié)點(diǎn)處都可以應(yīng)用流量守恒方程。在只含有一個虛擬形心點(diǎn)的交通網(wǎng)絡(luò)中，如果與某一節(jié)點(diǎn)相關(guān)聯(lián)的路段中只有一條路段的流量未知，那么通過流量守恒條件可確定該未知流量。如果能依次在每個節(jié)點(diǎn)處應(yīng)用流量守恒，一步一步獲得各條路段上的流量信息，直至最后獲取所有路段的流量信息，那么我們的全網(wǎng)路段流量觀測問題即得以解決。可利用如下算法求解全網(wǎng)可測的線圈布局問題：step1：為只含有一個虛擬形心點(diǎn)的交通網(wǎng)絡(luò)構(gòu)建一個支撐樹，將支撐樹中所包含的路段標(biāo)記為“不需要安裝線圈的路段”，將其余的路段標(biāo)記為“安裝線圈的路段”。step2：搜索支撐樹或該支撐樹的余圖，令S是度為1的節(jié)點(diǎn)的集合。執(zhí)行如下操作：step2．1：如果S是空集，則算法終止；如果S不是空集，則需要進(jìn)行如下步驟：從S中任意選取一個節(jié)點(diǎn)v，在節(jié)點(diǎn)v處，應(yīng)用流量守恒計算出屬于該支撐樹并與節(jié)點(diǎn)v相關(guān)聯(lián)路段的流量或支撐樹的余圖中流量未知路段的流量。step2．2：從集合S和支撐樹（或支撐樹的余圖）中同時刪除節(jié)點(diǎn)v．并從支撐樹（或支撐樹的余圖）中刪除連接節(jié)點(diǎn)v與支撐樹（或支撐樹的余圖）的路段。如果此時集合S不是空集，返回step2．1；否則，再次搜索支撐樹（或支撐樹的余圖）找到一個新的集合S，然后進(jìn)入step2．1。由于利用了網(wǎng)絡(luò)的支撐樹，因此我們稱上述算法為全網(wǎng)可測的支撐樹算法。引理1如果圖G是一個連通圖，C是圖G中的任意一個回路，刪除C中的一條路段，圖G仍是連通的［14］。定理1每一個連通圖都有支撐樹。證明設(shè)圖G是連通圖，如果G不含回路，那么G本身是一個樹，從而G是它自身的一個支撐樹；如果G含回路，任取一個回路C1．通過引理1可知從C1中任意去掉一條邊，得到圖G的子圖是連通的，如果這個子圖中不存在回路，那么其就是支撐樹；如果這個子圖中仍存在回路，那么至少存在一個回路C2，從C2中任意去掉一條邊，得到圖G的子圖仍是連通的。重復(fù)上述步驟，直到最后得到的子圖T中不含回路。因?yàn)樵谶@一過程中并沒有刪除圖G的節(jié)點(diǎn)，所以T包含了G的每一個節(jié)點(diǎn)。因此T是G的一個支撐樹。定理2存在一個安裝線圈數(shù)量最少的路段集合，基于該集合中的路段檢測流量可推測出網(wǎng)絡(luò)全部路段的流量，但是該路段集合并不唯一。證明由定理1可知，只含一個虛擬形心點(diǎn)的交通網(wǎng)絡(luò)是連通的，因此該網(wǎng)絡(luò)有支撐樹。根據(jù)支撐樹算法，支撐樹的余圖中所包含的路段就構(gòu)成了安裝線圈的路段集合（路段數(shù)最少），由此存在性得證。從只含一個虛擬形心點(diǎn)的交通網(wǎng)絡(luò)的構(gòu)建過程可知必然存在一條由連接原始網(wǎng)絡(luò)的一OD對的一條路徑（路段的起訖點(diǎn)可能變?yōu)榱颂摂M形心點(diǎn)）和可能新增的虛擬路段（與上述路徑相連）構(gòu)成的回路。由定理1的證明可知，在回路中選擇不同的路段進(jìn)行刪除，從而可以得到不同的支撐樹，由此解的多樣性得證。定理3在只含有一個虛擬形心點(diǎn)的交通網(wǎng)絡(luò)中，分別用m和n表示路網(wǎng)中的路段數(shù)和節(jié)點(diǎn)數(shù)。在滿足可推測出全部路段流量的條件下，路網(wǎng)中需要安裝線圈的路段數(shù)最少為m－n＋1條，不需要安裝線圈的路段數(shù)最多為n－1條。證明給定正整數(shù)i，任意一個含有i個節(jié)點(diǎn)的樹都包含i－1條路段［14］。由于支撐樹包含了經(jīng)改造后交通網(wǎng)絡(luò)中的所有節(jié)點(diǎn)，并且有n－1條路段。如果增加任意一條路段到支撐樹中，則至少形成一個回路。如果將回路中所有路段的流量都增加或減少一定量，那么在所有節(jié)點(diǎn)處流量守恒條件依然成立。但是這將使得一部分路段的流量無法被推斷出來的。因此不需要安裝線圈的路段數(shù)最多為n－1條。又因?yàn)樵摻煌ňW(wǎng)絡(luò)中有m條路段，因此在能夠推斷出全部路段流量的前提下，需要安裝線圈的路段數(shù)最少為m－n＋1條。
定理4對于圖中任何一個由度大于或等于2的節(jié)點(diǎn)組成的連通子圖（回路），其路段流量是無法確定的。證明將連通子圖分成兩類：第一類是由度等于2的節(jié)點(diǎn)構(gòu)成；第二類是由度大于或等于2的節(jié)點(diǎn)構(gòu)成，并且至少有一個節(jié)點(diǎn)的度大于2。假設(shè)C是任意一個屬于第一類且至少含有2個節(jié)點(diǎn)的子圖，考慮下面的算法：step1：從C中選擇一條路段e，令v和v″是e的兩個端點(diǎn)。step2：當(dāng)v和v″不相同時，重復(fù)步驟2a，2b，2c．step2a：選擇與v相關(guān)聯(lián)的路段e′，并且e≠e′．step2b：令v′是路段e′的另一個端點(diǎn)。step2c：令e＝e′，v＝v′．該算法最終一定會終止，因?yàn)樽訄DC是連通的并且節(jié)點(diǎn)的個數(shù)是有限的。當(dāng)算法終止時，包含了C中所有節(jié)點(diǎn)的一個回路就出現(xiàn)了。事實(shí)上這個回路就是C本身。如果回路C中每條路段的流量均增加或減少一定量，由于流量守恒在所有節(jié)點(diǎn)處仍然成立，因此第一類子圖的路段流量都是無法確定的。對于第二類子圖，當(dāng)利用節(jié)點(diǎn)流量守恒條件時，易知未知數(shù)數(shù)目大于方程數(shù)目，因此根據(jù)線性方程理論可知問題的解不唯一。這里方程數(shù)對應(yīng)節(jié)點(diǎn)數(shù)目，未知數(shù)對應(yīng)網(wǎng)絡(luò)的路段數(shù)目。交通網(wǎng)絡(luò)中對于給定數(shù)量的線圈的布局優(yōu)化問題，其實(shí)質(zhì)在于通過所安裝的線圈能夠推斷出更多路段的流量。影響線圈布局的因素主要有兩個：（1）給定線圈的數(shù)量；（2）線圈布局的拓?fù)涮匦浴？紤]上述兩個因素，在交通網(wǎng)絡(luò)G中，對于給定t個線圈的布局優(yōu)化問題給出如下算法：step1：應(yīng)用上節(jié)給出的支撐樹算法，構(gòu)造G的支撐樹T．用H和W分別表示T和T的余圖中路段的集合；用C表示T的子圖中能夠構(gòu)成回路的路段集合。如果t≥m－n＋1，則轉(zhuǎn)至step2；否則，轉(zhuǎn)至step3。step2：在T中，選擇任意的t＋n－m－1條路段，在其上安裝線圈，然后將安裝了線圈的路段從支撐樹中刪除，轉(zhuǎn)至step5。step3：令Temp為圖G的一個子圖并且與T相同。用Htemp和Vtemp分別表示圖Temp中路段和節(jié)點(diǎn)的集合，表示一個空的路段集合，圖G中所有路段的權(quán)都分配為0。令Mtemp＝2｜Htemp｜，并且S∶＝（定義｜S｜為集合S的基數(shù)）。當(dāng)Htemp≠時，反復(fù)執(zhí)行如下步驟：step3a：僅考慮Temp中的路段并計算其節(jié)點(diǎn)度，將Temp中度為1的節(jié)點(diǎn)添加到集合S中。step3b：對于任意一個節(jié)點(diǎn)v∈S，都會存在一條連接節(jié)點(diǎn)v與Temp的余圖的路段e，并將e的權(quán)設(shè)為Mtemp．step3c：令Mtemp∶＝Mtemp－2｜S｜。從Vtemp中刪除集合S中的所有節(jié)點(diǎn)，并且從Htemp中刪除連接集合S中節(jié)點(diǎn)與圖Temp的所有路段。然后更新圖Temp，令S∶＝．step4：反復(fù)執(zhí)行下述步驟m－n－t＋1次：step4a：從W中選擇一條路段e與從W中選擇的其他路段進(jìn)行比較，將e添加到T中，在此過程中會得到權(quán)最小的C．step4b：將e從W中刪除，并添加到T中，更新C．Step5：除了最終得到的圖T中包含的路段，其余的路段就構(gòu)成了安裝給定的t個線圈的路段集合，也就是對于給定t個線圈的優(yōu)化布局。需要特別指出的是一個連通圖能構(gòu)建出多個支撐樹。算法中用到的支撐樹只是眾多支撐樹中的一個，因此線圈的優(yōu)化布局也會多種方案。然而至今還沒有有效的方法能夠?qū)⒁粋€圖的支撐樹全部都列舉出來。例如一個含有l(wèi)個節(jié)點(diǎn)的完全圖，就能構(gòu)建出ll－2個支撐樹。因此，現(xiàn)實(shí)有效的方法就是將算法應(yīng)用于不同的支撐樹，綜合比較產(chǎn)生的結(jié)果，進(jìn)而選擇一個最佳的線圈布局方案。根據(jù)定理3，如果t≥m－n＋1，則可以推斷出交通網(wǎng)絡(luò)中所有路段的流量；如果t＜m－n＋1，受到線圈數(shù)量的限制，部分路段的流量是無法推斷出來的。由定理4的證明可知，如果一條路段處于回路中，那么其流量也是無法推斷出來的。在使用支撐樹算法時，可采取向支撐樹中添加路段序列的方法來計算未安裝線圈路段上的流量。當(dāng)一條路段處于回路中時，該路段會阻礙接下來的路段流量推斷，因此應(yīng)該先計算出其流量。這就是為什么要使最終C的權(quán)重最小，并且當(dāng)形成回路不可避免時，應(yīng)盡量使新添路段處于已有回路或與已有回路中的路段形成新的回路。
3算例分析
圖1所示交通網(wǎng)絡(luò)中包含了4個形心點(diǎn)、30條路段和15個節(jié)點(diǎn)。節(jié)點(diǎn)1和2是出行起點(diǎn)，節(jié)點(diǎn)14和15是出行終點(diǎn)。圖2中經(jīng)轉(zhuǎn)換后的網(wǎng)絡(luò)僅含有一個標(biāo)記為16的虛擬形心點(diǎn)，30條路段和12個節(jié)點(diǎn)。對于基本的NSLP問題，由于利用支撐樹算法可以得到不同的安裝策略。由路段1、4、7、10、11、14、15、19、23、24、30構(gòu)成圖2中網(wǎng)絡(luò)的一個支撐樹；路段3、8、9、13、18、19、22、24、26、28、29形成另一支撐樹。上述任一支撐樹包涵的路段均可作為不需要安裝線圈的路段集合完成全網(wǎng)流量的檢測。在圖2所示的網(wǎng)絡(luò)中，對于給定的16個線圈進(jìn)行優(yōu)化布局。根據(jù)定理3，為了能夠推斷出全部路段的流量，安裝線圈的路段數(shù)最少應(yīng)為：30－12＋1＝19條。很顯然這個數(shù)字比16大，因此該網(wǎng)絡(luò)中有部分路段的流量是無法推斷出來的。利用第2節(jié)提出的算法，首先構(gòu)建包含路段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）構(gòu)成了不需要安裝線圈的路段集合。棋中1、2、3、4、5（或2、5、6、7、8）五條路段的流量是無法推斷出來的。但是如果構(gòu)建一個包含路段1、5、6、10、13、16、19、21、22、26、27的支撐樹，并且添加路段序列17、20、23到以上路段集合中，最終會有16、17、20、21、22、23共六條路段的流量無法推出。比較以上構(gòu)建不同支撐樹而得到的結(jié)果，很顯然第一種基礎(chǔ)支撐樹的選擇優(yōu)于第二種。
作者：何勝學(xué)潘紅向樂佳王芳單位：上海理工大學(xué)管理學(xué)院