許自昌

（1. 中國(guó)地質(zhì)大學(xué)（武漢）資源學(xué)院，武漢430074；2. 福建省地質(zhì)測(cè)繪院遙感中心，福州 350011）

·農(nóng)業(yè)水土工程·

基于最小生成樹(shù)的渠道系統(tǒng)優(yōu)化布局模型

許自昌

（1. 中國(guó)地質(zhì)大學(xué)（武漢）資源學(xué)院，武漢430074；2. 福建省地質(zhì)測(cè)繪院遙感中心，福州 350011）

針對(duì)平原地區(qū)農(nóng)田灌溉渠道優(yōu)化布局問(wèn)題，當(dāng)前普遍采用渠道布局原則進(jìn)行布局，但其不能取得成本最優(yōu)的布局。通過(guò)簡(jiǎn)化平原地區(qū)農(nóng)田灌溉渠道優(yōu)化布局問(wèn)題，該文構(gòu)建了基于最小生成樹(shù)的渠道優(yōu)化布局模型。與傳統(tǒng)最小生成樹(shù)模型不同的是該模型涵蓋了2級(jí)渠道的優(yōu)化布局問(wèn)題，而且該模型得到的方案要大于等于1棵最小生成樹(shù)。為了能利用成熟的最小生產(chǎn)樹(shù)理論的求解方法，該文通過(guò)創(chuàng)建虛擬點(diǎn)概念去除渠道優(yōu)化布局模型和傳統(tǒng)最小生成樹(shù)模型的區(qū)別，運(yùn)用凸殼理論討論求解該模型的 4種情況，編寫(xiě)求解該模型的LINGO程序，然后將基于最小生成樹(shù)的渠道優(yōu)化布局模型用于案例，得到了研究區(qū)渠道布局方案。該方案的工程量是16 095 m3，而采用渠道布局原則得到的渠道布局方案的工程量是16 938.25 m3。結(jié)果表明基于最小生成樹(shù)的渠道優(yōu)化布局模型能得到成本更少的渠道布局方案，即最大程度地控制土地整治費(fèi)用。研究為控制土地整治項(xiàng)目的費(fèi)用提供了一條有效途徑。

渠道;優(yōu)化系統(tǒng)；土地復(fù)墾；布局；最小生成樹(shù)模型；凸殼理論；LINGO

0 引 言

現(xiàn)有的土地復(fù)墾工程研究主要集中在土方工程、GIS技術(shù)應(yīng)用方面[1-6]，現(xiàn)有研究成果能提供精確的定量模型，進(jìn)行復(fù)墾工程的土方計(jì)算，但是關(guān)注溝渠布局的研究很少，特別是建立定量模型進(jìn)行溝渠優(yōu)化布局的研究更少[7-12]。溝渠工程費(fèi)用占土地復(fù)墾工程費(fèi)用比例較大，因此有必要進(jìn)行相關(guān)研究，為溝渠優(yōu)化布局提供依據(jù)，從而節(jié)約工程費(fèi)用。在灌溉與排水工程設(shè)計(jì)規(guī)程和農(nóng)田水利學(xué)等專業(yè)書(shū)籍或期刊里，有部分關(guān)于溝渠路的布局模式及布局原則的描述[12-18]，也有一些簡(jiǎn)單的布局模型對(duì)農(nóng)田的灌溉系統(tǒng)進(jìn)行優(yōu)化。僅依靠這樣的定性說(shuō)明進(jìn)行布局，得不到成本最優(yōu)的布局方案[19-22]。該文選擇平原地區(qū)的采煤塌陷地作為研究區(qū)域，通過(guò)構(gòu)建定量的數(shù)學(xué)模型，尋找成本最優(yōu)的布局方案，以期為土地整理項(xiàng)目渠道優(yōu)化布局提供依據(jù)。

1 溝渠優(yōu)化布局總體思路

在平原地區(qū)，田地受地形條件限制較少，各田塊比較規(guī)整，而且根據(jù)土地開(kāi)發(fā)整理項(xiàng)目規(guī)劃設(shè)計(jì)規(guī)范，劃分田塊的長(zhǎng)邊和短邊都必須在一定范圍內(nèi)，不會(huì)相差很多，因此平原地區(qū)的田塊近似于矩形，田塊與田塊的拓?fù)潢P(guān)系近似于圖1。

圖1 土地整治灌溉渠道布局示意圖Fig.1 Diagram of irrigation canals layout for land consolidation

圖1中農(nóng)渠1將田塊1、2、3連接在一起，并負(fù)責(zé)這些田塊的灌溉任務(wù)，其長(zhǎng)度等于田塊2、3的短邊之和，由于各田塊規(guī)格相同，即其長(zhǎng)、寬均相等，因此滿足田塊1、2、3的灌溉渠道的長(zhǎng)度等于3個(gè)田塊重心之間的距離。以此類推，在一定范圍內(nèi)的農(nóng)田布局渠道，可以簡(jiǎn)化為將該范圍內(nèi)的田塊重心連接起來(lái)。因此，灌溉渠道優(yōu)化布局問(wèn)題可轉(zhuǎn)化為網(wǎng)絡(luò)優(yōu)化問(wèn)題。此處的網(wǎng)絡(luò)是指運(yùn)籌學(xué)中定義的網(wǎng)絡(luò)，又稱為圖，是由一系列節(jié)點(diǎn)和一系列連接點(diǎn)的線組成。

