Transport Network Design Problem under Uncertainty: A Review and New Developments

This paper aims to provide a state-of-the-art review of the transport network design problem (NDP) under uncertainty and to present some new developments on a bi-objective-reliable NDP (BORNDP) model that explicitly optimizes the capacity reliability and travel time reliability under demand uncertainty. Both are useful performance measures that can describe the supply-side reliability and demand-side reliability of a road network. A simulation-based multi-objective genetic algorithm solution procedure, which consists of a traffic assignment algorithm, a genetic algorithm, a Pareto filter, and a Monte-Carlo simulation, is developed to solve the proposed BORNDP model. A numerical example based on the capacity enhancement problem is presented to demonstrate the tradeoff between capacity reliability and travel time reliability in the NDP.     

A simulation‐based reliability assessment approach for congested transit network

This paper is an attempt to develop a generic simulation‐based approach to assess transit service reliability, taking into account interaction between network performance and passengers' route choice behaviour. Three types of reliability, say, system wide travel time reliability, schedule reliability and direct boarding waiting‐time reliability are defined from perspectives of the community or transit administration, the operator and passengers. A Monte Carlo simulation approach with a stochastic user equilibrium transit assignment model embedded is proposed to quantify these three reliability measures of transit service. A simple transit network with a bus rapid transit (BRT) corridor is analysed as a case study where the impacts of BRT components on transit service reliability are evaluated preliminarily.     

Comparative analysis of three user equilibrium models under stochastic demand

Recent empirical studies on the value of time and reliability reveal that travel time variability plays an important role on travelers' route choice decision process. It can be considered as a risk to travelers making a trip. Therefore, travelers are not only interested in saving their travel time but also in reducing their risk. Typically, risk can be represented by two different aspects: acceptable risk and unacceptable risk. Acceptable risk refers to the reliability aspect of acceptable travel time, which is defined as the average travel time plus the acceptable additional time (or buffer time) needed to ensure more frequent on‐time arrivals, while unacceptable risk refers to the unreliability aspect of unacceptable late arrivals (though infrequent) that have a travel time excessively higher than the acceptable travel time. Most research in the network equilibrium based approach to modeling travel time variability ignores the unreliability aspect of unacceptable late arrivals. This paper examines the effects of both reliability and unreliability aspects in a network equilibrium framework. Specifically, the traditional user equilibrium model, the demand driven travel time reliability‐based user equilibrium model, and the α‐reliable mean‐excess travel time user equilibrium model are considered in the investigation under an uncertain environment due to stochastic travel demand. Numerical results are presented to examine how these models handle risk under travel time variability.     

An integrated Bayesian approach for passenger flow assignment in metro networks

This paper proposes an integrated Bayesian statistical inference framework to characterize passenger flow assignment model in a complex metro network. In doing so, we combine network cost attribute estimation and passenger route choice modeling using Bayesian inference. We build the posterior density by taking the likelihood of observing passenger travel times provided by smart card data and our prior knowledge about the studied metro network. Given the high-dimensional nature of parameters in this framework, we apply the variable-at-a-time Metropolis sampling algorithm to estimate the mean and Bayesian confidence interval for each parameter in turn. As a numerical example, this integrated approach is applied on the metro network in Singapore. Our result shows that link travel time exhibits a considerable coefficient of variation about 0.17, suggesting that travel time reliability is of high importance to metro operation. The estimation of route choice parameters conforms with previous survey-based studies, showing that the disutility of transfer time is about twice of that of in-vehicle travel time in Singapore metro system.     

Distributed algorithm for empty vehicles management in personal rapid transit (PRT) network

