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.     

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.     

Robust transit network design with stochastic demand considering development density

This paper analyzes the influence of urban development density on transit network design with stochastic demand by considering two types of services, rapid transit services, such as rail, and flexible services, such as dial-a-ride shuttles. Rapid transit services operate on fixed routes and dedicated lanes, and with fixed schedules, whereas dial-a-ride services can make use of the existing road network, hence are much more economical to implement. It is obvious that the urban development densities to financially sustain these two service types are different. This study integrates these two service networks into one multi-modal network and then determines the optimal combination of these two service types under user equilibrium (UE) flows for a given urban density. Then we investigate the minimum or critical urban density required to financially sustain the rapid transit line(s). The approach of robust optimization is used to address the stochastic demands as captured in a polyhedral uncertainty set, which is then reformulated by its dual problem and incorporated accordingly. The UE principle is represented by a set of variational inequality (VI) constraints. Eventually, the whole problem is linearized and formulated as a mixed-integer linear program. A cutting constraint algorithm is adopted to address the computational difficulty arising from the VI constraints. The paper studies the implications of three different population distribution patterns, two CBD locations, and produces the resultant sequences of adding more rapid transit services as the population density increases.     

Intermodal hub-and-spoke network design: Incorporating multiple stakeholders and multi-type containers

This paper develops a mathematical program with equilibrium constraints (MPEC) model for the intermodal hub-and-spoke network design (IHSND) problem with multiple stakeholders and multi-type containers. The model incorporates a parametric variational inequality (VI) that formulates the user equilibrium (UE) behavior of intermodal operators in route choice for any given network design decision of the network planner. The model also uses a cost function that is capable of reflecting the transition from scale economies to scale diseconomies in distinct flow regimes for carriers or hub operators, and a disutility function integrating actual transportation charges and congestion impacts for intermodal operators. To solve the MPEC model, a hybrid genetic algorithm (HGA) embedded with a diagonalization method for solving the parametric VI is proposed. Finally, the comparative analysis of the HGA and an exhaustive enumeration algorithm indicates a good performance of the HGA in terms of computational time and solution quality. The HGA is also applied to solve a large-scale problem to show the applicability of the proposed model and algorithm.     

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.     

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.     

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.     

Formulating and solving the network design problem by decomposition

The optimal transportation network design problem is formulated as a convex nonlinear programming problem and a solution method based on standard traffic assignment algorithms is presented. The technique can deal with network improvements which introduce new links, which increase the capacity of existing links, or which decrease the free-flow (uncongested) travel time on existing links (with or without simultaneously increasing link capacity). Preliminary computational experience with the method demonstrates that it is capable of solving very large problems with reasonable amounts of computer time.     

A network enhancement model with integrated lane reorganization and traffic control strategies

Lane reorganization strategies such as lane reversal, one‐way street, turning restriction, and cross elimination have demonstrated their effectiveness in enhancing transportation network capacity. However, how to select the most appropriate combination of those strategies in a network remains challenging to transportation professionals considering the complex interactions among those strategies and their impacts on conventional traffic control components. This article contributes to developing a mathematical model for a traffic equilibrium network, in which optimization of lane reorganization and traffic control strategies are integrated in a unified framework. The model features a bi‐level structure with the upper‐level model describing the decision of the transportation authorities for maximizing the network capacity. A variational inequality (VI) formulation of the user equilibrium (UE) behavior in choosing routes in response to various strategies is developed in the lower level. A genetic algorithm (GA) based heuristic is used to yield meta‐optimal solutions to the model. Results from extensive numerical analyses reveal the promising property of the proposed model in enhancing network capacity and reducing congestion. Copyright © 2016 John Wiley & Sons, Ltd.     

Roads in transition: Integrated modeling of a manufacturer-traveler-infrastructure system in a mixed autonomous/human driving environment

This paper develops an integrated model to characterize the market penetration of autonomous vehicles (AVs) in urban transportation networks. The model explicitly accounts for the interplay among the AV manufacturer, travelers with heterogeneous values of travel time (VOTT), and road infrastructure capacity. By making in-vehicle time use more leisurely or productive, AVs reduce travelers’ VOTT. In addition, AVs can move closer together than human-driven vehicles because of shorter safe reaction time, which leads to increased road capacity. On the other hand, the use of AV technologies means added manufacturing cost and higher price. Thus, traveler adoption of AVs will trade VOTT savings with additional out-of-pocket cost. The model is structured as a leader (AV manufacturer)-follower (traveler) game. Given the cost of producing AVs, the AV manufacturer sets AV price to maximize profit while anticipating AV market penetration. Given an AV price, the vehicle and routing choice of heterogeneous travelers are modeled by combining a multinomial logit model with multi-modal multi-class user equilibrium (UE). The overall problem is formulated as a mathematical program with complementarity constraints (MPCC), which is challenging to solve. We propose a solution approach based on piecewise linearization of the MPCC as a mixed-integer linear program (MILP) and solving the MILP to global optimality. Non-uniform distribution of breakpoints that delimit piecewise intervals and feasibility-based domain reduction are further employed to reduce the approximation error brought by linearization. The model is implemented in a simplified Singapore network with extensive sensitivity analyses and the Sioux Falls network. Computational results demonstrate the effectiveness and efficiency of the solution approach and yield valuable insights about transportation system performance in a mixed autonomous/human driving environment.     