渠道優(yōu)化布局問(wèn)題可以近似描述為尋找一系列重心點(diǎn)之間的1個(gè)弧集合，這些弧把所有的重心點(diǎn)連接起來(lái)，并且這些弧的長(zhǎng)度之和最小[23-27]。這跟最小生成樹(shù)的定義類似，所以土地整治渠道優(yōu)化布局問(wèn)題可以抽象為1個(gè)近似最小生成樹(shù)問(wèn)題。該模型與傳統(tǒng)的最小生成樹(shù)模型有以下區(qū)別：1）體現(xiàn)在渠道優(yōu)化布局模型要解決的是2級(jí)渠道的最優(yōu)化布局問(wèn)題，并且這2級(jí)渠道的成本是不一樣的，但是最小生成樹(shù)模型中連接節(jié)點(diǎn)的弧具有單位長(zhǎng)度同質(zhì)的前提假設(shè)，也就是說(shuō)，如果用現(xiàn)有的最小生成樹(shù)模型處理渠道最優(yōu)化布局問(wèn)題只能解決 1 級(jí)渠道的最優(yōu)化布局問(wèn)題。因此，很多文獻(xiàn)中的解決方法是先按一定原則確定上一級(jí)渠道的走向，然后再運(yùn)用最小生成樹(shù)模型確定下一級(jí)渠道的最優(yōu)布局，這種方法的局限是求得的是局部?jī)?yōu)化布局方案；2）研究區(qū)的渠道系統(tǒng)并不一定是1棵最小生成樹(shù)，有可能是2棵或者是3棵。

為能運(yùn)用最小生成樹(shù)模型描述土地整治渠道優(yōu)化布局模型，需做如下假設(shè)：1）2組0-1型變量。最小生成樹(shù)的數(shù)學(xué)模型是用0-1型變量表示連接節(jié)點(diǎn)的弧，現(xiàn)有最小生成樹(shù)的數(shù)學(xué)模型只用1組0-1型變量來(lái)表示連接節(jié)點(diǎn)的弧。但是渠道優(yōu)化布局模型要處理 2 級(jí)不同的渠道的優(yōu)化布局問(wèn)題，因此需要2組0-1型變量來(lái)表示連接田塊重心點(diǎn)的渠道，其中一組表示斗渠，另一組表示農(nóng)渠；2）虛擬點(diǎn)假設(shè)。根據(jù)研究區(qū)內(nèi)或周圍支渠或支渠以上水源分布情況和研究區(qū)平整后的坡度，可以確定其中幾個(gè)田塊作為渠道起始點(diǎn)。因此土地整治研究區(qū)灌溉渠道布局方案實(shí)際上不是1棵最小生成樹(shù)，而是幾棵最小生成樹(shù)。為了能運(yùn)用最小生成樹(shù)模型需要假設(shè) 1 個(gè)虛擬點(diǎn)，該點(diǎn)到確定的渠道起始點(diǎn)的距離無(wú)限小，但是到其他重心點(diǎn)的距離卻無(wú)限大；3）可能取水點(diǎn)假設(shè)。根據(jù)研究區(qū)內(nèi)或周圍支渠或支渠以上水源分布情況和研究區(qū)平整后的坡度選出來(lái)的、作為研究區(qū)渠道根節(jié)點(diǎn)的重心點(diǎn)，稱為可能取水點(diǎn)。研究區(qū)只有可能取水點(diǎn)可以和虛擬點(diǎn)連接。

為簡(jiǎn)化問(wèn)題，需定義：1）折算比例。因?yàn)槎非c農(nóng)渠的建造成本不一樣，所以需要根據(jù)折算比例，將建造成本統(tǒng)一折算到農(nóng)渠；2）渠道長(zhǎng)度約束。根據(jù)土地開(kāi)發(fā)整理項(xiàng)目規(guī)劃設(shè)計(jì)規(guī)范，斗渠和農(nóng)渠的長(zhǎng)度都有 1 個(gè)上限；3）渠道分支約束。不管是斗渠還是農(nóng)渠都不能在中途分叉。

為方便建模引入下列記號(hào)：第i個(gè)田塊斗渠和農(nóng)渠的長(zhǎng)度分別用Ldi、Lni表示；田塊之間的距離用Lij表示；單位長(zhǎng)度斗渠和農(nóng)渠的造價(jià)分別用Cd和Cn表示；田塊重心數(shù)量用 n 表示；田塊重心集合的任意子集用S表示；農(nóng)渠0-1型變量用xij表示，0代表i與j間無(wú)農(nóng)渠連接，1代表i與j間有農(nóng)渠連接；斗渠0-1型變量用yij表示，0代表i與j間無(wú)斗渠連接，1代表i與j間有斗渠連接。

2 溝渠優(yōu)化布局模型

2.1 目標(biāo)函數(shù)

以整個(gè)區(qū)域灌溉渠道的總造價(jià)最小作為目標(biāo)。

當(dāng)?shù)趇個(gè)田塊與第j個(gè)田塊由斗渠連接時(shí)，yij的值為1，xij的值為0，則Cd·Lij·yij=Cd·Lij、Cd·Lij·xij=0，其建造成本為Cd·Lij；當(dāng)?shù)趇個(gè)田塊與第j個(gè)田塊由農(nóng)渠連接時(shí)，yij的值為0，xij的值為1，則Cn·Lij·xij=Cn·Lij、Cn·Lij·yij=0，其建造成本為Cn·Lij；當(dāng)?shù)趇個(gè)田塊與第j個(gè)田塊不連接時(shí)，yij的值為0，xij的值為0，則Cd·Lij·yij=Cd·Lij·xij=0，其建造成本為0?？偨ㄔ斐杀綵為任意田塊之間的建造成本之和，則目標(biāo)函數(shù)為

式（1）以yij和xij為決策變量。溝渠優(yōu)化布局模型需要對(duì)田塊間連接方式進(jìn)行決策，確定yij和xij為0型還是1型變量。

2.2 模型約束條件

2.2.1 樹(shù)約束

研究區(qū)所有田塊都需要灌溉，因此需要將田塊的重心點(diǎn)連接在一起。為了保證生成的是 1 棵樹(shù)，連接邊的數(shù)量比重心點(diǎn)數(shù)量少 1 個(gè)。由于部分節(jié)點(diǎn)之間可能形成環(huán)，保證邊的數(shù)量并不能保證生成的一定是樹(shù)。因此需要防止環(huán)的形成，節(jié)點(diǎn)集合的任意子集中其連接邊的數(shù)量比子集的節(jié)點(diǎn)數(shù)少1個(gè)。只有在這2個(gè)約束下才能保證生成的是樹(shù)，其具體形式如下：

