Stochastic optimal path problem with relays

This paper studies the optimal path problem for travelers driving with vehicles of a limited range, such as most battery electric vehicles currently available in the market. The optimal path in this problem often consists of several relay points, where the vehicles can be refueled to extend its range. We propose a stochastic optimal path problem with relays (SOPPR), which aims at minimizing a general expected cost while maintaining a reasonable arrival probability. To account for uncertainty in the road network, the travel speed on a road segment is treated as a discrete random variable, which determines the total energy required to traverse the segment. SOPPR is formulated in two stages in this paper. In the first stage, an optimal routing problem is solved repeatedly to obtain the expected costs and arrival probabilities from any node to all refueling nodes and the destination. With this information, the second stage constructs an auxiliary network, on which the sequence of refueling decisions can be obtained by solving another optimal path problem. Label-correcting algorithms are developed to solve the routing problems in both stages. Numerical experiments are conducted to compare the stochastic and deterministic models, to examine the impact of different parameters on the routing results, and to evaluate the computational performance of the proposed algorithms.     

Adding a new station and a road link to a road–rail network in the presence of modal competition

In this paper we study the problem of locating a new station on an existing rail corridor and a new junction on an existing road network, and connecting them with a new road segment under a budget constraint. We consider three objective functions and the corresponding optimization problems, which are modeled by means of mixed integer non-linear programs. For small instances, the models can be solved directly by a standard solver. For large instances, an enumerative algorithm based on a discretization of the problem is proposed. Computational experiments show that the latter approach yields high quality solutions within short computing times.     

Network-oriented household activity pattern problem for system optimization

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

Cellpath: Fusion of cellular and traffic sensor data for route flow estimation via convex optimization

A new convex optimization framework is developed for the route flow estimation problem from the fusion of vehicle count and cellular network data. The issue of highly underdetermined link flow based methods in transportation networks is investigated, then solved using the proposed concept of cellpaths for cellular network data. With this data-driven approach, our proposed approach is versatile: it is compatible with other data sources, and it is model agnostic and thus compatible with user equilibrium, system-optimum, Stackelberg concepts, and other models. Using a dimensionality reduction scheme, we design a projected gradient algorithm suitable for the proposed route flow estimation problem. The algorithm solves a block isotonic regression problem in the projection step in linear time. The accuracy, computational efficiency, and versatility of the proposed approach are validated on the I-210 corridor near Los Angeles, where we achieve 90% route flow accuracy with 1033 traffic sensors and 1000 cellular towers covering a large network of highways and arterials with more than 20,000 links. In contrast to long-term land use planning applications, we demonstrate the first system to our knowledge that can produce route-level flow estimates suitable for short time horizon prediction and control applications in traffic management. Our system is open source and available for validation and extension.     

Mapping evacuation risk on transportation networks using a spatial optimization model

The focus of this paper is on the development of a methodology to identify network and demographic characteristics on real transportation networks which may lead to significant problems in evacuation during some extreme event, like a wildfire or hazardous material spill. We present an optimization model, called the critical cluster model, that can be used to identify small areas or neighborhoods which have high ratios of population to exit capacity. Although this model in its simplest form is a nonlinear, constrained optimization problem, a special integer-linear programming equivalent can be formulated. Special contiguity constraints are needed to keep identified clusters spatially connected. We present details on how this model can be solved optimally as well as discuss computational experience for several example transportation networks. We describe how this model can be integrated within a GIS system to produce maps of evacuation risk or vulnerability. This model is now being utilized in several research projects, in Europe and the US.     

Continuous equilibrium network design models

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

Estimation of road traffic noise emissions: The influence of speed and acceleration

This paper relies on vehicle trajectory collection on a corridor, to compare different traffic representations used for the estimation of the sound power of light vehicles and the resulting sound pressure levels. Four noise emission models are tested. The error introduced when the emissions are calculated based on speeds measured at regular intervals along the road network are quantified and explained. The current noise emission models might in particular misestimate noise levels under congestion. This bias can be reduced by introducing additional traffic variables in the modeling. In addition, significant differences within the models are highlighted, especially concerning their accounting of vehicle accelerations. Models that rely on a binary representation of acceleration regimes (a vehicle or a road segment is accelerating or not) can lead to errors in practice. Models under use in Europe have a very low sensitivity to acceleration values. These results help underlying the further required improvements of dynamic road traffic noise models.     

