Impact analysis of cordon-based congestion pricing on mode-split for a bimodal transportation network

This paper investigates the impact of cordon-based congestion pricing scheme on the mode-split of a bimodal transportation network with auto and rail travel modes. For any given toll-charge pattern, its impact on the mode-split can be estimated by solving a combined mode-split and traffic-assignment problem. Using a binary logit model for the mode-split, the combined problem is converted into a traffic-assignment problem with elastic demand. Probit-based stochastic user equilibrium (SUE) principle is adopted for this traffic-assignment problem, and a continuously distributed value of time (VOT) is assumed to convert the toll charges and transit fares into time-units. This combined mode-split and traffic-assignment problem is then formulated as a fixed-point model, which can be solved by a convergent Cost Averaging method. The combined mode-split and traffic-assignment problem is then used to analyze a multimodal toll design problem for cordon-based congestion pricing scheme, with the aim of increasing the mode-share of public transport system to a targeted level. Taking the fixed-point model as a constraint, the multimodal toll design problem is thus formulated as a mathematical programming with equilibrium constraints (MPEC) model. A genetic algorithm (GA) is employed to solve this MPEC model, which is then numerical validated by a network example.     

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.     

Solving a discrete multimodal transportation network design problem

This paper investigates the multimodal network design problem (MMNDP) that optimizes the auto network expansion scheme and bus network design scheme in an integrated manner. The problem is formulated as a single-level mathematical program with complementarity constraints (MPCC). The decision variables, including the expanded capacity of auto links, the layout of bus routes, the fare levels and the route frequencies, are transformed into multiple sets of binary variables. The layout of transit routes is explicitly modeled using an alternative approach by introducing a set of complementarity constraints. The congestion interaction among different travel modes is captured by an asymmetric multimodal user equilibrium problem (MUE). An active-set algorithm is employed to deal with the MPCC, by sequentially solving a relaxed MMNDP and a scheme updating problem. Numerical tests on nine-node and Sioux Falls networks are performed to demonstrate 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.     

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.     

Road pricing for congestion control with unknown demand and cost functions

It is widely recognized that precise estimation of road tolls for various pricing schemes requires a few pieces of information such as origin–destination demand functions, link travel time functions and users’ valuations of travel time savings, which are, however, not all readily available in practice. To circumvent this difficulty, we develop a convergent trial-and-error implementation method for a particular pricing scheme for effective congestion control when both the link travel time functions and demand functions are unknown. The congestion control problem of interest is also known as the traffic restraint and road pricing problem, which aims at finding a set of effective link toll patterns to reduce link flows to below a desirable target level. For the generalized traffic equilibrium problem formulated as variational inequalities, we propose an iterative two-stage approach with a self-adaptive step size to update the link toll pattern based on the observed link flows and given flow restraint levels. Link travel time and demand functions and users’ value of time are not needed. The convergence of the iterative toll adjustment algorithm is established theoretically and demonstrated on a set of numerical examples.     

Solving the Pareto-improving toll problem via manifold suboptimization

Congestion tolls are considered to be Pareto-improving if they reduce travel delay or improve social benefit and ensure that, when compared to the situation without any tolling intervention, no user is worse off in terms of travel cost measured, e.g., in units of time. The problem of finding Pareto-improving tolls can be formulated as a mathematical program with complementarity constraints, a class of optimization problems difficult to solve. Using concepts from manifold suboptimization, we propose a new algorithm that converges to a strongly stationary solution in a finite number of iterations. The algorithm is also applicable to the problem of finding approximate Pareto-improving tolls and can address the cases where demands are either fixed or elastic. Numerical results using networks from the literature are also given.     

Network-oriented household activity pattern problem for system optimization

The recently emerging trend of self-driving vehicles and information sharing technologies, made available by private technology vendors, starts creating a revolutionary paradigm shift in the coming years for traveler mobility applications. By considering a deterministic traveler decision making framework at the household level in congested transportation networks, this paper aims to address the challenges of how to optimally schedule individuals’ daily travel patterns under the complex activity constraints and interactions. We reformulate two special cases of household activity pattern problem (HAPP) through a high-dimensional network construct, and offer a systematic comparison with the classical mathematical programming models proposed by Recker (1995). Furthermore, we consider the tight road capacity constraint as another special case of HAPP to model complex interactions between multiple household activity scheduling decisions, and this attempt offers another household-based framework for linking activity-based model (ABM) and dynamic traffic assignment (DTA) tools. Through embedding temporal and spatial relations among household members, vehicles and mandatory/optional activities in an integrated space-time-state network, we develop two 0–1 integer linear programming models that can seamlessly incorporate constraints for a number of key decisions related to vehicle selection, activity performing and ridesharing patterns under congested networks. The well-structured network models can be directly solved by standard optimization solvers, and further converted to a set of time-dependent state-dependent least cost path-finding problems through Lagrangian relaxation, which permit the use of computationally efficient algorithms on large-scale high-fidelity transportation networks.     

Solution methods for the taxi pooling problem

In Taiwan, taxi pooling is currently performed by some taxi companies using a trial-and-error experience-based method, which is neither effective nor efficient. There is, however, little in the literature on effective models and solution methods for solving the taxi pooling problem. Thus, in this study we employ network flow techniques and a mathematical programming method to develop a taxi pooling solution method. This method is composed of three models. First, a fleet routing/scheduling model is constructed to produce fleet/passenger routes and schedules. A solution algorithm, based on Lagrangian relaxation, a sub-gradient method and a heuristic to find the upper bound of the solution, is proposed to solve the fleet routing/scheduling model. Then, two single taxi-passenger matching models are constructed with the goals of decreasing number of passenger transfers and matching all passengers and taxis. These two taxi-passenger matching models are directly solved using a mathematical programming solver. For comparison with the solution method, we also develop another heuristic by modifying a heuristic recently proposed for solving a one-to-many taxi pooling problem. The performance of the solution method and the additional heuristic are evaluated by carrying out a case study using real data and suitable assumptions. The test results show that these two solution methods could be useful in practice.     