2.2.2 農(nóng)渠度和斗渠度約束

首先明確2個(gè)概念，節(jié)點(diǎn)與其他節(jié)點(diǎn)連接邊的數(shù)量稱為節(jié)點(diǎn)的度，對(duì)生成樹(shù)中各節(jié)點(diǎn)度數(shù)加上一定限制的最小生成樹(shù)稱為度約束最小生成樹(shù)。相對(duì)于基本最小生成樹(shù)，該模型與很多實(shí)踐問(wèn)題更加接近。例如該文的溝渠優(yōu)化布局模型必須按照同級(jí)渠道不能相連的原則進(jìn)行布局，即指渠道不能分叉。這就要求1個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)連接邊的數(shù)量應(yīng)該≤2（1個(gè)表示進(jìn)入，1個(gè)表示出去），但是處于渠道末尾的節(jié)點(diǎn)則只有1條表示進(jìn)入的連接邊。因此該文的溝渠優(yōu)化布局模型是度約束最小生成樹(shù)模型。其具體的農(nóng)渠度約束形式如下：

上式中的 xij不包括虛擬點(diǎn)。

斗渠度約束與農(nóng)渠度約束類似，不再贅述，其具體形式如下：

2.2.3 斗渠與農(nóng)渠互斥約束

第i個(gè)重心點(diǎn)與第j個(gè)重心點(diǎn)之間只能由斗渠或農(nóng)渠連接，而不能同時(shí)由這兩者連接。因此這是該文最小生成樹(shù)模型特有的約束，因?yàn)橐话愕淖钚∩蓸?shù)模型只有1個(gè)0-1型決策變量，根本就不會(huì)有這個(gè)問(wèn)題，只有該文的有2個(gè)0-1型決策變量的最小生成樹(shù)模型才會(huì)出現(xiàn)這個(gè)問(wèn)題。因此在 2 個(gè)田塊之間斗渠與農(nóng)渠是互斥的，其具體形式如下：

這里包括虛擬點(diǎn)在內(nèi)。

2.2.4 斗渠和農(nóng)渠長(zhǎng)度約束

斗渠和農(nóng)渠長(zhǎng)度約束的具體形式為

式中Ldmax和Lnmax分別為所有斗渠和農(nóng)渠長(zhǎng)度的最大值，Ldm和Lnm分別為規(guī)程規(guī)定的斗渠和農(nóng)渠最大值。這里不包括虛擬點(diǎn)。

2.2.5 可能取水點(diǎn)約束

考慮水源約束，在建立模型時(shí)選擇水源邊的田塊作為可能取水點(diǎn)?？赡苋∷c(diǎn)出去的連接只能為斗渠，令k=1,2,…,t為可能取水點(diǎn)，則可能取水點(diǎn)約束的具體形式為

這里不包括虛擬點(diǎn)。

綜上，該文建立的溝渠優(yōu)化布局模型不同于一般的最小生成樹(shù)模型，一般的最小生成樹(shù)模型只包括1個(gè)0-1型變量，只能處理一級(jí)線性工程的優(yōu)化布局，而該文建立的模型包括2個(gè)0-1型變量，能夠處理兩級(jí)線性工程優(yōu)化布局，這符合實(shí)際情況。在實(shí)踐中很多優(yōu)化布局問(wèn)題不僅僅是處理一級(jí)線性工程，而是2級(jí)甚至多級(jí)。如果用一般的最小生成樹(shù)模型進(jìn)行二級(jí)線性工程的優(yōu)化布局，首先需要憑經(jīng)驗(yàn)確定高一級(jí)線性工程的布局，然后再運(yùn)用模型求得次一級(jí)線性工程的布局，求得的布局方案是局部最優(yōu)的方案，具有很大限制。而如果用該文建立的最小生成樹(shù)模型進(jìn)行二級(jí)線性工程的優(yōu)化布局，求得的布局方案是全局最優(yōu)的方案，因此該文建立的模型更符合實(shí)際。該文將只有1個(gè)0-1型變量的最小生成樹(shù)模型稱為一級(jí)最小生成樹(shù)模型，具有2個(gè)0-1型變量的最小生成樹(shù)模型稱為兩級(jí)最小生成樹(shù)模型。至此，把溝渠優(yōu)化布局問(wèn)題抽象成了具有長(zhǎng)度約束、度約束的兩級(jí)最小生成樹(shù)模型。

3 溝渠優(yōu)化布局模型求解方法

采用LINGO軟件進(jìn)行求解。整個(gè)模型共3類節(jié)點(diǎn)，虛擬點(diǎn)、可能取水點(diǎn)和田塊重心點(diǎn)。

3.1 虛擬點(diǎn)處理

研究區(qū)可有多個(gè)可能取水點(diǎn)，可以生成多條斗渠，從而其渠道布局方案是由多棵生成樹(shù)組成。虛擬點(diǎn)是多個(gè)可能取水點(diǎn)的根節(jié)點(diǎn)，虛擬點(diǎn)、虛擬渠道和研究區(qū)多棵生成樹(shù)組成了 1 棵更大的生成樹(shù)，從而將求解研究區(qū)多棵生成樹(shù)問(wèn)題轉(zhuǎn)化成求解 1 棵生成樹(shù)問(wèn)題。為了在程序中將新增的虛擬點(diǎn)與研究區(qū)田塊重心點(diǎn)統(tǒng)一處理，而又顯示其特殊性，需要對(duì)其做如下處理。虛擬點(diǎn)編號(hào)：程序中的循環(huán)結(jié)構(gòu)和分支結(jié)構(gòu)對(duì)數(shù)組變量第 1 個(gè)值即能將其與后面的值做統(tǒng)一處理，同時(shí)也方便將其做特殊處理。因此將虛擬點(diǎn)放在程序節(jié)點(diǎn)集合的第1個(gè)。

3.2 求解思路

