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

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

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

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

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

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

1 引 言

道路選取對(duì)于路網(wǎng)制圖綜合、多尺度表達(dá),以及道路等級(jí)分析都具有重要意義。被選取的道路不僅應(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ò)分析道路的重要性、劃分道路等級(jí)并提取主干道[9-11]。但是該類方法的道路選取結(jié)果過于簡(jiǎn)化,屬于城市整體結(jié)構(gòu),難以滿足多尺度表達(dá)的需要;而街區(qū)合并方法則考慮街區(qū)密度、幾何、語(yǔ)義等屬性,通過局部漸進(jìn)式方法刪除街區(qū)邊界道路、合并道路街區(qū),減少道路密度[12-13]。該類方法能在每次迭代中保持合并后道路街區(qū)的形態(tài)特點(diǎn),但每次合并只考慮兩個(gè)街區(qū),對(duì)于解決多街區(qū)合并的形態(tài)保持問題尚有所不足。另外由于制圖綜合需求的復(fù)雜性,街區(qū)合并可能存在多種合理結(jié)果,局部合并方法缺少整體合并效果的評(píng)價(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)。但是該方法的研究對(duì)象是土地利用地圖數(shù)據(jù),未考慮城市道路網(wǎng)的結(jié)構(gòu)特征,不能直接用于街區(qū)合并簡(jiǎn)化。目前尚缺少針對(duì)城市道路格網(wǎng)模式保持的街區(qū)合并優(yōu)化模型。本文從格網(wǎng)模式的提取和保持入手,構(gòu)建相應(yīng)的目標(biāo)函數(shù)和約束條件,建立規(guī)劃模型。通過求模型最優(yōu)解,在街區(qū)合并過程中實(shí)現(xiàn)對(duì)道路格網(wǎng)模式的保持,以滿足多尺度制圖綜合的需要。

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

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

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

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

