Solving the Median Shortest Path Problem in the Planning and Design of Urban Transportation Networks Using a Vector Labeling Algorithm

This paper proposes an alternative algorithm to solve the median shortest path problem (MSPP) in the planning and design of urban transportation networks. The proposed vector labeling algorithm is based on the labeling of each node in terms of a multiple and conflicting vector of objectives which deletes cyclic, infeasible and extreme-dominated paths in the criteria space imposing cyclic break (CB), path cost constraint (PCC) and access cost parameter (ACP) respectively. The output of the algorithm is a set of Pareto optimal paths (POP) with an objective vector from predetermined origin to destination nodes. Thus, this paper formulates an algorithm to identify a non-inferior solution set of POP based on a non-dominated set of objective vectors that leaves the ultimate decision to decision-makers. A numerical experiment is conducted using an artificial transportation network in order to validate and compare results. Sensitivity analysis has shown that the proposed algorithm is more efficient and advantageous over existing solutions in terms of computing execution time and memory space used.     

Multi-agent simulation of individual mobility behavior in carpooling

Carpooling is an emerging alternative transportation mode that is eco-friendly and sustainable as it enables commuters to save time, travel resource, reduce emission and traffic congestion. The procedure of carpooling consists of a number of steps namely; (i) create a motive to carpool, (ii) communicate this motive with other agents, (iii) negotiate a plan with the interested agents, (iv) execute the agreed plans, and (v) provide a feedback to all concerned agents. In this paper, we present a conceptual design of an agent-based model (ABM) for the carpooling a that serves as a proof of concept. Our model for the carpooling application is a computational model that is used for simulating the interactions of autonomous agents and to analyze the effects of change in factors related to the infrastructure, behavior and cost. In our carpooling application, we use agent profiles and social networks to initiate our agent communication model and then employ a route matching algorithm, and a utility function to trigger the negotiation process between agents. We developed a prototype of our agent-based carpooling application based on the work presented in this paper and carried out a validation study of our results with real data collected in Flanders, Belgium.     

Finding the k reliable shortest paths under travel time uncertainty

This paper investigates the problem of finding the K reliable shortest paths (KRSP) in stochastic networks under travel time uncertainty. The KRSP problem extends the classical K loopless shortest paths problem to the stochastic networks by explicitly considering travel time reliability. In this study, a deviation path approach is established for finding K α-reliable paths in stochastic networks. A deviation path algorithm is proposed to exactly solve the KRSP problem in large-scale networks. The A^* technique is introduced to further improve the KRSP finding performance. A case study using real traffic information is performed to validate the proposed algorithm. The results indicate that the proposed algorithm can determine KRSP under various travel time reliability values within reasonable computational times. The introduced A^* technique can significantly improve KRSP finding performance.     

Stable ride-sharing matching for the commuters with payment design

Ride-sharing enables reduction of private car usage for commuting. This paper proposes a stable matching model for the ride-sharing which aims to minimize the travel cost of all commuters. A payment for the ride-sharing is designed considering the equity and incentive. An algorithm based on the deferred acceptance algorithm is proposed for the model. To verify the model and algorithm, cases with different scales are presented based on Dalian. The results illustrate that the compensation, time window and driver-to-rider ratios can affect the successful matching rate.

     

Clustering of heterogeneous networks with directional flows based on “Snake” similarities

Aggregated network level modeling and control of traffic in urban networks have recently gained a lot of interest due to unpredictability of travel behaviors and high complexity of physical modeling in microscopic level. Recent research has shown the existence of well-defined Macroscopic Fundamental Diagrams (MFDs) relating average flow and density in homogeneous networks. The concept of MFD allows to design real-time traffic control schemes specifically hierarchical perimeter control approaches to alleviate or postpone congestion. Considering the fact that congestion is spatially correlated in adjacent roads and it propagates spatiotemporaly with finite speed, describing the main pockets of congestion in a heterogeneous city with small number of clusters is conceivable. In this paper, we propose a three-step clustering algorithm to partition heterogeneous networks into connected homogeneous regions, which makes the application of perimeter control feasible. The advantages of the proposed method compared to the existing ones are the ability of finding directional congestion within a cluster, robustness with respect to parameters calibration, and its good performance for networks with low connectivity and missing data. Firstly, we start to find a connected homogeneous area around each road of the network in an iterative way (i.e. it forms a sequence of roads). Each sequence of roads, defined as ‘snake’, is built by starting from a single road and iteratively adding one adjacent road based on its similarity to join previously added roads in that sequence. Secondly, based on the obtained sequences from the first step, a similarity measure is defined between each pair of the roads in the network. The similarities are computed in a way that put more weight on neighboring roads and facilitate connectivity of the clusters. Finally, Symmetric Non-negative Matrix Factorization (SNMF) framework is utilized to assign roads to proper clusters with high intra-similarity and low inter-similarity. SNMF partitions the data by providing a lower rank approximation of the similarity matrix. The proposed clustering framework is applied in medium and large-size networks based on micro-simulation and empirical data from probe vehicles. In addition, the extension of the algorithm is proposed to deal with the networks with sparse measurements where information of some links is missing. The results show the effectiveness and robustness of the extended algorithm applied to simulated network under different penetration rates (percentage of links with data).     