除了斗渠和農(nóng)渠的長(zhǎng)度約束外，模型中其他約束都可以直接用程序語(yǔ)言表示出來(lái)。但是長(zhǎng)度約束卻還要先求出每條農(nóng)渠和斗渠的長(zhǎng)度。因此，該文的溝渠優(yōu)化布局模型比最小生成樹(shù)模型更復(fù)雜。求解思路是將長(zhǎng)度約束剝離出來(lái)，然后再利用LINGO求解無(wú)長(zhǎng)度約束的溝渠優(yōu)化布局模型。具體方法是先確定斗渠。這些斗渠能使研究區(qū)任何地方到斗渠的距離小于農(nóng)渠的長(zhǎng)度約束，而且是最短的，相當(dāng)于將長(zhǎng)度約束剝離出來(lái)，且保證了全局最優(yōu)。然后再利用最小生成樹(shù)模型求解最短農(nóng)渠。保證所求的布局方案是工程量最小的。

3.2.1 確定斗渠

斗渠要滿足使研究區(qū)任何地方到斗渠的距離小于農(nóng)渠的長(zhǎng)度約束，而且滿足斗渠長(zhǎng)度最短的要求。

借助計(jì)算幾何中的凸殼理論，先求研究區(qū)邊界的凸殼；然后求研究區(qū)邊界的最小外圓；最后求研究區(qū)邊界最小外圓的一個(gè)劃分，該劃分使研究區(qū)邊界最小外圓的任何地方到劃分該圓的線段的距離都小于農(nóng)渠約束距離，且這些線段的總長(zhǎng)度是最短的。這樣就把確定滿足要求的斗渠問(wèn)題轉(zhuǎn)化成了較簡(jiǎn)單的幾何問(wèn)題。

1）研究區(qū)邊界凸殼。研究區(qū)邊界是平面多邊形，其頂點(diǎn)凸殼是指包括平面多邊形頂點(diǎn)的最小凸集。而凸集是指平面上點(diǎn)集中的任意 2 點(diǎn)所連接線段全部位于其內(nèi)部的非空點(diǎn)集。平面多邊形頂點(diǎn)凸殼邊界是凸多邊形，其頂點(diǎn)為多邊形頂點(diǎn)中的點(diǎn)。如圖2所示，平面多邊形ABCDEFG的凸殼是點(diǎn)集{A,B,C,E,F,G}，凸殼邊界是凸多邊形ABCEFG。

圖2 平面多邊形凸殼及其邊界示意圖Fig.2 Diagram of planar polygon convex hull and its boundary

2）研究區(qū)邊界的最小覆蓋圓。平面凸多邊形直徑是凸多邊形頂點(diǎn)間最遠(yuǎn)的點(diǎn)對(duì)之間的距離。平面凸多邊形的最小覆蓋圓是指包括平面多邊形的最小覆蓋圓。如圖2所示，設(shè)凸多邊形覆蓋圓直徑為AE，AE中點(diǎn)為O，O到凸多邊形中其他各點(diǎn)的距離必有最大值rm，假設(shè)該點(diǎn)為A。若rm≤|AE|/2，則以AB為直徑的圓即是該凸多邊形的最小覆蓋圓。否則以O(shè)為圓心、rm為半徑的圓為最小覆蓋圓。

3）研究區(qū)斗渠確定。該文討論的范圍是研究區(qū)最小外圓的半徑＞600 m及＜2 400 m的土地整治項(xiàng)目。因?yàn)楫?dāng)圓的半徑為600 m時(shí)，面積為113.04 hm2，當(dāng)圓的半徑為1 200 m時(shí)，面積為452.16 hm2，當(dāng)半徑為2 400 m，面積為1 809.50 hm2。一般來(lái)說(shuō)土地整治項(xiàng)目的面積不會(huì)太小但也不會(huì)大于1 000 hm2，所以研究區(qū)外接圓的半徑基本＞600 m及＜2 400 m，因此該文討論的范圍就是研究區(qū)最小外圓的半徑＞600 m及＜2 400 m的土地整治項(xiàng)目。

當(dāng)研究區(qū)半徑＞600 m及＜1 200 m時(shí)，如圖3a所示，圖中大圓為研究區(qū)邊界最小外圓，設(shè)其半徑為X，小圓半徑為1 200-X，則通過(guò)可能取水點(diǎn)A且相交于小圓的所有斗渠都能滿足大圓上所有點(diǎn)到該斗渠的距離都＜1 200 m，通過(guò)可能取水點(diǎn)A且相切于小圓的斗渠AD滿足大圓上所有點(diǎn)到該斗渠的距離≤1 200 m，而且距離的最大值為線段BC的長(zhǎng)度1 200 m。通過(guò)可能取水點(diǎn)A且相離于小圓的斗渠AF則不能滿足大圓上所有點(diǎn)到該斗渠的距離都≤1 200 m，如弧HCI到該斗渠的距離＞1 200 m，要使大圓上所有點(diǎn)到斗渠的距離＜1 200 m，必須將斗渠AF變成斗渠ABF。從圖中可以看出AD是所有滿足要求的斗渠中長(zhǎng)度最短的，因此當(dāng)研究區(qū)半徑＞600 m及＜1 200 m時(shí)，滿足要求的最短的斗渠為AD。

圖3 研究區(qū)最短斗渠示意圖Fig.3 Diagram of shortest lateral canal in study area

2）當(dāng)研究區(qū)半徑等于1 200 m時(shí)，如圖3b所示，圖中圓為研究區(qū)邊界最小外圓，其半徑為1 200 m，則通過(guò)可能取水點(diǎn)A、圓心O的斗渠能滿足大圓上所有點(diǎn)到該斗渠的距離≤1 200 m，而通過(guò)可能取水點(diǎn)A的斗渠AF則不能滿足大圓上所有點(diǎn)到該斗渠的距離≤1 200 m，如弧HI到該斗渠的距離＞1 200 m，要使大圓上所有點(diǎn)到斗渠的距離＜1 200 m，必須將斗渠AF變成斗渠AOF。從圖中可以看出AE是所有滿足要求的斗渠中長(zhǎng)度最短的，因此當(dāng)研究區(qū)半徑等于1 200 m時(shí)，滿足要求的最短的斗渠為AE。