Optimal offsets for traffic signal systems in urban networks

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

The vehicle platooning problem: Computational complexity and heuristics

We create a mathematical framework for modeling trucks traveling in road networks, and we define a routing problem called the platooning problem. We prove that this problem is NP-hard, even when the graph used to represent the road network is planar. We present integer linear programming formulations for instances of the platooning problem where deadlines are discarded, which we call the unlimited platooning problem. These allow us to calculate fuel-optimal solutions to the platooning problem for large-scale, real-world examples. The problems solved are orders of magnitude larger than problems previously solved exactly in the literature. We present several heuristics and compare their performance with the optimal solutions on the German Autobahn road network. The proposed heuristics find optimal or near-optimal solutions in most of the problem instances considered, especially when a final local search is applied. Assuming a fuel reduction factor of 10% from platooning, we find fuel savings from platooning of 1–2% for as few as 10 trucks in the road network; the percentage of savings increases with the number of trucks. If all trucks start at the same point, savings of up to 9% are obtained for only 200 trucks.     

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.     

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.     

Modeling residential location choice in relation to housing location and road tolls on congested urban highway networks

We present a reformulation of the residential location submodel of the Integrated Model of Residential and Employment Location as a network equilibrium problem, thereby making travel costs by auto endogenous. The location of housing supply is examined as a welfare maximization problem for both user-optimal and system-optimal travel costs using concepts of bilevel programming. Finally, we briefly discuss how the employment submodel can be reformulated, and the entire model solved as a variational inequality problem.     

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 multi-objective analysis of a rural road network problem in the hilly regions of Nepal

This paper considers the rural road network upgrading problem, using a multi-objective optimization model, to support decision-makers in the choice of roads to upgrade in the hilly regions of Nepal. The model considers two objectives: minimization of user operation costs and maximization of population covered. The problem was solved for a real-world rural road network in the Gorkha district of Nepal. For this case, all non-dominated solutions were obtained and the ones providing more interesting trade-offs were analysed. The model was found suitable for the case under study, and possibly, easily extendable to rural areas of other developing countries.     

A practical method to estimate the benefits of improved road network reliability: an application to departing air passengers

This paper develops and applies a practical method to estimate the benefits of improved reliability of road networks. We present a general methodology to estimate the scheduling costs due to travel time variability for car travel. In contrast to existing practical methods, we explicitly consider the effect of travel time variability on departure time choices. We focus on situations when only mean delays are known, which is typically the case when standard transport models are used. We first show how travel time variability can be predicted from mean delays. We then estimate the scheduling costs of travellers, taking into account their optimal departure time choice given the estimated travel time variability. We illustrate the methodology for air passengers traveling by car to Amsterdam Schiphol Airport. We find that on average planned improvements in network reliability only lead to a small reduction in access costs per trip in absolute terms, mainly because most air passengers drive to the airport outside peak hours, when travel time variability tends to be low. However, in relative terms the reduction in access costs due to the improvements in network reliability is substantial. In our case we find that for every 1 Euro reduction in travel time costs, there is an additional cost reduction of 0.7 Euro due to lower travel time variability, and hence lower scheduling costs. Ignoring the benefits from improved reliability may therefore lead to a severe underestimation of the total benefits of infrastructure improvements.     

The transit network design problem with elastic demand and internalisation of external costs: An application to rail frequency optimisation

In this paper we examine the transit network design problem under the assumption of elastic demand, focusing on the problem of designing the frequencies of a regional metro. In this problem, investments in transit services have appreciable effects on modal split. Neglecting demand elasticity can lead to solutions that may not represent the actual objectives of the design. We propose four different objective functions that can be adopted to assume demand as elastic, considering the costs of all transportation systems (car, bus and rail) as well as the external costs, and we define the constraints of the problem. Heuristic and meta-heuristic solution algorithms are also proposed. The models and algorithms are tested on a small network and on a real-scale network.     

