A bilevel flow model for hazmat transportation network design

In this work we consider the following hazmat transportation network design problem. A given set of hazmat shipments has to be shipped over a road transportation network in order to transport a given amount of hazardous materials from specific origin points to specific destination points, and we assume there are regional and local government authorities that want to regulate the hazmat transportations by imposing restrictions on the amount of hazmat traffic over the network links. In particular, the regional authority aims to minimize the total transport risk induced over the entire region in which the transportation network is embedded, while local authorities want the risk over their local jurisdictions to be the lowest possible, forcing the regional authority to assure also risk equity. We provide a linear bilevel programming formulation for this hazmat transportation network design problem that takes into account both total risk minimization and risk equity. We transform the bilevel model into a single-level mixed integer linear program by replacing the second level (follower) problem by its KKT conditions and by linearizing the complementary constraints, and then we solve the MIP problem with a commercial optimization solver. The optimal solution may not be stable, and we provide an approach for testing its stability and for evaluating the range of its solution values when it is not stable. Moreover, since the bilevel model is difficult to be solved optimally and its optimal solution may not be stable, we provide a heuristic algorithm for the bilevel model able to always find a stable solution. The proposed bilevel model and heuristic algorithm are experimented on real scenarios of an Italian regional network.     

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.     

Path-differentiated pricing in congestion mitigation

Instead of charging tolls on individual links, this paper considers doing the same on paths. Path and link tolls are “valid” if they encourage motorists to use routes that collectively lead to a target distribution, e.g., one that minimizes travel delay. Because the numbers of valid link and path tolls are typically infinite, an objective in pricing tolls is to find a set of valid tolls that yields the least revenue to lessen the financial burden on motorists.Path tolls are generally more flexible than link tolls and this paper shows that this flexibility can substantially reduce the financial burden on motorists. Additionally, valid path tolls yielding the least revenue possess characteristics with interesting policy implications. To determine these path tolls, it is natural to formulate the problem as a mathematical program with complementarity constraints. However, this paper also investigates alternative formulations that highlight the problem’s complexity and suggest ways to solve the problem efficiently.     

A cost and expected consequence approach to planning and managing railroad transportation of hazardous materials

Although hazardous materials (hazmat) account for around 140 million tons of all railroad freight traffic in the US, it has not received much attention from academic researchers. This is surprising especially when one considers the volume of hazmat moved by railroads in both North America and Europe. In this paper we develop a bi-objective optimization model, where cost is determined based on the characteristics of railroad industry and the determination of transport risk incorporates the dynamics of railroad accident. The optimization model and the solution framework is used to solve a realistic-size problem instance based in south-east US, which is then analyzed to gain managerial insights. In addition, a risk-cost frontier depicting non-dominated solutions is developed, followed by conclusion.     

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.     

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.     

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 reliability‐based optimal toll design

Optimal toll design from a network reliability point of view is addressed in this paper. Improving network reliability is proposed as a policy objective of road pricing. A reliability‐based optimal toll design model, where on the upper level network performance including travel time reliability is optimized, while on the lower level a dynamic user‐equilibrium is achieved, is presented. Road authorities aim to optimize network travel time reliability by setting tolls in a network design problem. Travelers are influenced by these tolls and make route and trip decisions by considering travel times and tolls. Network performance reliability is analyzed for a degradable network with elastic and fluctuated travel demand, which integrates reliability and uncertainty, dynamic network equilibrium models, and Monte Carlo methods. The proposed model is applied to a small hypothesized network for which optimal tolls are derived. The network travel time reliability is indeed improved after implementing optimal tolling system. Trips may have a somewhat higher, but more reliable, travel time.     

Network sensor health problem

Many existing studies on the sensor health problem determine an individual sensor’s health status based on the statistical characteristics of collected data by the sensor. In this research, we study the sensor health problem at the network level, which is referred to as the network sensor health problem. First, based on the conservation principle of daily flows in a network, we separate all links into base links and non-base links, such that the flows on the latter can be calculated from those on the former. In reality, the network flow conservation principle can be violated due to the existence of unhealthy sensors. Then we define the least inconsistent base set of links as those that minimize the sum of squares of the differences between observed and calculated flows on non-base links. But such least inconsistent base sets may not be unique in a general road network. Finally we define the health index of an individual sensor as the frequency that it appears in all of the least inconsistent base sets. Intuitively, a lower health index suggests that the corresponding sensor is more likely to be unhealthy. We present the brute force method to find all least inconsistent base sets and calculate the health indices. We also propose a greedy search algorithm to calculate the approximate health indices more efficiently. We solve the network sensor health problem for a real-world example with 16 nodes and 30 links, among which 18 links are monitored with loop detectors. Using daily traffic count data from the Caltrans Performance Measurement System (PeMS) database, we use both the brute-force and greedy search methods to calculate the health indices for all the sensors. We find that all the four sensors flagged as unhealthy (high value) by PeMS have the lowest health indices. This confirms that a sensor with a lower health index is more likely to be unhealthy. Therefore, we can use such health indices to determine the relative reliability of different sensors’ data and prioritize the maintenance of sensors.     