3）當(dāng)研究區(qū)半徑＞1 200～1 800 m時(shí)，如圖3c所示，圖中圓為研究區(qū)邊界最小外圓，EF和EI長(zhǎng)度為1 200 m，CB和DH的長(zhǎng)度必定＜1 200 m，設(shè)其半徑為X。因?yàn)槠浒霃剑? 200 m，所以1條斗渠不能滿足圓上所有的點(diǎn)到斗渠的距離≤1 200 m，而是需要2條，圖中斗渠AF和AI就是滿足要求的最短的斗渠。

4）當(dāng)研究區(qū)半徑＞1 800～2 400 m時(shí)，如圖3d所示，圖中圓為研究區(qū)邊界最小外圓，EF、EI、CB、DH的長(zhǎng)度為1 200 m。斗渠ACF和ADI為滿足要求的最短的斗渠。

3.2.2 無(wú)長(zhǎng)度約束溝渠優(yōu)化布局模型

無(wú)長(zhǎng)度約束溝渠優(yōu)化布局模型是指剔除斗渠和農(nóng)渠長(zhǎng)度約束后的溝渠優(yōu)化布局模型[28-30]。該模型可以直接用LINGO求解。

4 案例分析

4.1 研究區(qū)概況

研究區(qū)位于安徽省宿州市埇橋區(qū)蘄縣鎮(zhèn)忠陳村（117°3＇～117°5＇E、33°24＇～33°25＇2N），屬于采煤塌陷區(qū)。研究區(qū)于2011年進(jìn)行土地整理項(xiàng)目，筆者于2011年參與該項(xiàng)目的規(guī)劃設(shè)計(jì)。筆者在對(duì)該區(qū)進(jìn)行渠道系統(tǒng)布置時(shí)發(fā)現(xiàn)現(xiàn)有渠道布置方法不能根據(jù)各級(jí)渠道造價(jià)建立優(yōu)化模型選擇最優(yōu)的布局方案。因此筆者根據(jù)材料信息價(jià)及渠道結(jié)構(gòu)設(shè)計(jì)得到各級(jí)渠道單位長(zhǎng)度的造價(jià)，并基于研究區(qū)田塊通過(guò)Arcgis軟件處理獲得田塊重心點(diǎn)及各田塊之間的距離等基礎(chǔ)數(shù)據(jù)代入本文建立的模型進(jìn)行求解。

4.2 結(jié)果與分析

4.2.1 研究區(qū)斗渠布局方案

畫(huà)出研究區(qū)邊界的最小覆蓋圓后，作過(guò)可能取水點(diǎn)的最小覆蓋圓的直徑，因?yàn)橛?個(gè)可能取水點(diǎn)，需要選出1個(gè)更合適的。對(duì)比這2條直徑的走向與研究區(qū)主要規(guī)劃道路的走向，選擇其中與研究區(qū)主要規(guī)劃道路的走向更接近的直徑，連接該直徑經(jīng)過(guò)的田塊的重心點(diǎn)作為研究區(qū)斗渠。斗渠具體布局方案見(jiàn)圖4。

圖4 研究區(qū)斗渠布局圖Fig. 4 Layout of lateral canal in study area

4.2.2 研究區(qū)渠道布局方案

確定研究區(qū)斗渠后，將對(duì)應(yīng)的yij賦值為1，然后運(yùn)行運(yùn)用LINGO編寫(xiě)的無(wú)長(zhǎng)度約束溝渠優(yōu)化布局模型求解程序，得到如圖5a所示的研究區(qū)渠道系統(tǒng)。共斗渠1條，長(zhǎng)2 811 m，農(nóng)渠22條，長(zhǎng)17 712 m，共20 523 m。根據(jù)優(yōu)化原則布設(shè)，且已通過(guò)評(píng)審的渠道布局方案如圖 5 b所示，共有斗渠2條，長(zhǎng)6 037 m，農(nóng)渠23條，長(zhǎng)14 535 m。共20 572 m。

通常土地整治工程設(shè)計(jì)中斗渠設(shè)計(jì)為口寬150 cm，底寬50 cm，深100 cm的梯形；農(nóng)渠設(shè)計(jì)為口寬80 cm，深90 cm的矩形。斗渠每米工程量是1 m3，農(nóng)渠每米工程量是0.75 m3，斗渠單位長(zhǎng)度的工程量是農(nóng)渠單位長(zhǎng)度工程量的 1 .33倍。這樣換算出來(lái)模型優(yōu)化方案的工程量是16 095 m3，評(píng)審方案的工程量是16 938.25 m3，模型優(yōu)化方案的工程量比評(píng)審方案的工程量減少了5%，按斗渠工程2011年當(dāng)?shù)貑蝺r(jià)85元/m，農(nóng)渠工程2011年當(dāng)?shù)貑蝺r(jià)49.58元/m，可節(jié)約工程造價(jià)116 694元。

圖5 基于不同方法的研究區(qū)渠道布局圖Fig.5 Canal layout in study area based on different methods

表1 渠道布局方案比較Table 1 Comparison of canal layout methods

5 結(jié)論與討論