In this paper, an original heuristic algorithm of empty vehicles management in personal rapid transit network is presented. The algorithm is used for the delivery of empty vehicles for waiting passengers, for balancing the distribution of empty vehicles within the network, and for providing an empty space for vehicles approaching a station. Each of these tasks involves a decision on the trip that has to be done by a selected empty vehicle from its actual location to some determined destination. The decisions are based on a multi‐parameter function involving a set of factors and thresholds. An important feature of the algorithm is that it does not use any central database of passenger input (demand) and locations of free vehicles. Instead, it is based on the local exchange of data between stations: on their states and on the vehicles they expect. Therefore, it seems well‐tailored for a distributed implementation. The algorithm is uniform, meaning that the same basic procedure is used for multiple tasks using a task‐specific set of parameters. Copyright © 2016 John Wiley & Sons, Ltd.     

A reliability‐based network design problem

This paper presents a reliability‐based network design problem. A network reliability concept is embedded into the continuous network design problem in which travelers' route choice behavior follows the stochastic user equilibrium assumption. A new capacity‐reliability index is introduced to measure the probability that all of the network links are operated below their capacities when serving different traffic patterns deviating from the average condition. The reliability‐based network design problem is formulated as a bi‐level program in which the lower level sub‐program is the probit‐based stochastic user equilibrium problem and the upper level sub‐program is the maximization of the new capacity reliability index. The lower level sub‐program is solved by a variant of the method of successive averages using the exponential average to represent the learning process of network users on a daily basis that results in the daily variation of traffic‐flow pattern, and Monte Carlo stochastic loading. The upper level sub‐program is tackled by means of genetic algorithms. A numerical example is used to demonstrate the concept of the proposed framework.     

Network reliability‐based optimal toll design

Optimal toll design from a network reliability point of view is addressed in this paper. Improving network reliability is proposed as a policy objective of road pricing. A reliability‐based optimal toll design model, where on the upper level network performance including travel time reliability is optimized, while on the lower level a dynamic user‐equilibrium is achieved, is presented. Road authorities aim to optimize network travel time reliability by setting tolls in a network design problem. Travelers are influenced by these tolls and make route and trip decisions by considering travel times and tolls. Network performance reliability is analyzed for a degradable network with elastic and fluctuated travel demand, which integrates reliability and uncertainty, dynamic network equilibrium models, and Monte Carlo methods. The proposed model is applied to a small hypothesized network for which optimal tolls are derived. The network travel time reliability is indeed improved after implementing optimal tolling system. Trips may have a somewhat higher, but more reliable, travel time.     

Transit network design based on travel time reliability

This paper presents a transit network optimization method, in which travel time reliability on road is considered. A robust optimization model, taking into account the stochastic travel time, is formulated to satisfy the demand of passengers and provide reliable transit service. The optimization model aims to maximize the efficiency of passenger trips in the optimized transit network. Tabu search algorithm is defined and implemented to solve the problem. Then, transit network optimization method proposed in this paper is tested with two numerical examples: a simple route and a medium-size network. The results show the proposed method can effectively improve the reliability of a transit network and reduce the travel time of passengers in general.     

Equity based land‐use and transportation problem

Due to additional trip production by land use development, the O‐D travel costs between some O‐D pairs may also change intuitively. This leads to positive and negative impacts on network users traveling between different O‐D pairs. Therefore the equity issue about the benefit distribution gained from the land‐use development problem is raised. This paper proposes an Equity based Land‐Use Transportation Problem (ELUTP) which is intended to examine the benefit distribution among the network users and the resulting equity associated with land‐use development problem in terms of the change of equilibrium O‐D travel cost. In the resulting bi‐level programming model, the upper level sub‐problem maximizes traffic production incorporating equity constraints, while the lower level sub‐problem is a combined trip distribution/assignment user equilibrium problem. Genetic algorithm based method is applied to test the models using an example network.     

Charging infrastructure demands of shared-use autonomous electric vehicles in urban areas

