A network equilibrium approach for modelling activity-travel pattern scheduling problems in multi-modal transit networks with uncertainty

An understanding of the interaction between individuals’ activities and travel choice behaviour plays an important role in long-term transit service planning. In this paper, an activity-based network equilibrium model for scheduling daily activity-travel patterns (DATPs) in multi-modal transit networks under uncertainty is presented. In the proposed model, the DATP choice problem is transformed into a static traffic assignment problem by constructing a new super-network platform. With the use of the new super-network platform, individuals’ activity and travel choices such as time and space coordination, activity location, activity sequence and duration, and route/mode choices, can be simultaneously considered. In order to capture the stochastic characteristics of different activities, activity utilities are assumed in this study to be time-dependent and stochastic in relation to the activity types. A concept of DATP budget utility is proposed for modelling the uncertainty of activity utility. An efficient solution algorithm without prior enumeration of DATPs is developed for solving the DATP scheduling problem in multi-modal transit networks. Numerical examples are used to illustrate the application of the proposed model and the solution algorithm.     

A solution algorithm for a dynamic deterministic user equilibrium assignment model with departure time choice

Abstract

A route-based combined model of dynamic deterministic route and departure time choice and a solution method for many origin and destination pairs is proposed. The divided linear travel time model is used to calculate the link travel time and to describe the propagation of flow over time. For the calculation of route travel times, the predictive ideal route travel time concept is adopted. Solving the combined model of dynamic deterministic route and departure time choice is shown to be equivalent to solving simultaneously a system of non-linear equations. A Newton-type iterative scheme is proposed to solve this problem. The performance of the proposed solution method is demonstrated using a version of the Sioux Falls network. This shows that the proposed solution method produces good equilibrium solutions with reasonable computational cost.     

Bottleneck model revisited: An activity-based perspective

The timing of commuting trips made during morning and evening peaks has typically been investigated using Vickrey’s bottleneck model. However, in the conventional trip-based approach, the decisions that commuters make during the day about their activity schedules and time use are not explicitly considered. This study extends the bottleneck model to address the scheduling problem of commuters’ morning home-to-work and evening work-to-home journeys by using an activity-based approach. A day-long activity-travel scheduling model is proposed for the simultaneous determination of departure times for morning and evening commutes, together with allocations of time during the day among travel and activities undertaken at home or at the workplace. The proposed model maximizes the total net utility of the home-based tour, which is the difference between the benefits derived from participating in activities and the disutility incurred by travel between activity locations. The properties of the model solution are analytically explored and compared with the conventional bottleneck model for a special case with constant marginal-activity utility. For the case with linear marginal-activity utility, we develop a heuristic procedure to seek the equilibrium scheduling solution. We also explore the effects of marginal-work utility (or the employees’ average wage level) and of flexible work-hour schemes on the scheduling problem in relation to the morning and evening commuting tours.     

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 activity-travel assignment in multi-state supernetworks

The integration of activity-based modeling and dynamic traffic assignment for travel demand analysis has recently attracted ever-increasing attention. However, related studies have limitations either on the integration structure or the number of choice facets being captured. This paper proposes a formulation of dynamic activity-travel assignment (DATA) in the framework of multi-state supernetworks, in which any path through a personalized supernetwork represents a particular activity-travel pattern (ATP) at a high level of spatial and temporal detail. DATA is formulated as a discrete-time dynamic user equilibrium (DUE) problem, which is reformulated as an equivalent variational inequality (VI) problem. A generalized dynamic link disutility function is established with the accommodation of different characteristics of the links in the supernetworks. Flow constraints and non-uniqueness of equilibria are also investigated. In the proposed formulation, the choices of departure time, route, mode, activity sequence, activity and parking location are all unified into one time-dependent ATP choice. As a result, the interdependences among all these choice facets can be readily captured. A solution algorithm based on the route-swapping mechanism is adopted to find the user equilibrium. A numerical example with simulated scenarios is provided to demonstrate the advantages of the proposed approach.     

The existence, uniqueness and computation of an arc-based dynamic network user equilibrium formulation

In this paper, a dynamic user equilibrium traffic assignment model with simultaneous departure time/route choices and elastic demands is formulated as an arc-based nonlinear complementarity problem on congested traffic networks. The four objectives of this paper are (1) to develop an arc-based formulation which obviates the use of path-specific variables, (2) to establish existence of a dynamic user equilibrium solution to the model using Brouwer's fixed-point theorem, (3) to show that the vectors of total arc inflows and associated minimum unit travel costs are unique by imposing strict monotonicity conditions on the arc travel cost and demand functions along with a smoothness condition on the equilibria, and (4) to develop a heuristic algorithm that requires neither a path enumeration nor a storage of path-specific flow and cost information. Computational results are presented for a simple test network with 4 arcs, 3 nodes, and 2 origin–destination pairs over the time interval of 120 periods.     