Biofuel refinery location and supply chain planning under traffic congestion

This research focuses on planning biofuel refinery locations where the total system cost for refinery investment, feedstock and product transportation and public travel is minimized. Shipment routing of both feedstock and product in the biofuel supply chain and the resulting traffic congestion impact are incorporated into the model to decide optimal locations of biofuel refineries. A Lagrangian relaxation based heuristic algorithm is introduced to obtain near-optimum feasible solutions efficiently. To further improve optimality, a branch-and-bound framework (with linear programming relaxation and Lagrangian relaxation bounding procedures) is developed. Numerical experiments with several testing examples demonstrate that the proposed algorithms solve the problem effectively. An empirical Illinois case study and a series of sensitivity analyses are conducted to show the effects of highway congestion on refinery location design and total system costs.     

Relaxation approaches to large scale bus driver scheduling problems

The bus driver scheduling (BDS) problem in a transit company consists of establishing, at minimum cost, a list of work-days in which a driver is assigned to each bus in the given time-table and all clauses of the union contract are respected. In this paper we present a general mathematical programming formulation for the BDS problem. Because, in general, the problem is too large to be solved directly, we introduce a relation of the problem and three different solution approaches. Computational results obtained on real life problems indicate that mathematical programming techniques can solve the BDS problem efficiently.     

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.     

Continuous equilibrium network design models

It is known that the network design problem with the assumption of user optimal flows can be modeled as a 0–1 mixed integer programming problem. Instead, we formulate the network design problem with continuous investment variables subject to equilibrium assignment as a nonlinear optimization problem. We show that this optimization problem is equivalent to an unconstrained problem which we solve by direct search techniques. For convex investment cost functions, the performance of both Powell's method and the method of Hooke and Jeeves is approximately the same with respect to computational requirements for a 24 node, 76 arc network. For the case of concave investment functions, Hooke and Jeeves was superior. The solution to the concave continuous model was very similar to that of the 0–1 model. Furthermore, the required solution time was far less than that required by the corresponding discrete model of the same network. The advantages and disadvantages of the continuous approach as well as the computational requirements are discussed.     

Advanced pricing and rationing policies for large scale multimodal networks

The applying of simplified schemes, such as cordon pricing, as second-best solution to the toll network design problem is investigated here in the context of multiclass traffic assignment on multimodal networks. To this end a suitable equilibrium model has been developed, together with an efficient algorithm capable of simulating large scale networks in quite reasonable computer time. This model implements the theoretical framework proposed in a previous work on the toll optimization problem, where the validity of marginal cost pricing for the context at hand is stated. Application of the model to the real case of Rome shows us, not only that on multimodal networks a relevant share (up to 20%) of the maximum improvements in terms of social welfare achievable with marginal cost pricing can in fact be obtained through cordon pricing, but also that in practical terms rationing is a valid alternative to pricing, thus getting around some of the relevant questions (theoretical, technical, social) the latter raises. As a result we propose a practical method to analyze advanced pricing and rationing policies differentiated for user categories, which enables us to compare alternative operative solutions with an upper bound on social welfare based on a solid theoretical background.     

Global optimization method for network design problem with stochastic user equilibrium

In this paper, we consider the continuous road network design problem with stochastic user equilibrium constraint that aims to optimize the network performance via road capacity expansion. The network flow pattern is subject to stochastic user equilibrium, specifically, the logit route choice model. The resulting formulation, a nonlinear nonconvex programming problem, is firstly transformed into a nonlinear program with only logarithmic functions as nonlinear terms, for which a tight linear programming relaxation is derived by using an outer-approximation technique. The linear programming relaxation is then embedded within a global optimization solution algorithm based on range reduction technique, and the proposed approach is proved to converge to a global optimum.     

Optimal offsets for traffic signal systems in urban networks

The paper proposes a binary integer programming model for the computation of optimal traffic signal offsets for an urban road network. The basic theoretical assumptions for the computation of delay on the network are those employed by the main models developed during the last few years. The set of input data coincides with that needed for the Combination Method and its extensions. The model is solved through a branch-and-backtrack method and allows the obtaining of optimal offsets for condensable or uncondensable networks without introducing any special assumption on delay-offset functions, contrary to what occurs within other mathematical programming formulations of the problem. A reduced memory dimension is required by the developed algorithm, which promptly supplies during the computation better and better sub-optimal solutions, very interesting in view of the possible application of the method to real-time control problems. The tests performed show that the method can be applied to networks of practical size.     

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.     

A predictive dynamic traffic assignment model in congested capacity-constrained road networks

In this paper, a predictive dynamic traffic assignment model in congested capacity-constrained road networks is formulated. A traffic simulator is developed to incrementally load the traffic demand onto the network, and updates the traffic conditions dynamically. A time-dependent shortest path algorithm is also given to determine the paths with minimum actual travel time from an origin to all the destinations. The traffic simulator and time-dependent shortest path algorithm are employed in a method of successive averages to solve the dynamic equilibrium solution of the problem. A numerical example is given to illustrate the effectiveness of the proposed method.     

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.