保持城市道路格網(wǎng)模式的街區(qū)合并混合整數(shù)規(guī)劃模型

欒學(xué)晨,楊必勝,李秋萍

1．武漢大學(xué)測繪遙感信息工程國家重點(diǎn)實驗室,湖北武漢 430079;2．武漢大學(xué)時空數(shù)據(jù)智能獲取技術(shù)與應(yīng)用教育部工程研究中心,湖北武漢 430079;3．廣東瑞圖萬方科技股份有限公司,廣東佛山 528305;4．中山大學(xué)地理科學(xué)與規(guī)劃學(xué)院綜合地理信息研究中心,廣東廣州 510275

保持城市道路格網(wǎng)模式的街區(qū)合并混合整數(shù)規(guī)劃模型

欒學(xué)晨1,2,3,楊必勝1,2,李秋萍4

1．武漢大學(xué)測繪遙感信息工程國家重點(diǎn)實驗室,湖北武漢 430079;2．武漢大學(xué)時空數(shù)據(jù)智能獲取技術(shù)與應(yīng)用教育部工程研究中心,湖北武漢 430079;3．廣東瑞圖萬方科技股份有限公司,廣東佛山 528305;4．中山大學(xué)地理科學(xué)與規(guī)劃學(xué)院綜合地理信息研究中心,廣東廣州 510275

基于優(yōu)化建模理論提出一種保持城市道路格網(wǎng)模式的街區(qū)合并模型。首先識別道路網(wǎng)中的格網(wǎng)模式,確定模型的應(yīng)用范圍。然后定義道路格網(wǎng)模式保持的目標(biāo)函數(shù)和街區(qū)合并的約束條件。其中目標(biāo)函數(shù)集成了用地類型相似性、街區(qū)緊密性、道路重要性、格網(wǎng)排列規(guī)則性和合并方向性5個評價函數(shù)。而約束條件則包括合并尺度、路劃刪除、聯(lián)動合并和連通性保持約束,以保證合并過程正確有效且滿足目標(biāo)尺度需求。最后利用識別的主干道對道路網(wǎng)進(jìn)行分區(qū),在保持道路網(wǎng)整體結(jié)構(gòu)的基礎(chǔ)上在每個分區(qū)內(nèi)分別建立混合整數(shù)規(guī)劃模型。采用數(shù)學(xué)規(guī)劃軟件CPLEX對模型進(jìn)行求解。試驗使用ATKIS 1∶25 000數(shù)據(jù),目標(biāo)是將其簡化至1∶100 000比例尺。與已有的1∶100 000比例尺數(shù)據(jù)和一般地塊合并模型比較,本文提出的街區(qū)合并模型能夠有效保持道路網(wǎng)中的格網(wǎng)模式特征。

1 引 言

道路選取對于路網(wǎng)制圖綜合、多尺度表達(dá),以及道路等級分析都具有重要意義。被選取的道路不僅應(yīng)反映城市道路網(wǎng)的整體結(jié)構(gòu),還需保持道路網(wǎng)局部模式特征[1-4]。其中格網(wǎng)街區(qū)是道路網(wǎng)中普遍存在的一類重要模式,指城市部分區(qū)域的道路呈現(xiàn)縱橫相交的形態(tài),而且格網(wǎng)街區(qū)的排列具有明顯的規(guī)則性。這些特征在道路選取過程中應(yīng)予以保持[5-7]。以往的道路選取研究集中于主干道選取和街區(qū)合并兩類[8]。主干道選取通過復(fù)雜網(wǎng)絡(luò)分析道路的重要性、劃分道路等級并提取主干道[9-11]。但是該類方法的道路選取結(jié)果過于簡化,屬于城市整體結(jié)構(gòu),難以滿足多尺度表達(dá)的需要;而街區(qū)合并方法則考慮街區(qū)密度、幾何、語義等屬性,通過局部漸進(jìn)式方法刪除街區(qū)邊界道路、合并道路街區(qū),減少道路密度[12-13]。該類方法能在每次迭代中保持合并后道路街區(qū)的形態(tài)特點(diǎn),但每次合并只考慮兩個街區(qū),對于解決多街區(qū)合并的形態(tài)保持問題尚有所不足。另外由于制圖綜合需求的復(fù)雜性,街區(qū)合并可能存在多種合理結(jié)果,局部合并方法缺少整體合并效果的評價準(zhǔn)則,導(dǎo)致局部最優(yōu)結(jié)果難以保證全局最優(yōu)。文獻(xiàn)[14]從整體出發(fā)提出一種地塊合并的全局優(yōu)化方法,根據(jù)合并后地塊面積、形狀、用地類型的變化建立了優(yōu)化模型。相比于局部合并方法,優(yōu)化算法可以考慮地圖的全局特征,比鄰域合并方法更能保持整體性。優(yōu)化算法還可以通過目標(biāo)函數(shù)的設(shè)定從多種備選方案中選取最優(yōu)結(jié)果,比只能得到單一處理結(jié)果的局部合并更符合制圖綜合的特點(diǎn)。但是該方法的研究對象是土地利用地圖數(shù)據(jù),未考慮城市道路網(wǎng)的結(jié)構(gòu)特征,不能直接用于街區(qū)合并簡化。目前尚缺少針對城市道路格網(wǎng)模式保持的街區(qū)合并優(yōu)化模型。本文從格網(wǎng)模式的提取和保持入手,構(gòu)建相應(yīng)的目標(biāo)函數(shù)和約束條件,建立規(guī)劃模型。通過求模型最優(yōu)解,在街區(qū)合并過程中實現(xiàn)對道路格網(wǎng)模式的保持,以滿足多尺度制圖綜合的需要。