該文運(yùn)用最小生成樹(shù)理論對(duì)土地整治項(xiàng)目渠道布局進(jìn)行描述，并結(jié)合虛擬點(diǎn)、可能取水點(diǎn)、分權(quán)重定義節(jié)點(diǎn)建立了基于最小生成樹(shù)理論的優(yōu)化模型。該模型能夠反映平原地區(qū)土地整治項(xiàng)目渠道布局的分級(jí)情況、多取水點(diǎn)情況，并能利用成熟的最小生成樹(shù)理論的求解方法進(jìn)行求解。最后通過(guò)實(shí)例分析表明，基于最小生成樹(shù)的渠道布局比基于優(yōu)化原則的布局節(jié)省5%的工程量，驗(yàn)證了該模型的實(shí)用性。但是該模型還有一些未考慮到的地方，使得該模型具有一定的局限性，希望進(jìn)一步的研究將這些因素考慮進(jìn)來(lái)完善渠道優(yōu)化布局模型，具體如下：1）該研究斗、農(nóng)渠單位長(zhǎng)度的造價(jià)是根據(jù)多年設(shè)計(jì)平原地區(qū)渠道的經(jīng)驗(yàn)確定的，沒(méi)有考慮斗、農(nóng)渠設(shè)計(jì)尺寸的概率分布，沒(méi)進(jìn)行嚴(yán)格的統(tǒng)計(jì)學(xué)處理，得到的結(jié)果有一定的誤差。進(jìn)一步的研究需要積累設(shè)計(jì)數(shù)據(jù)，得出斗、農(nóng)渠設(shè)計(jì)尺寸的概率分布，對(duì)設(shè)計(jì)尺寸進(jìn)行嚴(yán)格的統(tǒng)計(jì)學(xué)處理，使研究結(jié)果具有更廣泛的適用性；2）該文的渠道優(yōu)化布局模型雖然通過(guò)可能取水點(diǎn)概念的提出，考慮了水源約束。但是該文的研究區(qū)是平原地區(qū)，整個(gè)研究區(qū)高差很小，未考慮地形約束和上下級(jí)渠道、各取水點(diǎn)的水位約束。因此該模型只適用于平原地區(qū)的渠道優(yōu)化布局，為了推廣至其他區(qū)域，需要進(jìn)一步的研究來(lái)完善模型。此外，該文模型只考慮了渠道的投資，未考慮灌溉、排水系統(tǒng)及道路等交叉建筑物的投資。因此該模型得到的最優(yōu)方案只是灌溉渠道的最優(yōu)布局方案，為了降低整個(gè)研究區(qū)總的投資，需要進(jìn)一步將灌溉系統(tǒng)、排水系統(tǒng)、道路系統(tǒng)及其交叉建筑物投資納入模型內(nèi)，構(gòu)建綜合模型。

[1] 劉飛，陸林. 采煤塌陷區(qū)的生態(tài)恢復(fù)研究進(jìn)展[J]. 自然資源學(xué)報(bào). 2009，24(4)：612-620. Liu Fei,Lu Lin. Progress in the study of ecological restoration of coa1 mining subsidence areas[J]. Journal of Natural Resources,2009,24(4):612－620.(in Chinese with English abstract)

[2] 胡振琪，趙艷玲，程玲玲. 中國(guó)土地復(fù)墾目標(biāo)與內(nèi)涵擴(kuò)展[J]. 中國(guó)土地科學(xué)，2004，18(3):3－8. Hu Zhenqi,Zhao Yanling,Cheng Lingling. Extension of goal and meaning of land reclamation in china[J]. China Land Science,2004,18(3):3－8.(in Chinese with English abstract)

[3] 周復(fù)旦，趙長(zhǎng)勝，丁佩，等. 任樓礦區(qū)塌陷土地復(fù)墾規(guī)劃與利用現(xiàn)狀研究[J]. 水土保持通報(bào)，2011，31(1):227－230. Zhou Fudan,Zhao Changsheng,Ding Pei,et al. Reclamation planning and use status of subsided lands in Renlou mining area[J]. Bulletin of Soil and Water Conservation,2011,31(1):227－230.(in Chinese with English abstract)

[4] 趙艷玲，黃琴煥，薛靜，等. 礦區(qū)土地復(fù)墾方案編制中土地破壞程度評(píng)價(jià)研究[J]. 金屬礦山，2009，395(5)：161－163. Zhao Yanling,Huang Qinhuan,Xue Jing,et al. Study on the assessment of land destroy degree in mine land reclamation design[J]. Metal Mine,2009,395(5):161－163.(in Chinese with English abstract)

[5] 蔣俊峰，趙瓊祥，高議民. 我國(guó)礦區(qū)廢棄區(qū)土地復(fù)墾技術(shù)的研究[J]. 山西煤炭，2010，30(6)：74－76. Jiang Junfeng,Zhao Qiongxiang,Gao Yimin. China’s land reclamation technology research of abandoned mining area [J]. Shanxi Coal,2010,30(6):74－76.(in Chinese with English abstract)

[6] 馮小軍，陳宇，魏穎. 我國(guó)礦區(qū)廢棄區(qū)土地復(fù)墾技術(shù)研究[J]. 煤，2009，18(10)：1－5. Feng Xiaojun,Chen Yu,Wei Ying. Technology research of reclaimed abandoned mine land in china[J]. Coal,2009,18(10):1－5.(in Chinese with English abstract)

[7] 陳秋成，卞正富. 礦區(qū)土地復(fù)墾規(guī)劃決策支持系統(tǒng)開(kāi)發(fā)[J].地理空間信息，2008，6(4)：98－100. Chen Qiucheng,Bian Zhengfu. Development of land reclamation planning decision support system in mining areas [J]. Geospatial Information,2008,6(4):98－100.(in Chinese with English abstract)

[8] 卞正富. 國(guó)內(nèi)外煤礦區(qū)土地復(fù)墾研究綜述[J]. 中國(guó)土地科學(xué)，2000，14(1)：6－11.

[9] 張洪波，陳秋計(jì)，謝宏全，等. 礦區(qū)復(fù)墾土地資源優(yōu)化配置方法研究[J]. 西安科技大學(xué)學(xué)報(bào)，2005，25(2)：172－174. Zhang Hongbo,Chen Qiuji,Xie Hongquan,et al. Optimization configuration method of reclamation land resources in mining area[J]. Journal Of Xi’an University Of Science And Technology,2005,25(2):172－174.(in Chinese with English abstract)

[10] 羅儀寧. DEM表面地形突變特征表達(dá)方法研究[D]. 西安：西北大學(xué)，2011. Luo Yining. Method of the Representation for Artificial Discontinuous Terrain on the DEM Surface[D]. Xi’an:Northwest University,2011.(in Chinese with English abstract)

[11] 胡晉山，康建榮，吳志強(qiáng)，等. 基于GIS的礦區(qū)地表塌陷預(yù)計(jì)及規(guī)劃治理系統(tǒng)的設(shè)計(jì)[J]. 現(xiàn)代礦業(yè)，2010，496(8)：52－54.

