最小生成樹在城市地下管網(wǎng)優(yōu)化中的應(yīng)用

朱恒其 張 穎 王華雨

（泰州職業(yè)技術(shù)學(xué)院，江蘇 泰州225300）

由于城市化進(jìn)程的進(jìn)一步加快，人口的快速增長(zhǎng)，城市對(duì)電力電纜、通信電纜、給水排水管線、燃?xì)夤芾淼染S持城市“生命力”的各種市政管線的需求量日益劇增。 因此，各管線承建單位為了滿足發(fā)展現(xiàn)狀或未來的需求，需要挖掘城市道路來鋪設(shè)、更新和維修管線，經(jīng)常剛鋪好的道路，很快會(huì)被其它管理單位開挖施工，如此反復(fù)，讓人恨不得在馬路上安條“拉鏈”。

為解決這樣的問題，我市市政出臺(tái)了若干新規(guī)，并開始了地下管廊的建設(shè)研究工作。 地下管廊一般設(shè)置在地下，將各類公用管線集中容納于一體，并留有供檢修人員行走通道的隧道。 地下管廊設(shè)有專門的檢修口、吊裝口和監(jiān)測(cè)系統(tǒng)，實(shí)施統(tǒng)一規(guī)劃、設(shè)計(jì)、建設(shè)和管理，徹底改變以往各自建設(shè)、各自管理的零亂局面。 而且避免了酸堿物質(zhì)的腐蝕，延長(zhǎng)了管線的使用壽命。 但地下管廊的開發(fā)初期需要投入的費(fèi)用較大,為緩解財(cái)政壓力,可以利用圖論理論求出城區(qū)主干線的最小生成樹，使總修建長(zhǎng)度之和最小。

1 圖論模型的建立

設(shè)賦權(quán)連通無向圖G(V,E)是城市道路構(gòu)成的網(wǎng)絡(luò)圖，其中，V 表示圖中所有的頂點(diǎn)集(vi)，E 表示由城市道路構(gòu)成的弧集，道路的長(zhǎng)度用邊權(quán)d(vivj)表示，如圖1 所示。

圖1

2 模型的求解

求最小生成樹的方法常用的算法主要有Prim 和Kruskal 算法，這里我們選用Prim 算法。

令P={vi},Q={}， 分別用于存放G 的最小生成樹中的頂點(diǎn)和邊。Prim 算法的的思想是：從所有p∈P，v∈V-P 的邊中，選取具有最小權(quán)值的邊pv，將頂點(diǎn)v 加入集合P 中，將邊加入集合Q 中，如此不斷重得，直到P=V，最小生成樹構(gòu)造完畢。 具體程序如下：

clc;clear;

a=zeros(24);

a(1,2)=5.9;a(1,3)=0.8;a(2,6)=1.3;……;a(23,24)=2;

a=a+a';a(find(a==0))=inf;

result=[];p=1;tb=2:length(a);

while length(result)～=length(a)-1

temp=a(p,tb);temp=temp(:);

d=min(temp);

[jb,kb]=find(a(p,tb)==d);

j=p(jb(1));k=tb(kb(1));

result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];

end

Result

程序運(yùn)行后，即可求得最小生成樹，如圖2。

圖2

3 模型評(píng)價(jià)

該模型結(jié)合實(shí)際給出了城市主干線上的最小生成樹，為城市修建地下管廊提供方案。 若考慮不同道路適宜修建不同類型管廊，即不同道路的修建成本不同時(shí)，可通過改變相應(yīng)的邊權(quán)值，重新由Prim 算法得出最小生成樹。

［1］郭培俊，毛海舟.高職數(shù)學(xué)建模[M].浙江：浙江大學(xué)出版社，2010，12.

［2］司守奎.數(shù)學(xué)建模算法與應(yīng)用[M].國(guó)防工業(yè)出版社，2011，08.