A comparison of scenario-based hybrid bilevel and multi-objective location-allocation models for earthquake emergency shelters: a case study in the central area of Beijing,China

The accurate location and allocation of disaster emergency shelters are key components of effective urban planning and emergency management. Various models have been developed to solve the location-allocation problem, but gaps remain with regard to model realism and associated applicability. For the available location and allocation models of earthquake emergency shelters, uncertainty with respect to earthquake hazard, population exposure, rate of damage to buildings and the effects of evacuee behavior are often neglected or oversimplified. Moreover, modifying the models can be an alternative means of improving the solution quality when the optimization algorithm has difficulty coping with a complex, high-dimensional problem. This article develops a scenario-based hybrid bilevel model that addresses the concerns related to high-dimensional complexity and provides a higher degree of realism by incorporating the uncertainties of population dynamics and earthquake damage scenarios into location-allocation problems for earthquake emergency shelters. A modified particle swarm optimization algorithm combined with a simulated annealing algorithm was applied to derive solutions using the hybrid bilevel model and a conventional multi-objective model, and the solutions obtained using the two models were then compared. The novel features of the study include the hybrid bilevel model that considers the dynamic number of evacuees and its implementation for earthquake emergency shelter location and allocation. The results show that the solutions significantly differ between daytime and nighttime. When applied to the multi-objective model, the optimization algorithm is time consuming and may only find the local optima and provide suboptimal solutions in the considered scenarios with more evacuees. By contrast, the hybrid bilevel model shows more desirable performance because it significantly reduces the dimensionality of the location-allocation problem based on a two-step-to-reach approach. The proposed hybrid bilevel model is proven to be useful for optimal shelter allocation, and the presented results can be used as a reference for balancing the interests of the government and residents during the planning of shelters in Beijing.     

An artificial bee colony-based multi-objective route planning algorithm for use in pedestrian navigation at night

Pedestrian navigation at night should differ from daytime navigation due to the psychological safety needs of pedestrians. For example, pedestrians may prefer better-illuminated walking environments, shorter travel distances, and greater numbers of pedestrian companions. Route selection at night is therefore a multi-objective optimization problem. However, multi-objective optimization problems are commonly solved by combining multiple objectives into a single weighted-sum objective function. This study extends the artificial bee colony (ABC) algorithm by modifying several strategies, including the representation of the solutions, the limited neighborhood search, and the Pareto front approximation method. The extended algorithm can be used to generate an optimal route set for pedestrians at night that considers travel distance, the illumination of the walking environment, and the number of pedestrian companions. We compare the proposed algorithm with the well-known Dijkstra shortest-path algorithm and discuss the stability, diversity, and dynamics of the generated solutions. Experiments within a study area confirm the effectiveness of the improved algorithm. This algorithm can also be applied to solving other multi-objective optimization problems.     

A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case

Providing distributed services on road networks is an essential concern for many applications, such as mail delivery, logistics and police patrolling. Designing effective and balanced routes for these applications is challenging, especially when involving multiple postmen from distinct depots. In this research, we formulate this routing problem as a Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP). To solve this routing problem, we develop an efficient tabu-search-based algorithm and propose three novel lower bounds to evaluate the routes. To demonstrate its practical usefulness, we show how to formulate the route design for police patrolling in London as an MMMDRPP and generate balanced routes using the proposed algorithm. Furthermore, the algorithm is tested on multiple adapted benchmark problems. The results demonstrate the efficiency of the algorithm in generating balanced routes.     

模拟退火算法用于产生城市土地空间布局方案

本文发展了一种模拟退火算法辅助产生城市土地空间布局方案。首先建立了城市土地空间配置问题的数学模型 ,目标函数是最小化土地开发费用、最大化不同功能地块间的空间协调性。由于问题存在的诸多空间约束条件使得可行的土地利用布局方案的搜寻过程变得十分缓慢 ,采用了将一些空间约束条件结合到目标函数中的方法 ,如结合了距离约束、方向约束、相同土地利用单元的邻近约束和地块形状的紧凑约束等约束条件。应用于湖南省长沙市暮云工业区用地规划的结果表明 ,模拟退火算法是一种辅助城市土地利用规划的有用的、有潜力的优化方法     

一种结合GIS的双重目标多准则决策方法及其应用

在土地适宜性评价中,现有结合GIS的多准则决策方法难以适用于存在多个冲突决策目标的问题。该文对已有方法进行改进,提出一种适用于相互冲突双重目标的多准则决策方法。该方法应用矢量数据模型,逐个进行单一目标的多准则决策,根据决策结果建立决策平面;根据两个目标间的权重划分决策平面,采用图解算法实现双重目标的决策。与现有的线性整数规划、遗传算法等相比,该方法简单易用,适用于城市规划中具有大量候选项的土地适宜性评价和土地布局研究。     

