Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach

This paper proposes a global optimization algorithm for solving a mixed (continuous/discrete) transportation network design problem (MNDP), which is generally expressed as a mathematical programming with equilibrium constraint (MPEC). The upper level of the MNDP aims to optimize the network performance via both expansion of existing links and addition of new candidate links, whereas the lower level is a traditional Wardrop user equilibrium (UE) problem. In this paper, we first formulate the UE condition as a variational inequality (VI) problem, which is defined from a finite number of extreme points of a link-flow feasible region. The MNDP is approximated as a piecewise-linear programming (P-LP) problem, which is then transformed into a mixed-integer linear programming (MILP) problem. A global optimization algorithm based on a cutting constraint method is developed for solving the MILP problem. Numerical examples are given to demonstrate the efficiency of the proposed method and to compare the results with alternative algorithms reported in the literature.     

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.     

Optimal joint distance and time toll for cordon-based congestion pricing

This paper addresses the optimal toll design problem for the cordon-based congestion pricing scheme, where both a time-toll and a nonlinear distance-toll (i.e., joint distance and time toll) are levied for each network user’s trip in a pricing cordon. The users’ route choice behaviour is assumed to follow the Logit-based stochastic user equilibrium (SUE). We first propose a link-based convex programming model for the Logit-based SUE problem with a joint distance and time toll pattern. A mathematical program with equilibrium constraints (MPEC) is developed to formulate the optimal joint distance and time toll design problem. The developed MPEC model is equivalently transformed into a semi-infinite programming (SIP) model. A global optimization method named Incremental Constraint Method (ICM) is designed for solving the SIP model. Finally, two numerical examples are used to assess the proposed methodology.     

On the modeling and solution algorithm for the reverse logistics recycling flow equilibrium problem

This paper presents a study that characterizes, formulates, and solves the reverse logistic recycling flow equilibrium (RLRFE) problem. The RLRFE problem is concerned with the recycling channel in which recyclable collectors, processors, landfills, and demand markets form a multi-tiered network to process the recycled material flows from sources destined either for landfills or demand markets. Motivated by a government policy making or enterprise conglomerate recycling system design and operation needs, the RLRFE problem is elaborated from a system-optimal perspective using the variational inequality (VI) approach. For each origin–destination (OD) pair, the corresponding equilibrium conditions are established as a variation of the Wardrop second principle. In light of demand and cost function interactions, a nested diagonalization solution (ND) algorithm is proposed that gradually transforms the RLRFE problem into a traffic assignment model. To address multiple landfills in the recycling network and to understand how a variable-demand problem can be analyzed as a fixed-demand problem, we propose a supernetwork representation of the RLRFE problem. A numerical analysis on a test case illustrates the model formulation and the proposed algorithm.     

Optimal multi-step toll design under general user heterogeneity

This paper studies the optimal multi-step toll design problem for the bottleneck model with general user heterogeneity. The design model is formulated as a mathematical program with equilibrium constraints (MPEC), which is NP-hard due to non-convexity in both the objective function and the feasible set. An analytical method is proposed to solve the MPEC by decomposing it into smaller and easier quadratic programs, each corresponding to a unique departure order of different user classes. The quadratic programs are defined on a polyhedral set, which makes it easier to identify a local optimum. Importantly, each quadratic program is constrained by a set of linear feasibility cuts that define the presence of each user class in the arrival window. We prove that the proposed method ensures global optimality provided that each quadratic program can be solved globally. To obviate enumerating all departure orders, a heuristic method is developed to navigate through the solution space by using the multipliers associated with the feasibility cuts. Numerical experiments are conducted on several small examples to validate the proposed methodology. These experiments show that the proposed heuristic method is effective in finding near-optimal solutions within a relatively small number of iterations.     

A toll-based bi-level programming approach to managing hazardous materials shipments over an intermodal transportation network

This research proposes a bi-level bi-objective model to regulate the usage of rail intermodal terminals for hazardous materials (hazmat) shipments, where government imposes tolls to deter carriers from using certain terminals. The complexity of the resulting mathematical program motivates the development of a hybrid speed-constrained multi-objective particle swarm optimization algorithm, which is then integrated with CPLEX, to solve the model. Through a real problem instance based on the intermodal service chain of Norfolk Southern in US, the toll-setting model is examined and further compared with a regular network design approach, in which certain terminals are closed to hazmat containers. The computational results show that the toll-setting policy is more practical and efficient, and the two models can be combined as a two-stage strategy in long-term hazmat transportation regulations. Additional managerial insights are derived for different stakeholders.     

Modeling dry-port-based freight distribution planning