2 道路格網(wǎng)模式的識別和特征分析

由于道路街區(qū)合并的目標(biāo)是保持格網(wǎng)模式的形態(tài)和排列規(guī)則性,首先需要從原始道路網(wǎng)中檢測出具有格網(wǎng)模式的街區(qū)(多邊形)。根據(jù)街區(qū)合并建模的需要,本文的格網(wǎng)檢測規(guī)則有兩點(diǎn):

(1)緊密度。表示多邊形形狀的緊密程度,多邊形的輪廓越復(fù)雜,緊密度越低。其計算公式為

緊密度的值域是(0,1],其中緊密度最高的為圓形,格網(wǎng)街區(qū)也應(yīng)具有較高的緊密度。該指標(biāo)主要用于排除主干道中的長條多邊形。

(2)正交度。格網(wǎng)街區(qū)的邊界方向大多相互正交,導(dǎo)致出現(xiàn)例如圖1所示的矩形和弓形兩種街區(qū)形態(tài)。其中矩形街區(qū)反映格網(wǎng)模式的并列關(guān)系,而弓形街區(qū)反映包含關(guān)系。本文提出的正交度表示為多邊形邊界中正交道路占全部道路的比例。首先通過鄰邊比較遍歷多邊形的所有內(nèi)角,當(dāng)內(nèi)角接近90°、180°和270°時,則將鄰邊聚為一類。為識別路網(wǎng)中變形的格網(wǎng)街區(qū),可通過放松夾角閾值調(diào)整聚類結(jié)果,本文將其設(shè)為±15°。在道路聚類的基礎(chǔ)上,正交度計算公式為

式中,ci(i＝1,2,…,n)表示多邊形的任一道路聚類;分子部分表示長度之和最大的道路聚類,而分母表示全部道路之和,即多邊形的周長。正交度越大,表示多邊形的格網(wǎng)模式特征越明顯。

圖1 常見的格網(wǎng)街區(qū)結(jié)構(gòu)Fig．1 Common grid blocks structures

以上兩點(diǎn)不僅是格網(wǎng)模式的檢測規(guī)則,也是街區(qū)合并之后格網(wǎng)模式保持的評價規(guī)則。其中無論格網(wǎng)如何合并,街區(qū)的邊界總是正交,因此重點(diǎn)是保持街區(qū)緊密度。此外格網(wǎng)模式還具有排列規(guī)則性和形態(tài)特征[6-7]。其中排列規(guī)則性指格網(wǎng)街區(qū)通常規(guī)則地排成行列,而形態(tài)特征指在合并過程中應(yīng)盡量保持格網(wǎng)模式的長寬比值。這需要避免只刪除單一方向的道路,而是同時在長寬兩個方向上刪除道路。因此本文也將其稱為合并的方向性。圖2為不同簡化方案對于格網(wǎng)模式保持的示意圖。假設(shè)原始數(shù)據(jù)為4×4標(biāo)準(zhǔn)方格網(wǎng),方案1的合并結(jié)果具有最大的緊密度,并且保持了排列規(guī)則性和合并方向性。而后3種方案都無法同時保持格網(wǎng)模式的這3點(diǎn)特征。其中排列規(guī)則性評價為合并后相鄰街區(qū)中心連線與公共邊界的夾角。如圖2中的虛線段表示相鄰格網(wǎng)中心點(diǎn)的連線,排列規(guī)則性需要保持中心點(diǎn)連線與格網(wǎng)公共邊界道路盡可能的垂直。本文的街區(qū)合并優(yōu)化模型通過設(shè)定評價函數(shù)量化各種格網(wǎng)模式,同時綜合考慮被合并街區(qū)用地類型的相似性以及被刪除道路的重要性,求解優(yōu)化的合并結(jié)果。

圖2 格網(wǎng)街區(qū)合并方案示意圖Fig．2 Example of grid-like blocks aggregation plans

3 格網(wǎng)街區(qū)合并混合整數(shù)規(guī)劃模型

3．1 目標(biāo)函數(shù)

在建立目標(biāo)函數(shù)對格網(wǎng)模式進(jìn)行量化之前,首先定義變量xuv∈{0,1}指示道路網(wǎng)中的街區(qū)u與v是否合并。其中街區(qū)u定義為合并的中心街區(qū),當(dāng)v同u合并時,xuv＝1,否則xuv＝0。規(guī)定xuv＝xvu及xuu＝1,可將變量數(shù)目減少一半,提高計算效率。目標(biāo)函數(shù)根據(jù)變量xuv建立格網(wǎng)模式保持的優(yōu)化函數(shù)關(guān)系。通過求解使目標(biāo)函數(shù)達(dá)到極值的xuv,便能得到街區(qū)合并結(jié)果。本文的目標(biāo)函數(shù)為5個評價準(zhǔn)則函數(shù)之和,包括用地類型相似性、街區(qū)緊密性、道路重要性、格網(wǎng)排列規(guī)則性和合并方向性。其中用地類型相似性和街區(qū)緊密性是一般性地塊合并模型中都需要考慮的評價準(zhǔn)則[14];道路重要性是本文針對于城市道路網(wǎng)整體結(jié)構(gòu)特征保持所提出的評價準(zhǔn)則;而格網(wǎng)排列規(guī)則性和合并方向性則是針對于道路網(wǎng)中的格網(wǎng)模式保持進(jìn)一步提出的評價準(zhǔn)則。每個評價準(zhǔn)則的具體含義闡述如下。

