Dynamic Stackelberg equilibrium congestion pricing

This paper considers the problem of dynamic congestion pricing that determines optimal time-varying tolls for a pre-specified subset of arcs with bottleneck on a congested general traffic network. A two-person nonzero-sum dynamic Stackelberg game model is formulated with the assumption that the underlying information structure is open loop. Characteristics of the Stackelberg equilibrium solution are analyzed. The Hooke–Jeeves algorithm that obviates an evaluation of the gradient vector of the objective function is presented with a numerical example. The paper concludes with its future extensions.     

Infrastructure planning for fast charging stations in a competitive market

Most existing studies on EV charging infrastructure planning take a central planner’s perspective, by assuming that investment decision on charging facilities can be controlled by a single decision entity. In this paper, we establish modeling and computational methods to support business-driven EV charging infrastructure investment planning problem, where the infrastructure system is shaped by collective actions of multiple decision entities who do not necessarily coordinate with each other. A network-based multi-agent optimization modeling framework is developed to simultaneously capture the selfish behaviors of individual investors and travelers and their interactions over a network structure. To overcome computational difficulty imposed by non-convexity of the problem, we rely on recent theoretical development on variational convergence of bivariate functions to design a solution algorithm with analysis on its convergence properties. Numerical experiments are implemented to study the performance of proposed method and draw practical insights.     

Network-based real option models

Building on earlier work to incorporate real option methodologies into network modeling, two models are proposed. The first is the network option design problem, which maximizes the expanded net present value of a network investment as a function of network design variables with the option to defer the committed design investment. The problem is shown to be a generalized version of the network design problem and the multi-period network design problem. A heuristic based on radial basis functions is used to solve the problem for continuous link expansion with congestion effects. The second model is a link investment deferral option set, which decomposes the network investment deferral option into individual, interacting link or project investments. This model is a project selection problem under uncertainty, where each link or project can be deferred such that the expanded net present value is maximized. The option is defined in such a way that a lower bound can be solved using an exact method based on multi-option least squares Monte Carlo simulation. Numerical tests are conducted with the classical Sioux Falls network and compared to earlier published results.     

A general bilevel linear programming formulation of the network design problem

A formulation of the network design problem as a bilevel linear program is presented which admits both the convex and concave investment functions. It also allows a more general representation of travel cost functions than a previous formulation by LeBlanc and Boyce (1986).     

Approximate algorithms for the discrete network design problem

The discrete network design problem is one of finding a set of feasible actions (projects) from among a collection of possible actions, that when implemented, optimizes some objective function(s). This is a combinatorial optimization problem that is very expensive to solve exactly. This paper proposes two algorithms for obtaining approximate solutions to the discrete network design problem with much less computational effeort. The computational savings are achieved by approximating the original problem with a new formulation which is easier to solve. The first algorithm proposed solves this approximate problem exactly, while the second is even more efficient, but provides only a near-optimal solution to the approximate problem. Experience with test problems indicates that these approximations can reduce the computational effort by a factor of 3–5, with little loss in solution accuracy.     

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.     

A comparison of user-optimum versus system-optimum traffic assignment in transportation network design

In this report, we compare the computational efficiency and results of solving two alternative models for the problem of determining improvements to an urban road network. Using a 1462 link, 584 node test network of the north Dallas area, we compare a model which assumes user-optimum behavior of travelers with a model which assumes system-optimum flows. Both of these models allow improvements to the road network to take on any nonnegative value, rather than requiring discrete improvement values. Investment costs are modeled by functions with decreasing marginal costs. Unfortunately, the user-optimum model, which is much more realistic than the system-optimum one, normally cannot be solved optimally. However, the simpler system-optimum model can be optimally solved, provided that investment costs are approximated by linear functions. Thus, for this network design problem we compare an accurate representation which can be solved only approximately with an approximate representation which can be solved optimally. Our computational testing showed that the system-optimum model produces solutions as good as those from the user-optimum model, and thus seems justified when favored by other considerations, such as ease of coding, availability of “canned” programs, etc.     

Co-design of traffic network topology and control measures

