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

許自昌

（1. 中國地質大學（武漢）資源學院，武漢430074；2. 福建省地質測繪院遙感中心，福州 350011）

·農業(yè)水土工程·

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

許自昌

（1. 中國地質大學（武漢）資源學院，武漢430074；2. 福建省地質測繪院遙感中心，福州 350011）

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

2.1 目標函數(shù)

以整個區(qū)域灌溉渠道的總造價最小作為目標。

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

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

2.2 模型約束條件

2.2.1 樹約束

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

2.2.2 農渠度和斗渠度約束

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

上式中的 xij不包括虛擬點。

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

2.2.3 斗渠與農渠互斥約束

第i個重心點與第j個重心點之間只能由斗渠或農渠連接，而不能同時由這兩者連接。因此這是該文最小生成樹模型特有的約束，因為一般的最小生成樹模型只有1個0-1型決策變量，根本就不會有這個問題，只有該文的有2個0-1型決策變量的最小生成樹模型才會出現(xiàn)這個問題。因此在 2 個田塊之間斗渠與農渠是互斥的，其具體形式如下：

這里包括虛擬點在內。

2.2.4 斗渠和農渠長度約束

斗渠和農渠長度約束的具體形式為

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

2.2.5 可能取水點約束

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

這里不包括虛擬點。

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

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

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

3.1 虛擬點處理

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

3.2 求解思路

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

3.2.1 確定斗渠

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

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

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

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

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

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

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

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

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

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

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

3.2.2 無長度約束溝渠優(yōu)化布局模型

無長度約束溝渠優(yōu)化布局模型是指剔除斗渠和農渠長度約束后的溝渠優(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年進行土地整理項目，筆者于2011年參與該項目的規(guī)劃設計。筆者在對該區(qū)進行渠道系統(tǒng)布置時發(fā)現(xiàn)現(xiàn)有渠道布置方法不能根據(jù)各級渠道造價建立優(yōu)化模型選擇最優(yōu)的布局方案。因此筆者根據(jù)材料信息價及渠道結構設計得到各級渠道單位長度的造價，并基于研究區(qū)田塊通過Arcgis軟件處理獲得田塊重心點及各田塊之間的距離等基礎數(shù)據(jù)代入本文建立的模型進行求解。

4.2 結果與分析

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

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

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

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

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

通常土地整治工程設計中斗渠設計為口寬150 cm，底寬50 cm，深100 cm的梯形；農渠設計為口寬80 cm，深90 cm的矩形。斗渠每米工程量是1 m3，農渠每米工程量是0.75 m3，斗渠單位長度的工程量是農渠單位長度工程量的 1 .33倍。這樣換算出來模型優(yōu)化方案的工程量是16 095 m3，評審方案的工程量是16 938.25 m3，模型優(yōu)化方案的工程量比評審方案的工程量減少了5%，按斗渠工程2011年當?shù)貑蝺r85元/m，農渠工程2011年當?shù)貑蝺r49.58元/m，可節(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ōu)化模型。該模型能夠反映平原地區(qū)土地整治項目渠道布局的分級情況、多取水點情況，并能利用成熟的最小生成樹理論的求解方法進行求解。最后通過實例分析表明，基于最小生成樹的渠道布局比基于優(yōu)化原則的布局節(jié)省5%的工程量，驗證了該模型的實用性。但是該模型還有一些未考慮到的地方，使得該模型具有一定的局限性，希望進一步的研究將這些因素考慮進來完善渠道優(yōu)化布局模型，具體如下：1）該研究斗、農渠單位長度的造價是根據(jù)多年設計平原地區(qū)渠道的經驗確定的，沒有考慮斗、農渠設計尺寸的概率分布，沒進行嚴格的統(tǒng)計學處理，得到的結果有一定的誤差。進一步的研究需要積累設計數(shù)據(jù)，得出斗、農渠設計尺寸的概率分布，對設計尺寸進行嚴格的統(tǒng)計學處理，使研究結果具有更廣泛的適用性；2）該文的渠道優(yōu)化布局模型雖然通過可能取水點概念的提出，考慮了水源約束。但是該文的研究區(qū)是平原地區(qū)，整個研究區(qū)高差很小，未考慮地形約束和上下級渠道、各取水點的水位約束。因此該模型只適用于平原地區(qū)的渠道優(yōu)化布局，為了推廣至其他區(qū)域，需要進一步的研究來完善模型。此外，該文模型只考慮了渠道的投資，未考慮灌溉、排水系統(tǒng)及道路等交叉建筑物的投資。因此該模型得到的最優(yōu)方案只是灌溉渠道的最優(yōu)布局方案，為了降低整個研究區(qū)總的投資，需要進一步將灌溉系統(tǒng)、排水系統(tǒng)、道路系統(tǒng)及其交叉建筑物投資納入模型內，構建綜合模型。