3．1．1 用地類型相似性評價

街區(qū)合并首先需要考慮合并之后用地類型的語義信息變化,相似類型的街區(qū)被合并的可能性更高[15]。本文將城市區(qū)域分為6種用地類型,包括水體、居民地、工業(yè)用地、農(nóng)業(yè)用地、草地和森林。其中水體邊界不被刪除,而其他用地類型之間的合并代價如表1所示[14]。用地類型相似性評價函數(shù)計算公式如下

式中,街區(qū)u、v∈P,P為多邊形的集合;Cuv表示街區(qū)u和v之間的合并代價;Av表示街區(qū)v的面積。該函數(shù)通過使面積加權(quán)合并代價最小化,從語義層面引導(dǎo)用地類型相似的街區(qū)優(yōu)先合并。

表1 合并代價矩陣Tab．1 Aggregation costs matrix

3．1．2 街區(qū)緊密性評價

城市街區(qū)合并后一般很少出現(xiàn)復(fù)雜形狀的街區(qū),需要建立評價函數(shù)使合并后街區(qū)的緊密度之和最大化。由于式(1)計算的緊密度為非線性函數(shù),難以計算模型最優(yōu)解,本文建立近似的線性函數(shù)評價合并后街區(qū)的緊密度之和。文獻(xiàn)[14]已證明當(dāng)合并尺度確定時,被保留的道路長度越小,則合并后街區(qū)的緊密度就越高。因此本文的緊密性評價函數(shù)表示為合并后保留道路長度最小化,如式(4)所示。

式中,Luv表示街區(qū)u與v之間公共道路邊界的長度,如果街區(qū)u與v之間沒有公共道路,則lengthuv＝0。而(1－xuv)表示道路是否被刪除。該評價函數(shù)使得模型更傾向于得到使街區(qū)形狀簡單緊湊的街區(qū)合并方案。

3．1．3 道路重要性評價

道路街區(qū)的合并還應(yīng)保持道路網(wǎng)的整體結(jié)構(gòu)特征,主要表現(xiàn)為道路的重要性[8-9]。重要性高的道路應(yīng)當(dāng)被優(yōu)先保留,這樣可以反映城市區(qū)域的框架形態(tài)。根據(jù)格式塔原理,道路重要性評價通常以路劃(stroke)作為基本評價單位。路劃定義為由多條平滑道路鏈組成的長道路[16]。路劃的長度越長,重要性越高,對體現(xiàn)道路網(wǎng)整體結(jié)構(gòu)特征的作用也越大[17]。因此本文的道路重要性評價準(zhǔn)則為使刪除的路劃長度最小化,即避免在街區(qū)合并過程中刪除長路劃。其中路劃通過同名道路和平滑道路夾角進(jìn)行提取。引入變量ys∈{0, 1}表示第s條路劃是否被刪除,當(dāng)被刪除時ys＝1。刪除路劃長度最小化評價函數(shù)的計算公式如下

式中,路劃s∈S,S為所有路劃的集合;Ls表示路劃s的長度。而變量ys與xuv的關(guān)系可以表述為

式中,euv∈E表示街區(qū)u與v之間公共道路,體現(xiàn)了道路與街區(qū)之間的拓?fù)潢P(guān)系,E為所有的道路邊集合;strs(euv)∈{0,1}為常量,表示道路euv是否屬于路劃s。如果euv屬于路劃s,則strs(euv)＝1;當(dāng)u與v之間公共道路e不屬于路劃s,或者u與v之間不存在公共道路時,則strs(euv)＝0。式(6)可以保證在計算式(5)時,同一條被刪除路劃的長度只被計算一次。

3．1．4 排列規(guī)則性評價

以上3點(diǎn)特征評價準(zhǔn)則適用于所有道路街區(qū)。但對于道路格網(wǎng)街區(qū),還需建立排列規(guī)則性的評價函數(shù)保持格網(wǎng)模式。由前節(jié)所述需要保持合并后街區(qū)的中心點(diǎn)連線與格網(wǎng)公共邊界道路盡可能的垂直。本文通過計算合并前街區(qū)中心點(diǎn)連線與公共邊界道路夾角余弦的面積加權(quán)之和,構(gòu)建線性函數(shù)進(jìn)行近似計算。定義i、j表示任意街區(qū),euv為u、v街區(qū)的公共道路,ij和euv分別表示以街區(qū)i和j的中心點(diǎn)為起止點(diǎn)的向量和道路euv起止點(diǎn)構(gòu)成的向量,夾角余弦計算公式如下ij和euv的垂直度越高,則cos(ij,euv)越接近0。排列規(guī)則的格網(wǎng)此夾角余弦應(yīng)盡量小,因此排列一致性評價函數(shù)計算公式為

式中,PG表示所有識別出的格網(wǎng)街區(qū)集合;EG表示格網(wǎng)街區(qū)的公共邊界集合,這兩個集合可在格網(wǎng)識別過程中建立;zeij∈{0,1}為新定義的變量,表示i、j、u、v四個格網(wǎng)街區(qū)之間的關(guān)系。當(dāng)且僅當(dāng)i與u合并,且j與v合并時,即當(dāng)xui和xvj同時等于1時,zeij＝1,否則為0。該規(guī)則可由式(9)得到保證

圖3 排列方向計算示意圖Fig．3 Example of arrangement calculation