(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°時(shí),則將鄰邊聚為一類。為識(shí)別路網(wǎng)中變形的格網(wǎng)街區(qū),可通過放松夾角閾值調(diào)整聚類結(jié)果,本文將其設(shè)為±15°。在道路聚類的基礎(chǔ)上,正交度計(jì)算公式為

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

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

以上兩點(diǎn)不僅是格網(wǎng)模式的檢測(cè)規(guī)則,也是街區(qū)合并之后格網(wǎng)模式保持的評(píng)價(jià)規(guī)則。其中無(wú)論格網(wǎng)如何合并,街區(qū)的邊界總是正交,因此重點(diǎn)是保持街區(qū)緊密度。此外格網(wǎng)模式還具有排列規(guī)則性和形態(tài)特征[6-7]。其中排列規(guī)則性指格網(wǎng)街區(qū)通常規(guī)則地排成行列,而形態(tài)特征指在合并過程中應(yīng)盡量保持格網(wǎng)模式的長(zhǎng)寬比值。這需要避免只刪除單一方向的道路,而是同時(shí)在長(zhǎng)寬兩個(gè)方向上刪除道路。因此本文也將其稱為合并的方向性。圖2為不同簡(jiǎn)化方案對(duì)于格網(wǎng)模式保持的示意圖。假設(shè)原始數(shù)據(jù)為4×4標(biāo)準(zhǔn)方格網(wǎng),方案1的合并結(jié)果具有最大的緊密度,并且保持了排列規(guī)則性和合并方向性。而后3種方案都無(wú)法同時(shí)保持格網(wǎng)模式的這3點(diǎn)特征。其中排列規(guī)則性評(píng)價(jià)為合并后相鄰街區(qū)中心連線與公共邊界的夾角。如圖2中的虛線段表示相鄰格網(wǎng)中心點(diǎn)的連線,排列規(guī)則性需要保持中心點(diǎn)連線與格網(wǎng)公共邊界道路盡可能的垂直。本文的街區(qū)合并優(yōu)化模型通過設(shè)定評(píng)價(jià)函數(shù)量化各種格網(wǎng)模式,同時(shí)綜合考慮被合并街區(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ù)對(duì)格網(wǎng)模式進(jìn)行量化之前,首先定義變量xuv∈{0,1}指示道路網(wǎng)中的街區(qū)u與v是否合并。其中街區(qū)u定義為合并的中心街區(qū),當(dāng)v同u合并時(shí),xuv＝1,否則xuv＝0。規(guī)定xuv＝xvu及xuu＝1,可將變量數(shù)目減少一半,提高計(jì)算效率。目標(biāo)函數(shù)根據(jù)變量xuv建立格網(wǎng)模式保持的優(yōu)化函數(shù)關(guān)系。通過求解使目標(biāo)函數(shù)達(dá)到極值的xuv,便能得到街區(qū)合并結(jié)果。本文的目標(biāo)函數(shù)為5個(gè)評(píng)價(jià)準(zhǔn)則函數(shù)之和,包括用地類型相似性、街區(qū)緊密性、道路重要性、格網(wǎng)排列規(guī)則性和合并方向性。其中用地類型相似性和街區(qū)緊密性是一般性地塊合并模型中都需要考慮的評(píng)價(jià)準(zhǔn)則[14];道路重要性是本文針對(duì)于城市道路網(wǎng)整體結(jié)構(gòu)特征保持所提出的評(píng)價(jià)準(zhǔn)則;而格網(wǎng)排列規(guī)則性和合并方向性則是針對(duì)于道路網(wǎng)中的格網(wǎng)模式保持進(jìn)一步提出的評(píng)價(jià)準(zhǔn)則。每個(gè)評(píng)價(jià)準(zhǔn)則的具體含義闡述如下。

3．1．1 用地類型相似性評(píng)價(jià)

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

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

表1 合并代價(jià)矩陣Tab．1 Aggregation costs matrix

3．1．2 街區(qū)緊密性評(píng)價(jià)

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

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

3．1．3 道路重要性評(píng)價(jià)

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

式中,路劃s∈S,S為所有路劃的集合;Ls表示路劃s的長(zhǎng)度。而變量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之間不存在公共道路時(shí),則strs(euv)＝0。式(6)可以保證在計(jì)算式(5)時(shí),同一條被刪除路劃的長(zhǎng)度只被計(jì)算一次。

3．1．4 排列規(guī)則性評(píng)價(jià)

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

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

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

3．1．5 合并方向性評(píng)價(jià)

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

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

根據(jù)每個(gè)評(píng)價(jià)函數(shù)的定義,通過將公式中的變量xuv、ys、zeij去除后的求和結(jié)果作為分母對(duì)各個(gè)評(píng)價(jià)函數(shù)進(jìn)行歸一化,將上述五項(xiàng)評(píng)價(jià)函數(shù)的值域歸一化為[0,1]。最終的目標(biāo)函數(shù)為5個(gè)評(píng)價(jià)函數(shù)之和。可以看出對(duì)于非格網(wǎng)街區(qū),其排列規(guī)則性和合并方向性評(píng)價(jià)函數(shù)均為零。路網(wǎng)中的格網(wǎng)街區(qū)比例越大,則后兩個(gè)評(píng)價(jià)函數(shù)所占的比重也就越大。因此,雖然本文模型主要適用于格網(wǎng)街區(qū)的合并,但對(duì)于城市范圍內(nèi)其他類型的街區(qū),也可簡(jiǎn)化為只依靠前三項(xiàng)評(píng)價(jià)函數(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,則不對(duì)其進(jìn)行合并,如果Amin和Amax之間出現(xiàn)沖突,例如一個(gè)面積小于Amin的街區(qū)僅與一個(gè)面積大于Amax的街區(qū)相鄰,則這兩個(gè)街區(qū)無(wú)論合并與否都不能同時(shí)滿足公式(11)中的兩個(gè)約束條件。因此設(shè)置寬松項(xiàng)δ和步長(zhǎng)k∈{0,1,2,…,n},當(dāng)面積閾值沖突時(shí)逐步放大最大閾值直至沖突解決。本文將δ設(shè)為最小面積閾值A(chǔ)min。

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

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

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

3．2．2 路劃刪除約束

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

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

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

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

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

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

3．2．4 連通性約束

街區(qū)合并過程還需要保證合并街區(qū)的連通性,即不存在隔空合并。本文根據(jù)流模型建立約束條件,基本原則如圖5所示[19]。其中非中心街區(qū)用細(xì)圓圈表示,初始量設(shè)為1;粗圓圈為指定的某個(gè)中心街區(qū),表示所有流的最終匯入點(diǎn),無(wú)初始量。箭頭表示自由構(gòu)建的連通流。每個(gè)非中心街區(qū)都有且只有一個(gè)輸出流,流量大小等于輸入流加上街區(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ū)時(shí),街區(qū)v向鄰接街區(qū)w的輸出流。同理tuwv則表示來自街區(qū)w流向v的輸入流,連通性約束條件如式(16)—式(18)所示。

式中,M是一個(gè)非負(fù)整數(shù),表示合并過程中所允許的最大街區(qū)數(shù)。如果M設(shè)為所有街區(qū)總數(shù),表示無(wú)街區(qū)合并數(shù)的約束,式(18)可以刪除。xuv的定義與之前一致,用于表示街區(qū)v與u是否合并。式(16)表達(dá)了每個(gè)非中心格網(wǎng)v的凈流量,等式左邊的兩項(xiàng)分別表示格網(wǎng)v的總輸出流和總輸入流。如果格網(wǎng)v與中心格網(wǎng)u合并,那么xuv＝1,則總凈流量必須等于1,表示流模型中與v連通的所有上級(jí)街區(qū)都被輸送到下一級(jí)街區(qū)。式(17)表示每個(gè)非中心街區(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,其中前三項(xiàng)的值域?yàn)?－1整數(shù),tuvw為非負(fù)實(shí)數(shù)。所有的評(píng)價(jià)函數(shù)和約束函數(shù)都是線性函數(shù),其中式(8)和式(10)中絕對(duì)值可以轉(zhuǎn)化成線性形式。因此本文所構(gòu)建的模型屬于混合整數(shù)規(guī)劃模型(mixed integer programming, MIP)。常用的混合整數(shù)規(guī)劃模型的求解方法是“分支約束”的方法。本文采用該方法,通過使用IBM ILOG CPLEX軟件求解混合整數(shù)規(guī)劃模型。該軟件運(yùn)算性能高,支持多CPU,并且算法穩(wěn)健,對(duì)模型中方程和變量數(shù)目的支持能力僅取決于計(jì)算機(jī)的硬件水平。

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

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

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

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

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

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

圖7為綜合各個(gè)分區(qū)街區(qū)合并之后得到的街區(qū)合并結(jié)果以及與同時(shí)期德國(guó)1∶100 000地形圖的比較,其中街區(qū)合并之后長(zhǎng)度小于300 m的懸掛道路被刪除。各個(gè)用地類型用不同顏色表示,黑色道路表示兩份數(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相對(duì)應(yīng),對(duì)本文試驗(yàn)結(jié)果中保留與舍棄的道路以及兩種原始數(shù)據(jù)中的道路長(zhǎng)度進(jìn)行統(tǒng)計(jì)。統(tǒng)計(jì)結(jié)果如表2所示。

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

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

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

(2)統(tǒng)計(jì)發(fā)現(xiàn)本文模型未刪除的道路(黑色虛線道路)要明顯多于本文模型多刪除的道路(灰色虛線道路)。部分未刪除道路由于兩側(cè)街區(qū)面積較大,或路劃長(zhǎng)度較長(zhǎng),受面積或路劃長(zhǎng)度約束未進(jìn)行合并。這部分道路主要位于草地、森林和農(nóng)業(yè)用地中,約占未刪除道路總數(shù)的37%,因?yàn)榈缆分匾暂^低而被人工刪除,另有部分未刪除道路作為某些長(zhǎng)路劃的一部分被整體保留。而在人工選取中考慮到語(yǔ)義信息,部分刪除了一些路劃。這部分道路主要位于居民地街區(qū)中,約占未刪除道路總數(shù)的29%。這種差異主要是由于地圖簡(jiǎn)化規(guī)則不同。本文模型保留的這些道路不會(huì)影響地圖的可讀性,還保持了地圖的信息量。因此認(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é)。同時(shí),為了展示本文模型的評(píng)價(jià)和約束規(guī)則對(duì)格網(wǎng)模式保持的影響,本文還與文獻(xiàn)[14]中的地塊合并模型進(jìn)行了細(xì)節(jié)對(duì)比。該模型僅使用緊密度和用地類型相似性作為目標(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)。

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

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

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

6 結(jié)束語(yǔ)

本文針對(duì)城市道路網(wǎng)的結(jié)構(gòu)模式特征,在格網(wǎng)模式保持分析的基礎(chǔ)上,提出了一種保持區(qū)域格網(wǎng)模式特征的街區(qū)合并模型。試驗(yàn)分析表明,本文模型通過建立街區(qū)合并的特征評(píng)價(jià)函數(shù)和約束規(guī)則能夠保持街區(qū)所具有的格網(wǎng)模式特征。通過與人工道路選取的地圖的對(duì)比分析,發(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é)果不可避免地存在差異性。考慮如何利用語(yǔ)義信息合并模型進(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)模式的自動(dòng)識(shí)別方法[J]．中國(guó)圖象圖形學(xué)報(bào),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)格模式識(shí)別[J]．測(cè)繪學(xué)報(bào),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]．測(cè)繪學(xué)報(bào),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．(楊必勝,張?jiān)品?欒學(xué)晨．保持幾何模式的城市道路格網(wǎng)簡(jiǎn)化方法[J]．中國(guó)圖象圖形學(xué)報(bào),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]．測(cè)繪學(xué)報(bào),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é)報(bào):信息科學(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—),男,博士,研究方向?yàn)榭臻g數(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]．測(cè)繪學(xué)報(bào),2014,43(4):426-434．)

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

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

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

修回日期:2013-05-24