[12] 王慎敏，金曉斌，周寅康. 基于GIS的采煤塌陷區(qū)土地復(fù)墾項(xiàng)目規(guī)劃設(shè)計(jì)研究[J]. 地理科學(xué)，2008，28(2)：195－199. Wang Shenmin,Jin Xiaobin,Zhou Yinkang. Planning and designing of reclamation project in mining subsided land based on GIS[J]. Scientia Geographica Sinica,2008,28(2):195－199.(in Chinese with English abstract)

[13] 劉玉華. 煤礦區(qū)土地復(fù)墾管理信息系統(tǒng)的設(shè)計(jì)與應(yīng)用[D].濟(jì)南：山東師范大學(xué)，2008. Liu Yuhua. Design and Apply in Land Reclamation Management Information System of Coal Mining Area[D]. Ji’nan:Shandong Normal University,2008.(in Chinese with English abstract)

[14] 胡晉山，康建榮，王文福. 基于GIS的礦區(qū)土地復(fù)墾信息系統(tǒng)的設(shè)計(jì)[J]. 金屬礦山，2010，414(12)：113－116. Hu Jinshan,Kang Jianrong,Wang Wenfu. Design of information system of mine land reclamation based on GIS[J]. Metal Mine,2010,414(12):113－116.(in Chinese with English abstract)

[15] 付浩，催玉朝，奚新麗. GIS在礦區(qū)復(fù)墾土地相關(guān)模型中的耦合應(yīng)用[J]. 礦業(yè)工程，2009，7(2)：57－59. Fu Hao,Cui Yuchao,Xi Xinli. Application of GIS based land reclamation models[J]. Mining Engineering,2009,7(2):57－59.(in Chinese with English abstract)

[16] 黃琪. 基于DEM與LP的土地平整工程設(shè)計(jì)優(yōu)化研究[D].南京：南京農(nóng)業(yè)大學(xué)，2011. Huang Qi. Study on Optimal Design for Land Leveling Project based on DEM and LP[D]. Nanjing:Nanjing Agricultural University,2011.(in Chinese with English abstract)

[17] 胡振琪. 土地復(fù)墾與生態(tài)重建[M]. 徐州：中國(guó)礦業(yè)大學(xué)出版社，2008.

[18] 江帆. DEM表面建模與精度評(píng)估方法研究[D]. 鄭州：解放軍信息工程大學(xué)，2006. Jiang Fan. Researches on the Surface Modeling and the Accuracy Evaluation of DEM[D]. Zhenzhou:The PLA Information Engineering University,2006.(in Chinese with English abstract)

[19] 曲世潔. GIS結(jié)合 E xcel在土方計(jì)算及調(diào)配中的應(yīng)用研究[D]. 大連：大連理工大學(xué)，2011. Qu Shijie. Application Research of GIS Combined with Excel for Calculating Earthwork and Earth Dispensation[D]. Dalian:Dalian University of Technology,2011.(in Chinese with English abstract)

[20] 柳長(zhǎng)順，齊實(shí)，杜麗娟. 土地整理項(xiàng)目土方量計(jì)算方法[J].中國(guó)水土保持科學(xué). 2003，1(2)：77－79. Liu Changshun,Qi Shi,Du Lijuan. Method to calculate earthwork in land consolidation project[J]. Science of Soil and Water Conservation,2003,1(2):77－79.(in Chinese with English abstract)

[21] 陸鋒. 最短路徑算法:分類體系與研究進(jìn)展[J]. 測(cè)繪學(xué)報(bào)，2001(3)：269－275. Lu Feng. Shortest path algorithms:Taxonomy and advance in research[J]. Acta Geodaetica et Cartographica Sinaca,2001(3):269－275.(in Chinese with English abstract)

[22] 趙艷玲，胡振琪，高永光，等. ERDAS IMAGINE在采煤沉陷地復(fù)墾土方量計(jì)算中的應(yīng)用[J]. 礦業(yè)研究與開(kāi)發(fā)，2005，25(2)：82－88. Zhao Yanling,Hu Zhengqi,Gao Yongguang,et al. Application of ERDAS IMAGINE in the earthwork calculation of subsided land reclamation for coal mining[J]. Mining Research and Development,2005,25(2):82－88.(in Chinese with English abstract)

[23] 付梅臣，胡振琪，米靜. 土地整理和復(fù)墾工程費(fèi)用結(jié)構(gòu)分析及控制對(duì)策研究[J]. 農(nóng)業(yè)工程學(xué)報(bào)，2003，19(4)：291－294. Fu Meichen,Hu Zhenqi,Mi Jing. Contribution analyses and control countermeasures of land consolidation and reclamation project cost[J]. Transactions of the Chinese Society of Agricultural Engineering(Transactions of the CSAE),2003,19(4):291－294.(in Chinese with English abstract)

[24] 石磊，馮祖針，楊建強(qiáng)，等. 度-半徑約束最小生成樹(shù)問(wèn)題及其算法[J]. 沈陽(yáng)大學(xué)學(xué)報(bào)，2012，24(4)：63－66. Shi Lei,Feng Zuzhen,Yang Jianqiang,et al. Degreeconstrained,radius-constrained minimum spanning tree problem and its algorithm[J]. Journal of Shenyang University,2012,24(4):63－66.(in Chinese with English abstract)

[25] 蔣曉紅，程吉林，曾慶祝. 平原河網(wǎng)地區(qū)灌溉泵站群優(yōu)化布局研究[J]. 灌溉排水學(xué)報(bào)，2009(4)：52－54. Jiang Xiaohong,Cheng Jilin,Zeng Qinzhu. The layout optimization of irrigation pumping stations in plain river network region[J]. Journal of Irrigation and Drainage,2009(4):52－54.(in Chinese with English abstract)

[26] 許夕保，周振紅，程吉林. 渠道簡(jiǎn)化設(shè)計(jì)[J]. 中國(guó)農(nóng)村水利水電，1997(9)：25－27. Xu Xibao,Zhou Zhenhong,Cheng Jilin. Simplified design to Canal[J]. China Rural Water and Hydropower,1997(9):25－27.(in Chinese with English abstract)