3．1．5 合并方向性評價

對于格網(wǎng)街區(qū)還應(yīng)當(dāng)盡量在長寬兩個方向上刪除道路。本文計算簡化前所有格網(wǎng)街區(qū)長寬方向道路長度比值,將合并方向性評價函數(shù)定義為合并前后的長寬比值差異最小化,計算公式如下

式中,E1和E2分別表示簡化前格網(wǎng)街區(qū)在兩個正交方向上的道路集合,可在格網(wǎng)識別中計算正交度時求得。r0表示簡化前的正交方向比值。最優(yōu)的格網(wǎng)合并方案應(yīng)當(dāng)盡量使式(10)取值最小,這樣便能保持合并前后正交方向道路長度的比值關(guān)系。

根據(jù)每個評價函數(shù)的定義,通過將公式中的變量xuv、ys、zeij去除后的求和結(jié)果作為分母對各個評價函數(shù)進(jìn)行歸一化,將上述五項評價函數(shù)的值域歸一化為[0,1]。最終的目標(biāo)函數(shù)為5個評價函數(shù)之和。可以看出對于非格網(wǎng)街區(qū),其排列規(guī)則性和合并方向性評價函數(shù)均為零。路網(wǎng)中的格網(wǎng)街區(qū)比例越大,則后兩個評價函數(shù)所占的比重也就越大。因此,雖然本文模型主要適用于格網(wǎng)街區(qū)的合并,但對于城市范圍內(nèi)其他類型的街區(qū),也可簡化為只依靠前三項評價函數(shù)進(jìn)行建模。

3．2 約束條件

3．2．1 合并尺度約束

為使街區(qū)進(jìn)行合并,但又不出現(xiàn)過度合并,應(yīng)當(dāng)設(shè)定合并后的最小和最大面積閾值。合并尺度約束公式如下

式中,Amin和Amax分別表示街區(qū)合并的最小和最大面積閾值;max(Amax,Au)表示如果街區(qū)u的面積在合并之前就已經(jīng)大于Amax,則不對其進(jìn)行合并,如果Amin和Amax之間出現(xiàn)沖突,例如一個面積小于Amin的街區(qū)僅與一個面積大于Amax的街區(qū)相鄰,則這兩個街區(qū)無論合并與否都不能同時滿足公式(11)中的兩個約束條件。因此設(shè)置寬松項δ和步長k∈{0,1,2,…,n},當(dāng)面積閾值沖突時逐步放大最大閾值直至沖突解決。本文將δ設(shè)為最小面積閾值A(chǔ)min。

最小面積閾值A(chǔ)min可根據(jù)地圖中最小可視元(smallest visible object,SVO)進(jìn)行設(shè)定。SVO的面積受線劃寬度、街區(qū)內(nèi)含建筑物等多方面影響,需參照具體制圖規(guī)范,或根據(jù)經(jīng)驗和數(shù)據(jù)分析確定[18]。簡便起見,本文認(rèn)為已有的初始尺度數(shù)據(jù)中的最小街區(qū)為該尺度下的SVO。而目標(biāo)尺度下最小面積閾值A(chǔ)min則設(shè)為初始尺度SVO面積乘以簡化前后比例尺變化率的平方,如式(12)所示。

例如本文街區(qū)合并的目標(biāo)是由1∶25 000簡化至1∶100 000,比例尺變化率為4,表示地圖上SVO的長度擴(kuò)大4倍,則最小面積閾值為當(dāng)前SVO面積的16倍。

最大面積閾值A(chǔ)max設(shè)為與區(qū)域內(nèi)所有街區(qū)面積均值成正比,如式(13)所示。

3．2．2 路劃刪除約束

根據(jù)道路等級性評價準(zhǔn)則,在街區(qū)合并過程中應(yīng)以路劃為基本單位,保持路劃整體刪除或者保留,防止破壞道路形態(tài)。路劃刪除約束公式如下

式(14)表示當(dāng)?shù)缆范蝒u1v1、eu2v2、…、eukvk都屬于同一條路劃STRs時,則這些路段兩側(cè)的街區(qū)將被同時合并或保留。如果刪除路劃的某段會導(dǎo)致格網(wǎng)面積大與最大閾值時,可以保留該段道路。

3．2．3 道路聯(lián)動刪除約束

如圖4所示,當(dāng)相鄰街區(qū)v和w分別和街區(qū)u合并,那么街區(qū)v和w之間的公共邊界(虛線道路)也應(yīng)當(dāng)被聯(lián)動刪除,聯(lián)動刪除的計算公式如下

式(15)能夠保證3個相關(guān)變量xuv、xuw、xvw不會出現(xiàn)兩個取值為1,一個為0的情況,從而保證了道路刪除的聯(lián)動性。

圖4 道路聯(lián)動刪除示意圖Fig．4 Example of conjoint road deletion

3．2．4 連通性約束

街區(qū)合并過程還需要保證合并街區(qū)的連通性,即不存在隔空合并。本文根據(jù)流模型建立約束條件,基本原則如圖5所示[19]。其中非中心街區(qū)用細(xì)圓圈表示,初始量設(shè)為1;粗圓圈為指定的某個中心街區(qū),表示所有流的最終匯入點(diǎn),無初始量。箭頭表示自由構(gòu)建的連通流。每個非中心街區(qū)都有且只有一個輸出流,流量大小等于輸入流加上街區(qū)自身的初始量;而中心街區(qū)只有輸入流,最終的匯入量不超過非中心街區(qū)數(shù)。如果合并后的街區(qū)中構(gòu)建的流模型滿足上述約束條件,則認(rèn)為街區(qū)合并是連通的。

