| 1. |
- Yang, Can, 1990-
(author)
-
Discovering Contiguous Sequential Patterns in Network-Constrained Movement
- 2017
-
Licentiate thesis (other academic/artistic)abstract
- A large proportion of movement in urban area is constrained to a road network such as pedestrian, bicycle and vehicle. That movement information is commonly collected by Global Positioning System (GPS) sensor, which has generated large collections of trajectories. A contiguous sequential pattern (CSP) in these trajectories represents a certain number of objects traversing a sequence of spatially contiguous edges in the network, which is an intuitive way to study regularities in network-constrained movement. CSPs are closely related to route choices and traffic flows and can be useful in travel demand modeling and transportation planning. However, the efficient and scalable extraction of CSPs and effective visualization of the heavily overlapping CSPs are remaining challenges.To address these challenges, the thesis develops two algorithms and a visual analytics system. Firstly, a fast map matching (FMM) algorithm is designed for matching a noisy trajectory to a sequence of edges traversed by the object with a high performance. Secondly, an algorithm called bidirectional pruning based closed contiguous sequential pattern mining (BP-CCSM) is developed to extract sequential patterns with closeness and contiguity constraint from the map matched trajectories. Finally, a visual analytics system called sequential pattern explorer for trajectories (SPET) is designed for interactive mining and visualization of CSPs in a large collection of trajectories.Extensive experiments are performed on a real-world taxi trip GPS dataset to evaluate the algorithms and visual analytics system. The results demonstrate that FMM achieves a superior performance by replacing repeated routing queries with hash table lookups. BP-CCSM considerably outperforms three state-of-the-art algorithms in terms of running time and memory consumption. SPET enables the user to efficiently and conveniently explore spatial and temporal variations of CSPs in network-constrained movement.
|
|
| 2. |
- Gidofalvi, Gyözö, 1975-
(author)
-
Spatio-Temporal Data Mining for Location-Based Services
- 2008
-
Doctoral thesis (other academic/artistic)abstract
- Largely driven by advances in communication and information technology, such as the increasing availability and accuracy of GPS technology and the miniaturization of wireless communication devices, Location–Based Services (LBS) are continuously gaining popularity. Innovative LBSes integrate knowledge about the users into the service. Such knowledge can be derived by analyzing the location data of users. Such data contain two unique dimensions, space and time, which need to be analyzed. The objectives of this thesis are three–fold. First, to extend popular data mining methods to the spatio–temporal domain. Second, to demonstrate the usefulness of the extended methods and the derived knowledge in two promising LBS examples. Finally, to eliminate privacy concerns in connection with spatio–temporal data mining by devising systems for privacy–preserving location data collection and mining. To this extent, Chapter 2 presents a general methodology, pivoting, to extend a popular data mining method, namely rule mining, to the spatio–temporal domain. By considering the characteristics of a number of real–world data sources, Chapter 2 also derives a taxonomy of spatio–temporal data, and demonstrates the usefulness of the rules that the extended spatio–temporal rule mining method can discover. In Chapter 4 the proposed spatio–temporal extension is applied to find long, sharable patterns in trajectories of moving objects. Empirical evaluations show that the extended method and its variants, using high–level SQL implementations, are effective tools for analyzing trajectories of moving objects. Real–world trajectory data about a large population of objects moving over extended periods within a limited geographical space is difficult to obtain. To aid the development in spatio–temporal data management and data mining, Chapter 3 develops a Spatio–Temporal ACTivity Simulator (ST–ACTS). ST–ACTS uses a number of real–world geo–statistical data sources and intuitive principles to effectively generate realistic spatio–temporal activities of mobile users. Chapter 5 proposes an LBS in the transportation domain, namely cab–sharing. To deliver an effective service, a unique spatio–temporal grouping algorithm is presented and implemented as a sequence of SQL statements. Chapter 6 identifies ascalability bottleneck in the grouping algorithm. To eliminate the bottleneck, the chapter expresses the grouping algorithm as a continuous stream query in a data stream management system, and then devises simple but effective spatio–temporal partitioning methods for streams to parallelize the computation. Experimental results show that parallelization through adaptive partitioning methods leads to speed–ups of orders of magnitude without significantly effecting the quality of the grouping. Spatio–temporal stream partitioning is expected to be an effective method to scale computation–intensive spatial queries and spatial analysis methods for streams. Location–Based Advertising (LBA), the delivery of relevant commercial information to mobile consumers, is considered to be one of the most promising business opportunities amongst LBSes. To this extent, Chapter 7 describes an LBA framework and an LBA database that can be used for the management of mobile ads. Using a simulated but realistic mobile consumer population and a set of mobile ads, the LBA database is used to estimate the capacity of the mobile advertising channel. The estimates show that the channel capacity is extremely large, which is evidence for a strong business case, but it also necessitates adequate user controls. When data about users is collected and analyzed, privacy naturally becomes a concern. To eliminate the concerns, Chapter 8 first presents a grid–based framework in which location data is anonymized through spatio–temporal generalization, and then proposes a system for collecting and mining anonymous location data. Experimental results show that the privacy–preserving data mining component discovers patterns that, while probabilistic, are accurate enough to be useful for many LBSes. To eliminate any uncertainty in the mining results, Chapter 9 proposes a system for collecting exact trajectories of moving objects in a privacy–preserving manner. In the proposed system there are no trusted components and anonymization is performed by the clients in a P2P network via data cloaking and data swapping. Realistic simulations show that under reasonable conditions and privacy/anonymity settings the proposed system is effective.
|
|
| 3. |
- Hatzenbühler, Jonas
(author)
-
Simulation and optimization of innovative urban transportation systems
- 2022
-
Doctoral thesis (other academic/artistic)abstract
- The ongoing trends of urbanization and e-commerce continuously challenge the existing urban transportation systems. A steadily growing number of people traveling within urban areas, results in more trips taken with public transportation systems. Additionally, the constantly increasing number of urban logistic operations leads to more commercial vehicles in cities. These ongoing trends and the need for more sustainable operations require the design of robust and efficient transportation systems which additionally provide a high level of service for their users. In recent years, two innovative approaches have been proposed to overcome these challenges. That is, first, the use of autonomous buses as a replacement, or an addition to existing public transportation systems, and second, the consideration of consolidating multiple types of demand (i.e. passenger and freight) when planning and designing transportation systems. In this thesis, both approaches are studied and their impact on urban transportation systems is evaluated. This is achieved by developing novel simulation-based optimization models that consider technology-specific cost structures and capture the changed mode of operation for different vehicle technologies.In Papers I and II the deployment of autonomous buses on fixed-line public transportation networks is investigated. Changes in service frequency, vehicle capacity, and metrics corresponding to the level of service for public transportation users due to new vehicle technology are investigated. Furthermore, Paper I explores the transition from conventional public transportation systems to systems operated by autonomous buses, while Paper II investigates the changes in network design due to autonomous bus operations. The developed models are applied to case studies in Kista, Sweden, and Barkarby, Sweden. Two key results can be identified in these studies. First, autonomous bus deployment leads to an increase in service frequency, while waiting time for passengers can be reduced. Second, more passengers are attracted to autonomous bus lines by reducing the access walking distances and increased level-of-service. On more complex networks these trends are amplified. In each of Papers III and IV, a novel pickup and delivery model is proposed. The models consider vehicle concepts which allow for the consolidated transport of multiple demand types. In Paper III the vehicles can serve different types of demand by exchanging purpose-specific modules at dedicated service depots, while in Paper IV individual demand-specific vehicles can form platoons with modular length and varying configuration. The results of the extensive scenario studies and parameter analysis show that for multi-purpose vehicle operations (Paper III) the total costs can be reduced by an average of 13% and for platoon operations (Paper IV) the total costs are reduced by over 48%. In both models, the cost savings stem mainly from a reduction in fleet size, total vehicle trip duration, and the total distance traveled.
|
|
| 4. |
- Murekatete, Rachel Mundeli, 1981-
(author)
-
Sensitivity, Variation, and Application of Least-Cost Path Models in Landscape Connectivity Analysis and Corridor Planning
- 2022
-
Doctoral thesis (other academic/artistic)abstract
- In recent decades, Rwanda has been affected by the loss and fragmentation of natural habitats for native species of animals and plants. As a consequence, landscape connectivity—i.e., the degree to which a landscape facilitates or impedes the movement of organisms between resource patches—has considerably weakened or is even completely lost, causing detrimental effects on biodiversity, notably the reduction of populations of key native species. In order to counter this problem, one potential solution currently being explored by local planners in Rwanda consists of establishing conservation corridors for organisms to move safely between their habitat remnants. Specifically, this thesis was inspired by a project initiated by the Dian Fossey Gorilla Fund International, a conservation non-governmental organization (NGO) based in Rwanda, which consists of establishing a conservation corridor for pollinators.For their capabilities of storing, processing, and visualizing landscape data, geographic information systems (GIS) have been increasingly popular among conservation biologists and practitioners. Of particular relevance to connectivity analysis and corridor planning is the least-cost path model. A typical use of this model is such that one first estimates the cost for a certain action (e.g., movement by an organism or acquisition by a government) at each location of a given landscape and represents the results in the form of a raster surface, and then measures the degrees of connectivity between patches of interest in terms of effective distances, which are equated with least-cost path distances over the raster cost surface. While the least-cost path model is easy to use and available in virtually any commercial raster-based GIS, we observe that users of it often overlook some important assumptions, the violation of which might greatly affect the validity of the model’s outcome.The goal of this thesis is to provide a scientific contribution to landscape connectivity analysis and conservation corridor planning by 1) investigating the potential misuse or abuse of the conventional least-cost path model when sufficient information is not available on the underlying cost surface, 2) proposing an alternative model under such a circumstance and 3) demonstrating its relevance to conservation practice. More specifically, for the model to work, it is explicitly or implicitly assumed that, the optimality of a path is evaluated as the sum of the cost-weighted lengths of all its segments—cost-weighted, i.e., multiplied by their underlying cost values. The validity of this assumption must be questioned, however, if cost values are measured on a scale—e.g., an ordinal scale of measurement in Stevens’s typology—that does not permit arithmetic operations. In a typical practice of landscape connectivity analysis and corridor planning, the raster cost surface is created by transforming one or more sets of values (e.g., land cover type, land ownership, and elevation) attributed to cells into another set of such values (representing cost) through a function reflecting one or more criteria. A question arises: how certain can one be about the correctness of such a cost estimation function?There are at least four issues in the application of the least-cost path model to landscape connectivity analysis and corridor planning under uncertainty. First, while it is generally anticipated that different cost estimation functions lead to different least-cost paths (hence to different effective distances or different corridor locations), little is known on how such differences arise (or do not arise). Second, while it is generally recognized that the location and length of a least-cost path are both sensitive to the spatial resolution of the raster cost surface, little is known if they are always sensitive in the same way and to the same degree and if not, what makes them more (or less) sensitive. Third, when it is difficult to establish a fully connected corridor between target habitat areas (e.g., because of surrounding anthropogenic activities), the least-cost path (which is by definition fully connected) may not be useful at least in its original form. Lastly, even if the conventional least-cost path model may have inconsistent results in theory, it may well be continued to be used in practice, unless there is a sound alternative to it.The issues raised above are addressed through four studies corresponding to four respective papers which are appended to this thesis. While the first three studies use artificial landscape data generated by computers with varying spatial and non-spatial characteristics, the fourth study uses data on a real landscape. The first study (Paper 1) evaluates how the locations and lengths of least-cost paths (the latter of which are referred to as least-cost distances) vary with change in cost estimation parameters. This is done through a series of computational experiments, in which each of the artificial landscapes is converted into different cost surfaces by systematically varying parameters of a cost-estimation function, on which least-cost paths are generated. The locations and lengths of those paths are statistically analyzed to find sources of their variation. The second study (Paper 2) investigates how the least-cost distance is affected by the spatial resolution of the corresponding cost surface. This is also done through a series of computational experiments, in which each of the artificial landscapes is converted into a cost surface, which is, in turn, converted into different cost surfaces (different, i.e., only in their spatial resolutions) by systematically aggregating grid cells. Then, the statistical behavior of the ratio of the least-cost distance measured on a lower-resolution cost surface to that measured on a higher-resolution cost surface is analyzed. The third study (Paper 3) proposes the mini-max path model as an alternative to the least-cost path model. Unlike the conventional model (in which the optimality of a path is based on the sum of its length multiplied by the underlying cost values), the alternative model determines the optimality of a path using the length of a segment(s) of the path that intersects the cells having the maximum cost value (with a special tie-breaking rule). The performances of the two models are tested in one of the following two assumptions at a time: the cost values are measured on an ordinal scale or on a ratio scale. The fourth study (Paper 4) applies the model proposed in the third study to an ongoing conservation project of the Dian Fossey Gorilla Fund International that plans to design a ‘stepping-stone’ corridor—which is not fully connected but takes the form of a sequence of fragmented forest patches—between two core habitat areas of pollinator birds between two protected areas in Rwanda. The project does not have complete information on the study area and the target species and thus the project staff can only rank land cover types in terms of their suitability/cost for being part of the corridor. The utility of the model is tested with different assumptions on the behavior of the birds (e.g., minimum stepping stone size) as well as on the cost associated with the implementation of the corridor (e.g., cost for planting shrubs along the corridor to encourage the birds to use it).The first study finds that the same pair of terminal cells may well be connected by different least-cost paths on different cost surfaces though derived from the same landscape data. The variation among those paths is highly sensitive to the forms of spatial and non-spatial distributions of landscape elements (which cannot be controlled by users of the least-cost path model) as well as by those of cost values derived from them (which may be, at least indirectly, controlled by users of the model). The second study finds that least-cost distances measured on lower-resolution cost surfaces are generally highly correlated with—and useful predictors of—effective distances measured on higher-resolution cost surfaces. This relationship tends to be weakened when linear barriers to connectivity (e.g., roads and rivers) exist, but strengthened as distances increase and/or when linear barriers (if any) are detected by other presumably more accessible and affordable sources such as vector line data. The third study confirms the effectiveness of the conventional least-cost path model on ratio-scaled cost surfaces but finds that the alternative mini-max path model is mathematically sounder if the cost values are measured on an ordinal scale and practically useful if the problem is concerned not with the minimization of cost but with the maximization of some desirable condition such as suitability. The fourth study demonstrates the utility of the mini-max path model by effectively casting the stepping stone corridor problem as a special case of it. The model allows for a rapid first delineation of candidate routes for stepping stone corridors and facilitates the early exploratory stages of conservation projects.Major implications of this thesis to the research and practice in landscape connectivity analysis and conservation corridor planning with raster-based GIS are summarized as follows.When sufficient information is available for quantification of cost values, the conventional least-cost path model is a reasonable approach to use.However, it is worth trying or at least acknowledging alternatives that do not rely on the quantitative-cost assumption if the value of each cell only indicates the ordinal category of cost of intersecting that cell. Note in particular that information used for cost estimation in practice (e.g., expert opinions or public surveys) are often of subjective and qualitative nature.The highest-resolution data may not always be most effective—much less, most cost-effective—for the task being undertaken. The choice of spatial resolution of th
|
|
| 5. |
- Yang, Can, 1990-
(author)
-
Efficient Map Matching and Discovery of Frequent and Dominant Movement Patterns in GPS Trajectory Data
- 2020
-
Doctoral thesis (other academic/artistic)abstract
- The wide deployment of Global Positioning System (GPS) sensors for movement data collection has enabled a wide range of applications in transportation and urban planning. Frequent and dominant movement patterns embedded in GPS trajectory data provide valuable knowledge including the spatial and temporal distribution of frequent routes selected by the tracked objects and the regular movement behavior in certain regions. Discovering frequent and dominant movement patterns embedded in GPS trajectory data needs to address several tasks including (1) matching noisy trajectories to the road network (referred as map matching), (2) extracting frequent and dominant movement patterns, and (3) retrieving the distribution of these patterns over user-specified attribute (e.g., timestamp, travel mode, etc.). These tasks confront several challenges in observation error, efficiency and large pattern search space.To address those challenges, this thesis develops a set of algorithms and tools for efficient map matching and discovery of frequent and dominant movement patterns in GPS trajectory data. More specifically, two map matching algorithms are first developed, which improve the performance by precomputation and A-star search. Subsequently, a frequent route is extracted from map matched trajectories as a Contiguous Sequential Pattern (CSP). A novel CSP mining algorithm is developed by performing bidirectional pruning to efficiently search CSP and reduce redundancy in the result. After that, an efficient CSP comparison algorithm is developed to extend the bidirectional pruning to compare multiple sets of CSP. By comparing CSP mined from trajectories partitioned by a user-specified attribute, the distribution of frequent routes in the attribute space can be obtained. Finally, Regional Dominant Movement Pattern (RDMP) in trajectory data is discovered as regions where most of the objects follow a specific pattern. A novel movement feature descriptor called Directional Flow Image (DFI) is proposed to capture local directional movement information of trajectories in a multiple channel image and a convolutional neural network model is designed for DFI classification and RDMP detection.Comprehensive experiments on both real-world and synthetic GPS datasets demonstrate the efficiency of the proposed algorithms as well as their superiority over state-of-the-art methods. The two map matching algorithms achieve considerable performance in matching densely sampled GPS data to small scale network and sparsely sampled GPS data to large scale network respectively. The CSP mining and comparison algorithms significantly outperform their competitors and effectively retrieve both spatial and temporal distribution of frequent routes. The RDMP detection method can robustly discover ten classes of commonly encountered RDMP in real-world trajectory data. The proposed methods in this thesis collectively provide an effective solution for answering sophisticated queries concerning frequent and dominant movement patterns in GPS trajectory data.
|
|
| 6. |
- Palmberg, Robin, 1992-, et al.
(author)
-
Towards a better understanding of the health impacts of one’s movement in space and time
- 2022
-
In: Journal of Literature and Science. - : Informa UK Limited. - 1754-646X. ; , s. 1-24
-
Journal article (peer-reviewed)abstract
- To better understand the interactions between physical built environment conditions and one’s well-being, we created a passive data collector for travellers and made the first step towards an explanatory model based on psychophysiological relations. By measuring biometric information from select trial participants we showed how different controlled factors are affecting the heart rate of the participants. A regression model with the impact factors such as speed, location, time and activity (accelerometer data) reveals how the factors relate to each other and how they correlate with the recorded individual’s heart rates throughout the observed period. For examples, the results show that the increase in movement speed is not linearly correlated with the heart rate. One’s heart rate would increase significantly when the individual reaches brisk walking and running speed, but not before nor after. Early morning and early evening time slots were the time where the observed individuals have the highest heart rates, which may correlate to individuals’ commute activities. Heart rates at the office would be lower than at home, which might correlate to more physical activities in the household.
|
|
| 7. |
- Prelipcean, Adrian Corneliu, 1989-
(author)
-
Capturing travel entities to facilitate travel behaviour analysis : A case study on generating travel diaries from trajectories fused with accelerometer readings
- 2016
-
Licentiate thesis (other academic/artistic)abstract
- The increase in population, accompanied by an increase in the availability of travel opportunities have kindled the interest in understanding how people make use of the space around them and their opportunities. Understanding the travel behaviour of individuals and groups is difficult because of two main factors: the travel behaviour's wide coverage, which encompasses different research areas, all of which model different aspects of travel behaviour, and the difficulty of obtaining travel diaries from large groups of respondents, which is imperative for analysing travel behaviour and patterns.A travel diary allows an individual to describe how she performed her activities by specifying the destinations, purposes and travel modes occurring during a predefined period of time. Travel diaries are usually collected during a large-scale survey, but recent developments show that travel diaries have important drawbacks such as the collection bias and the decreasing response rate. This led to a surge of studies that try to complement or replace the traditional declaration-based travel diary collection with methods that extract travel diary specific information from trajectories and auxiliary datasets.With the automation of travel diary generation in sight, this thesis presents a suitable method for collecting data for travel diary automation (Paper I), a framework to compare multiple travel diary collection systems (Paper II), a set of relevant metrics for measuring the performance of travel mode segmentation methods (Paper III), and applies these concepts during different case studies (Paper IV).
|
|
| 8. |
- Sadeghian, Paria
(author)
-
Human mobility behavior : Transport mode detection by GPS data
- 2021
-
Licentiate thesis (other academic/artistic)abstract
- GPS tracking data are widely used to understand human travel behavior and to evaluate the impact of travel. A major advantage with the usage of GPS tracking devices for collecting data is that it enables the researcher to collect large amounts of highly accurate and detailed human mobility data. However, unlabeled GPS tracking data does not easily lend itself to detecting transportation mode and this has given rise to a range of methods and algorithms for this purpose. The algorithms used vary in design and functionality, from defining specific rules to advanced machine learning algorithms. There is however no previous comprehensive review of these algorithms and this thesis aims to identify their essential features and methods and to develop and demonstrate a method for the detection of transport mode in GPS tracking data. To do this, it is necessary to have a detailed description of the particular journey undertaken by an individual. Therefore, as part of the investigation, a microdata analytic approach is applied to the problem areas, including the stages of data collection, data processing, analyzing the data, and decision making.In order to fill the research gap, Paper I consists of a systematic literature review of the methods and essential features used for detecting the transport mode in unlabeled GPS tracking data. Selected empirical studies were categorized into rule-based methods, statistical methods, and machine learning methods. The evaluation shows that machine learning algorithms are the most common. In the evaluation, I compared the methods previously used, extracted features, types of dataset, and model accuracy of transport mode detection. The results show that there is no standard method used in transport mode detection. In the light of these results, I propose in Paper II a stepwise methodology to detect five transport modes taking advantage of the unlabeled GPS data by first using an unsupervised algorithm to detect the five transport modes. A GIS multi-criteria process was applied to label part of the dataset. The performance of the five supervised algorithms was evaluated by applying them to different portions of the labeled dataset. The results show that stepwise methodology can achieve high accuracy in detecting the transport mode by labeling only 10% of the data from the entire dataset. For the future, one interesting area to explore would be the application of the stepwise methodology to a balanced and larger dataset. A semi-supervised deep-learning approach is suggested for development in transport mode detection, since this method can detect transport modes with only small amounts of labeled data. Thus, the stepwise methodology can be improved upon for further studies.
|
|
