Pedestrian network generation based on crowdsourced tracking data

ABSTRACT

Pedestrian networks play an important role in various applications, such as pedestrian navigation services and mobility modeling. This paper presents a novel method to extract pedestrian networks from crowdsourced tracking data based on a two-layer framework. This framework includes a walking pattern classification layer and a pedestrian network generation layer. In the first layer, we propose a multi-scale fractal dimension (MFD) algorithm in order to recognize the two different types of walking patterns: walking with a clear destination (WCD) or walking without a clear destination (WOCD). In the second layer, we generate the pedestrian network by combining the pedestrian regions and pedestrian paths. The pedestrian regions are extracted based on a modified connected component analysis (CCA) algorithm from the WOCD traces. We generate the pedestrian paths using a kernel density estimation (KDE)-based point clustering algorithm from the WCD traces. The pedestrian network generation results using two actual crowdsourced datasets show that the proposed method has good performance in both geometrical correctness and topological correctness.     

Spatial localization of closeness and betweenness measures: a self-contradictory but useful form of network analysis

Closeness and betweenness are forms of spatial network analysis grounded in a long-standing tradition of measuring accessibility and flow potential. More recently, these measures have been enhanced by the concept of spatial localization, producing effective models for the prediction of pedestrian and vehicle driver behaviour.

A contradiction arises where the distance metric used to define locality does not match the distance metric used to define shortest paths for closeness and betweenness. A typical case is the use of angular shortest paths within a Euclidean buffer as a pedestrian flow model. Such a model assumes that people make a mode choice based on distance, but a route choice based on least angular change – even when this results in an excessively long ‘problem route’, which conflicts with their criterion for mode choice.

This study examines the prevalence of problem routes and the magnitude of their effect on some pedestrian and vehicle models. We show that while in a weighted analysis, pathological cases could invalidate an entire model, in the models presented the effect of this contradiction is minor. We do this by comparing model predictions to real flow data, using four strategies for handling problem routes: ignore, discard, reroute and strict locality. Strict locality is justified on the grounds of bounded rationality. We find all strategies to give broadly similar results, although the reroute and strict strategies give marginally better simulation accuracy. We also present a discussion of the characteristics of each strategy, and findings on computational efficiency.

We conclude that it is prudent in any computation of localized closeness and betweenness to consider the impact of problem routes; however, they do not necessarily invalidate these forms of analysis, which remain useful.     

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.     

Pedestrian network map generation approaches and recommendation

With the advanced capabilities of mobile devices and the success of car navigation systems, interest in pedestrian navigation systems is on the rise. A critical component of any navigation system is a map database, which represents a network (e.g., road networks for car navigation) and supports key functionality such as map display, geocoding, and routing. Road networks, mainly due to the popularity of car navigation systems, are well defined and publicly available. However, in pedestrian navigation systems, as well as other applications including urban planning and physical activity studies, road networks do not adequately represent the paths that pedestrians usually travel. Currently, there is a void in literatures discussing the challenges, methods, and best practices for pedestrian network map generation. This coupled with the increased demand for pedestrian networks is the prime motivation for development of new approaches and algorithms to automatically generating pedestrian networks. Three approaches, network buffering, using existing road networks, collaborative mapping, using Global Positioning System (GPS) traces collected by volunteers, and image processing, using high-resolution satellite and laser imageries, were implemented and evaluated with a pedestrian network baseline as a ground truth. The results of the experiments indicate that these three approaches, while differing in complexity and outcome, are viable for automatic pedestrian network map generation. The recommendation of a suitable approach for generating pedestrian networks for a given set of sources and requirements is provided.     

Computing least air pollution exposure routes