圖5 連通性約束示意圖Fig．5 Example of connectivity constrain

為構(gòu)建流模型,引入新的非負(fù)的連續(xù)變量tuvw,表示當(dāng)u為中心街區(qū)時,街區(qū)v向鄰接街區(qū)w的輸出流。同理tuwv則表示來自街區(qū)w流向v的輸入流,連通性約束條件如式(16)—式(18)所示。

式中,M是一個非負(fù)整數(shù),表示合并過程中所允許的最大街區(qū)數(shù)。如果M設(shè)為所有街區(qū)總數(shù),表示無街區(qū)合并數(shù)的約束,式(18)可以刪除。xuv的定義與之前一致,用于表示街區(qū)v與u是否合并。式(16)表達(dá)了每個非中心格網(wǎng)v的凈流量,等式左邊的兩項分別表示格網(wǎng)v的總輸出流和總輸入流。如果格網(wǎng)v與中心格網(wǎng)u合并,那么xuv＝1,則總凈流量必須等于1,表示流模型中與v連通的所有上級街區(qū)都被輸送到下一級街區(qū)。式(17)表示每個非中心街區(qū)v的總輸入流不能超過M－2,即允許合并的最大街區(qū)數(shù)減去自身和中心街區(qū)u。式(18)表示中心街區(qū)u的總輸入流不能超過最大街區(qū)數(shù)減去自身。結(jié)合式(16)和式(17)可知,如果街區(qū)v不與u合并,則街區(qū)v的輸入流和輸出流都為零,即沒有未合并的街區(qū)流入合并集合中,也沒有合并集中的街區(qū)流出到集合外。

3．3 模型求解

本文的街區(qū)合并模型中的變量分別為xuv、yi、zeij和tuvw,其中前三項的值域為0－1整數(shù),tuvw為非負(fù)實數(shù)。所有的評價函數(shù)和約束函數(shù)都是線性函數(shù),其中式(8)和式(10)中絕對值可以轉(zhuǎn)化成線性形式。因此本文所構(gòu)建的模型屬于混合整數(shù)規(guī)劃模型(mixed integer programming, MIP)。常用的混合整數(shù)規(guī)劃模型的求解方法是“分支約束”的方法。本文采用該方法,通過使用IBM ILOG CPLEX軟件求解混合整數(shù)規(guī)劃模型。該軟件運(yùn)算性能高,支持多CPU,并且算法穩(wěn)健,對模型中方程和變量數(shù)目的支持能力僅取決于計算機(jī)的硬件水平。

4 高等級道路提取和路網(wǎng)分區(qū)

在道路選取過程中除了保持格網(wǎng)模式特征之外,還需要保證高等級道路在街區(qū)合并時不能被刪除,即保持道路網(wǎng)主干道的整體結(jié)構(gòu)特征。高等級道路還能間接保持道路網(wǎng)中一些其他結(jié)構(gòu)模式。例如放射狀結(jié)構(gòu)是道路網(wǎng)中一種比整體結(jié)構(gòu)更概括的特征結(jié)構(gòu),可以在高等級道路和城市中心模式識別的基礎(chǔ)上進(jìn)行提取[1,3]。二者存在一種包含關(guān)系,保持了道路的骨架結(jié)構(gòu)也就間接保持了放射狀結(jié)構(gòu)。當(dāng)放射狀結(jié)構(gòu)尺度較小時,則可根據(jù)前面所提的道路重要性評價準(zhǔn)則優(yōu)先選取長路劃進(jìn)行控制。

本文使用中介中心性(betweenness centrality, BC)提取道路網(wǎng)的高等級道路。該指標(biāo)能夠較全面地反映道路網(wǎng)的整體結(jié)構(gòu)特征[20-21]。BC定義為某條道路被任意兩條連通道路之間的最短連通路徑所經(jīng)過的次數(shù),反映了道路被其他道路所依賴的程度[22]。BC值越大,道路的重要性越高。BC值具有指數(shù)分布特征,少量道路具有極高的BC值,可以通過設(shè)定閾值選取高等級道路,構(gòu)造道路網(wǎng)的整體結(jié)構(gòu)特征?；诘缆肪W(wǎng)整體結(jié)構(gòu),還可將城市劃分為多個區(qū)域,對每個分區(qū)內(nèi)部分別進(jìn)行建模。既保持了道路網(wǎng)整體結(jié)構(gòu)不被破壞,又減少了合并模型的復(fù)雜度。由于模型以路劃為取舍單位,當(dāng)一條路劃穿過多個分區(qū)時,則將這些分區(qū)作為一個整體進(jìn)行建模,保證各個分區(qū)內(nèi)部的道路選取互不干擾。

5 試驗結(jié)果與分析