In this paper we review the dry port concept and its outfalls in terms of optimal design and management of freight distribution. Some optimization challenges arising from the presence of dry ports in intermodal freight transport systems are presented and discussed. Then we consider the tactical planning problem of defining the optimal routes and schedules for the fleet of vehicles providing transportation services between the terminals of a dry-port-based intermodal system. An original service network design model based on a mixed integer programming mathematical formulation is proposed to solve the considered problem. An experimental framework built upon realistic instances inspired by regional cases is described and the computational results of the model are presented and discussed.     

Approximate network loading and dual-time-scale dynamic user equilibrium

In this paper we present a dual-time-scale formulation of dynamic user equilibrium (DUE) with demand evolution. Our formulation belongs to the problem class that Pang and Stewart (2008) refer to as differential variational inequalities. It combines the within-day time scale for which route and departure time choices fluctuate in continuous time with the day-to-day time scale for which demand evolves in discrete time steps. Our formulation is consistent with the often told story that drivers adjust their travel demands at the end of every day based on their congestion experience during one or more previous days. We show that analysis of the within-day assignment model is tremendously simplified by expressing dynamic user equilibrium as a differential variational inequality. We also show there is a class of day-to-day demand growth models that allow the dual-time-scale formulation to be decomposed by time-stepping to yield a sequence of continuous time, single-day, dynamic user equilibrium problems. To solve the single-day DUE problems arising during time-stepping, it is necessary to repeatedly solve a dynamic network loading problem. We observe that the network loading phase of DUE computation generally constitutes a differential algebraic equation (DAE) system, and we show that the DAE system for network loading based on the link delay model (LDM) of Friesz et al. (1993) may be approximated by a system of ordinary differential equations (ODEs). That system of ODEs, as we demonstrate, may be efficiently solved using traditional numerical methods for such problems. To compute an actual dynamic user equilibrium, we introduce a continuous time fixed-point algorithm and prove its convergence for effective path delay operators that allow a limited type of nonmonotone path delay. We show that our DUE algorithm is compatible with network loading based on the LDM and the cell transmission model (CTM) due to Daganzo (1995). We provide a numerical example based on the much studied Sioux Falls network.     

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.     

Joint deployment of charging stations and photovoltaic power plants for electric vehicles

The focus of this study is to jointly design charging stations and photovoltaic (PV) power plants with time-dependent charging fee, to improve the management of the coupled transportation and power systems. We first propose an efficient and extended label-setting algorithm to solve the EV joint routing and charging problem that considers recharging amount choices at different stations and loop movement cases. Then, a variational inequality problem is formulated to model the equilibrium of EV traffic on transportation networks, and an optimal power flow model is proposed to model the power network flow with PV power plants and optimally serve the EV charging requirements. Based on the above models for describing system states, we then formulate a model to simultaneously design charging stations, PV plants, and time-dependent charging fee. A surrogate-based optimization (SBO) algorithm is adopted to solve the model. Numerical examples demonstrate that the proposed SBO algorithm performs well. Additionally, important insights concerning the infrastructure design and price management of the coupled transportation and power networks are derived accordingly.     

Intermodal freight transport planning – A receding horizon control approach

This paper investigates intermodal freight transport planning problems among deep-sea terminals and inland terminals in hinterland haulage for a horizontally fully integrated intermodal freight transport operator at the tactical container flow level. An intermodal freight transport network (IFTN) model is first developed to capture the key characteristics of intermodal freight transport such as the modality change phenomena at intermodal terminals, physical capacity constraints of the network, time-dependent transport times on freeways, and time schedules for trains and barges. After that, the intermodal freight transport planning problem is formulated as an optimal intermodal container flow control problem from a system and control perspective with the use of the proposed IFTN model. To deal with the dynamic transport demands and dynamic traffic conditions in the IFTN, a receding horizon intermodal container flow control (RIFC) approach is proposed to control and to reassign intermodal container flows in a receding horizon way. This container flow control approach involves solving linear programming problems and is suited for transport planning on large-sized networks. Both an all-or-nothing approach and the proposed RIFC approach are evaluated through simulation studies. Simulation results show the potential of the proposed RIFC approach.     

Robust optimization of distance-based tolls in a network considering stochastic day to day dynamics

This paper investigates the nonlinear distance-based congestion pricing in a network considering stochastic day-to-day dynamics. After an implementation/adjustment of a congestion pricing scheme, the network flows in a certain period of days are not on an equilibrium state, thus it is problematic to take the equilibrium-based indexes as the pricing objective. Therefore, the concept of robust optimization is taken for the congestion toll determination problem, which takes into account the network performance of each day. First, a minimax model which minimizes the maximum regret on each day is proposed. Taking as a constraint of the minimax model, a path-based day to day dynamics model under stochastic user equilibrium (SUE) constraints is discussed in this paper. It is difficult to solve this minimax model by exact algorithms because of the implicity of the flow map function. Hence, a two-phase artificial bee colony algorithm is developed to solve the proposed minimax regret model, of which the first phase solves the minimal expected total travel cost for each day and the second phase handles the minimax robust optimization problem. Finally, a numerical example is conducted to validate the proposed models and methods.     