A Value-at-Risk (VAR) approach to routing rail hazmat shipments

Hazardous materials (hazmat) accidents are rare though the consequences could be disastrous. Given the possibility of low probability – high consequence event, a risk-averse routing hazmat shipment is necessary. We propose a value-at-risk (VaR) approach to route rail hazmat shipments, using the best train configuration, over a given railroad network with limited number of train services such that the transport risk as measured by VaR is minimized. Freight train derailment reports of the Federal Railroad Administration were analyzed to develop expressions that would incorporate characteristics of railroad accidents, and then to estimate the different inputs. The proposed methodology was used to study several problem instances generated using the realistic network of a railroad operator, and to demonstrate that it is possible to develop different routes for shipments depending on the risk preference of the decision maker.     

Congestion pricing under operational,supply-side uncertainty

This paper is concerned with finding first-best tolls in static transportation networks with day-to-day variation in network capacity, as accounted for by changes in the volume-delay function. The key question in addressing this problem is that of information, namely, which agents have access to what information when making decisions. In this work, travelers are assumed to be either fully informed about network conditions before embarking on travel, or having no information except the probability distributions; likewise, the network manager (toll-setter) is either able to vary tolls in response to realized network conditions, or must apply the same tolls every day. Further, travelers’ preference for reliable travel is accounted for, representing risk aversion in the face of uncertainty. For each of the scenarios implied by combinations of these assumptions, we present methods to determine system-optimal link prices. A demonstration is provided, using the Sioux Falls test network, suggesting that attempts to incorporate uncertainty into nonresponsive tolls involve significantly higher prices.     

Global convergence of the trial-and-error method for the traffic-restraint congestion-pricing scheme with day-to-day flow dynamics

The traffic-restraint congestion-pricing scheme (TRCPS) aims to maintain traffic flow within a desirable threshold for some target links by levying the appropriate link tolls. In this study, we propose a trial-and-error method using observed link flows to implement the TRCPS with the day-to-day flow dynamics. Without resorting to the origin–destination (O–D) demand functions, link travel time functions and value of time (VOT), the proposed trial-and-error method works as follows: tolls for the traffic-restraint links are first implemented each time (trial) and they are subsequently updated using observed link flows in a disequilibrium state at any arbitrary time interval. The trial-and-error method has the practical significance because it is necessary only to observe traffic flows on those tolled links and it does not require to wait for the network flow pattern achieving the user equilibrium (UE) state. The global convergence of the trial-and-error method is rigorously demonstrated under mild conditions. We theoretically show the viability of the proposed trial-and-error method, and numerical experiments are conducted to evaluate its performance. The result of this study, without doubt, enhances the confidence of practitioners to adopt this method.     

Recursive expected conditional value at risk in the fleet renewal problem with alternative fuel vehicles

We study the fleet portfolio management problem faced by a firm deciding which alternative fuel vehicles (AFVs) to choose for its fleet to minimise the weighted average of cost and risk, in a stochastic multi-period setting. We consider different types of technology and vehicles with heterogeneous capabilities. We propose a new time consistent recursive risk measure, the Recursive Expected Conditional Value at Risk (RECVaR), which we prove to be coherent. We then solve the problem for a large UK based company, reporting how the optimal policies are affected by risk aversion and by the clustering for each type of vehicle.     

Minimal-revenue congestion pricing Part II: An efficient algorithm for the general case

The second of a two-part series, this paper derives an efficient solution to the minimal-revenue tolls problem. As introduced in Part I, this problem can be defined as follows: Assuming each trip uses only a path whose generalized cost is smallest, find a set of arc tolls that simultaneously minimizes both average travel time and out-of-pocket cost. As a point of departure, this paper first re-solves the single-origin problem of Part I, modeling it as a linear program. Then with a change of variable, it transforms the LP's dual into a simple longest-path problem on an acyclic network. The multiple-origin problem – where one toll for each arc applies to all origins – solves analogously. In this case, however, the dual becomes an elementary linear multi-commodity max-cost flow problem with an easy bundling constraint and infinite arc capacities. After a minor reformulation that simplifies the model's input to better accommodate output from common traffic assignment software, a solution algorithm is exemplified with a numerical example.     

Storage space allocation in container terminals