[27] 程吉林，畢榮石. 渠道設(shè)計(jì)的動(dòng)態(tài)規(guī)劃模型[J]. 灌溉排水，1991(1)：53－56. Cheng Jilin,Bi Rongshi. Dynamic programming model of canal design[J]. Irrigation and Drainage,1991(1):53－56.(in Chinese with English abstract)

[28] 仇錦先，程吉林，呂賽軍. 渠系網(wǎng)絡(luò)圖在大型灌區(qū)規(guī)劃中的應(yīng)用[J]. 中國(guó)農(nóng)村水利水電，2004(1)：56－58. Chou Jinxian,Cheng Jilin,Lü Saijun. Application of network diagrams of canal system in large-sized irrigation districts planning[J]. China Rural Water and Hydropower,2004(1):56－58.(in Chinese with English abstract)

[29] 程吉林，陳平，朱春龍. 輸水渠道線路優(yōu)化與漫游數(shù)學(xué)家模型[J]. 水科學(xué)進(jìn)展，2004(3)：397－399. Cheng Jilin,Chen Pin,Zhu Chunlong. Optimal alignment of channel and wanderings mathematician model[J]. Advances in Water Science,2004(3):397－399.(in Chinese with English abstract)

[30] 周榮敏，雷延峰. 不同灌溉工作制度下的灌溉管網(wǎng)優(yōu)化設(shè)計(jì)研究[J]. 西北水資源與水工程，2002，13(2)：1－5. Zhou Rongmin,Lei Yanfeng. Study on optimization design f or irrigation pipe network under different irrigation schedules[J]. Northwest Water Resources &Water Engineering,2002,13(2):1－5.(in Chinese with English abstract)

Optimal model of channel layout based on minimum spanning trees

Xu Zichang
(1. School of Earth Resources,China University of Geosciences(Wuhan),Wuhan 430074,China;2. Fujian Geologic Surveying and Mapping Institute of Remote Sensing Center,Fuzhou 350011,China)

Few studies have been done on the layout of ditches,and the quantitative models for the optimization of the channel layout is lacking. Since the cost of channel layout project accounts for a large proportion of the cost of land reclamation project,it is necessary to find a design in order to reduce the cost of channel project. In this paper,a new model was developed for optimal layout of canals and ditches. The theory of minimum spanning tree was used to describe the channel layout of land reclamation project,and an optimal model based on minimum spanning tree theory was established in combination with the virtual point,the alternative water intake point and the weighted definition node. The study area was located at a coal mining subsidence area in Yongqiao District,Suzhou City,Anhui Province(33°24＇-33°25＇N and 117°3＇-117°5＇E). The channel optimization layout model based on the minimum spanning tree was constructed to optimize the layout of farmland irrigation channels in the plain areas. Different from the traditional minimum spanning tree model,this model solved the optimization problem for two-level channels,and the final solution using this model was greater than or equal to a minimum spanning tree. In order to take advantage of the mature minimum- production-tree approach,the virtual point concept was created to eliminate the difference between the channel optimization layout model and the traditional minimum spanning tree model. Four cases of solving the model were discussed by convex hull theory. The LINGO program was written for solving the model. Finally,the channel optimization model based on the minimum spanning tree was applied to a research area,and then the channel layout scheme using this model was obtained with a total length of 20 523 m containing 1 lateral canal(2 811-m length) and 22 ditches(17 712-m length). According to the traditional optimum principle,there were totally 20 572 m with 2 lateral canals(6 037-m length) and 23 ditches(14 535-m length). The lateral canal was designed as a trapezoid for the land reclamation with a mouth width of 150 cm,a base width of 50 cm and a depth of 100 cm. The ditch was designed as a rectangle with a mouth width of 80 cm and a depth of 90 cm. For the lateral canal,the engineering workload of unit length was 1 m3and for ditch engineering workload per unit length was 0.75 m3. The unit length engineering workload of the lateral canal was 1.33 times of the ditch. Based on unit length engineering workload mentioned above,the total engineering workload of the land reclamation project was 16 095 m3by using the channel optimization layout method based on minimum spanning tree and 16 938.25 m3by using optimum principle method,respectively. The engineering workload of the minimum spanning tree method was 5.0% less than that of the optimum principle. According to the unit price of the lateral canal engineering project 85 yuan per meter and the unit price of ditch engineering 49.58 yuan per meter,the project cost of 116 694 yuan was saved. The result shows that the channel optimization model based on the minimum spanning tree can obtain the channel layout plan with less cost,that is,the maximum control of land reclamation cost. This study can provide an effective way to cost control of land reclamation projects.

canals;optimal systems;land reclamation;layout;minimum spanning tree model;convex hull theory;LINGO

10.11975/j.issn.1002-6819.2017.01.017

F301.24

A

1002-6819(2017)-01-0124-07

許自昌. 基于最小生成樹(shù)的渠道系統(tǒng)優(yōu)化布局模型[J]. 農(nóng)業(yè)工程學(xué)報(bào)，2017，33(1)：124－130.

10.1197 5/j.issn.1002-6819.2017.01.017 http://www.tcsae.org

Xu Zichang.Optimal model of channel layout based on minimum spanning trees [J]. Transactions of the Chinese Society of Agricultural Engineering(Transactions of the CSAE),2017,33(1):124－130.(in Chinese with English abstract) doi：10.11975/j.issn.1002-6819.2017.01.017 http://www.tcsae.org

2016-03-30

2016-11-07

國(guó)土資源部公益性行業(yè)科研專項(xiàng)課題（201011016-2）

許自昌，男，江西撫州人，博士生，高級(jí)工程師，中國(guó)土地估價(jià)師，中國(guó)房地產(chǎn)估價(jià)師，主要從事土地管理、土地規(guī)劃、土地整理設(shè)計(jì)、礦山復(fù)墾等研究。武漢 中國(guó)地質(zhì)大學(xué)（武漢）資源學(xué)院，430074。Email：120433676@qq.com