[1] 劉飛，陸林. 采煤塌陷區(qū)的生態(tài)恢復研究進展[J]. 自然資源學報. 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] 胡振琪，趙艷玲，程玲玲. 中國土地復墾目標與內涵擴展[J]. 中國土地科學，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] 周復旦，趙長勝，丁佩，等. 任樓礦區(qū)塌陷土地復墾規(guī)劃與利用現(xiàn)狀研究[J]. 水土保持通報，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ū)土地復墾方案編制中土地破壞程度評價研究[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] 蔣俊峰，趙瓊祥，高議民. 我國礦區(qū)廢棄區(qū)土地復墾技術的研究[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] 馮小軍，陳宇，魏穎. 我國礦區(qū)廢棄區(qū)土地復墾技術研究[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ū)土地復墾規(guī)劃決策支持系統(tǒng)開發(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] 卞正富. 國內外煤礦區(qū)土地復墾研究綜述[J]. 中國土地科學，2000，14(1)：6－11.

[9] 張洪波，陳秋計，謝宏全，等. 礦區(qū)復墾土地資源優(yōu)化配置方法研究[J]. 西安科技大學學報，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]. 西安：西北大學，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] 胡晉山，康建榮，吳志強，等. 基于GIS的礦區(qū)地表塌陷預計及規(guī)劃治理系統(tǒng)的設計[J]. 現(xiàn)代礦業(yè)，2010，496(8)：52－54.

[12] 王慎敏，金曉斌，周寅康. 基于GIS的采煤塌陷區(qū)土地復墾項目規(guī)劃設計研究[J]. 地理科學，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ū)土地復墾管理信息系統(tǒng)的設計與應用[D].濟南：山東師范大學，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ū)土地復墾信息系統(tǒng)的設計[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ū)復墾土地相關模型中的耦合應用[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的土地平整工程設計優(yōu)化研究[D].南京：南京農業(yè)大學，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] 胡振琪. 土地復墾與生態(tài)重建[M]. 徐州：中國礦業(yè)大學出版社，2008.

[18] 江帆. DEM表面建模與精度評估方法研究[D]. 鄭州：解放軍信息工程大學，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結合 E xcel在土方計算及調配中的應用研究[D]. 大連：大連理工大學，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] 柳長順，齊實，杜麗娟. 土地整理項目土方量計算方法[J].中國水土保持科學. 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]. 測繪學報，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在采煤沉陷地復墾土方量計算中的應用[J]. 礦業(yè)研究與開發(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] 付梅臣，胡振琪，米靜. 土地整理和復墾工程費用結構分析及控制對策研究[J]. 農業(yè)工程學報，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] 石磊，馮祖針，楊建強，等. 度-半徑約束最小生成樹問題及其算法[J]. 沈陽大學學報，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]. 灌溉排水學報，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] 許夕保，周振紅，程吉林. 渠道簡化設計[J]. 中國農村水利水電，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] 程吉林，畢榮石. 渠道設計的動態(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)絡圖在大型灌區(qū)規(guī)劃中的應用[J]. 中國農村水利水電，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ù)學家模型[J]. 水科學進展，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)化設計研究[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

許自昌. 基于最小生成樹的渠道系統(tǒng)優(yōu)化布局模型[J]. 農業(yè)工程學報，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

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

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