Personalized routing counts on traveler’s preferences which are usually based on different criteria, such as shortest, fastest, least traffic, or less expensive (e.g., less fuel cost, toll free). However, people are increasingly becoming concerned about the adverse health effects of exposure to air pollution in chosen routes. Exposures to elevated air pollution concentrations particularly endanger children, pregnant women, elderly people, and people with asthma and other respiratory conditions. Choosing routes with least air pollution exposure (APE) is seen as one approach to minimize the level of pollution exposed, which is a major public health issue. Routing algorithms use weights on segments of road networks to find optimum routes. While existing weights are commonly distance and time, among a few others, there is currently no weight based on APE to compute least APE routes. In this paper, we present a weight function that computes weight based on APE. Two different approaches, geostatistical and non-geostatistical, were used to compute APE weight. Each approach was evaluated, and the results indicate that the APE weight is suitable for computing least APE routes.     

Map-matching algorithm for large-scale low-frequency floating car data

Large-scale global positioning system (GPS) positioning information of floating cars has been recognised as a major data source for many transportation applications. Mapping large-scale low-frequency floating car data (FCD) onto the road network is very challenging for traditional map-matching (MM) algorithms developed for in-vehicle navigation. In this paper, a multi-criteria dynamic programming map-matching (MDP-MM) algorithm is proposed for online matching FCD. In the proposed MDP-MM algorithm, the MDP technique is used to minimise the number of candidate routes maintained at each GPS point, while guaranteeing to determine the best matching route. In addition, several useful techniques are developed to improve running time of the shortest path calculation in the MM process. Case studies based on real FCD demonstrate the accuracy and computational performance of the MDP-MM algorithm. Results indicated that the MDP-MM algorithm is competitive with existing algorithms in both accuracy and computational performance.     

建成环境对北京市郊区居民工作日汽车出行的影响

郊区化导致的汽车出行增加及相关的城市环境与社会问题日益成为城市研究关注的焦点,但目前国内对建成环境与汽车出行行为的研究刚刚起步。基于GPS与活动日志相结合的居民一周活动与出行数据,利用GIS空间分析分别以居住地、工作地和活动空间作为地理背景,分析建成环境对于郊区居民汽车出行距离的影响因素。研究发现,建成环境对工作日汽车出行的影响因地理背景的选择而有不同。整日出行受到工作地和活动空间的影响,工作地与活动空间建设密度增高汽车出行减少,但是居住空间的影响不显著;通勤出行受到居住地、工作地和活动空间的影响,居住地商业密度提高和建设密度降低、工作地和活动空间建设密度提高,汽车出行减少;非工作活动出行也受到居住地、工作地和活动空间的影响,居住地、工作地和活动空间的公交密度低、工作地和活动空间建设密度高,汽车出行少。基于研究结果,本文对地理背景不确定性问题进行了探讨,提出出行行为的研究需要考虑居住地以外其他地理背景的影响,并对控制汽车使用的公共政策提出了建议。     

公共交通影响下的北京公共服务设施可达性

本文尝试利用大量微观空间数据从供需角度评价北京公共交通影响下的公共服务设施可达性及其空间效率和供需匹配情况,分别采用比例法与最短时间距离法测算公共服务设施的可达性,运用定序变量相关法与因子空间叠置法分析公共设施可达性的供需匹配程度。结果表明：北京居住小区公共设施总体可达性水平较高。其中,4环以内各类公共设施可达性水平最高,居住小区到公共设施的平均时间20分钟内的小区占比高达90%以上;5-6环可达性水平最差,平均时间20分钟内的小区占比在50%以下。高需求高可达性街道比重相对较高,而高需求低可达性街道主要分布于5-6环的东部和北部地区。在公共设施中,小学可达性最好,而医院和购物中心则更强调空间效率。针对识别出的公共设施的高需求低可达性街道,应从出行方式、公共交通线路与公共服务设施建设等方面采取对策,化解公共设施的供需矛盾问题。     

A GIS data model for landmark-based pedestrian navigation