Multi-objective spatially constrained clustering for regionalization with particle swarm optimization

Regionalization is an important part of the spatial analysis process, and the solution should be contiguity-constrained in each region. In general, several objectives need to be optimized in practical regionalization, such as the homogeneity of regions and the heterogeneity among regions. Therefore, multi-objective techniques are more suitable for solving regionalization problems. In this paper, we design a multi-objective particle swarm optimization algorithm for solving regionalization problems. Towards this goal, a novel particle representation for regionalization is proposed, which can be expressed in continuous space and has flexible constraints on the number of regions. In the process of optimization, a contiguous-region method is designed that satisfies the constraints and improves the efficiency. The decision solution is selected in the Pareto set based on a trade-off between the objective functions, and the number of regions can be automatically determined. The proposed method outperforms six regionalization algorithms in terms of both the number and the quality of the solutions.     

土地利用结构多目标优化遗传算法

传统数学方法难以有效解决土地利用结构多目标优化问题,针对土地利用结构优化的多目标性和遗传算法在多目标优化求解方面的优势,以经济效益和生态效益为目标函数建立土地利用结构优化数学模型,采用遗传算法进行模型求解.以重庆市合川区为例详细介绍了具体应用过程,得出了4个可行方案,对方案进行论证择优,选出满意的最佳方案,证明采用遗传算法进行土地利用结构多目标优化求解是科学可行的.     

Construction and computation of geometries on the ellipsoid

This article describes how to construct a wide range of geometry objects (called GeographicGeometry objects) in the coordinate system of an ellipsoid such as the Geographic coordinate system. Each construction process is formulated analytically and algorithmically using a combination of a set of fairly well-known mathematical methods such as ellipsoid geodesic construction functions, spherical trigonometry and iterative refinement methods. Each such geometry object may efficiently be converted to a corresponding Cartesian geometry object in any map projection coordinate system using an approximation algorithm. This property makes them particularly useful as a coordinate-system-independent geometry representation. A geographic geometry object is normally topologically equivalent to its Cartesian geometry counterpart except for some discontinuity and singularity cases.     

A unified approach for location-allocation analysis: integrating GIS,distributed computing and spatial optimization

Location-allocation modeling is an important area of research in spatial optimization and GIScience. A large number of analytical models for location-allocation analysis have been developed in the past 50 years to meet the requirements of different planning and spatial-analytic applications, ranging from the location of emergency response units (EMS) to warehouses and transportation hubs. Despite their great number, many location-allocation models are intrinsically linked to one another. A well-known example is the theoretical link between the classic p-median problem and coverage location problems. Recently, Lei and Church showed that a large number of classic and new location models can be posed as special case problems of a new modeling construct called the vector assignment ordered median problem (VAOMP). Lei and Church also reported extremely high computational complexity in optimally solving the best integer linear programming (ILP) formulation developed for the VAOMP even for medium-sized problems in certain cases.

In this article, we develop an efficient unified solver for location-allocation analysis based on the VAOMP model without using ILP solvers. Our aim is to develop a fast heuristic algorithm based on the Tabu Search (TS) meta-heuristic, and message passing interface (MPI) suitable for obtaining optimal or near-optimal solutions for the VAOMP in a real-time environment. The unified approach is particularly interesting from the perspective of GIScience and spatial decision support systems (DSS) as it makes it possible to solve a wide variety of location models in a unified manner in a GIS environment. Computational results show that the TS method can often obtain in seconds, solutions that are better than those obtained using the ILP-based approach in hours or a day.     

Spatial multi-objective land use optimization: extensions to the non-dominated sorting genetic algorithm-II

A spatial multi-objective land use optimization model defined by the acronym ‘NSGA-II-MOLU’ or the ‘non-dominated sorting genetic algorithm-II for multi-objective optimization of land use’ is proposed for searching for optimal land use scenarios which embrace multiple objectives and constraints extracted from the requirements of users, as well as providing support to the land use planning process. In this application, we took the MOLU model which was initially developed to integrate multiple objectives and coupled this with a revised version of the genetic algorithm NSGA-II which is based on specific crossover and mutation operators. The resulting NSGA-II-MOLU model is able to offer the possibility of efficiently searching over tens of thousands of solutions for trade-off sets which define non-dominated plans on the classical Pareto frontier. In this application, we chose the example of Tongzhou New Town, China, to demonstrate how the model could be employed to meet three conflicting objectives based on minimizing conversion costs, maximizing accessibility, and maximizing compatibilities between land uses. Our case study clearly shows the ability of the model to generate diversified land use planning scenarios which form the core of a land use planning support system. It also demonstrates the potential of the model to consider more complicated spatial objectives and variables with open-ended characteristics. The breakthroughs in spatial optimization that this model provides lead directly to other properties of the process in which further efficiencies in the process of optimization, more vivid visualizations, and more interactive planning support are possible. These form directions for future research.     