Network design for personal rapid transit under transit-oriented development

This study addresses guideway network design for personal rapid transit (PRT) favoring transit-oriented development. The guideway network design problem seeks to minimize both the guideway construction cost and users’ travel time. In particular, a set of optional points, known as Steiner points, are introduced in the graph to reduce the guideway length. The model is formulated as a combined Steiner and assignment problem, and a Lagrangian relaxation based solution algorithm is developed to solve the optimal solution. Numerical studies are carried on a real-sized network, and illustrate that the proposed model and solution algorithm can solve the PRT guideway network design problem effectively.     

Dynamic and disequilibrium analysis of interdependent infrastructure systems

There is a growing awareness in recent years that the interdependencies among the civil infrastructure systems have significant economic, security and engineering implications that may influence their resiliency, efficiency and effectiveness. To capture the various types of infrastructure interdependencies and incorporate them into decision-making processes in various application domains, Zhang and Peeta (2011) propose a generalized modeling framework that combines a multilayer infrastructure network (MIN) concept and a market-based economic approach using computable general equilibrium (CGE) theory and its spatial extension (SCGE) to formulate a static equilibrium infrastructure interdependencies problem. This paper extends the framework to address the dynamic and disequilibrium aspects of the infrastructure interdependencies problems. It briefly reviews the static model, and proposes an alternative formulation for it using the variational inequality (VI) technique. Based on this equivalent VI formulation, a within-period equilibrium-tending dynamic model is proposed to illustrate how these systems evolve towards an equilibrium state within a short duration after a perturbation. To address a longer time scale, a multi-period dynamic model is proposed. This model explicitly considers the evolution of infrastructure interdependencies over time and the temporal interactions among the various systems through dynamic parameters that link the different time periods. Using this model, numerical experiments are conducted for a special case with a single region to analyze the sensitivity of the model to the various parameters, and demonstrate the ability of the modeling framework to formulate and solve practical problems such as cascading failures, disaster recovery, and budget allocation in a dynamic setting.     

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.     

Parametric search for the bi-attribute concave shortest path problem

A bi-attribute concave shortest path (BC-SP) problem seeks to find an optimal path in a bi-attribute network that minimizes a linear combination of two path costs, one of which is evaluated by a nondecreasing concave function. Due to the nonadditivity of its objective function, Bellman’s principle of optimality does not hold. This paper proposes a parametric search method to solve the BC-SP problem, which only needs to solve a series of shortest path problems, i.e., the parameterized subproblems (PSPs). Several techniques are developed to reduce both the number of PSPs and the computation time for these PSPs. Specifically, we first identify two properties of the BC-SP problem to guide the parametric search using the gradient and concavity of its objective function. Based on the properties, a monotonic descent search (MDS) and an intersection point search (IPS) are proposed. Second, we design a speedup label correcting (LC) algorithm, which uses optimal solutions of previously solved PSPs to reduce the number of labeling operations for subsequent PSPs. The MDS, IPS and speedup LC techniques are embedded into a branch-and-bound based interval search to guarantee optimality. The performance of the proposed method is tested on the mean-standard deviation shortest path problem and the route choice problem with a quadratic disutility function. Experiments on both real transportation networks and grid networks show that the proposed method reduces the computation time of existing algorithms by one to two orders of magnitude.     

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.     

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.     

Stochastic transit equilibrium

We present a transit equilibrium model in which boarding decisions are stochastic. The model incorporates congestion, reflected in higher waiting times at bus stops and increasing in-vehicle travel time. The stochastic behavior of passengers is introduced through a probability for passengers to choose boarding a specific bus of a certain service. The modeling approach generates a stochastic common-lines problem, in which every line has a chance to be chosen by each passenger. The formulation is a generalization of deterministic transit assignment models where passengers are assumed to travel according to shortest hyperpaths. We prove existence of equilibrium in the simplified case of parallel lines (stochastic common-lines problem) and provide a formulation for a more general network problem (stochastic transit equilibrium). The resulting waiting time and network load expressions are validated through simulation. An algorithm to solve the general stochastic transit equilibrium is proposed and applied to a sample network; the algorithm works well and generates consistent results when considering the stochastic nature of the decisions, which motivates the implementation of the methodology on a real-size network case as the next step of this research.