Vehicle reidentification and travel time measurement on congested freeways

The paper presents an algorithm for matching individual vehicles measured at a freeway detector with the vehicles’ corresponding measurements taken earlier at another detector located upstream. Although this algorithm is potentially compatible with many vehicle detector technologies, the paper illustrates the method using existing dual-loop detectors to measure vehicle lengths. This detector technology has seen widespread deployment for velocity measurement. Since the detectors were not developed to measure vehicle length, these measurements can include significant errors. To overcome this problem, the algorithm exploits drivers’ tendencies to retain their positions within dense platoons. The otherwise complicated task of vehicle reidentification is carried out by matching these platoons rather than individual vehicles. Of course once a vehicle has been matched across neighboring detector stations, the difference in its arrival time at each station defines the vehicle’s travel time on the intervening segment.Findings from an application of the algorithm over a 1/3 mile long segment are presented herein and they indicate that a sufficient number of vehicles can be matched for the purpose of traffic surveillance. As such, the algorithm extracts travel time data without requiring the deployment of new detector technologies. In addition to the immediate impacts on traffic monitoring, the work provides a means to quantify the potential benefits of emerging detector technologies that promise to extract more detailed information from individual vehicles.     

A route-based solution algorithm for dynamic user equilibrium assignments

The aim of this study is to establish a method to calculate good quality user equilibrium assignments under time varying conditions. For this purpose, it introduces a dynamic network loading method that can maintain correct flow propagation as well as flow conservation, and it shows a novel route-based solution algorithm. This novel algorithm turns out to be convenient and logically plausible compared to the conventional [Frank, M., Wolfe, P., 1956. An algorithm for quadratic programming. Naval Research Logistics Quarterly 3, 95–110] algorithm, because the former does not require evaluation of an objective function and it finds solutions maintaining correct flow propagation in the time-varying network conditions. The application of novel dynamic network loading method and solution algorithm to test networks shows that we can find high quality dynamic user equilibrium assignment. This is illustrated in an example network using the deterministic queuing model for a link performance function and associating costs and flows in a predictive way in discrete time.     

Traffic assignment by paired alternative segments

The static user-equilibrium (UE) traffic assignment model is widely used in practice. One main computational challenge in this model is to obtain sufficiently precise solutions suitable for scenario comparisons, as quickly as possible. An additional computational challenge stems from the need in practice to perform analyses based on route flows, which are not uniquely determined by the UE condition. Past research focused mainly on the first aspect. The purpose of this paper is to describe an algorithm that addresses both issues. The traffic assignment by paired alternative segments (TAPAS) algorithm, focuses on pairs of alternative segments as the key building block to the UE solution. A condition of proportionality, which is practically equivalent to entropy maximization, is used to choose one stable route flow solution. Numerical results for five publicly available networks, including two large-scale realistic networks, show that the algorithm can identify highly precise solutions that maintain proportionality in relatively short computation times.     

Effective arterial road incident detection: A Bayesian network based algorithm

Timely and accurate incident detection is an essential part of any successful advanced traffic management system. The complex nature of arterial road traffic makes automated incident detection a real challenge. Stable performance and strong transferability remain major issues concerning the existing incident detection algorithms. A new arterial road incident detection algorithm TSC_ar is presented in this paper. In this algorithm, Bayesian networks are used to quantitatively model the causal dependencies between traffic events (e.g. incident) and traffic parameters. Using real time traffic data as evidence, the Bayesian networks update the incident probability at each detection interval through two-way inference. An incident alarm is issued when the estimated incident probability exceeds the predefined decision threshold. The Bayesian networks allow us to subjectively build existing traffic knowledge into their conditional probability tables, which makes the knowledge base for incident detection robust and dynamic. Meanwhile, we incorporate intersection traffic signals into traffic data processing. A total of 40 different types of arterial road incidents are simulated to test the performance of the algorithm. The high detection rate of 88% is obtained while the false alarm rate of the algorithm is maintained as low as 0.62%. Most importantly, it is found that both the detection rate and false alarm rate are not sensitive to the incident decision thresholds. This is the unique feature of the TSC_ar algorithm, which suggests that the Bayesian network approach is advanced in enabling effective arterial road incident detection.     