Path-constrained traffic assignment: A trip chain analysis under range anxiety

This paper proposes and analyzes a distance-constrained traffic assignment problem with trip chains embedded in equilibrium network flows. The purpose of studying this problem is to develop an appropriate modeling tool for characterizing traffic flow patterns in emerging transportation networks that serve a massive adoption of plug-in electric vehicles. This need arises from the facts that electric vehicles suffer from the “range anxiety” issue caused by the unavailability or insufficiency of public electricity-charging infrastructures and the far-below-expectation battery capacity. It is suggested that if range anxiety makes any impact on travel behaviors, it more likely occurs on the trip chain level rather than the trip level, where a trip chain here is defined as a series of trips between two possible charging opportunities (Tamor et al., 2013). The focus of this paper is thus given to the development of the modeling and solution methods for the proposed traffic assignment problem. In this modeling paradigm, given that trip chains are the basic modeling unit for individual decision making, any traveler’s combined travel route and activity location choices under the distance limit results in a distance-constrained, node-sequenced shortest path problem. A cascading labeling algorithm is developed for this shortest path problem and embedded into a linear approximation framework for equilibrium network solutions. The numerical result derived from an illustrative example clearly shows the mechanism and magnitude of the distance limit and trip chain settings in reshaping network flows from the simple case characterized merely by user equilibrium.     

Hierarchical network-based equilibrium model and algorithm for a mixed-traffic urban transport system

Abstract

Many equilibrium models and algorithms based on homogeneous motorized traffic have been devised to model urban transport systems in developed countries, but they are inadequate when it comes to represent mixed-traffic urban transport systems, including automobiles, transit, bicycles, and pedestrians, in developing countries such as China or India. In these cases, traffic flow on a road segment is an aggregated result of travellers' combined mode/route choices and corresponding interactions. Therefore, a special assignment model and algorithm are needed for modeling these distinct behaviors. In this article, the structure of a mixed-traffic urban transport system is analyzed and then expanded and represented using a hierarchical network model based on graph theory. Based on the analysis of travelers' combined mode/route choices, generalized travel cost functions and link impedance functions for different modes are formulated, where the interferences between different modes on the same road segments are taken into account. Due to the ‘asymmetric’ nature of these functions, a variational inequality model is proposed to represent the equilibrium assignment problem in a mixed-traffic urban transport system. The corresponding solution algorithm is also presented. Finally, a numerical example is provided to illustrate the practicality of the proposed model and algorithm.     

A stochastic multimodal reliable network design problem under adverse weather conditions

This paper formulates a network design problem (NDP) for finding the optimal public transport service frequencies and link capacity expansions in a multimodal network with consideration of impacts from adverse weather conditions. The proposed NDP aims to minimize the sum of expected total travel time, operational cost of transit services, and construction cost of link capacity expansions under an acceptable level of variance of total travel time. Auto, transit, bus, and walking modes are considered in the multimodal network model for finding the equilibrium flows and travel times. In the proposed network model, demands are assumed to follow Poisson distribution, and weather‐dependent link travel time functions are adopted. A probit‐based stochastic user equilibrium, which is based on the perceived expected travel disutility, is used to determine the multimodal route of the travelers. This model also considers the strategic behavior of the public transport travelers in choosing their routes, that is, common‐line network. Based on the stochastic multimodal model, the mean and variance of total travel time are analytical estimated for setting up the NDP. A sensitivity‐based solution algorithm is proposed for solving the NDP, and two numerical examples are adopted to demonstrate the characteristics of the proposed model. Copyright © 2014 John Wiley & Sons, Ltd.     

Optimal speed detector density for the network with travel time information

In the expressway network, detectors are installed on the links for detecting the travel time information while the predicted travel time can be provided by the route guidance system (RGS). The speed detector density can be determined to influence flow distributions in such a way that the precision of the travel time information and the social cost of the speed detectors are optimized, provided that each driver chooses the minimum perceived travel time path in response to the predicted travel time information. In this paper, a bilevel programming model is proposed for the network with travel time information provided by the RGS. The lower-level problem is a probit-based traffic assignment model, while the upper-level problem is to determine the speed detector density that minimizes the measured travel time error variance as well as the social cost of the speed detectors. The sensitivity analysis based algorithm is proposed for the bilevel programming problem. Numerical examples are provided to illustrate the applications of the proposed model and of the solution algorithm.     

