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.     

Traffic signal timing problems with environmental and equity considerations

Traffic signal timings in a road network can not only affect total user travel time and total amount of traffic emissions in the network but also create an inequity problem in terms of the change in travel costs of users traveling between different locations. This paper proposes a multi‐objective bi‐level programming model for design of sustainable and equitable traffic signal timings for a congested signal‐controlled road network. The upper level of the proposed model is a multi‐objective programming problem with an equity constraint that maximizes the reserve capacity of the network and minimizes the total amount of traffic emissions. The lower level is a deterministic network user equilibrium problem that considers the vehicle delays at signalized intersections of the network. To solve the proposed model, an approach for normalizing incommensurable objective functions is presented, and a heuristic solution algorithm that combines a penalty function approach and a simulated annealing method is developed. Two numerical examples are presented to show the effects of reserve capacity improvement and green time proportion on network flow distribution and transportation system performance and the importance of incorporating environmental and equity objectives in the traffic signal timing problems. Copyright © 2013 John Wiley & Sons, Ltd.     

Sensitivity analysis on stochastic equilibrium transportation networks using genetic algorithm

This study deals with the sensitivity analysis of an equilibrium transportation networks using genetic algorithm approach and uses the bi‐level iterative sensitivity algorithm. Therefore, integrated Genetic Algorithm‐TRANSYT and Path Flow Estimator (GATPFE) is developed for signalized road networks for various level of perceived travel time in order to test the sensitivity of perceived travel time error in an urban stochastic road networks. Level of information provided to drivers correspondingly affects the signal timing parameters and hence the Stochastic User Equilibrium (SUE) link flows. When the information on road system is increased, the road users try to avoid conflicting links. Therefore, the stochastic equilibrium assignment concept tends to be user equilibrium. The GATPFE is used to solve the bi‐level problem, where the Area Traffic Control (ATC) is the upper‐level and the SUE assignment is the lower‐level. The GATPFE is tested for six‐junction network taken from literature. The results show that the integrated GATPFE can be applied to carry out sensitivity analysis at the equilibrium network design problems for various level of information and it simultaneously optimize the signal timings (i.e. network common cycle time, signal stage and offsets between junctions).     

Influence of peak spreading and departure time choice on evaluation of its measures

Intelligent transport systems provide various means to improve capacity and travel time in road networks. Evaluation of the benefits of these improvements requires consideration of travellers' response to them. We consider a continuous‐time equilibrium model of departure time choice and identify a formula for the dynamic equilibrium departure rate profile. We develop the analysis to consider the effect on the cost incurred by travellers of ITS measures through their effects on each of the travel time in the absence of congestion, and the capacity for travel. This shows the importance in choice of departure time of travellers' values of time at each of the origin and destination of their journeys. We show the importance of these values of time in evaluation, and that if travellers value their time at both the origin and destination of their journeys, their responses will lead them to achieve a greater reduction in costs than would be achieved under free‐flow conditions.     

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.     

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 State-of-the-Art Review: Developments in Utility Theory,Prospect Theory and Regret Theory to Investigate Travellers' Behaviour in Situations Involving Travel Time Uncertainty

Abstract

Despite the wide use of utility theory to model travellers' behaviour, the interest in non-expected utility theories has increased due to their potential to capture more realistic behaviour. A main question raised is whether travellers are better described as utility maximizers or should be qualified differently.

This paper presents a literature review on the use of expected utility theory (EUT), prospect theory (PT) and regret theory (RT) to model travellers' behaviour. Gaps in the literature are identified and a discussion about advantages and disadvantages of each theory is presented. A case study illustrates the differences between the theories.

Under certain conditions, PT and RT restrict themselves to EUT. Their added value, however, is the possibility of capturing loss aversion, risk aversion and risk-seeking (PT) and regret aversion (RT). On the practical level, the use of EUT is well established, while contributions of PT and RT are marginal. On the theoretical level, however, RT seems to be (marginally) more suitable to model travellers' behaviour, while EUT and PT are equally suitable. This suggests that the large use of EUT is highly influenced by its very tractable framework. We do not claim the superiority of any theory, but propose to compare them through a systematic review.     

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.     

Impact of congestion charging on the transit market: An inter-modal equilibrium model

An inter-modal equilibrium model links an urban road network subject to a congestion charge to a parallel urban transit market, with a view to finding the optimum congestion charge consistent with the commercial decisions of the transit operator(s). A congestion charge is set to maximise social surplus. Travel behaviour is assumed to conform to elastic-demand user equilibrium traffic assignment. The transit market is assumed to be either a profit maximising monopoly or a profit maximising duopoly competing non-cooperatively. The operator(s) set the fares to maximise profits and the supply of transit services are determined by the resulting demand. The problem has been formulated as a bi-level programme with the determination of the congestion charge on the upper level and the setting of transit fares on the lower level. In the case of non-cooperating operators, the Bertrand–Nash equilibrium fares are sought. The results of the model are analysed for a small example based loosely on Edinburgh. This reveals the importance of competition in the transit market for the trade off between the government, the transit provider(s) and the travellers.     