Ride-hailing is a clear initial market for autonomous electric vehicles (AEVs) because it features high vehicle utilization levels and strong incentive to cut down labor costs. An extensive and reliable network of recharging infrastructure is the prerequisite to launch a lucrative AEV ride-hailing fleet. Hence, it is necessary to estimate the charging infrastructure demands for an AEV fleet in advance. This study proposes a charging system planning framework for a shared-use AEV fleet providing ride-hailing services in urban area. We first adopt an agent-based simulation model, called BEAM, to describe the complex behaviors of both passengers and transportation systems in urban cities. BEAM simulates the driving, parking and charging behaviors of the AEV fleet with range constraints and identifies times and locations of their charging demands. Then, based on BEAM simulation outputs, we adopt a hybrid algorithm to site and size charging stations to satisfy the charging demands subject to quality of service requirements. Based on the proposed framework, we estimate the charging infrastructure demands and calculate the corresponding economics and carbon emission impacts of electrifying a ride-hailing AEV fleet in the San Francisco Bay Area. We also investigate the impacts of various AEV and charging system parameters, e.g., fleet size, vehicle battery capacity and rated power of chargers, on the ride-hailing system’s overall costs.     

Network equilibrium for congested multi‐mode networks with elastic demand

This paper proposes an elastic demand network equilibrium model for networks with transit and walking modes. In Hong Kong, the multi‐mode transit system services over 90% of the total journeys and the demand on it is continuously increasing. Transit and walking modes are related to each other as transit passengers have to walk to and from transit stops. In this paper, the multi‐mode elastic‐demand network equilibrium problem is formulated as a variational inequality problem where the combined mode and route choices are modeled in a hierarchical logit structures and the total travel demand for each origin‐destination pair is explicitly given by an elastic demand function. In addition, the capacity constraint for transit vehicles and the effects of bi‐directional flows on walkways are considered in the proposed model. All these congestion effects are taken into account for modeling the travel choices. A solution algorithm is developed to solve the multi‐mode elastic‐demand network equilibrium model. It is based on a Block Gauss‐Seidel decomposition approach coupled with the method of successive averages. A numerical example is used to illustrate the application of the proposed model and solution algorithm.     

Dynamic travel mode searching and switching analysis considering hidden model preference and behavioral decision processes

This paper proposes a conceptual framework to model the travel mode searching and switching dynamics. The proposed approach is structurally different from existing mode choice models in the way that a non-homogeneous hidden Markov model (HMM) has been constructed and estimated to model the dynamic mode srching process. In the proposed model, each hidden state represents the latent modal preference of each traveler. The empirical application suggests that the states can be interpreted as car loving and carpool/transit loving, respectively. At each time period, transitions between the states are functions of time-varying covariates such as travel time and travel cost of the habitual modes. The level-of-service (LOS) changes are believed to have an enduring impact by shifting travelers to a different state. While longitudinal data is not readily available, the paper develops an easy-to-implement memory-recall survey to collect required process data for the empirical estimation. Bayesian estimation and Markov chain Monte Carlo method have been applied to implement full Bayesian inference. As demonstrated in the paper, the estimated HMM is reasonably sensitive to mode-specific LOS changes and can capture individual and system dynamics. Once applied with travel demand and/or traffic simulation models, the proposed model can describe time-dependent multimodal behavior responses to various planning/policy stimuli.     

Location configuration design for Dynamic Message Signs under stochastic incident and ATIS scenarios

This paper proposes a methodology for deploying permanent Dynamic Message Signs (DMS) in a vehicular traffic network. Of particular interest is the planning problem to optimize the number of DMS to deploy in conjunction with Advanced Traveler Information Systems (ATIS), operating and maintenance cost of DMS, and incident-related user cost under random traffic incident situations. The optimal DMS location design problem discussed herein is formulated as a two-stage stochastic program with recourse (SPR). A Tabu search algorithm combined with dynamic traffic simulation and assignment approaches are employed to solve this problem. A case study performed on the Fort-Worth, Texas network highlights the effectiveness of the proposed framework and illustrates the affect factors such as demand, network structure, DMS response rate, and incident characteristics have on the solution. The numerical results suggest that designing and deploying DMS and ATIS jointly is more cost-effective and efficient than the sequential build-out of the two from the system management perspective.     