Long distance truck tracking from advanced point detectors using a selective weighted Bayesian model

Truck flow patterns are known to vary by season and time-of-day, and to have important implications for freight modeling, highway infrastructure design and operation, and energy and environmental impacts. However, such variations cannot be captured by current truck data sources such as surveys or point detectors. To facilitate development of detailed truck flow pattern data, this paper describes a new truck tracking algorithm that was developed to estimate path flows of trucks by adopting a linear data fusion method utilizing weigh-in-motion (WIM) and inductive loop point detectors. A Selective Weighted Bayesian Model (SWBM) was developed to match individual vehicles between two detector locations using truck physical attributes and inductive waveform signatures. Key feature variables were identified and weighted via Bayesian modeling to improve vehicle matching performance. Data for model development were collected from two WIM sites spanning 26 miles in California where only 11 percent of trucks observed at the downstream site traversed the whole corridor. The tracking model showed 81 percent of correct matching rate to the trucks declared as through trucks from the algorithm. This high accuracy showed that the tracking model is capable of not only correctly matching through vehicles but also successfully filtering out non-through vehicles on this relatively long distance corridor. In addition, the results showed that a Bayesian approach with full integration of two complementary detector data types could successfully track trucks over long distances by minimizing the impacts of measurement variations or errors from the detection systems employed in the tracking process. In a separate case study, the algorithm was implemented over an even longer 65-mile freeway section and demonstrated that the proposed algorithm is capable of providing valuable insights into truck travel patterns and industrial affiliation to yield a comprehensive truck activity data source.     

Shortest route algorithm with movement prohibitions

This paper presents an algorithm with movement prohibitions which eliminates some problems encountered in network representation used for traffic assignment models, and further allows the representation of the network to be simplified. The paper first presents an appraisal of some proposed methods and reviews the basic concept of existing shortest-route algorithms. The problem of obtaining shortest routes in networks with movement prohibitions is formulated and an algorithm presented. The computational procedure is illustrated by means of a numerical example. The computational efficiency of the algorithm is tested and the test results show that the algorithm is very efficient.     

Map-matching poor-quality GPS data in urban environments: the pgMapMatch package

Global Positioning System (GPS) data have become ubiquitous in many areas of transportation planning and research. The usefulness of GPS data often depends on the points being matched to the true sequence of edges on the underlying street network – a process known as ‘map matching.’ This paper presents a new map-matching algorithm that is designed for use with poor-quality GPS traces in urban environments, where drivers may circle for parking and GPS quality may be affected by underground parking and tall buildings. The paper is accompanied by open-source Python code that is designed to work with a PostGIS spatial database. In a test dataset that includes many poor-quality traces, our new algorithm accurately matches about one-third more traces than a widely available alternative. Our algorithm also provides a ‘match score’ that evaluates the likelihood that the match for an individual trace is correct, reducing the need for manual inspection.     

Design and evaluation of an automated highway system with optimized lane assignment

Highway automation entails the application of control, sensing and communication technologies to road vehicles, with the objective of improving highway performance. It has been envisioned that automation could increase highway capacity by a factor of three. The purpose of this paper is to develop a methodology for predicting highway capacity and comparing alternative automation concepts. It extends earlier research on optimal lane assignment on an automated highway to dynamic networks. A path-based linear program is formulated and solved through a column generation method. The algorithm has been applied to networks with as many as 20 on and off ramps, 80 segments, 4 lanes and 12 time periods.     

A real-time system for monitoring driver fatigue

ABSTRACT

This paper presents a nonintrusive prototype computer vision system for real-time fatigue driving detection. First, we use Haar-like features to detect a driver’s face and conduct tracking by introducing an improved Camshift algorithm. Second, we propose a new eye-detection algorithm that combines the Adaboost algorithm with template matching to reduce computational costs and add an eye-validation process to increase the accuracy of the detection rate. Third, and different from other methods focusing on detecting eyes using the ‘bright pupil’ effect, which only works well only for certain constrained lighting conditions, our method detects and estimates the iris center in the hue (H) channel of the hue, saturation, value color space and fits the iris with an ellipse. After extracting the eye fatigue features, we calculate the PERCLOS measurement for fatigue evaluation. This system has been tested on the IMM Face Database, which contains more than 200 faces, and in a real-time test. The experimental results show that the system possesses good accuracy and robustness.     

Efficient solution algorithm for finding spatially dependent reliable shortest path in road networks

