Block Aggregation Optimization Model for Grid Pattern Maintenance in Urban Network

Abstract

Abstract:

In this article we present a mixed-integer programming model for urban blocks aggregation, aiming to maintain grid pattern after road selection. This model firstly defines the objective function to quantify the grid pattern maintenance, composed of four evaluations namely compactness, hierarchy, arrangement consistence and aggregating directionality. Secondly, four constraints are built ensuring effective and efficient aggregation for the target scale, including aggregating scale, stroke deletion, conjoint aggregation and connectivity. Finally, the whole urban road network are divided in to several subregions with high-level roads, and the aggregation problem are decomposed into independent subinstances to model to maintain both the skeleton and grid patterns of the urban. The mixed-integer programming model can be solved by optimization software CPLEX. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:25,000 and output scale 1:100,000. We also compare results of this model with existing map data. These tests allow us to conclude that our optimization method yields high-quality results for both global and local patterns maintenance.

Key words: Map generalization, Urban street network, Grid pattern, Optimization

CLC Number:

P208

References

参考文献
[1] ZHANG Q N. Modeling Structure and Patterns in Road Network Generalization [C] // Proceedings of ICA Work-shop on Generalization and Multiple Representation. Leicester: [s.n.], 2004.
[2] HEINZLE F, ANDERS K H, Sester M. Graph based ap-proaches for recognition of patterns and implicit infor-mation in road networks [C]. // Proceeding of XXII inter-national 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]. // GIScience [s.l.]: Springer, 2006: 153–167.
[4] HEINZLE F, ANDERS K H. Characterising Space via Pattern Recognition Techniques: Identifying Patterns in Road Networks [A]. The Generalisation of Geographic Information: Models and Applications [M]. Netherlands: Elsevier, 2007. 233-253.
[5] YANG B S, LUAN X C. An Automated Method for Structural Pattern Recognition of Road Networks [J]. Journal of Image and Graphics, 2009 ,14(7): 1251-1255. (杨必胜, 栾学晨. 城市道路网几何结构模式的自动识别方法[J]. 中国图象图形学报, 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 J, AI T, DING S. Grid Pattern Recognition in Road Networks Based on C4.5 Algorithm [J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1): 121-126. (田晶, 艾廷华, 丁绍军. 基于C4.5算法的道路网网格模式识别[J]. 测绘学报, 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 BS, LUAN XC, Li QQ. Generating hierarchical strokes from urban street networks based on spatial pattern recognition [J]. International Journal of Geographical In-formation Science. 2011, 25(12): 2025-2050.
[12] HU Y G, CHENJ, LI Z L, ZHAO R L. Selective Omission of Road Features Based on Mesh Density for Digital Map Generalization [J]. Acta Geodaetica et Cartographica Sinica, 2007,36 (3):351-357. (胡云岗,陈军,李志林,赵仁亮. 基于网眼密度的道路选取方法[J]. 测绘学报. 2007, 36(3): 351-357.)
[13] YANG B S, LUAN X C. ZHANG Y F. Pattern preserving method for grid simplification in road networks [J]. Journal of Image and Graphics, 2012, 17(1): 150-156. (杨必胜, 张云菲, 栾学晨. 保持几何模式的城市道路格网简化方法[J]. 中国图象图形学报, 2012, 17(1): 150-156.)
[14] HAUNERT J H, Wolff A. Area aggregation in map gener-alisation by mixed-integer programming [J]. International Journal of Geographical Information Science, 2010, 24(12): 1871-1897.
[15] XU Z, LIU C F, ZHANG H,et al. Road Selection Based on Evaluation of Stroke Network Functionality [J]. Acta Ge-odaetica et Cartographica Sinica, 2012, 41(5): 769-776. (徐柱, 刘彩凤, 张红, 黄泽纯, 李志林. 基于路划网络功能的道路选取方法 [J]. 测绘学报. 2012, 41 (5): 769-776.)
[16] THOMSON R. C. The ‘Stroke’ Concept in Geographic Network Generalization and Analysis [C] // Proceeding of 12th International Symposium on Spatial Data Handling. Vienna: [s.n.], 2006.
[17] SHIRABE T. A model of contiguity for spatial unit alloca-tion [J]. Geographical Analysis. 2005, 37(1): 2-16.
[18] LI Q Q, ZENG Z, YANG B S, LI B J. Betweenness Cen-trality Analysis for Urban Road Networks [J]. Geomatics and Information Science of Wuhan University, 2010, 35(1): 37-41. (李清泉, 曾喆, 杨必胜, 李必军. 城市道路网络的中介中心性分析[J]. 武汉大学学报?信息科学版, 2010, 35(1): 37-41.)
[19] TOMKO M, WINTER S, Claramunt C. Experiential hier-archies of streets [J]. Computers, Environment and Urban Systems, 2008, 32(1): 41-52.
[20] FREEMAN L C. Centrality in social networks: conceptual clarification [J]. Social networks, 1979, 1(3): 215-239.