Deploying public charging stations for electric vehicles on urban road networks

This paper explores how to optimally locate public charging stations for electric vehicles on a road network, considering drivers’ spontaneous adjustments and interactions of travel and recharging decisions. The proposed approach captures the interdependency of different trips conducted by the same driver by examining the complete tour of the driver. Given the limited driving range and recharging needs of battery electric vehicles, drivers of electric vehicles are assumed to simultaneously determine tour paths and recharging plans to minimize their travel and recharging time while guaranteeing not running out of charge before completing their tours. Moreover, different initial states of charge of batteries and risk-taking attitudes of drivers toward the uncertainty of energy consumption are considered. The resulting multi-class network equilibrium flow pattern is described by a mathematical program, which is solved by an iterative procedure. Based on the proposed equilibrium framework, the charging station location problem is then formulated as a bi-level mathematical program and solved by a genetic-algorithm-based procedure. Numerical examples are presented to demonstrate the models and provide insights on public charging infrastructure deployment and behaviors of electric vehicles.     

A bi-criteria indicator to assess supply chain network performance for critical needs under capacity and demand disruptions

In this paper, we develop a supply chain/logistics network model for critical needs in the case of disruptions. The objective is to minimize the total network costs, which are generalized costs that may include the monetary, risk, time, and social costs. The model assumes that disruptions may have an impact on both the network link capacities as well as on the product demands. Two different cases of disruption scenarios are considered. In the first case, we assume that the impacts of the disruptions are mild and that the demands can be met. In the second case, the demands cannot all be satisfied. For these two cases, we propose two individual performance indicators. We then construct a bi-criteria indicator to assess the supply chain network performance for critical needs. An algorithm is described which is applied to solve a spectrum of numerical examples in order to illustrate the new concepts.     

Multiclass fuzzy user equilibrium with endogenous membership functions and risk‐taking behaviors

Over the last decades, several approaches have been proposed in the literature to incorporate users' perceptions of travel costs, their bounded rationality, and risk‐taking behaviors into network equilibrium modeling for traffic assignment problem. While theoretically advanced, these models often suffer from high complexity and computational cost and often involve parameters that are difficult to estimate. This study proposes an alternative approach where users' imprecise perceptions of travel times are endogenously constructed as fuzzy sets based on the probability distributions of random link travel times. Two decision rules are proposed accordingly to account for users' heterogeneous risk‐taking behaviors, that is, optimistic and pessimistic rules. The proposed approach, namely, the multiclass fuzzy user equilibrium, can be formulated as a link‐based variational inequality model. The model can be solved efficiently, and parameters involved can be either easily estimated or treated as factors for calibration against observed traffic flow data. Numerical examples show that the proposed model can be solved efficiently even for a large‐scale network of Mashhad, Iran, with 2538 links and 7157 origin–destination pairs. The example also illustrates the calibration capability of the proposed model, highlighting that the model is able to produce much more accurate flow estimates compared with the Wardropian user equilibrium model. Copyright © 2016 John Wiley & Sons, Ltd.     

International experience with speed limits during and prior to the energy crisis of 1973–4

This paper presents an artificial neural network (ANN) based method for estimating route travel times between individual locations in an urban traffic network. Fast and accurate estimation of route travel times is required by the vehicle routing and scheduling process involved in many fleet vehicle operation systems such as dial‐a‐ride paratransit, school bus, and private delivery services. The methodology developed in this paper assumes that route travel times are time‐dependent and stochastic and their means and standard deviations need to be estimated. Three feed‐forward neural networks are developed to model the travel time behaviour during different time periods of the day‐the AM peak, the PM peak, and the off‐peak. These models are subsequently trained and tested using data simulated on the road network for the City of Edmonton, Alberta. A comparison of the ANN model with a traditional distance‐based model and a shortest path algorithm is then presented. The practical implication of the ANN method is subsequently demonstrated within a dial‐a‐ride paratransit vehicle routing and scheduling problem. The computational results show that the ANN‐based route travel time estimation model is appropriate, with respect to accuracy and speed, for use in real applications.