Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach

This paper studies a mean-standard deviation shortest path model, also called travel time budget (TTB) model. A route’s TTB is defined as this route’s mean travel time plus a travel time margin, which is the route travel time’s standard deviation multiplied with a factor. The TTB model violates the Bellman’s Principle of Optimality (BPO), making it difficult to solve it in any large stochastic and time-dependent network. Moreover, it is found that if path travel time distributions are skewed, the conventional TTB model cannot reflect travelers’ heterogeneous risk-taking behavior in route choice. This paper proposes to use the upper or lower semi-standard deviation to replace the standard deviation in the conventional TTB model (the new models are called derived TTB models), because these derived TTB models can well capture such heterogeneous risk-taking behavior when the path travel time distributions are skewed. More importantly, this paper shows that the optimal solutions of these two derived TTB models must be non-dominated paths under some specific stochastic dominance (SD) rules. These finding opens the door to solve these derived TTB models efficiently in large stochastic and time-dependent networks. Numerical examples are presented to illustrate these findings.     

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.     

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.     

Sampling of alternatives for route choice modeling

This paper presents a new paradigm for choice set generation in the context of route choice model estimation. We assume that the choice sets contain all paths connecting each origin–destination pair. Although this is behaviorally questionable, we make this assumption in order to avoid bias in the econometric model. These sets are in general impossible to generate explicitly. Therefore, we propose an importance sampling approach to generate subsets of paths suitable for model estimation. Using only a subset of alternatives requires the path utilities to be corrected according to the sampling protocol in order to obtain unbiased parameter estimates. We derive such a sampling correction for the proposed algorithm.Estimating models based on samples of alternatives is straightforward for some types of models, in particular the multinomial logit (MNL) model. In order to apply MNL for route choice, the utilities should also be corrected to account for the correlation using, for instance, a path size (PS) formulation. We argue that the PS attribute should be computed based on the full choice set. Again, this is not feasible in general, and we propose a new version of the PS attribute derived from the sampling protocol, called Expanded PS.Numerical results based on synthetic data show that models including a sampling correction are remarkably better than the ones that do not. Moreover, the Expanded PS shows good results and outperforms models with the original PS formulation.     

An assignment model with modified Logit,which obviates enumeration and overlapping problems

One of the main components of stochastic assignment models is the route choice model solved with implicit or explicit path enumeration algorithms. Such models are used both for congested networks within equilibrium or dynamic models and for non-congested networks within static or pseudo-dynamic network loading models. This paper proposes a C-Logit model specification within a Dial algorithm structure for the implicit assignment of network flows. The model and its solution algorithm, called D-C-Logit, combine several positive features found in the literature for choice set generation and choices from a given choice set: generation of a set of alternatives with a selective approach; calculation of the path choice probability in a closed form; simulation of the overlapping effect among alternative paths; computation of just one tree for each origin avoiding explicit path enumeration.This paper has two main objectives: the proposition of a Dial-like algorithm to solve a C-Logit assignment model and application of the algorithm to different networks in order to demonstrate certain properties.     

Reliable route guidance: A case study from Chicago

Reliable route guidance can be obtained by solving the reliable a priori shortest path problem, which finds paths that maximize the probability of arriving on time. The goal of this paper is to demonstrate the benefits and applicability of such route guidance using a case study. An adaptive discretization scheme is first proposed to improve the efficiency in computing convolution, a time-consuming step used in the reliable routing algorithm to obtain path travel time distributions. Methods to construct link travel time distributions from real data in the case study are then discussed. Particularly, the travel time distributions on arterial streets are estimated from linear regression models calibrated from expressway data. Numerical experiments demonstrate that optimal paths are substantially affected by the reliability requirement in rush hours, and that reliable route guidance could generate up to 5-15% of travel time savings. The study also verifies that existing algorithms can solve large-scale problems within a reasonable amount of time.     

Path finding under uncertainty

Path finding problems have many real‐world applications in various fields, such as operations research, computer science, telecommunication, transportation, etc. In this paper, we examine three definitions of optimality for finding the optimal path under an uncertain environment. These three stochastic path finding models are formulated as the expected value model, dependent‐chance model, and chance‐constrained model using different criteria to hedge against the travel time uncertainty. A simulation‐based genetic algorithm procedure is developed to solve these path finding models under uncertainties. Numerical results are also presented to demonstrate the features of these stochastic path finding models.     

A model and algorithm for multicriteria route-mode choice

Using an idea proposed independently by Quandt and Schneider, the paper declares mode choice to be a special instance of route choice. It describes a (non-logit) model which includes in its route-choice mechanism the decision variables traditionally associated with mode choice. With the assumption that each traveller selects the route which minimizes his own personal linear choice function, it is clear that the routes with a nonzero chance of being picked are only those not dominated by any other path (e.g. are not both costlier and longer than any other path). The precise probability of a route being chosen is just the integral over the appropriate portion of the probability density of the coefficients of the choice function. The integration limits are implied by the amount of each disutility on each of the undominated routes. An algorithm is given which is quite efficient in finding these paths in a large and complex multimodal network.     

Determining structural route components from GPS traces