The two main directions to improve traffic flows in networks involve changing the network topology and introducing new traffic control measures. In this paper, we consider a co-design approach to apply these two methods jointly to improve the interaction between different methods and to get a better overall performance. We aim at finding the optimal network topology and the optimal parameters of traffic control laws at the same time by solving a co-optimization problem. However, such an optimization problem is usually highly non-linear and non-convex, and it possibly involves a mixed-integer form. Therefore, we discuss four different solution frameworks that can be used for solving the co-optimization problem, according to different requirements on the computational complexity and speed. A simulation-based study is implemented on the Singapore freeway network to illustrate the co-design approach and to compare the four different solution frameworks.     

On activity-based network design problems

This paper examines network design where OD demand is not known a priori, but is the subject of responses in household or user itinerary choices to infrastructure improvements. Using simple examples, we show that falsely assuming that household itineraries are not elastic can result in a lack in understanding of certain phenomena; e.g., increasing traffic even without increasing economic activity due to relaxing of space–time prism constraints, or worsening of utility despite infrastructure investments in cases where household objectives may conflict. An activity-based network design problem is proposed using the location routing problem (LRP) as inspiration. The bilevel formulation includes an upper level network design and shortest path problem while the lower level includes a set of disaggregate household itinerary optimization problems, posed as household activity pattern problem (HAPP) (or in the case with location choice, as generalized HAPP) models. As a bilevel problem with an NP-hard lower level problem, there is no algorithm for solving the model exactly. Simple numerical examples show optimality gaps of as much as 5% for a decomposition heuristic algorithm derived from the LRP. A large numerical case study based on Southern California data and setting suggest that even if infrastructure investments do not result in major changes in link investment decisions compared to a conventional model, the results provide much higher resolution temporal OD information to a decision maker. Whereas a conventional model would output the best set of links to invest given an assumed OD matrix, the proposed model can output the same best set of links, the same daily OD matrix, and a detailed temporal distribution of activity participation and travel from which changes in peak period OD patterns can be observed.     

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.     

Green supply chain network design to reduce carbon emissions

We consider a supply chain network design problem that takes CO₂ emissions into account. Emission costs are considered alongside fixed and variable location and production costs. The relationship between CO₂ emissions and vehicle weight is modeled using a concave function leading to a concave minimization problem. As the direct solution of the resulting model is not possible, Lagrangian relaxation is used to decompose the problem into a capacitated facility location problem with single sourcing and a concave knapsack problem that can be solved easily. A Lagrangian heuristic based on the solution of the subproblem is proposed. When evaluated on a number of problems with varying capacity and cost characteristics, the proposed algorithm achieves solutions within 1% of the optimal. The test results indicate that considering emission costs can change the optimal configuration of the supply chain, confirming that emission costs should be considered when designing supply chains in jurisdictions with carbon costs.     

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.     

Benders Decomposition for Discrete–Continuous Linear Bilevel Problems with application to traffic network design

We propose a new fast solution method for linear Bilevel Problems with binary leader and continuous follower variables under the partial cooperation assumption. We reformulate the Bilevel Problem into a single-level problem by using the Karush–Kuhn–Tucker conditions. This non-linear model can be linearized because of the special structure achieved by the binary leader decision variables and subsequently solved by a Benders Decomposition Algorithm to global optimality. We illustrate the capability of the approach on the Discrete Network Design Problem which adds arcs to an existing road network at the leader stage and anticipates the traffic equilibrium for the follower stage. Because of the non-linear objective functions of this problem, we use a linearization method for increasing, convex and non-linear functions based on continuous variables. Numerical tests show that this algorithm can solve even large instances of Bilevel Problems.     

An efficient and exact event-based algorithm for solving simplified first order dynamic network loading problems in continuous time