A computational model for the probit‐based dynamic stochastic user optimal traffic assignment problem

This paper focuses on computational model development for the probit‐based dynamic stochastic user optimal (P‐DSUO) traffic assignment problem. We first examine a general fixed‐point formulation for the P‐DSUO traffic assignment problem, and subsequently propose a computational model that can find an approximated solution of the interest problem. The computational model includes four components: a strategy to determine a set of the prevailing routes between each origin–destination pair, a method to estimate the covariance of perceived travel time for any two prevailing routes, a cell transmission model‐based traffic performance model to calculate the actual route travel time used by the probit‐based dynamic stochastic network loading procedure, and an iterative solution algorithm solving the customized fixed‐point model. The Ishikawa algorithm is proposed to solve the computational model. A comparison study is carried out to investigate the efficiency and accuracy of the proposed algorithm with the method of successive averages. Two numerical examples are used to assess the computational model and the algorithm proposed. Results show that Ishikawa algorithm has better accuracy for smaller network despite requiring longer computational time. Nevertheless, it could not converge for larger network. Copyright © 2010 John Wiley & Sons, Ltd.     

Dynamic stochastic transit assignment with explicit seat allocation model

This paper proposes a stochastic dynamic transit assignment model with an explicit seat allocation process. The model is applicable to a general transit network. A seat allocation model is proposed to estimate the probability of a passenger waiting at a station or on-board to get a seat. The explicit seating model allows a better differentiation of in-vehicle discomfort experienced by sitting and standing passengers. The paper proposes simulation procedures for calculating the sitting probability of each type of passengers. A heuristic solution algorithm for finding an equilibrium solution of the proposed model is developed and tested. The numerical tests show significant influences of the seat allocation model on equilibrium departure time and route choices of passengers. The proposed model is also applied to evaluate the effects of an advanced public transport information system (APTIS) on travellers’ decision-making.     

Spatial and temporal characterization of travel patterns in a traffic network using vehicle trajectories

This paper presents a trajectory clustering method to discover spatial and temporal travel patterns in a traffic network. The study focuses on identifying spatially distinct traffic flow groups using trajectory clustering and investigating temporal traffic patterns of each spatial group. The main contribution of this paper is the development of a systematic framework for clustering and classifying vehicle trajectory data, which does not require a pre-processing step known as map-matching and directly applies to trajectory data without requiring the information on the underlying road network. The framework consists of four steps: similarity measurement, trajectory clustering, generation of cluster representative subsequences, and trajectory classification. First, we propose the use of the Longest Common Subsequence (LCS) between two vehicle trajectories as their similarity measure, assuming that the extent to which vehicles’ routes overlap indicates the level of closeness and relatedness as well as potential interactions between these vehicles. We then extend a density-based clustering algorithm, DBSCAN, to incorporate the LCS-based distance in our trajectory clustering problem. The output of the proposed clustering approach is a few spatially distinct traffic stream clusters, which together provide an informative and succinct representation of major network traffic streams. Next, we introduce the notion of Cluster Representative Subsequence (CRS), which reflects dense road segments shared by trajectories belonging to a given traffic stream cluster, and present the procedure of generating a set of CRSs by merging the pairwise LCSs via hierarchical agglomerative clustering. The CRSs are then used in the trajectory classification step to measure the similarity between a new trajectory and a cluster. The proposed framework is demonstrated using actual vehicle trajectory data collected from New York City, USA. A simple experiment was performed to illustrate the use of the proposed spatial traffic stream clustering in application areas such as network-level traffic flow pattern analysis and travel time reliability analysis.     

An efficient iterative link transmission model