Landmarks provide the most predominant navigation cue for pedestrian navigation. Very few navigation data models in the geographical information science and transportation communities support modeling of landmarks and use of landmark-based route instructions for pedestrian navigation services. This article proposes a landmark-based pedestrian navigation data model to fill this gap. This data model can model landmarks in several pedestrian navigation scenarios (buildings, open spaces, multimodal transportation systems, and urban streets). This article implements the proposed model in the ArcGIS software environment and demonstrates two typical pedestrian navigation scenarios: (1) a multimodal pedestrian navigation environment involving bus lines, parks, and indoor spaces and (2) a subway system in a metropolitan environment. These two scenarios illustrate the feasibility of the proposed data model in real-world environments. Further improvements of this model could lead to more intuitive and user-friendly landmark-based pedestrian navigation services than the functions supported by current map-based navigation systems.     

A hybrid ensemble learning method for tourist route recommendations based on geo-tagged social networks

Geo-tagged travel photos on social networks often contain location data such as points of interest (POIs), and also users’ travel preferences. In this paper, we propose a hybrid ensemble learning method, BAyes-Knn, that predicts personalized tourist routes for travelers by mining their geographical preferences from these location-tagged data. Our method trains two types of base classifiers to jointly predict the next travel destination: (1) The K-nearest neighbor (KNN) classifier quantifies users’ location history, weather condition, temperature and seasonality and uses a feature-weighted distance model to predict a user’s personalized interests in an unvisited location. (2) A Bayes classifier introduces a smooth kernel function to estimate a-priori probabilities of features and then combines these probabilities to predict a user’s latent interests in a location. All the outcomes from these subclassifiers are merged into one final prediction result by using the Borda count voting method. We evaluated our method on geo-tagged Flickr photos and Beijing weather data collected from 1 January 2005 to 1 July 2016. The results demonstrated that our ensemble approach outperformed 12 other baseline models. In addition, the results showed that our framework has better prediction accuracy than do context-aware significant travel-sequence-patterns recommendations and frequent travel-sequence patterns.     

建成环境对步行通勤通学的影响——以中国香港为例

步行是一种重要的交通方式,也是体力活动的重要组成部分。然而,现代城市居民步行频率持续下降,相应地带来体力活动水平的持续降低,伴随着肥胖等慢性非传染病广泛蔓延,值得警惕。西方很多研究证实了建成环境(常以“3D”或“5D”等模型刻画)对步行行为的影响。基于西方的结论对于中国香港、北京和上海等具有与西方城市大相迥异的建成环境的城市是否适用?不同的人群由于具有不同的社会经济属性和生活节奏、习惯,其步行行为受建成环境的影响在方向、强度上是否存在差异?为解决上述问题,论文以香港为案例地,以职员和学生2类人群的步行通勤通学行为为研究对象,利用香港人口普查数据、Open Street Map数据以及中原地图数据等,采用传统的线性回归和空间计量模型进行分析,发现：①通勤通学距离是影响职员和学生步行通勤通学行为的最重要变量;②以“5D”模型刻画的建成环境对香港居民步行通勤通学行为的影响,与西方情境下的结论存在一定的差异,如,在香港,距地铁站的距离与职员和学生步行通勤比例相关性均不显著;③建成环境对步行通勤通学行为的影响,在职员与学生两类人群之间在方向和强度上存在显著差异。例如人口密度与职员步行通勤比例负相关,但与学生步行通学比例正相关。研究凸显了在“建成环境-交通行为”关系研究中情境(context)和人群区分(segmentation)的重要性。     

Why GPS makes distances bigger than they are