試驗數(shù)據(jù)使用德國漢諾威ATKIS-DLM 1∶25 000的數(shù)據(jù),將尺度綜合至1∶100 000。經(jīng)過數(shù)據(jù)預(yù)處理的結(jié)果如圖6所示,黑色道路表示的是根據(jù)BC＞100 000選取的高等級道路,其中粗線表示人工從中選取的放射狀結(jié)構(gòu)?？梢钥闯龈叩燃壍缆纺軌蝮w現(xiàn)出道路網(wǎng)的整體結(jié)構(gòu)和隱含的結(jié)構(gòu)形態(tài)。灰色街區(qū)表示的是根據(jù)緊密度和正交度識別出來的格網(wǎng)模式,閾值分別為0．45和0．7。可以看出格網(wǎng)街區(qū)在城市道路網(wǎng)中的普遍性。利用高等級道路對道路網(wǎng)進(jìn)行分區(qū),然后對每個區(qū)域單獨(dú)進(jìn)行街區(qū)合并建模。原始數(shù)據(jù)中最小街區(qū)面積約為150 m2,則areamin參數(shù)設(shè)置為2400 m2。areamax中的f根據(jù)經(jīng)驗設(shè)為3．5,表示每個分區(qū)內(nèi)街區(qū)合并的面積上限是平均面積的3．5倍。

圖6 道路格網(wǎng)識別與分區(qū)(BC＞100 000)Fig．6 Grid-like blocks recognition and partition(BC＞100 000)

圖7為綜合各個分區(qū)街區(qū)合并之后得到的街區(qū)合并結(jié)果以及與同時期德國1∶100 000地形圖的比較,其中街區(qū)合并之后長度小于300 m的懸掛道路被刪除。各個用地類型用不同顏色表示,黑色道路表示兩份數(shù)據(jù)中都被保留的道路,而灰色表示都被刪除的道路;黑色虛線道路表示本文結(jié)果比已有圖多出的道路,而灰色虛線道路表示已有圖比本文結(jié)果多出的道路。首先從直觀分析可以看出本文的道路選取結(jié)果很好地保持了道路網(wǎng)整體的城市結(jié)構(gòu)、局部的格網(wǎng)排列一致性以及區(qū)域之間的密度差別。

圖7 道路選取結(jié)果及與已有圖比較Fig．7 Roads selection results compared with existing map

與圖7相對應(yīng),對本文試驗結(jié)果中保留與舍棄的道路以及兩種原始數(shù)據(jù)中的道路長度進(jìn)行統(tǒng)計。統(tǒng)計結(jié)果如表2所示。

表2 選取結(jié)果對比統(tǒng)計Tab．2 Statistics of comparison between selected result and existing maps m

從統(tǒng)計數(shù)據(jù)分析發(fā)現(xiàn)本文模型具有以下特點(diǎn):

(1)本文試驗結(jié)果與已有的地圖數(shù)據(jù)相比,正確率和查全率都較高,說明本文模型與人工的道路選取結(jié)果基本相符。

(2)統(tǒng)計發(fā)現(xiàn)本文模型未刪除的道路(黑色虛線道路)要明顯多于本文模型多刪除的道路(灰色虛線道路)。部分未刪除道路由于兩側(cè)街區(qū)面積較大,或路劃長度較長,受面積或路劃長度約束未進(jìn)行合并。這部分道路主要位于草地、森林和農(nóng)業(yè)用地中,約占未刪除道路總數(shù)的37%,因為道路重要性較低而被人工刪除,另有部分未刪除道路作為某些長路劃的一部分被整體保留。而在人工選取中考慮到語義信息,部分刪除了一些路劃。這部分道路主要位于居民地街區(qū)中,約占未刪除道路總數(shù)的29%。這種差異主要是由于地圖簡化規(guī)則不同。本文模型保留的這些道路不會影響地圖的可讀性,還保持了地圖的信息量。因此認(rèn)為本模型在這些道路的保留上也是合理的。

(3)本文模型在某些區(qū)域保留了一些人工刪除的道路,卻刪除了一些人工保留的道路,模型構(gòu)造的街區(qū)形態(tài)與已有數(shù)據(jù)存在差異。這部分道路主要分布在居民地街區(qū)中,約占未刪除道路總數(shù)的22%。但是相應(yīng)的多刪除道路卻占到多刪除道路總數(shù)的91%,說明本文模型產(chǎn)生的多刪除道路主要產(chǎn)生于此。差異產(chǎn)生的原因需分析具體的合并細(xì)節(jié)。同時,為了展示本文模型的評價和約束規(guī)則對格網(wǎng)模式保持的影響,本文還與文獻(xiàn)[14]中的地塊合并模型進(jìn)行了細(xì)節(jié)對比。該模型僅使用緊密度和用地類型相似性作為目標(biāo)函數(shù),未考慮道路網(wǎng)的結(jié)構(gòu)特點(diǎn)。圖8展示了3塊區(qū)域的比較,其中圖8(a)是較規(guī)則格網(wǎng)區(qū)域,圖8(b)是有道路彎曲的變形格網(wǎng)區(qū)域,圖8(c)的結(jié)構(gòu)則較復(fù)雜,只有在合并之后才能呈現(xiàn)格網(wǎng)形態(tài)。

對于圖8(a)的規(guī)則格網(wǎng)區(qū)域,3種合并結(jié)果在街區(qū)面積變化、形狀變化和數(shù)目變化都相似,而且都大體保持了街區(qū)格網(wǎng)模式。這是因為規(guī)則格網(wǎng)區(qū)域中無論如何合并總能保持道路正交,但是由于缺少格網(wǎng)排列評價準(zhǔn)則,一般的地塊合并模型不如本文模型合并的街區(qū)排列規(guī)則。對于圖8(b)和8 (c)的變形和復(fù)雜格網(wǎng)區(qū)域,一般的地塊合并模型已經(jīng)無法保證合并街區(qū)的形態(tài),而本文模型能夠較好保持住合并后街區(qū)的規(guī)則排列和長寬比形態(tài)。

