保持城市道路格网模式的街区合并混合整数规划模型

摘要/Abstract

摘要：

基于最优化建模理论提出一种保持城市道路格网模式的街区合并混合整数规划模型。首先定义道路格网模式保持的目标函数，集成了紧密性、骨干性、排列一致性和合并方向性四个评价指标；然后构建四个合并约束条件，包括合并尺度、路划删除、联动合并和连通性保持，来保证合并过程正确有效且满足目标尺度需求，；最后利用已识别的主干道和格网模式对道路网进行分区，在保持道路网的骨架和格网结构模式的基础上对每个分区内的道路街区独立建立最优化合并模型。本文采用数学最优化规划程序CPLEX对模型进行求解。。实验使用ATKIS 1:25000数据，将其简化至1:100000并与已有数据作比较。结果表明，通过本方法简化的道路网能够保持道路网中整体和局部的模式特征。

关键词: 制图综合, 城市道路网, 格网模式, 最优化

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

中图分类号:

P208

栾学晨杨必胜李秋萍. 保持城市道路格网模式的街区合并混合整数规划模型[J]. 测绘学报.

参考文献

参考文献
[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.