Travel times are generally stochastic and spatially correlated in congested road networks. However, very few existing route guidance systems (RGS) can provide reliable guidance services to aid travellers planning their trips with taking account explicitly travel time reliability constraint. This study aims to develop such a RGS with particular consideration of travellers' concern on travel time reliability in congested road networks with uncertainty. In this study, the spatially dependent reliable shortest path problem (SD‐RSPP) is formulated as a multi‐criteria shortest path‐finding problem in road networks with correlated link travel times. Three effective dominance conditions are established for links with different levels of travel time correlations. An efficient algorithm is proposed to solve SD‐RSPP by adaptively using three established dominance conditions. The complexities of road networks in reality are also explicitly considered. To demonstrate the applicability of proposed algorithm, a comprehensive case study is carried out in Hong Kong. The results of case study show that the proposed solution algorithm is robust to take account of travellers' multiple routing criteria. Computational results demonstrate that the proposed solution algorithm can determine the reliable shortest path on real‐time basis for large‐scale road networks. Copyright © 2016 John Wiley & Sons, Ltd.     

An efficient algorithm for building min-path trees for all origins in a multi-class network

Urban transportation planning models consume untold hours of computer time building zillions of min-path trees. Their networks have tens of thousands of arcs, accommodate several trip classes, and solve the traffic equilibrium problem via many, many iterations of min-path calculations for thousands of origins and destinations. This paper presents a simple algorithm that couples restricted reduced-cost analysis with label-correcting, which can reduce this min-path tree building time substantially. For a given origin, the algorithm rapidly transforms a tree for one class to that for next class. Test results using synthetic data suggest that its application to real networks should experience speedups of at least a factor of 2.0 and perhaps beyond 5.0.     

Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing

Emerging transportation network services, such as customized buses, hold the promise of expanding overall traveler accessibility in congested metropolitan areas. A number of internet-based customized bus services have been planned and deployed for major origin-destination (OD) pairs to/from inner cities with limited physical road infrastructure. In this research, we aim to develop a joint optimization model for addressing a number of practical challenges for providing flexible public transportation services. First, how to maintain minimum loading rate requirements and increase the number of customers per bus for the bus operators to reach long-term profitability. Second, how to optimize detailed bus routing and timetabling plans to satisfy a wide range of specific user constraints, such as passengers’ pickup and delivery locations with preferred time windows, through flexible decision for matching passengers to bus routes. From a space-time network modeling perspective, this paper develops a multi-commodity network flow-based optimization model to formulate a customized bus service network design problem so as to optimize the utilization of the vehicle capacity while satisfying individual demand requests defined through space-time windows. We further develop a solution algorithm based on the Lagrangian decomposition for the primal problem and a space-time prism based method to reduce the solution search space. Case studies using both the illustrative and real-world large-scale transportation networks are conducted to demonstrate the effectiveness of the proposed algorithm and its sensitivity under different practical operating conditions.     

Large-scale dynamic transportation network simulation: A space-time-event parallel computing approach

This paper describes a computationally efficient parallel-computing framework for mesoscopic transportation simulation on large-scale networks. By introducing an overall data structure for mesoscopic dynamic transportation simulation, we discuss a set of implementation issues for enabling flexible parallel computing on a multi-core shared memory architecture. First, we embed an event-based simulation logic to implement a simplified kinematic wave model and reduce simulation overhead. Second, we present a space-time-event computing framework to decompose simulation steps to reduce communication overhead in parallel execution and an OpenMP-based space-time-processor implementation method that is used to automate task partition tasks. According to the spatial and temporal attributes, various types of simulation events are mapped to independent logical processes that can concurrently execute their procedures while maintaining good load balance. We propose a synchronous space-parallel simulation strategy to dynamically assign the logical processes to different threads. The proposed method is then applied to simulate large-scale, real-world networks to examine the computational efficiency under different numbers of CPU threads. Numerical experiments demonstrate that the implemented parallel computing algorithm can significantly improve the computational efficiency and it can reach up to a speedup of 10 on a workstation with 32 computing threads.     

An algorithm for finding reasonable paths in transit networks

In this paper, reasonable paths in transit networks are defined as possible paths that satisfy the acceptable time criterion and transfer‐walk criterion. A recursive algorithm for finding all of the reasonable paths in a transit network that does not involve a rapid increase in program run‐time with network size is presented. Realistic transit networks in Hong Kong and Guangzhou were selected as case studies of the different phases of the development of a trip planning system. Transport planning practitioners and potential users were invited to test the system to evaluate its performance. The results of the prototype evaluation were satisfactory, and the viability of the system as a useful tool for supporting decision‐making has been confirmed by the positive feedback that was obtained from survey questionnaires.