A bi-level model for single-line rail timetable design with consideration of demand and capacity

This paper proposes a bi-level model to solve the timetable design problem for an urban rail line. The upper level model aims at determining the headways between trains to minimize total passenger cost, which includes not only the usual perceived travel time cost, but also penalties during travel. With the headways given by the upper level model, passengers’ arrival times at their origin stops are determined by the lower level model, in which the cost-minimizing behavior of each passenger is taken into account. To make the model more realistic, explicit capacity constraints of individual trains are considered. With these constraints, passengers cannot board a full train, but wait in queues for the next coming train. A two-stage genetic algorithm incorporating the method of successive averages is introduced to solve the bi-level model. Two hypothetical examples and a real world case are employed to evaluate the effectiveness of the proposed bi-level model and algorithm. Results show that the bi-level model performs well in reducing total passenger cost, especially in reducing waiting time cost and penalties. And the section loading-rates of trains in the optimized timetable are more balanced than the even-headway timetable. The sensitivity analyses show that passenger’s desired arrival time interval at destination and crowding penalty factor have a high influence on the optimal solution. And with the dispersing of passengers' desired arrival time intervals or the increase of crowding penalty factor, the section loading-rates of trains become more balanced.     

Global optimization methods for the discrete network design problem

This paper addresses the discrete network design problem (DNDP) with multiple capacity levels, or multi-capacity DNDP for short, which determines the optimal number of lanes to add to each candidate link in a road network. We formulate the problem as a bi-level programming model, where the upper level aims to minimize the total travel time via adding new lanes to candidate links and the lower level is a traditional Wardrop user equilibrium (UE) problem. We propose two global optimization methods by taking advantage of the relationship between UE and system optimal (SO) traffic assignment principles. The first method, termed as SO-relaxation, exploits the property that an optimal network design solution under SO principle can be a good approximate solution under UE principle, and successively sorts the solutions in the order of increasing total travel time under SO principle. Optimality is guaranteed when the lower bound of the total travel time of the unexplored solutions under UE principle is not less than the total travel time of a known solution under UE principle. The second method, termed as UE-reduction, adds the objective function of the Beckmann-McGuire-Winsten transformation of UE traffic assignment to the constraints of the SO-relaxation formulation of the multi-capacity DNDP. This constraint is convex and strengthens the SO-relaxation formulation. We also develop a dynamic outer-approximation scheme to make use of the state-of-the-art mixed-integer linear programming solvers to solve the SO-relaxation formulation. Numerical experiments based on a two-link network and the Sioux-Falls network are conducted.     

Regulating hazardous materials transportation by dual toll pricing

We investigate dual-toll setting as a policy tool to mitigate the risk of hazardous material (hazmat) shipment in road networks. We formulate the dual-toll problem as a bi-level program wherein the upper level aims at minimizing the risk, and the lower level explores the user equilibrium decision of the regular vehicles and hazmat carriers given the toll. When the upper level objective is to minimize the risk and all links are tollable, we decompose the formulation into first-stage and second-stage, and suggest a computational method to solve each stage. Our two-stage solution methodology guarantees nonnegative valid dual tolls regardless of the solution accuracy of the first-stage problem. We also consider a general dual-toll setting problem where the regulator rather wishes to minimize a combination of risk and the paid tolls and/or some links are untollable. To solve this truly bilevel problem, we provide heuristic algorithms that decompose the problem into subproblems each being solved by a line search. Case studies based on the Sioux Falls network illustrate the insights on the dual-toll policies.     

Reserve capacity model based on variable demand for land-use development control

In this paper, the concept of reserve capacity has been extended to zone level to measure the land-use development potentiality of each trip generation zone. Bi-level programing models are proposed to determine the signal setting of individual intersections for maximizing possible increase in total travel demand and the corresponding reserve capacity for each zone. The change of the origin–destination pattern with the variation of upper level decision variables is presented through the combined distribution/assignment model under user equilibrium conditions. Both singly constrained and doubly constrained combined models are considered for different trip purposes and data information. Furthermore, we have introduced the continuous network design problem by increasing road capacity and examined its effect on the land-use development potentiality of trip generation zone. A numerical example is presented to illustrate the application of the models and how a genetic algorithm is applied to solve the problem.     

Sequential optimization approach for the multi‐class user equilibrium problem in a continuous transportation system

We consider a city region with several facilities that are competing for customers of different classes. Within the city region, the road network is dense, and can be represented as a continuum. Customers are continuously distributed over space, and they choose a facility by considering both the transportation cost and market externalities. More importantly, the model takes into account the different transportation cost functions and market externalities to which different customer classes are subjected. A logit‐type distribution of demand is specified to model the decision‐making process of users' facility choice. We develop a sequential optimization approach to decompose the complex multi‐class and multi‐facility problem into a series of smaller single‐class and single‐facility sub‐problems. An efficient solution algorithm is then proposed to solve the resultant problem. A numerical example is given to demonstrate the effectiveness and potential applicability of the proposed methodology.     