本文模型與已有數(shù)據(jù)中的人工選取結(jié)果相比,二者都保持了道路網(wǎng)的結(jié)構(gòu)形態(tài)。主要差異在于本文模型保留了區(qū)域中的長路劃。由于保留的更多的道路,本文合并后的街區(qū)面積要小于人工選取結(jié)果,但保留的道路看上去更加連貫。而人工選取則體現(xiàn)出一種更加復(fù)雜的道路網(wǎng)結(jié)構(gòu)感知,體現(xiàn)了地圖綜合的多樣性和復(fù)雜性。雖然存在部分差異,但是相比手工選取,自動的道路選取方法效率更高。因為人工進(jìn)行選取時,需經(jīng)常檢查道路的整體和局部模式特征,效率很低。因此本文模型對于提高地圖生產(chǎn)效率和質(zhì)量具有重要的作用。

圖8 不同合并模型比較Fig．8 Comparison of different aggregation models

6 結(jié)束語

本文針對城市道路網(wǎng)的結(jié)構(gòu)模式特征,在格網(wǎng)模式保持分析的基礎(chǔ)上,提出了一種保持區(qū)域格網(wǎng)模式特征的街區(qū)合并模型。試驗分析表明,本文模型通過建立街區(qū)合并的特征評價函數(shù)和約束規(guī)則能夠保持街區(qū)所具有的格網(wǎng)模式特征。通過與人工道路選取的地圖的對比分析,發(fā)現(xiàn)本文的方法得到的道路選取能較好地反映道路網(wǎng)的模式特征,正確率高于90%。但是由于本文方法主要從道路網(wǎng)的模式結(jié)構(gòu)保持的角度出發(fā),只研究了道路網(wǎng)數(shù)據(jù),尚未考慮與道路網(wǎng)存在關(guān)聯(lián)和依賴關(guān)系的其他數(shù)據(jù),例如地形、建筑物、城市設(shè)施等,使得本文方法和人工的道路選取結(jié)果不可避免地存在差異性。考慮如何利用語義信息合并模型進(jìn)行優(yōu)化是后續(xù)的研究工作的重點(diǎn)。

[1] ZHANG Q N．Modeling Structure and Patterns in RoadNetwork Generalization[C]∥Proceedings of ICA Workshop on Generalization and Multiple Representation．Leicester:[s．n．],2004．

[2] HEINZLE F,ANDERS K H,SESTER M．Graph Based Approaches for Recognition of Patterns and Implicit Information in Road Networks[C]∥Proceedings of XXII International Cartographic Conference．La Coruna:[s．n．],2005．

[3] HEINZLE F,ANDERS K H,SESTER M．Pattern Recognition in Road Networks on the Example of Circular Road Detection[C]∥Geographic Information Science:Proceedings of 4th International Conference on GIScience．Münster: Springer,2006:153-167．

[4] HEINZLE F,ANDERS K H．Characterising Space via Pattern Recognition Techniques:Identifying Patterns in Road Networks[C]∥The Generalisation of Geographic Information:Cartographic Modelling and Applications [M]．Amsterdam:Elsevier,2007:233-253．

[5] YANG Bisheng,LUAN Xuechen．An Automated Method for Structural Pattern Recognition of Road Networks[J]．Journal of Image and Graphics,2009,14(7):1251-1255．(楊必勝,欒學(xué)晨．城市道路網(wǎng)幾何結(jié)構(gòu)模式的自動識別方法[J]．中國圖象圖形學(xué)報,2009,14(7):1251-1255．)

[6] YANG B S,LUAN X C,LI Q Q．An Adaptive Method for Identifying the Spatial Patterns in Road Networks[J]．Computers,Environment and Urban Systems,2010,34 (1):40-48．

[7] TIAN Jing,AI Tinghua,DING Shaojun．Grid Pattern Recognition in Road Networks Based on C4．5 Algorithm [J]．Acta Geodaetica et Cartographica Sinica,2012,41(1): 121-126．(田晶,艾廷華,丁紹軍．基于C4．5算法的道路網(wǎng)網(wǎng)格模式識別[J]．測繪學(xué)報,2012,41(1):121-126．)

[8] TOUYA G．A Road Network Selection Process Based on Data Enrichment and Structure Detection[J]．Transactions in GIS,2010,14(5):595-614．

[9] JIANG B,CLARAMUNT C．A Structural Approach to the Model Generalization of an Urban Street Network[J]．GeoInformatica,2002,8(2):157-171．

[10] PORTA S,CRUCITTI P,LATORA V．The Network Analysis of Urban Streets:A Dual Approach[J]．Physica A: Statistical Mechanics and Its Applications,2006,369(2): 853-866．

[11] YANG B S,LUAN X C,Li Q Q．Generating Hierarchical Strokes from Urban Street Networks Based on Spatial Pattern Recognition[J]．International Journal of Geographical Information Science,2011,25(12): 2025-2050．

[12] HU Yungang,CHEN Jun,LI Zhilin,et al．Selective Omission of Road Features Based on Mesh Density for Digital Map Generalization[J]．Acta Geodaetica et Cartographica Sinica,2007,36(3):351-357．(胡云崗,陳軍,李志林,等．基于網(wǎng)眼密度的道路選取方法[J]．測繪學(xué)報,2007,36(3):351-357．)

[13] YANG Bisheng,ZHANG Yunfei,LUAN Xuechen．Pattern Preserving Method for Grid Simplification in Road Networks[J]．Journal of Image and Graphics,2012,17 (1):150-156．(楊必勝,張云菲,欒學(xué)晨．保持幾何模式的城市道路格網(wǎng)簡化方法[J]．中國圖象圖形學(xué)報,2012, 17(1):150-156．)