Dynamic network equilibrium for daily activity-trip chains of heterogeneous travelers: application to large-scale networks

Applications of dynamic network equilibrium models have, mostly, considered the unit of traffic demand either as one-way trip, or as multiple independent trips. However, individuals’ travel patterns typically follow a sequence of trips chained together. In this study we aim at developing a general simulation-based dynamic network equilibrium algorithm for assignment of activity-trip chain demand. The trip chain of each individual trip maker is defined by the departure time at origin, sequence of activity destination locations, including the location of their intermediate destinations and their final destination, and activity duration at each of the intermediate destinations. Spatial and temporal dependency of subsequent trips on each other necessitate time and memory consuming calculations and storage of node-to-node time-dependent least generalized cost path trees, which is not practical for very large metropolitan area networks. We first propose a reformulation of the trip-based demand gap function formulation for the variational inequality formulation of the Bi-criterion Dynamic User Equilibrium (BDUE) problem. Next, we propose a solution algorithm for solving the BDUE problem with daily chain of activity-trips. Implementation of the algorithm for very large networks circumvents the need to store memory-intensive node-to-node time-dependent shortest path trees by implementing a destination-based time-dependent least generalized cost path finding algorithm, while maintaining the spatial and temporal dependency of subsequent trips. Numerical results for a real-world large scale network suggest that recognizing the dependency of multiple trips of a chain, and maintaining the departure time consistency of subsequent trips provide sharper drops in gap values, hence, the convergence could be achieved faster (compared to when trips are considered independent of each other).     

A semi-analytical approach for solving the bottleneck model with general user heterogeneity

This paper proposes a novel semi-analytical approach for solving the dynamic user equilibrium (DUE) of a bottleneck model with general heterogeneous users. The proposed approach makes use of the analytical solutions from the bottleneck analysis to create an equivalent assignment problem that admits closed-form commute cost functions. The equivalent problem is a static and asymmetric traffic assignment problem, which can be formulated as a variational inequality problem (VIP). This approach provides a new tool to analyze the properties of the bottleneck model with general heterogeneity, and to design efficient solution methods. In particular, the existence and uniqueness of the DUE solution can be established using the P-property of the Jacobian matrix. Our numerical experiments show that a simple decomposition algorithm is able to quickly solve the equivalent VIP to high precision. The proposed VIP formation is also extended to address simultaneous departure time and route choice in a single O–D origin-destination network with multiple parallel routes.     

An activity-based approach for scheduling multimodal transit services

This paper proposes a new activity-based transit assignment model for investigating the scheduling (or timetabling) problem of transit services in multi-modal transit networks. The proposed model can be used to generate the short-term and long-term timetables of multimodal transit lines for transit operations and service planning purposes. The interaction between transit timetables and passenger activity-travel scheduling behaviors is captured by the proposed model, as the activity and travel choices of transit passengers are considered explicitly in terms of departure time choice, activity/trip chain choices, activity duration choice, transit line and mode choices. A heuristic solution algorithm which combines the Hooke–Jeeves method and an iterative supply–demand equilibrium approach is developed to solve the proposed model. Two numerical examples are presented to illustrate the differences between the activity-based approach and the traditional trip-based method, together with comparison on the effects of optimal timetables with even and uneven headways. It is shown that the passenger travel scheduling pattern derived from the activity-based approach is significantly different from that obtained by the trip-based method, and that a demand-sensitive (with uneven headway) timetable is more efficient than an even-headway timetable.     

The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems

Dynamic user optimal simultaneous route and departure time choice (DUO-SRDTC) problems are usually formulated as variational inequality (VI) problems whose solution algorithms generally require continuous and monotone route travel cost functions to guarantee convergence. However, the monotonicity of the route travel cost functions cannot be ensured even if the route travel time functions are monotone. In contrast to traditional formulations, this paper formulates a DUO-SRDTC problem (that can have fixed or elastic demand) as a system of nonlinear equations. The system of nonlinear equations is a function of generalized origin-destination (OD) travel costs rather than route flows and includes a dynamic user optimal (DUO) route choice subproblem with perfectly elastic demand and a quadratic programming (QP) subproblem under certain assumptions. This study also proposes a solution method based on the backtracking inexact Broyden–Fletcher–Goldfarb–Shanno (BFGS) method, the extragradient algorithm, and the Frank-Wolfe algorithm. The BFGS method, the extragradient algorithm, and the Frank-Wolfe algorithm are used to solve the system of nonlinear equations, the DUO route choice subproblem, and the QP subproblem, respectively. The proposed formulation and solution method can avoid the requirement of monotonicity of the route travel cost functions to obtain a convergent solution and provide a new approach with which to solve DUO-SRDTC problems. Finally, numeric examples are used to demonstrate the performance of the proposed solution method.     