Improving the performance of genetic algorithms for land-use allocation problems

Multi-objective optimization can be used to solve land-use allocation problems involving multiple conflicting objectives. In this paper, we show how genetic algorithms can be improved in order to effectively and efficiently solve multi-objective land-use allocation problems. Our focus lies on improving crossover and mutation operators of the genetic algorithms. We tested a range of different approaches either based on the literature or proposed for the first time. We applied them to a land-use allocation problem in Switzerland including two conflicting objectives: ensuring compact urban development and reducing the loss of agricultural productivity. We compared all approaches by calculating hypervolumes and by analysing the spread of the produced non-dominated fronts. Our results suggest that a combination of different mutation operators, of which at least one includes spatial heuristics, can help to find well-distributed fronts of non-dominated solutions. The tested modified crossover operators did not significantly improve the results. These findings provide a benchmark for multi-objective optimization of land-use allocation problems with promising prospectives for solving complex spatial planning problems.     

Relocation optimization of electric cars in one-way car-sharing systems: modeling,exact solving and heuristics algorithms

Car-sharing system with electric cars is a very convenient service for urban transportation: it allows users to pick up a vehicle at a station and rent it during a short time. To manage this kind of system in the best way, it is necessary to solve the critical problem of vehicle stock imbalance across the stations. Several decision levels must be considered to balance the car distribution by taking into account the quality of service and the system operation cost. To this end, a linear programming model is proposed to formalize the problem in a mathematical framework, which allows the computation of optimal vehicle distribution strategies. To make our solution time efficient and usable for solving large problems, a greedy algorithm and a tabu search algorithm are proposed. These two algorithms are applied to the Auto Bleue network in Nice and its surrounding (France) using extensive simulations. Besides, an integrated mapping method is provided within the Geographical Information System QGIS to estimate flows and their locations. Numerical results demonstrate that the tabu search algorithm is able to find near-optimal solutions and good compromises between client satisfaction, number of staff agents and vehicles used, and computing time.     

禁忌搜索算法在图像匹配中的应用研究

搜索策略是图像匹配研究的主要问题之一,对匹配算法的执行速度和最终的匹配精度都有很大的影响。该文将禁忌搜索算法的思想用于图像匹配的搜索过程,并进行了改进,构造了永久禁忌和暂时禁忌两种禁忌表,每次搜索都将候选解中的点分别放入不同的禁忌表中,再利用基于灰度的匹配方法,以归一化积相关为相似性度量准则,克服了传统的归一化积相关图像匹配算法耗时过长的缺点,可以在不失匹配精度的条件下,大大减少匹配所用的时间,实现了准确而快速的图像匹配。     

New Tabu Algorithm for Positioning Mining Drillholes with Blocks Uncertainty

This paper proposes a new approach to the mining exploration drillholes positioning problem (DPP) that incorporates both geostatistical and optimization techniques. A metaheuristic was developed to solve the DPP taking into account an uncertainty index that quantifies the reliability of the current interpretation of the mineral deposit. The uncertainty index was calculated from multiple deposit realizations obtained by truncated Gaussian simulations conditional to the available drillholes samplings. A linear programming model was defined to select the subset of future drillholes that maximizes coverage of the uncertainty. A Tabu Search algorithm was developed to solve large instances of this set partitioning problem. The proposed Tabu Search algorithm is shown to provide good quality solutions approaching 95% of the optimal solution in a reasonable computing time, allowing close to optimal coverage of uncertainty for a fixed investment in drilling.

     

A spatial genetic algorithm for automating land partitioning

Land fragmentation is a widespread situation which may often hinder agricultural development. Land consolidation is considered to be the most effective land management planning approach for controlling land fragmentation and hence improving agricultural efficiency. Land partitioning is a basic process of land consolidation that involves the subdivision of land into smaller sub-spaces subject to a number of constraints. This paper explains the development of a module called LandParcelS (Land Parcelling System) that is a part of an integrated planning and decision support system called LACONISS (LAndCONsolidation Integrated Support System) which has been developed to assist land consolidation planning in Cyprus. LandParcelS automates the land partitioning process by designing and optimising land parcels in terms of their shape, size and value. The methodology integrates geographical information systems and a genetic algorithm that has been applied to two land blocks that are part of a larger case study area in Cyprus. Partitioning is treated as either a single or multi-objective problem for various optimisation cases. The results suggest that a step forward has been made in solving this complex spatial problem, although further research is needed to improve the algorithm. This approach may have relevance to other spatial planning tasks that involve single or multi-objective optimisation problems, especially those dealing with space partitioning.     

