Finding shortest paths on real road networks: the case for A*     

W. Zeng 《International journal of geographical information science》2013,27(4):531-543

The problem of identifying the shortest path along a road network is a fundamental problem in network analysis, ranging from route guidance in a navigation system to solving spatial allocation problems. Since this type of problem is solved so frequently, it is important to craft an approach that is as efficient as possible. Based upon past research, it is generally accepted that several efficient implementations of the Dijkstra algorithm are the fastest at optimally solving the ‘one‐to‐one’ shortest path problem (Cherkassky et al. 1996 Cherkassky, B. V., Goldberg, A. V. and Radzik, T. 1996. Shortest paths algorithms: theory and experimental evaluation.. Mathematical Programming: Series A and B, 73: 129–174. [Crossref], [Web of Science ®] , [Google Scholar]). We show that the most efficient state‐of‐the‐art implementations of Dijkstra can be improved by taking advantage of network properties associated with GIS‐sourced data. The results of this paper, derived from tests of different algorithmic approaches on real road networks, will be extremely valuable for application developers and researchers in the GIS community.  相似文献   

An adaptive approach to selecting a flow‐partition exponent for a multiple‐flow‐direction algorithm     

C. Qin  A.‐X. Zhu  T. Pei  B. Li  C. Zhou  L. Yang 《International journal of geographical information science》2013,27(4):443-458

Most multiple‐flow‐direction algorithms (MFDs) use a flow‐partition coefficient (exponent) to determine the fractions draining to all downslope neighbours. The commonly used MFD often employs a fixed exponent over an entire watershed. The fixed coefficient strategy cannot effectively model the impact of local terrain conditions on the dispersion of local flow. This paper addresses this problem based on the idea that dispersion of local flow varies over space due to the spatial variation of local terrain conditions. Thus, the flow‐partition exponent of an MFD should also vary over space. We present an adaptive approach for determining the flow‐partition exponent based on local topographic attribute which controls local flow partitioning. In our approach, the influence of local terrain on flow partition is modelled by a flow‐partition function which is based on local maximum downslope gradient (we refer to this approach as MFD based on maximum downslope gradient, MFD‐md for short). With this new approach, a steep terrain which induces a convergent flow condition can be modelled using a large value for the flow‐partition exponent. Similarly, a gentle terrain can be modelled using a small value for the flow‐partition exponent. MFD‐md is quantitatively evaluated using four types of mathematical surfaces and their theoretical ‘true’ value of Specific Catchment Area (SCA). The Root Mean Square Error (RMSE) shows that the error of SCA computed by MFD‐md is lower than that of SCA computed by the widely used SFD and MFD algorithms. Application of the new approach using a real DEM of a watershed in Northeast China shows that the flow accumulation computed by MFD‐md is better adapted to terrain conditions based on visual judgement.  相似文献   

Forest Fire Alert System: a Geo Web GIS prioritization model considering land susceptibility and hotspots – a case study in the Carajás National Forest,Brazilian Amazon     

Marcelo Roberto Barbosa  Mario Guimarães Buratto  Leonardo Santana de Oliveira Dias  João Paulo Carvalho Raivel  Flavio Lobos Martins 《International journal of geographical information science》2013,27(6):873-901

To increase the monitoring potential of forest fires, an alert classification methodology using satellite-mapped hotspots has been established to help forest managers in the prioritization of which hotspot to be verified in the field, thus potentially improving the distribution of fire-fighting resources. A computer application was developed based on web-distributed geographical information technology whose main function is to interact automatically generated satellite hotspots and risk areas indicated in fire-susceptibility maps and classify them into five alert levels. The location of the hotspots is available continuously every 4 h, and a susceptibility map is produced daily through map algebra algorithm, which uses static (topography, vegetation and land use) and dynamic (weather) variables. Every process runs through automated geoprocessing routines. The methodology was tested during the dry period of 2007 in the Carajás National Forest, in the Brazilian Amazon, within an area of 400,000 ha. It is a critical area constantly threatened by fires caused by invasions and deforestation owing to intense agribusiness advances and mining activities in its surroundings. This situation results in observations of many hotspots inside the study area for the same day and almost the same time period, in places of extreme opposites, demanding complex rapid analysis and hindering the decision of the displacement of fire-fighting teams. Further, a major mining company operates within the National Forest area, maintaining actions of protection as part of its environmental mining license. Results are presented under three aspects: (i) the credibility of the daily susceptibility map (algorithm), which showed strong correlation between areas of greatest risks and the confirmed forest fires; (ii) the reliability of hotspots (alert levels), confirming 71% of fires; (iii) accuracy in the decision of which hotspot to be checked, which revealed the same number of verifications at different alert levels, 82% confirmed alert 5 hotspots (maximum) and only 50% from alert 1 (minimum), resulting in faster fire-fighting actions, minimizing burned areas and, in some cases, allowing fire control before its spreading. Therefore, the methodology demonstrated that GIS routines are able to determine the relationship between a reality-based, interpreted susceptibility map of the area and satellite-generated hotspots, highlighting the ones of highest hazard level through the alert classification, becoming an important tool to help decisions from the fire-control center, especially for high-risk regions. The methodology may be extrapolated to other forested areas.  相似文献   

A spatial genetic algorithm for automating land partitioning     

Demetris Demetriou  Linda See  John Stillwell 《International journal of geographical information science》2013,27(12):2391-2409

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.  相似文献   

Clustering of temporal event processes   总被引：1，自引：0，他引：1  

Tao Pei  Xi Gong  Shih-Lung Shaw  Ting Ma 《International journal of geographical information science》2013,27(3):484-510