Optimization method of alternate traffic restriction scheme based on elastic demand and mode choice behavior

As a countermeasure to urban traffic congestion, alternate traffic restriction (ATR) involves a certain proportion of automobiles being prohibited from entering pre-determined ATR districts during specific time periods. The present study introduces an optimization method for ATR schemes in terms of both their restriction districts and the proportion of restricted automobiles. As a Stackelberg game between traffic policy makers and road users, the ATR scheme optimization problem is established using a bi-level programming model, with the upper-level examining an ATR scheme aimed at consumers’ surplus maximization under the condition of overload flow minimization, and the lower-level synthetically optimizing elastic demand, mode choice (private car, public transit and park-and-ride) and multi-class user equilibrium assignment. A genetic algorithm based on the graph theory is also proposed to solve the bi-level programming model with a gradient project algorithm for solving the lower-level model. To our knowledge, this study represents the first attempt to theoretically optimize an ATR scheme using a systematic approach with mathematical model specification.     

Optimization models for differentiating quality of service levels in probabilistic network capacity design problems

This paper develops various chance-constrained models for optimizing the probabilistic network design problem (PNDP), where we differentiate the quality of service (QoS) and measure the related network performance under uncertain demand. The upper level problem of PNDP designs continuous/discrete link capacities shared by multi-commodity flows, and the lower level problem differentiates the corresponding QoS for demand satisfaction, to prioritize customers and/or commodities. We consider PNDP variants that have either fixed flows (formulated at the upper level) or recourse flows (at the lower level) according to different applications. We transform each probabilistic model into a mixed-integer program, and derive polynomial-time algorithms for special cases with single-row chance constraints. The paper formulates benchmark stochastic programming models by either enforcing to meet all demand or penalizing unmet demand via a linear penalty function. We compare different models and approaches by testing randomly generated network instances and an instance built on the Sioux–Falls network. Numerical results demonstrate the computational efficacy of the solution approaches and derive managerial insights.     

Optimal transit fare in a bimodal network under demand uncertainty and bounded rationality

This paper investigates the optimal transit fare in a simple bimodal transportation system that comprises public transport and private car. We consider two new factors: demand uncertainty and bounded rationality. With demand uncertainty, travelers are assumed to consider both the mean travel cost and travel cost variability in their mode choice decision. Under bounded rationality, travelers do not necessarily choose the travel mode of which perceived travel cost is absolutely lower than the one of the other mode. To determine the optimal transit fare, a bi‐level programming is proposed. The upper‐level objective function is to minimize the mean of total travel cost, whereas the lower‐level programming adopts the logit‐based model to describe users' mode choice behaviors. Then a heuristic algorithm based on a sensitivity analysis approach is designed to solve the bi‐level programming. Numerical examples are presented to illustrate the effect of demand uncertainty and bounded rationality on the modal share, optimal transit fare and system performance. Copyright © 2013 John Wiley & Sons, Ltd.     

A bi-level programming for bus lane network design

This paper proposes a bi-level programming model to solve the design problem for bus lane distribution in multi-modal transport networks. The upper level model aims at minimizing the average travel time of travelers, as well as minimizing the difference of passengers’ comfort among all the bus lines by optimizing bus frequencies. The lower level model is a multi-modal transport network equilibrium model for the joint modal split/traffic assignment problem. The column generation algorithm, the branch-and-bound algorithm and the method of successive averages are comprehensively applied in this paper for the solution of the bi-level model. A simple numerical test and an empirical test based on Dalian economic zone are employed to validate the proposed model. The results show that the bi-level model performs well with regard to the objective of reducing travel time costs for all travelers and balancing transit service level among all bus lines.     

Robust intermodal hub location under polyhedral demand uncertainty

In this study, we consider the robust uncapacitated multiple allocation p-hub median problem under polyhedral demand uncertainty. We model the demand uncertainty in two different ways. The hose model assumes that the only available information is the upper limit on the total flow adjacent at each node, while the hybrid model additionally imposes lower and upper bounds on each pairwise demand. We propose linear mixed integer programming formulations using a minmax criteria and devise two Benders decomposition based exact solution algorithms in order to solve large-scale problems. We report the results of our computational experiments on the effect of incorporating uncertainty and on the performance of our exact approaches.     

A bi‐level programming approach — Optimal transit fare under line capacity constraints

The fare of a transit line is one of the important decision variables for transit network design. It has been advocated as an efficient means of coordinating the transit passenger flows and of alleviating congestion in the transit network. This paper shows how transit fare can be optimized so as to balance the passenger flow on the transit network and to reduce the overload delays of passengers at transit stops. A bi‐level programming method is developed to optimize the transit fare under line capacity constraints. The upper‐level problem seeks to minimize the total network travel time, while the lower‐level problem is a stochastic user equilibrium transit assignment model with line capacity constraints. A heuristic solution algorithm based on sensitivity analysis is proposed. Numerical example is used to illustrate the application of the proposed model and solution algorithm.