Global navigation satellite systems such as the Global Positioning System (GPS) is one of the most important sensors for movement analysis. GPS is widely used to record the trajectories of vehicles, animals and human beings. However, all GPS movement data are affected by both measurement and interpolation errors. In this article we show that measurement error causes a systematic bias in distances recorded with a GPS; the distance between two points recorded with a GPS is – on average – bigger than the true distance between these points. This systematic ‘overestimation of distance’ becomes relevant if the influence of interpolation error can be neglected, which in practice is the case for movement sampled at high frequencies. We provide a mathematical explanation of this phenomenon and illustrate that it functionally depends on the autocorrelation of GPS measurement error (C). We argue that C can be interpreted as a quality measure for movement data recorded with a GPS. If there is a strong autocorrelation between any two consecutive position estimates, they have very similar error. This error cancels out when average speed, distance or direction is calculated along the trajectory. Based on our theoretical findings we introduce a novel approach to determine C in real-world GPS movement data sampled at high frequencies. We apply our approach to pedestrian trajectories and car trajectories. We found that the measurement error in the data was strongly spatially and temporally autocorrelated and give a quality estimate of the data. Most importantly, our findings are not limited to GPS alone. The systematic bias and its implications are bound to occur in any movement data collected with absolute positioning if interpolation error can be neglected.     

武汉市快递自提点的空间格局与集聚模式研究

互联网经济时代的线上交易推动着线下物流行业的快速发展,为解决快递“最后一公里”配送问题,快递自提点应运而生,成为地理学多维视角下新的研究关注点。论文基于武汉市13个市辖区的菜鸟驿站和中国邮政速递物流站点的POI数据,综合运用文本分析、空间分析等方法,探析武汉市快递自提点的组织形式、区位选址、空间格局与集聚模式。结果表明：① 武汉市菜鸟驿站和邮政站点各自的依托方式和服务对象存在巨大差异,二者虽为竞争关系,却能达到优势互补;② 80%的快递自提点出现在距离社区出入口200 m以内的范围,菜鸟站点较邮政站点更邻近社区;③ 受城市人口分布、用地类型、居民购买力等因素的影响,快递自提点空间分布不均衡,沿“东北—西南”轴线呈对称分布并延伸,密度自内圈向外圈呈跳跃式递减;④ 快递自提点在城市中心城区集聚,形成“中心热点区”,在城市外围边缘地区离散,形成“边缘冷点区”,整体呈现“隔江‘2+3’五核集聚模式”,由菜鸟驿站的分布所主导;⑤ 快递自提点的分布与居民用地重合度高,但其数量在边缘居民区仍匮乏,其数量与各市辖区的面积和常住人口数量呈正相关。最后,论文提出了针对性的优化建议以及未来的研究方向。     

Satellite Navigation and Geospatial Awareness: Long-Term Effects of Using Navigation Tools on Wayfinding and Spatial Orientation

This article examined long-term effects of using navigation tools on wayfinding and spatial orientation, through a survey analysis of the experience of using navigation tools and spatial aptitudes, and a behavioral experiment of real-world navigation. Experience of tool use was measured in terms of regular use (time length and frequency) and accumulated experience (time length multiplied by frequency). The survey analysis showed that frequent users of pedestrian navigation systems tended to be low on sense of direction and mental rotation. In contrast, longtime users of maps tended to be high on sense of direction and favor survey navigation strategies. The behavioral experiment showed that people who had more accumulated experience of using in-car navigation systems traveled less efficiently and learned the configurations of traveled routes less accurately with a mobile tool and a paper map. The analysis of long-term effects through structural equation modeling showed that spatial aptitudes and accumulated experience of tool use independently affect wayfinding and spatial orientation and that the negative effects of accumulated experience were larger than the positive effects of spatial aptitudes. The results and implications are discussed in relation to existing studies of short-term effects and spatial thinking.     

Analysis of the geographical accessibility of neurosurgical emergency hospitals in Sapporo city using GIS and AHP