Tagging-the-triangle algorithm for partitioning features with inconsistent boundaries

In spatial data sets, gaps or overlaps among features are frequently found in spatial tessellations due to the non-abutting edges with adjacent features. These non-abutting edges in loose tessellations are also called inconsistent boundaries or slivers; polygons containing at least one inconsistent boundary are called inconsistent polygons or sliver polygons. The existing algorithms to solve topological inconsistencies in sliver polygons suffer from one or more of three major issues, namely determination of tolerances, excessive CPU processing time for large data sets and loss of vertex history. In this article, we introduce a new algorithm that mitigates these three issues. Our algorithm efficiently searches the features with inconsistent polygons in a given spatial data set and logically partitions them among adjacent features. The proposed algorithm employs the constrained Delaunay triangulation technique to generate labelled triangles from which inconsistent polygons with gaps and overlaps are identified using label counts. These inconsistent polygons are then partitioned using the straight skeleton method. Moreover, each of these partitioned gaps or overlaps is distributed among the adjacent features to improve the topological consistency of the spatial data sets. We experimentally verified our algorithm using the real land cadastre data set. The comparison results show that the proposed algorithm is four times faster than the existing algorithm for data sets with 200,000 edges.     

基于四叉树索引构建TIN的高效合成算法

不规则三角网(TIN)可以逼真的模拟地形表面,因此被广泛应用于地学领域。Delaunay三角剖分算法是构建TIN网的最优算法,该文对传统Delaunay三角网构建算法进行分析,提出了一种针对大规模离散数据点生成TIN的高效合成算法。该算法首先根据离散点的分布位置和密度对其进行四叉树区域划分;然后以每个叶子节点的边界四边形为凸包,采用逐点插入法构建三角网;最后采用顶点合并法自底向上合并具有相同父节点的4个子节点,生成Delaunay三角网。实验结果表明,该算法时间复杂度较低,有效提高了TIN网的构建效率。     

Book reviews

A digital elevation model (DEM), which is used to represent a terrain surface, is normally constructed by applying an interpolation method on given sample elevation points. Interpolation methods can be classified into two classes: linear methods, which have a low time cost and are suitable for terrains where there is little change in elevation, and nonlinear methods, which normally consume comparatively more time and are more suitable for terrains where there are frequent changes in elevation. A hybrid interpolation method, which involves both a linear method and a nonlinear method of interpolation, is proposed in this paper. The proposed method aims to integrate the advantages of both linear and nonlinear interpolation methods for the refinement of regular grid DEM. Here, the bilinear is identified as the linear method, and the bi‐cubic is taken to be the nonlinear interpolation method. The hybrid method is an integration of a linear model and nonlinear interpolation model with a parameter that defines the weights for each of the models. The parameter is dependent on the complexity of the terrain, for which a DEM is to be interpolated. The experimental results in this study demonstrate that the hybrid method is effective for interpolating DEMs for various types of terrain.     

基于主题相关度的地理信息Web服务爬虫研究

针对通用搜索引擎对于地理信息Web服务检索存在的不足,提出了一种基于主题相关度的服务爬虫方法,利用向量空间模型表示主题特征,通过引入特征值权重的计算方法分析页面内容与主题的相关度,过滤与主题无关的页面;并利用改进的PageRank算法从URL和锚文本两方面分析链接的重要性,优化爬取队列。实验表明,该方法在服务检索效率和抓取能力上都取得了良好的效果。     

A general-purpose parallel raster processing programming library test application using a geographic cellular automata model

A general-purpose parallel raster processing programming library (pRPL) was developed and applied to speed up a commonly used cellular automaton model with known tractability limitations. The library is suitable for use by geographic information scientists with basic programming skills, but who lack knowledge and experience of parallel computing and programming. pRPL is a general-purpose programming library that provides generic support for raster processing, including local-scope, neighborhood-scope, regional-scope, and global-scope algorithms as long as they are parallelizable. The library also supports multilayer algorithms. Besides the standard data domain decomposition methods, pRPL provides a spatially adaptive quad-tree-based decomposition to produce more evenly distributed workloads among processors. Data parallelism and task parallelism are supported, with both static and dynamic load-balancing. By grouping processors, pRPL also supports data–task hybrid parallelism, i.e., data parallelism within a processor group and task parallelism among processor groups. pSLEUTH, a parallel version of a well-known cellular automata model for simulating urban land-use change (SLEUTH), was developed to demonstrate full utilization of the advanced features of pRPL. Experiments with real-world data sets were conducted and the performance of pSLEUTH measured. We conclude not only that pRPL greatly reduces the development complexity of implementing a parallel raster-processing algorithm, it also greatly reduces the computing time of computationally intensive raster-processing algorithms, as demonstrated with pSLEUTH.