In this paper a novel solution algorithm is proposed for exactly solving simplified first order dynamic network loading (DNL) problems for any generalised network. This DNL solution algorithm, termed eLTM (event-based Link Transmission Model), is based on the seminal Lighthill–Witham–Richards (LWR) model, adopts a triangular fundamental diagram and includes a generalised first order node model formulation. Unlike virtually all DNL solution algorithms, eLTM does not rely on time discretisation, but instead adopts an event based approach. The main advantage of this approach is the possibility of yielding exact results. Furthermore, an approximate version of the same algorithm is introduced. The user can configure an a-priori threshold that dictates the approximation error (measurable a-posteriori). Using this approximation the computational effort required decreases significantly, making it especially suitable for large scale applications. The computational complexity is investigated and results are demonstrated via theoretical and real world case studies. Fixed periods of stationary demands are included adopting a matrix demand profile to mimic basic departure time demand fluctuations. Finally, the information loss of the approximate solution is assessed under different configurations.     

An efficient iterative link transmission model

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

Integrated optimization on train scheduling and preventive maintenance time slots planning

We address the problem of simultaneously scheduling trains and planning preventive maintenance time slots (PMTSs) on a general railway network. Based on network cumulative flow variables, a novel integrated mixed-integer linear programming (MILP) model is proposed to simultaneously optimize train routes, orders and passing times at each station, as well as work-time of preventive maintenance tasks (PMTSs). In order to provide an easy decomposition mechanism, the limited capacity of complex tracks is modelled as side constraints and a PMTS is modelled as a virtual train. A Lagrangian relaxation solution framework is proposed, in which the difficult track capacity constraints are relaxed, to decompose the original complex integrated train scheduling and PMTSs planning problem into a sequence of single train-based sub-problems. For each sub-problem, a standard label correcting algorithm is employed for finding the time-dependent least cost path on a time-space network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted on a small artificial network and a real-world network adapted from a Chinese railway network, to evaluate the effectiveness and computational efficiency of the integrated optimization model and the proposed Lagrangian relaxation solution framework. The benefits of simultaneously scheduling trains and planning PMTSs are demonstrated, compared with a commonly-used sequential scheduling method.     

A discrete-convex programming approach to the simultaneous optimization of land use and transportation

Three design problems are discussed in this article. First, it is shown that the network design problem with congestion reduces to an all-or nothing traffic assignment problem under some assumptions on the congestion function and the investment cost function. Second, the land use design problem is formulated as an extension of the Koopmans-Beckmann problem and a heuristic is proposed to solve this problem. Third, it is shown that the seemingly more complex problem of designing jointly a land-use plan and a transportation network reduces to a pure land-use design problem. All that is needed to solve the joint optimization problem is a shortest path algorithm and a heuristic to solve the land use design problem. Computational experience is reported for each algorithm.     

Dynamic system-optimal traffic assignment using a state space model

We propose a new mathematical formulation for the problem of optimal traffic assignment in dynamic networks with multiple origins and destinations. This problem is motivated by route guidance issues that arise in an Intelligent Vehicle-Highway Systems (IVHS) environment. We assume that the network is subject to known time-varying demands for travel between its origins and destinations during a given time horizon. The objective is to assign the vehicles to links over time so as to minimize the total travel time experienced by all the vehicles using the network. We model the traffic network over the time horizon as a discrete-time dynamical system. The system state at each time instant is defined in a way that, without loss of optimality, avoids complete microscopic detail by grouping vehicles into platoons irrespective of origin node and time of entry to network. Moreover, the formulation contains no explicit path enumeration. The state transition function can model link travel times by either impedance functions, link outflow functions, or by a combination of both. Two versions (with different boundary conditions) of the problem of optimal traffic assignment are studied in the context of this model. These optimization problems are optimal control problems for nonlinear discrete-time dynamical systems, and thus they are amenable to algorithmic solutions based on dynamic programming. The computational challenges associated with the exact solution of these problems are discussed and some heuristics are proposed.     

Modeling and solving discrete network design problem with stochastic user equilibrium

In this paper, we address the discrete network design problem, which determines the addition of new roads to existing transportation network to optimize the transportation system performance. Road users are assumed to follow the traffic assignment principle of stochastic user equilibrium. A mixed‐integer nonlinear nonconvex problem is developed to model this discrete network design problem with stochastic user equilibrium. The original problem is relaxed into a convex mixed‐integer nonlinear program, whose solution provides a lower bound of the original problem. The relaxed problem is then embedded into two proposed global optimization solution algorithms to obtain the global optimal solution of the problem. Copyright © 2016 John Wiley & Sons, Ltd.