In this paper a novel iterative algorithm is presented for the link transmission model, a fast macroscopic dynamic network loading scheme. The algorithm's solutions are defined on a space–time discretized grid. Unlike previous numerical schemes there is no hard upper limit on the time step size for the algorithm to be numerically stable, leaving only the trade-off between accuracy and interpolation errors. This is a major benefit because mandatory small time steps in existing algorithm (required for numerical tractability) are undesirable in most strategic analyses. They lead to highly increased memory costs on larger network instances and unnecessary complex behaviour. In practice results are often aggregated for storage or analysis, which leads to the loss of computationally expensive detailed information and to the introduction of inconsistencies. The novel iterative scheme is consistent with the modelling assumptions independent of the numerical time step. A second contribution of the iterative procedure is the smart handling of repeated runs, which can be initialized (or warm started) by an earlier solution. For applications, repeatedly loading a network is often needed when evaluating traffic states under changing variables or adjusted parameter settings, or in optimization and equilibration procedures. In these cases the iterative algorithm is initialized with the solution of a previous run and iterations are performed to find a new consistent solution. Pseudo-code is provided for both a basic upwind iterative scheme and an extended algorithm that significantly accelerates convergence. The most important computational gains are achieved by ordering and reducing calculations to that part of the network which has changed (most). The properties of the algorithm are demonstrated on a theoretical network as well as on some real-world networks.     

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.     

Dynamic stochastic journey time estimation and reliability analysis using stochastic cell transmission model: Algorithm and case studies

This paper proposes a framework for evaluating the distributions of stochastic dynamic link travel time and journey time as well as assessing the journey time reliability. Due to the stochastic nature of the flow profiles, the paper devises a sampling process to estimate the probability mass function (PMF) of the link travel time. This sampling process defines a likelihood concept that measures the probability of the difference between the cumulative stochastic link inflow and outflow profiles to be less than or equal to a prescribed bound. Based on this likelihood measure, the probability mass function (PMF) of the link travel time is evaluated over an appropriate sampling interval. The PMF of the journey time is then evaluated by extending the deterministic nested delay operator to a stochastic version which is defined as a series of “nested” conditional probabilities of the link travel time PMFs along the route. This paper also proposes a method to fit the PMF of the journey time to a class of statistical distribution to determine its skewness, which is useful in the analysis of journey time reliability. The paper then analyzes journey time reliability via the properties of dynamic travel time distributions such as confidence intervals and shape parameters. The proposed algorithm is applied to estimate the stochastic journey time on a freeway corridor from the stochastic cumulative inflow and outflow profiles generated from the stochastic cell transmission model. This methodology is validated with two empirical studies: (i) estimations of journey time distribution and reliability analysis for one short freeway segment in California during a specific time period and (ii) the effects of traffic incidents on journey time reliability for a long expressway corridor of Hanshin expressway (between Osaka and Kobe) in Japan.     

Integration of signal timing estimation model and dynamic traffic assignment in feedback loops: system design and case study

This paper presents an integrated framework for effective coupling of a signal timing estimation model and dynamic traffic assignment (DTA) in feedback loops. There are many challenges in effectively integrating signal timing tools with DTA software systems, such as data availability, exchange format, and system coupling. In this research, a tight coupling between a DTA model with various queue‐based simulation models and a quick estimation method Excel‐based signal control tool is achieved and tested. The presented framework design offers an automated solution for providing realistic signal timing parameters and intersection movement capacity allocation, especially for future year scenarios. The framework was used to design an open‐source data hub for multi‐resolution modeling in analysis, modeling and simulation applications, in which a typical regional planning model can be quickly converted to microscopic traffic simulation and signal optimization models. The coupling design and feedback loops are first demonstrated on a simple network, and we examine the theoretically important questions on the number of iterations required for reaching stable solutions in feedback loops. As shown in our experiment, the current coupled application becomes stable after about 30 iterations, when the capacity and signal timing parameters can quickly converge, while DTA's route switching model predominately determines and typically requires more iterations to reach a stable condition. A real‐world work zone case study illustrates how this application can be used to assess impacts of road construction or traffic incident events that disrupt normal traffic operations and cause route switching on multiple analysis levels. Copyright © 2014 John Wiley & Sons, Ltd.