[14] HAUNERT J H,WOLFF A．Area Aggregation in Map Generalisation by Mixed-integer Programming[J]．International Journal of Geographical Information Science,2010, 24(12):1871-1897．

[15] LIU Y L,MOLENAAR M,KRAAK M J．Semantic Similarity Evaluation Model in Categorical Database Generalization [R]∥Proceedings of the International Archives of the Photogrammetry,Remote Sensing and Spatial Information Sciences．Ottawa:ISPRS,2002:279-285．

[16] XU Zhu,LIU Caifeng,ZHANG Hong,et al．Road Selection Based on Evaluation of Stroke Network Functionality[J]．Acta Geodaetica et Cartographica Sinica,2012,41(5): 769-776．(徐柱,劉彩鳳,張紅,等．基于路劃網(wǎng)絡(luò)功能的道路選取方法[J]．測繪學(xué)報,2012,41(5):769-776．)

[17] THOMSON R C．The‘Stroke’Concept in Geographic Network Generalization and Analysis[C]∥Progress in Spatial Data Handling:12th International Symposium on Spatial Data Handling．Vienna:[s．n．],2006:681-697．

[18] CHEN J,HU Y G,LI Z L,et al．Selective Omission of Road Features Based on Mesh Density for Automatic Map Generalization[J]．International Journal of Geographical Information Science,2009,23(8):1013-1032．

[19] SHIRABE T．A Model of Contiguity for Spatial Unit Allocation [J]．Geographical Analysis,2005,37(1):2-16．

[20] LI Qingquan,ZENG Zhe,YANG Bisheng,et al．Betweenness Centrality Analysis for Urban Road Networks[J]．Geomatics and Information Science of Wuhan University, 2010,35(1):37-41．(李清泉,曾喆,楊必勝,等．城市道路網(wǎng)絡(luò)的中介中心性分析[J]．武漢大學(xué)學(xué)報:信息科學(xué)版,2010,35(1):37-41．)

[21] TOMKO M,WINTER S,CLARAMUNT C．Experiential Hierarchies of Streets[J]．Computers,Environment and Urban Systems,2008,32(1):41-52．

[22] FREEMAN L C．Centrality in Social Networks:Conceptual Clarification[J]．Social Networks,1979,1(3):215-239．

(責(zé)任編輯:叢樹平)

A Mixed Integer Programming Model of Block Aggregation for Grid Pattern Maintenance in Urban Network

LUAN Xuechen1,2,3,YANG Bisheng1,2,LI Qiuping4
1．State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University, Wuhan 430079,China;2．Engineering Research Center for Spatio-temporal Data Smart Acquisition and Application, Wuhan University,Wuhan 430079,China;3．Guangdong Ritu Information Systems Co Ltd,Foshan 528305,China; 4．Center of Integrated Geographic Information Analysis,School of Geography and Planning,Sun Yat-sen University, Guangzhou 510275,China

A model for urban blocks aggregation is presented,aiming to maintain grid pattern after road selection．It firstly detects the grid pattern from road network to determine the application ranges of proposed model．Then it defines the objective function to quantify the grid pattern maintenance,as well as four constraints to ensure effective and efficient aggregation for the target scale．The objective function is composed of five evaluations namely block compactness, land use similarity,road significance,grids arrangement consistence and aggregating directionality,and the four constraints are aggregating scale,stroke deletion,conjoint aggregation and connectivity constraints．Finally,the whole urban road network are divided into several subregions with high-level roads,and the aggregation problem are decomposed into independent subinstances to model to maintain the global structure of the road network．The mixed-integer programming model can be solved by optimization software CPLEX．The proposed method is tested for a dataset of the official German topographic database ATKIS with input scale 1∶25 000 and output scale 1∶100 000．The results of this model are compared with existing map data and the general aggregation model regardless the grid pattern maintenance．It can be concluded that this optimization method yields high-quality results for grid patterns maintenance．

map generalization,urban street network,grid pattern,optimization model

LUAN Xuechen(1985—),male,PhD, majors in spatial data LoD modeling．

YANG Bisheng

P208

A

1001-1595(2014)04-0426-09

2013-01-21

欒學(xué)晨(1985—),男,博士,研究方向為空間數(shù)據(jù)多尺度建模。

E-mail:luanxuechen＠gmail．com

楊必勝

E-mail:bshyang＠whu．edu．cn

LUAN Xuechen,YANG Bisheng,LI Qiuping．A Mixed Integer Programming Model of Block Aggregation for Grid Pattern Maintenance in Urban Network[J]．Acta Geodaetica et Cartographica Sinica,2014,43(4):426-434．(欒學(xué)晨,楊必勝,李秋萍．保持城市道路格網(wǎng)模式的街區(qū)合并混合整數(shù)規(guī)劃模型[J]．測繪學(xué)報,2014,43(4):426-434．)

10．13485/j．cnki．11-2089．2014．0063

國家863計劃(2012AA12A211;2012AA12A204);廣東省戰(zhàn)略性新興產(chǎn)業(yè)發(fā)展專項資金(高端新型電子信息)(2011168036);教育部博士研究生學(xué)術(shù)新人獎(5052011619019)

關(guān)鍵詞:制圖綜合;城市道路網(wǎng);格網(wǎng)模式;優(yōu)化模型

修回日期:2013-05-24