Analysis of GPS traces shows that people often do not use the least cost path through the transportation network while making trips. This leads to the question which structural path characteristics can be used to construct realistic route choice sets for use in traffic simulation models. In this paper, we investigate the hypothesis that, for utilitarian trips, the route between origin and destination consists of a small number of concatenated least cost paths. The hypothesis is verified by analyzing routes extracted from large sets of recorded GPS traces which constitute revealed preference information. Trips have been extracted from the traces and for each trip the path in the transportation network is determined by map matching. This is followed by a path decomposition phase for which the algorithm constitutes the first contribution of this paper. There are multiple ways to split a given path in a directed graph into a minimal number of subpaths of minimal cost. By calculating two specific path splittings, it is possible to identify subsets of the vertices (splitVertexSuites) that can be used to generate every possible minimum path splitting by taking one vertex from each such subset. As a second contribution, we show how the extracted information is used in microscopic travel simulation. The distribution for the size of the minimum decomposition, extracted from the GPS traces, can be used in constrained enumeration methods for route choice set generation. The sets of vertices that can act as boundary vertices separating consecutive route parts contain way points (landmarks) having a particular meaning to their user. The paper explains the theoretical aspects of route splitting as well as the process to extract splitVertexSuites from big data. It reports statistical distributions extracted from sets of GPS traces for both multimodal person movements and unimodal car trips.     

Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem

Using a sample-based representation scheme to capture spatial and temporal travel time correlations, this article constructs an integer programming model for finding the a priori least expected time paths. We explicitly consider the non-anticipativity constraint associated with the a priori path in a time-dependent and stochastic network, and propose a number of reformulations to establish linear inequalities that can be easily dualized by a Lagrangian relaxation solution approach. The relaxed model is further decomposed into two sub-problems, which can be solved directly by using a modified label-correcting algorithm and a simple single-value linear programming method. Several solution algorithms, including a sub-gradient method, a branch and bound method, and heuristics with additional constraints on Lagrangian multipliers, are proposed to improve solution quality and find approximate optimal solutions. The numerical experiments investigate the quality and computational efficiency of the proposed solution approach.     

An improved Dial's algorithm for logit-based traffic assignment within a directed acyclic network

Abstract

Dial's algorithm is one of the most effective and popular procedures for a logit-type stochastic traffic assignment, as it does not require path enumeration over a network. However, a fundamental problem associated with the algorithm is its simple definition of ‘efficient paths’, which sometimes produces unrealistic flow patterns. In this paper, an improved algorithm based on the route extension coefficient is proposed in order to circumvent this problem, in which ‘efficient paths’ simultaneously consider link travel cost and minimum travel cost. Path enumeration is still not required and a similar computing efficiency with the original algorithm is guaranteed. A limitation of the algorithm is that it can only be applied to a directed acyclic network because a topological sorting algorithm is used to decide the order of the sequential calculation. A numerical example based on the Beijing subway network illustrates the effectiveness of the proposed algorithm. It is found that it is able to exclude most unrealistic paths, but include all reasonable paths when compared with path enumeration and the original Dial's algorithm.     

The dynamic shortest path problem with time-dependent stochastic disruptions

The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.     

Walking infrastructure design assessment by continuous space dynamic assignment modeling

For the planning and design of walking infrastructure, characterized by the fact that the pedestrians can choose their paths freely in two‐dimensional space, applicability of traditional discrete network models is limited. This contribution puts forward an approach for user‐optimal dynamic assignment in continuous time and space for analyzing for instance walking infrastructure in a two‐dimensional space. Contrary to network‐based approaches, the theory allows the traffic units to choose from an infinite non‐countable set of paths through the considered space. The approach first determines the continuous paths using a path choice model. Then, origin‐destination flows are assigned and traffic conditions are calculated. The approach to determine a user‐optimal assignment is heuristic and consists of a sequence of all‐or‐nothing assignments. An application example is presented, showing dynamic user equilibrium traffic flows through a realistic transfer station. The example is aimed at illustrating the dynamic aspects of the modeling approach, such as anticipation on expected flow conditions, and predicted behavior upon catching or missing a connection.     

Bike route choice modeling using GPS data without choice sets of paths

Concerned by the nuisances of motorized travel on urban life, policy makers are faced with the challenge of making cycling a more attractive alternative for everyday transportation. Route choice models can help achieve this objective by gaining insights into the trade-offs cyclists make when choosing their routes and by allowing the effect of infrastructure improvements to be analyzed. We estimate a link-based bike route choice model from a sample of GPS observations in the city of Eugene on a network comprising over 40,000 links. The so-called recursive logit (RL) model (Fosgerau et al., 2013) does not require to sample any choice set of paths. We show the advantages of this approach in the context of prediction by focusing on two applications of the model: link flows and accessibility measures. Compared to the path-based approach which requires to generate choice sets, the RL model proves to make significant gains in computational time and to avoid paradoxical accessibility measure results discussed in previous works, e.g. Nassir et al. (2014).     

Robust Wardrop’s user equilibrium assignment under stochastic demand and supply: Expected residual minimization approach