Optimal locations and travel time display for variable message signs

This paper first develops a network equilibrium model with the travel time information displayed via variable message signs (VMS). Specifically, the equilibrium considers the impact of the displayed travel time information on travelers’ route choices under the recurrent congestion, with the endogenous utilization rates of displayed information by travelers. The existence of the equilibrium is proved and an iterative solution procedure is provided. Then, we conduct the sensitivity analyses of the network equilibrium and further propose a paradox, i.e., providing travel time information via VMS to travelers may degrade the network performance under some poor designs. Therefore, we investigate the problem of designing the VMS locations and travel time display within a given budget, and formulate it as a mixed integer nonlinear program, solved by an active-set algorithm. Lastly, numerical examples are presented to offer insights on the equilibrium results and optimal designs of VMS.     

A multi‐class mean‐excess traffic equilibrium model with elastic demand

Recent empirical studies have revealed that travel time variability plays an important role in travelers' route choice decisions. To simultaneously account for both reliability and unreliability aspects of travel time variability, the concept of mean‐excess travel time (METT) was recently proposed as a new risk‐averse route choice criterion. In this paper, we extend the mean‐excess traffic equilibrium model to include heterogeneous risk‐aversion attitudes and elastic demand. Specifically, this model explicitly considers (1) multiple user classes with different risk‐aversions toward travel time variability when making route choice decisions under uncertainty and (2) the elasticity of travel demand as a function of METT when making travel choice decisions under uncertainty. This model is thus capable of modeling travelers' heterogeneous risk‐averse behaviors with both travel choice and route choice considerations. The proposed model is formulated as a variational inequality problem and solved via a route‐based algorithm using the modified alternating direction method. Numerical analyses are also provided to illustrate the features of the proposed model and the applicability of the solution algorithm. Copyright © 2012 John Wiley & Sons, Ltd.     

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.     

Effects of queue spillover in networks considering simultaneous departure time and route choices

This paper explores the effects of queue spillover in transportation networks, in the context of dynamic traffic assignment. A model of spatial queue is defined to characterize dynamic traffic flow and queuing formation in network links. Network users simultaneously choose departure time and travel route to minimize the travel cost including journey time and unpunctuality penalty. Using some necessary conditions of the dynamic user equilibrium, dynamic network flows are obtained exactly on some networks with typical structure. Various effects of queue spillover are discussed based on the results of these networks, and some new paradoxes of link capacity expansion have been found as a result of such effects. Analytical and exact results in these typical networks show that ignoring queuing length may generate biased solutions, and the link storage capacity is a very important factor concerning the performance of networks.     

Dynamic user equilibrium with side constraints for a traffic network: Theoretical development and numerical solution algorithm

This paper investigates a traffic volume control scheme for a dynamic traffic network model which aims to ensure that traffic volumes on specified links do not exceed preferred levels. The problem is formulated as a dynamic user equilibrium problem with side constraints (DUE-SC) in which the side constraints represent the restrictions on the traffic volumes. Travelers choose their departure times and routes to minimize their generalized travel costs, which include early/late arrival penalties. An infinite-dimensional variational inequality (VI) is formulated to model the DUE-SC. Based on this VI formulation, we establish an existence result for the DUE-SC by showing that the VI admits at least one solution. To analyze the necessary condition for the DUE-SC, we restate the VI as an equivalent optimal control problem. The Lagrange multipliers associated with the side constraints as derived from the optimality condition of the DUE-SC provide the traffic volume control scheme. The control scheme can be interpreted as additional travel delays (either tolls or access delays) imposed upon drivers for using the controlled links. This additional delay term derived from the Lagrange multiplier is compared with its counterpart in a static user equilibrium assignment model. If the side constraint is chosen as the storage capacity of a link, the additional delay can be viewed as the effort needed to prevent the link from spillback. Under this circumstance, it is found that the flow is incompressible when the link traffic volume is equal to its storage capacity. An algorithm based on Euler’s discretization scheme and nonlinear programming is proposed to solve the DUE-SC. Numerical examples are presented to illustrate the mechanism of the proposed traffic volume control scheme.