To improve the geographical accessibility of neurosurgical emergency hospitals for elderly people, we developed several alternative site plans for a new neurosurgical emergency hospital in Sapporo, Japan. Hospitals, population data, routes, and the numerical information for the Analytic Hierarchy Process computations were input into a Geographical Information System. Pairwise comparison revealed the following weights which were assigned to each of the four criteria: 0.674 for availability of hospital beds; 0.169 for the maximum road distance of the shortest routes; 0.101 for the elderly population within a 3‐km radius; and 0.056 for the median road distance of the shortest routes. The alternative proposed could cover 4000 more elderly people in the 3‐km radius of the hospitals. The integration of Geographical Information Systems and the Analytic Hierarchy Process constitutes a powerful tool for analysing traffic conditions in mid‐sized cities and for suggesting city planning to improve prognosis of stroke.     

Have a nice trip: an algorithm for identifying excess routes under satisfaction constraints

Analysis of potential spatial behavior in transport infrastructures is usually carried out by means of a digital network. A basic condition for such a network analysis has traditionally been the desire to find solutions to optimization problems and to achieve greater efficiency in industry. Geographic information system (GIS) tools for network analysis are overwhelmingly targeted at finding solutions to optimization problems, which include the shortest path problem and the traveling salesman problem. This article addresses the problem of the lack of tools for finding solutions to a class of constraint satisfaction problems that are of potential interest to behavioral geographers. Constraint satisfaction problems differ from optimization problems in that they lack an expression to be maximized or minimized. We describe how a constraint-based approach to network analysis can be applied to search for ‘excess routes’ that are longer or in other ways exceed single, optimal routes. Our analysis considers both round-trips and travel from A to B and defines a set of constraints that can characterize such paths. We present a labeling algorithm that can generate solutions to such excess route problems.     

A bidirectional path-finding algorithm and data structure for maritime routing

Route planning is an important problem for many real-time applications in open and complex environments. The maritime domain is a relevant example of such environments where dynamic phenomena and navigation constraints generate difficult route finding problems. This paper develops a spatial data structure that supports the search for an optimal route between two locations while minimizing a cost function. Although various search algorithms have been proposed so far (e.g. breadth-first search, bidirectional breadth-first search, Dijkstra’s algorithm, A^*, etc.), this approach provides a bidirectional dynamic routing algorithm which is based on hexagonal meshes and an iterative deepening A^* (IDA^*) algorithm, and a front to front strategy using a dynamic graph that facilitates data accessibility. The whole approach is applied to the context of maritime navigation, taking into account navigation hazards and restricted areas. The algorithm developed searches for optimal routes while minimizing distance and computational time.     

An Indoor Routing Algorithm for the Blind: Development and Comparison to a Routing Algorithm for the Sighted

This paper presents a prototypical implementation of a non‐network‐based indoor routing algorithm for the sighted and the blind. The spatial abilities of the visually impaired are discussed. Former approaches of outdoor navigation systems for the blind are analyzed and deemed inappropriate for the purpose of modeling indoor navigation. The proposed routing algorithm for the blind calculates routes based on physical characteristics of traveling with a long cane. The algorithm distinguishes between clues, landmarks, obstacles, and hazards along the feasible paths and selects the optimal route by trading off distance and the number of landmarks and clues along a route. Subsequently, the routes for the blind are compared to routes calculated by the routing algorithm for the sighted. The paper asserts that the proposed indoor routing algorithm leads to more suitable routes for the blind.     

多尺度步行环境对居民肥胖的影响机理——以广州为例

基于2019年广州18个社区1 470份问卷数据,通过构建结构方程模型探究不同尺度步行环境（包括步行适宜性和其他与步行相关的建成环境要素）对居民肥胖的影响机理。研究发现：居民出行态度与偏好会影响通勤行为,但对居民肥胖没有显著的直接影响。在考虑了居民社会经济属性和出行态度偏好后,居住地步行环境对居民身体质量指数（body mass index, BMI）具有显著的负向总体效应。步行环境对居民BMI的影响具有尺度效应,社区尺度的步行适宜性影响最为显著。不同尺度的绿度、路网密度、地铁站密度和与城市中心的距离等其他与步行相关的建成环境均对居民BMI有不同程度的影响。