Container terminals are essential intermodal interfaces in the global transportation network. Efficient container handling at terminals is important in reducing transportation costs and keeping shipping schedules. In this paper, we study the storage space allocation problem in the storage yards of terminals. This problem is related to all the resources in terminal operations, including quay cranes, yard cranes, storage space, and internal trucks. We solve the problem using a rolling-horizon approach. For each planning horizon, the problem is decomposed into two levels and each level is formulated as a mathematical programming model. At the first level, the total number of containers to be placed in each storage block in each time period of the planning horizon is set to balance two types of workloads among blocks. The second level determines the number of containers associated with each vessel that constitutes the total number of containers in each block in each period, in order to minimize the total distance to transport the containers between their storage blocks and the vessel berthing locations. Numerical runs show that with short computation time the method significantly reduces the workload imbalance in the yard, avoiding possible bottlenecks in terminal operations.     

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

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

Integrating congestion pricing and transit investment planning

This paper develops a mathematical model and solution procedure to identify an optimal zonal pricing scheme for automobile traffic to incentivize the expanded use of transit as a mechanism to stem congestion and the social costs that arise from that congestion. The optimization model assumes that there is a homogenous collection of users whose behavior can be described as utility maximizers and for which their utility function is driven by monetary costs. These monetary costs are assumed to be the tolls in place, the per mile cost to drive, and the value of their time. We assume that there is a system owner who sets the toll prices, collects the proceeds from the tolls, and invests those funds in transit system improvements in the form of headway reductions. This yields a bi-level optimization model which we solve using an iterative procedure that is an integration of a genetic algorithm and the Frank–Wolfe method. The method and solution procedure is applied to an illustrative example.     

Design of income-equitable toll prices for high occupancy toll lanes in a single toll facility

Income inequity potentially exists under high occupancy toll (HOT) lanes whereby higher-income travelers may reap the benefits of the facility. An income-based multi-toll pricing approach is proposed for a single HOT lane facility in a network to maximize simultaneously the toll revenue and address the income equity concern, while ensuring a minimum level-of-service on the HOT lanes and that the toll prices do not exceed pre-specified thresholds. The problem is modeled as a bi-level optimization formulation. The upper level model maximizes revenue for the tolling authority subject to pre-specified upper bounds on tolls. The lower level model solves the stochastic user equilibrium problem. An agent-based solution approach is used to determine the toll prices by considering the tolling authority and commuters as agents. Results from numerical experiments indicate that a multi-toll pricing scheme is more equitable and can yield higher revenues compared to a single toll price scheme across travelers.     

Spatial decision support system for hazardous material truck routing

Shipping hazardous material (hazmat) places the public at risk. People who live or work near roads commonly traveled by hazmat trucks endure the greatest risk. Careful selection of roads used for a hazmat shipment can reduce the population at risk. On the other hand, a least time route will often consist of urban interstate, thus placing many people in harms way. Route selection is therefore the process of resolving the conflict between population at risk and efficiency considerations. To assist in resolving this conflict, a working spatial decision support system (SDSS) called Hazmat Path is developed. The proposed hazmat routing SDSS overcomes three significant challenges, namely handling a realistic network, offering sophisticated route generating heuristics and functioning on a desktop personal computer. The paper discusses creative approaches to data manipulation, data and solution visualization, user interfaces, and optimization heuristics implemented in Hazmat Path to meet these challenges.     

Tolling traffic links under stochastic assignment: Modelling the relationship between the number and price level of tolled links and optimal traffic flows

The classical road-tolling problem is to toll network links such that under the principles of Wardropian User Equilibrium Assignment a System Optimising (SO) flow pattern is obtained. Stochastic assignment methods are accepted to be more realistic than deterministic and it is of interest to examine the potential for optimal tolling in the case of Stochastic User Equilibrium (SUE). In examining the case of Stochastic User Equilibrium the ‘desired flow pattern’ to be created must first be determined. The classical economics solution of replacing unit-cost flow functions with marginal-cost flow functions which under deterministic assignment produces the System Optimal solution (where Total Network Travel Cost (TNTC) is minimised) does not generally result in TNTC being minimised in the Stochastic Case. Instead such tolls produce a ‘Stochastic System Optimal’ (SSO) solution where the Total Perceived Network Travel Cost (TPNTC) is minimised.This paper examines and compares link-based tolling solutions to achieve both the SSO (TPNTC minimised) and true SO (TNTC minimised) under SUE and illustrates the concept with numerical examples. Such link-based tolling schemes produce network benefit by re-routing rather than traffic suppression as opposed to the cordon-based charging schemes which have been implemented in practice. Equity issues relating to charging schemes are discussed and the desirability of zero-toll routes is highlighted associated with greater potential political acceptability of charging schemes that do not impose excessive charges upon users (such as minimal or low revenue tolls). A heuristic is developed to toll network links in such a way as to balance the number of links tolled against the revenue required to produce a desired reduction in TNTC such that optimal network flow patterns are approached.