A temporal point process is a sequence of points, each representing the occurrence time of an event. Each temporal point process is related to the behavior of an entity. As a result, clustering of temporal point processes can help differentiate between entities, thereby revealing patterns of behaviors. This study proposes a hierarchical cluster method for clustering temporal point processes based on the discrete Fréchet (DF) distance. The DF cluster method is divided into four steps: (1) constructing a DF similarity matrix between temporal point processes; (2) constructing a complete linkage hierarchical tree based on the DF similarity matrix; (3) clustering the point processes with a threshold determined by locating the local maxima on the curve of the pseudo-F statistic (an index which measures the separability between clusters and the compactness in clusters); and (4) identifying inner patterns for each cluster formed by a series of dense intervals, each of which contains at least one event of all processes of the cluster. The contributions of the article are: (1) the proposed DF cluster method can cluster temporal point processes into different groups and (2) more importantly, it can identify the inner pattern of each cluster. Two synthetic data sets were created to illustrate the DF distance between temporal point process clusters (the first data set) and validate the proposed DF cluster method (the second data set), respectively. An experiment and a comparison with a method based on dynamic time warping show that DF cluster successfully identifies the preconfigured patterns in the second synthetic data set. The cluster method was then applied to a population migration history data set for the Northern Plains of the United States, revealing some interesting population migration patterns.  相似文献   

Sediment fingerprinting in fluvial systems： review of tracers,sediment sources and mixing models   总被引：3，自引：0，他引：3  

Arman HADDADCHI  Darren S. RYDER  Olivier EVRARD  Jon OLLEY 《国际泥沙研究》2013,28(4):560-578

Suspended sediments in fluvial systems originate from a myriad of diffuse and point sources, with the relative contribution from each source varying over time and space. The process of sediment fingerprinting focuses on developing methods that enable discrete sediment sources to be identified from a composite sample of suspended material. This review identifies existing methodological steps for sediment fingerprinting including fluvial and source sampling, and critically compares biogeochemical and physical tracers used in fingerprinting studies. Implications of applying different mixing models to the same source data are explored using data from 41 catchments across Europe, Africa, Australia, Asia, and North and South America. The application of seven commonly used mixing models to two case studies from the US （North Fork Broad River watershed） and France （Bldone watershed） with local and global （genetic algorithm） optimization methods identified all outputs remained in the acceptable range of error defined by the original authors. We propose future sediment fingerprinting studies use models that combine the best explanatory parameters provided by the modified Collins （using correction factors） and Hughes （relying on iterations involving all data, and not only their mean values） models with optimization using genetic algorithms to best predict the relative contribution of sediment sources to fluvial systems.  相似文献   

中国东南屯溪-温州宽角地震资料去广角效应成像     

张智  董超  李飞  王海燕 《地球物理学进展》2013,28(3)

由于长排列广角地震采集中必定存在超临界角的广角反射信息,广角反射信息相对临界角内反射信息存在随偏移距变化的时移现象.本文研究了去广角效应下的走时反演成像,并将其应用到东南屯溪—温州的宽角地震资料.通过拾取中国东南屯溪—温州剖面宽角实际地震资料中P波垂直分量拾取到的反射P波走时,继而使用遗传反演方法进行处理,得到了该区丰乐、新安江、松阳、青田以及洞头五炮去广角效应与未考虑广角效应情况下的一维速度深度曲线,并对比了去广角效应前后的地壳结构界面形态.结果表明,广角效应去除前后影响主要体现在壳内层速度差异,地壳浅层界面深度的广角效应明显强于深层界面.  相似文献   

THE INFLUENCE OF SLOPE AND RAIN INTENSITY ON RUNOFF AND INFILTRATION / L'influence de l'inclinaison de terrain et de l'intensité de pluie sur l'écoulement et l'infiltration     

S. H. NASSIF  E. M. WILSON 《水文科学杂志》2013,58(4):539-553

Abstract

The design and construction of a special-purpose laboratory catchment and rainfall simulator is described. The equipment consists of a soil catchment area that can be inclined at various angles. Additional instrumentation then measures the flow of water across the surface of, and through, the soil bed. Precipitation is provided by a unit that simulates rainfall at particular rates with uniform distribution.

The equipment was used to examine infiltration, runoff and other hydrological properties of a number of soils under different rainfall intensities and with different catchment slopes. Correlations were obtained for these variables.  相似文献   

甘东南流动台阵微震监测结果   总被引：7，自引：1，他引：6  

高见  张元生  郭飚  刘旭宙 《地震工程学报》2013,35(1):177-182

利用高密度宽频带流动台阵资料,应用网格搜索地震定位方法对甘东南2009年11月-2011年11月期间的微震进行了重新定位.在研究区内有3个以上台站记录到的微震共3 014个,比常规台网记录多1 693个.重新定位结果显示:在各断裂带附近地震分布更加密集,沿断裂呈带状或簇集状分布;震源深度分布优势范围为5～20 km,其平均深度为11 km;地震深度分布与断裂的关系密切,地震条带与断裂构造可以较好的相对应.  相似文献   

基于环境激励的ERA方法在网架结构振动测试中的应用研究     

高永武  金波  侯钢领  刘明  刘国强 《地震工程与工程振动》2013,33(4)

基于环境激励的结构振动测试的方法中ERA方法是重要的时域分析方法.本文主要是以随机减量法(RD)和NExT两种数据处理方法结合ERA算法,对绥化学院正在建的网架结构的基本模态参数进行测试.通过分析比较得出RD/ERA和NExT/ERA较直接ERA有更高的精度,且实测分析结果与有限元分析结果较吻合.为网架结构在环境激励下用ERA方法测试模态参数提供了实验依据.  相似文献