Various models of traffic assignment under stochastic environment have been proposed recently, mainly by assuming different travelers’ behavior against uncertainties. This paper focuses on the expected residual minimization (ERM) model to provide a robust traffic assignment with an emphasis on the planner’s perspective. The model is further extended to obtain a stochastic prediction of the traffic volumes by the technique of path choice approach. We show theoretically the existence and the robustness of the ERM solution. In addition, we employ an improved solution algorithm for solving the ERM model. Numerical experiments are carried out to illustrate the characteristics of the proposed model, by comparing with other existing models.     

A probabilistic map matching method for smartphone GPS data

Smartphones have the capability of recording various kinds of data from built-in sensors such as GPS in a non-intrusive, systematic way. In transportation studies, such as route choice modeling, the discrete sequences of GPS data need to be associated with the transportation network to generate meaningful paths. The poor quality of GPS data collected from smartphones precludes the use of state of the art map matching methods. In this paper, we propose a probabilistic map matching approach. It generates a set of potential true paths, and associates a likelihood with each of them. Both spatial (GPS coordinates) and temporal information (speed and time) is used to calculate the likelihood of the data for a specific path. Applications and analyses on real trips illustrate the robustness and effectiveness of the proposed approach. Also, as an application example, a Path-Size Logit model is estimated based on a sample of real observations. The estimation results show the viability of applying the proposed method in a real route choice modeling context.     

Transit Users’ Route‐Choice Modelling in Transit Assignment: A Review

Abstract

This paper reviews the main studies on transit users’ route choice in the context of transit assignment. The studies are categorized into three groups: static transit assignment, within‐day dynamic transit assignment, and emerging approaches. The motivations and behavioural assumptions of these approaches are re‐examined. The first group includes shortest‐path heuristics in all‐or‐nothing assignment, random utility maximization route‐choice models in stochastic assignment, and user equilibrium based assignment. The second group covers within‐day dynamics in transit users’ route choice, transit network formulations, and dynamic transit assignment. The third group introduces the emerging studies on behavioural complexities, day‐to‐day dynamics, and real‐time dynamics in transit users’ route choice. Future research directions are also discussed.     

Incorporating space–time constraints and activity-travel time profiles in a multi-state supernetwork approach to individual activity-travel scheduling

Activity-travel scheduling is at the core of many activity-based models that predict short-term effects of travel information systems and travel demand management. Multi-state supernetworks have been advanced to represent in an integral fashion the multi-dimensional nature of activity-travel scheduling processes. To date, however, the treatment of time in the supernetworks has been rather limited. This paper attempts to (i) dramatically improve the temporal dimension in multi-state supernetworks by embedding space–time constraints into location selection models, not only operating between consecutive pairs of locations, but also at the overall schedule at large, and (ii) systematically incorporate time in the disutility profiles of activity participation and parking. These two improvements make the multi-state supernetworks fully time-dependent, allowing modeling choice of mode, route, parking and activity locations in a unified and time-dependent manner and more accurately capturing interdependences of the activity-travel trip chaining. To account for this generalized representation, refined behavioral assumptions and dominance relationships are proposed based on an earlier proposed bicriteria label-correcting algorithm to find the optimal activity-travel pattern. Examples are shown to demonstrate the feasibility of this new approach and its potential applicability to large scale agent-based simulation systems.     

Finding the most reliable path with and without link travel time correlation: A Lagrangian substitution based approach

Path travel time reliability is an essential measure of the quality of service for transportation systems and an important attribute in travelers’ route and departure time scheduling. This paper investigates a fundamental problem of finding the most reliable path under different spatial correlation assumptions, where the path travel time variability is represented by its standard deviation. To handle the non-linear and non-additive cost functions introduced by the quadratic forms of the standard deviation term, a Lagrangian substitution approach is adopted to estimate the lower bound of the most reliable path solution through solving a sequence of standard shortest path problems. A subgradient algorithm is used to iteratively improve the solution quality by reducing the optimality gap. To characterize the link travel time correlation structure associated with the end-to-end trip time reliability measure, this research develops a sampling-based method to dynamically construct a proxy objective function in terms of travel time observations from multiple days. The proposed algorithms are evaluated under a large-scale Bay Area, California network with real-world measurements.     

A portfolio theory of route choice

Although many individual route choice models have been proposed to incorporate travel time variability as a decision factor, they are typically still deterministic in the sense that the optimal strategy requires choosing one particular route that maximizes utility. In contrast, this study introduces an individual route choice model where choosing a portfolio of routes instead of a single route is the best strategy for a rational traveler who cares about both journey time and lateness when facing stochastic network conditions. The proposed model is compared with UE and SUE models and the difference in both behavioral foundation and model characteristics is highlighted. A numerical example is introduced to demonstrate how such model can be used in traffic assignment problem. The model is then tested with GPS data collected in metropolitan Minneapolis–St. Paul, Minnesota. Our data suggest there is no single dominant route (defined here as a route with the shortest travel time for a 15 day period) in 18% of cases when links travel times are correlated. This paper demonstrates that choosing a portfolio of routes could be the rational choice of a traveler who wants to optimize route decisions under variability.