Iterative procedure for equilibrium network traffic signal setting

The Equilibrium Network Traffic Signal Setting problem is an open research area. It can be approached using global optimization models or iterative procedures. In this paper, after a brief review of the state of the art, the main characteristics of the iterative procedure ENETS are described. In this procedure, traffic signal setting is performed in two successive steps: green timing and scheduling at each junction, and signal coordination on the network. Green timing and scheduling at a single junction is based on a mixed-binary linear program with capacity factor maximization. Signal coordination for the whole network is performed by solving a discrete programming model with total delay minimization. The flow assignment stage refers to the separable user equilibrium model with fixed demand, and uses a feasible direction algorithm, which can also be adopted to cover the cases of elastic demand and/or asymmetric equilibrium. An experimental test of ENETS on a small network and a graphical explanation of the procedure are described and discussed.     

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.     

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.     

The impact of speed limits on traffic equilibrium and system performance in networks

Speed limits are usually imposed on roads in an attempt to enhance safety and sometimes serve the purpose of reducing fuel consumption and vehicular emissions as well. Most previous studies up to date focus on investigation of the effects of speed limits from a local perspective, while network-wide traffic reallocation effects are overlooked. This paper makes the first attempt to investigate how a link-specific speed limit law reallocates traffic flow in an equilibrium manner at a macroscopic network level. We find that, although the link travel time–flow relationship is altered after a speed limit is imposed, the standard traffic assignment method still applies. With the commonly adopted assumptions, the uniqueness of link travel times at user equilibrium (UE) remains valid, and the UE flows on links with non-binding speed limits are still unique. The UE flows on other links with binding speed limits may not be unique but can be explicitly characterized by a polyhedron or a linear system of equalities and inequalities. Furthermore, taking into account the traffic reallocation effects of speed limits, we compare the capability of speed limits and road pricing for decentralizing desirable network flow patterns. Although from a different perspective for regulating traffic flows with a different mechanism, a speed limit law may play the same role as a toll charge scheme and perform better than some negative (rebate) toll schemes under certain conditions for network flow management.     

Liner shipping network design with emission control areas: A genetic algorithm-based approach

To curb emissions, containerized shipping lines face the traditional trade-off between cost and emissions (CO₂ and SO_x) reduction. This paper considers this element in the context of liner service design and proposes a mixed integer linear programming (MILP) model based on a multi-commodity pickup and delivery arc-flow formulation. The objective is to maximize the profit by selecting the ports to be visited, the sequence of port visit, the cargo flows between ports, as well as the number/operating speeds of vessels on each arc of the selected route. The problem also considers that Emission Control Areas (ECAs) exist in the liner network and accounts for the vessel carrying capacity. In addition to using the MILP solver of CPLEX, we develop in the paper a specific genetic algorithm (GA) based heuristic and show that it gives the possibility to reach an optimal solution when solving large size instances.     

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.     

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 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.     

Multi-objective optimization of a road diet network design

The present study focuses on the development of a model for the optimal design of a road diet plan within a transportation network, and is based on rigorous mathematical models. In most metropolitan areas, there is insufficient road space to dedicate a portion exclusively for cyclists without negatively affecting existing motorists. Thus, it is crucial to find an efficient way to implement a road diet plan that both maximizes the utility for cyclists and minimizes the negative effect on motorists. A network design problem (NDP), which is usually used to find the best option for providing extra road capacity, is adapted here to derive the best solution for limiting road capacity. The resultant NDP for a road diet (NDPRD) takes a bi-level form. The upper-level problem of the NDPRD is established as one of multi-objective optimization. The lower-level problem accommodates user equilibrium (UE) trip assignment with fixed and variable mode-shares. For the fixed mode-share model, the upper-level problem minimizes the total travel time of both cyclists and motorists. For the variable mode-share model, the upper-level problem includes minimization of both the automobile travel share and the average travel time per unit distance for motorists who keep using automobiles after the implementation of a road diet. A multi-objective genetic algorithm (MOGA) is mobilized to solve the proposed problem. The results of a case study, based on a test network, guarantee a robust approximate Pareto optimal front. The possibility that the proposed methodology could be adopted in the design of a road diet plan in a real transportation network is confirmed.     

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.