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.     

Unified closed-form expression of logit and weibit and its extension to a transportation network equilibrium assignment

This study proposes a generalized multinomial logit model that allows heteroscedastic variance and flexible utility function shape. The novelty of our approach is that the model is theoretically derived by applying a generalized extreme-value distribution to the random component of utility, while retaining its closed-form expression. In addition, the weibit model, in which the random utility is assumed to follow the Weibull distribution, is a special case of the proposed model. This is achieved by utilizing the q-generalization method developed in Tsallis statistics. Then, our generalized logit model is incorporated into a transportation network equilibrium model. The network equilibrium model with a generalized logit route choice is formulated as an optimization problem for uncongested networks. The objective function includes Tsallis entropy, a type of generalized entropy. The generalization of the Gumbel and Weibull distributions, logit and weibit models, and network equilibrium model are formulated within a unified framework with q-generalization or Tsallis statistics.     

Calibrating aggregate travel demand models with traffic counts: Estimators and statistical performance

Traffic counts on network links constitute an information source on travel demand which is easy to collect, cheap and repeatable. Many models proposed in recent years deal with the use of traffic counts to estimate Origin/Destination (O/D) trip matrices under different assumptions on the type of "a-priori" information available on the demand (surveys, outdated estimates, models, etc.) and the type of network and assignment mapping (see Cascetta & Nguyen 1988). Less attention has been paid to the possibility of using traffic counts to estimate the parameters of demand models. In this case most of the proposed methods are relative to particular demand model structures (e.g. gravity-type) and the statistical analysis of estimator performance is not thoroughly carried out. In this paper a general statistical framework defining Maximum Likelihood, Non Linear Generalized Least Squares (NGLS) and Bayes estimators of aggregated demand model parameters combining counts-based information with other sources (sample or a priori estimates) is proposed first, thus extending and generalizing previous work by the authors (Cascetta & Russo 1992). Subsequently a solution algorithm of the projected-gradient type is proposed for the NGLS estimator given its convenient theoretical and computational properties. The algorithm is based on a combination of analytical/numerical derivates in order to make the estimator applicable to general demand models. Statistical performances of the proposed estimators are evaluated on a small test network through a Monte Carlo method by repeatedly sampling "starting estimates" of the (known) parameters of a generation/distribution/modal split/assignment system of models. Tests were carried out assuming different levels of "quality" of starting estimates and numbers of available counts. Finally NGLS estimator was applied to the calibration of the described model system on the network of a real medium-size Italian town using real counts with very satisfactory results in terms of both parameter values and counted flows reproduction.     

Transit network design with allocation of green vehicles: A genetic algorithm approach

The use of fossil fuels in transportation generates harmful emissions that accounts for nearly half of the total pollutants in urban areas. Dealing with this issue, local authorities are dedicating specific efforts to seize the opportunity offered by new fuels and technological innovations in achieving a cleaner urban mobility. In fact, authorities are improving environmental performances of their public transport fleet by procuring cleaner vehicles, usually called low and zero emission vehicles (LEV and ZEV, respectively). Nevertheless there seems to be a lack of methodologies for supporting stakeholders in decisions related to the introduction of green vehicles, whose allocation should be performed since the network design process in order to optimize their available green capacity.In this paper, the problem of clean vehicle allocation in an existing public fleet is faced by introducing a method for solving the transit network design problem in a multimodal, demand elastic urban context dealing with the impacts deriving from transportation emissions.The solving procedure consists of a set of heuristics which includes a routine for route generation and a genetic algorithm for finding a sub-optimal set of routes with the associated frequencies.     

Train design and routing optimization for evaluating criticality of freight railroad infrastructures

Freight transportation by railroads is an integral part of the U.S. economy. Identifying critical rail infrastructures can help stakeholders prioritize protection initiatives or add necessary redundancy to maximize rail network resiliency. The criticality of an infrastructure element, link or yard, is based on the increased cost (delay) incurred when that element is disrupted. An event of disruption can cause heavy congestion so that the capacity at links and yards should be considered when freight is re-routed. This paper proposes an optimization model for making-up and routing of trains in a disruptive situation to minimize the system-wide total cost, including classification time at yards and travel time along links. Train design optimization seeks to determine the optimal number of trains, their routes, and associated blocks, subject to various capacity and operational constraints at rail links and yards. An iterative heuristic algorithm is proposed to attack the computational burden for real-world networks. The solution algorithm considers the impact of volume on travel time in a congested or near-congested network. The proposed heuristics provide quality solutions with high speed, demonstrated by numerical experiments for small instances. A case study is conducted for the network of a major U.S. Class-I railroad based on publicly available data. The paper provides maps showing the criticality of infrastructure in the study area from the viewpoint of strategic planning.     

A pedestrian flow model considering the impact of local density: Voronoi diagram based heuristics approach

Local density, which is an indicator for comfortable moving of a pedestrian, is rarely considered in traditional force based and heuristics based pedestrian flow models. However, comfortable moving is surely a demand of pedestrian in normal situations. Recently, Voronoi diagram had been successfully adopted to obtain the local density of a pedestrian in empirical studies. In this paper, Voronoi diagram is introduced into the heuristics based pedestrian flow model. It provides not only local density but also other information for determining moving velocity and direction. Those information include personal space, safe distance, neighbors, and three elementary characteristics directions. Several typical scenarios are set up to verify the proposed model. The simulation results show that the velocity-density relations and capacities of bottleneck are consistent with the empirical data, and many self-organization phenomena, i.e., arching phenomenon and lane formation, are also reproduced. The pedestrians are likely to be homogeneously distributed when they are sensitive to local density, otherwise pedestrians are non-uniformly distributed and the stop-and-go waves are likely to be reproduced. Such results indicate that the Voronoi diagram is a promising tool in modeling pedestrian dynamics.     

Isolated intersection control for various levels of vehicle technology: Conventional,connected, and automated vehicles

Connected vehicle technology can be beneficial for traffic operations at intersections. The information provided by cars equipped with this technology can be used to design a more efficient signal control strategy. Moreover, it can be possible to control the trajectory of automated vehicles with a centralized controller. This paper builds on a previous signal control algorithm developed for connected vehicles in a simple, single intersection. It improves the previous work by (1) integrating three different stages of technology development; (2) developing a heuristics to switch the signal controls depending on the stage of technology; (3) increasing the computational efficiency with a branch and bound solution method; (4) incorporating trajectory design for automated vehicles; (5) using a Kalman filter to reduce the impact of measurement errors on the final solution. Three categories of vehicles are considered in this paper to represent different stages of this technology: conventional vehicles, connected but non-automated vehicles (connected vehicles), and automated vehicles. The proposed algorithm finds the optimal departure sequence to minimize the total delay based on position information. Within each departure sequence, the algorithm finds the optimal trajectory of automated vehicles that reduces total delay. The optimal departure sequence and trajectories are obtained by a branch and bound method, which shows the potential of generalizing this algorithm to a complex intersection.Simulations are conducted for different total flows, demand ratios and penetration rates of each technology stage (i.e. proportion of each category of vehicles). This algorithm is compared to an actuated signal control algorithm to evaluate its performance. The simulation results show an evident decrease in the total number of stops and delay when using the connected vehicle algorithm for the tested scenarios with information level of as low as 50%. Robustness of this algorithm to different input parameters and measurement noises are also evaluated. Results show that the algorithm is more sensitive to the arrival pattern in high flow scenarios. Results also show that the algorithm works well with the measurement noises. Finally, the results are used to develop a heuristic to switch between the different control algorithms, according to the total demand and penetration rate of each technology.     

A bi-level programming for bus lane network design

This paper proposes a bi-level programming model to solve the design problem for bus lane distribution in multi-modal transport networks. The upper level model aims at minimizing the average travel time of travelers, as well as minimizing the difference of passengers’ comfort among all the bus lines by optimizing bus frequencies. The lower level model is a multi-modal transport network equilibrium model for the joint modal split/traffic assignment problem. The column generation algorithm, the branch-and-bound algorithm and the method of successive averages are comprehensively applied in this paper for the solution of the bi-level model. A simple numerical test and an empirical test based on Dalian economic zone are employed to validate the proposed model. The results show that the bi-level model performs well with regard to the objective of reducing travel time costs for all travelers and balancing transit service level among all bus lines.     

A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem

This paper proposes a new heuristic algorithm for the Capacitated Location-Routing Problem (CLRP), called Granular Variable Tabu Neighborhood Search (GVTNS). This heuristic includes a Granular Tabu Search within a Variable Neighborhood Search algorithm. The proposed algorithm is experimentally compared on the benchmark instances from the literature with several of the most effective heuristics proposed for the solution of the CLRP, by taking into account the CPU time and the quality of the solutions obtained. The computational results show that GVTNS is able to obtain good average solutions in short CPU times, and to improve five best known solutions from the literature. The main contribution of this paper is to show a successful new heuristic for the CLRP, combining two known heuristic approaches to improve the global performance of the proposed algorithm for what concerns both the quality of the solutions and the computing times required to find them.     

On the variance of recurrent traffic flow for statistical traffic assignment

This paper generalizes and extends classical traffic assignment models to characterize the statistical features of Origin-Destination (O-D) demands, link/path flow and link/path costs, all of which vary from day to day. The generalized statistical traffic assignment (GESTA) model has a clear multi-level variance structure. Flow variance is analytically decomposed into three sources, O-D demands, route choices and measurement errors. Consequently, optimal decisions on roadway design, maintenance, operations and planning can be made using estimated probability distributions of link/path flow and system performance. The statistical equilibrium in GESTA is mathematically defined. Its multi-level statistical structure well fits large-scale data mining techniques. The embedded route choice model is consistent with the settings of O-D demands considering link costs that vary from day to day. We propose a Method of Successive Averages (MSA) based solution algorithm to solve for GESTA. Its convergence and computational complexity are analyzed. Three example networks including a large-scale network are solved to provide insights for decision making and to demonstrate computational efficiency.     

An integrated Bayesian approach for passenger flow assignment in metro networks

This paper proposes an integrated Bayesian statistical inference framework to characterize passenger flow assignment model in a complex metro network. In doing so, we combine network cost attribute estimation and passenger route choice modeling using Bayesian inference. We build the posterior density by taking the likelihood of observing passenger travel times provided by smart card data and our prior knowledge about the studied metro network. Given the high-dimensional nature of parameters in this framework, we apply the variable-at-a-time Metropolis sampling algorithm to estimate the mean and Bayesian confidence interval for each parameter in turn. As a numerical example, this integrated approach is applied on the metro network in Singapore. Our result shows that link travel time exhibits a considerable coefficient of variation about 0.17, suggesting that travel time reliability is of high importance to metro operation. The estimation of route choice parameters conforms with previous survey-based studies, showing that the disutility of transfer time is about twice of that of in-vehicle travel time in Singapore metro system.     

An AI-based approach for transit route system planning and design

We present an AI-based solution approach to the transit network design problem (TNDP). Past approaches fall into three categories: optimization formulations of idealized situations, heuristic approaches, or practical guidelines and ad hoc procedures reflecting the professional judgement and practical experience of transit planners. We discuss the sources of complexity of the TNDP as well as the shortcomings of the previous approaches. This discussion motivates the need for AI search techniques that implement the existing designer's knowledge and expertise to achieve better solutions efficiently. Then we propose a hybrid solution approach that incorporates the knowledge and expertise of transit network planners and implements efficient search techniques using AI tools, algorithmic procedures developed by others, and modules for tools implemented in conventional languages. The three major components of the solution approach are presented, namely, the lisp-implemented route generation design algorithm (RGA), the analysis procedure TRUST (Transit Route Analyst), and the route improvement algorithm (RIA). An example illustration is included.     

Designing an integrated distribution system for catering services for high-speed railways: A three-echelon location routing model with tight time windows and time deadlines

An emerging task in catering services for high-speed railways (CSHR) is to design a distribution system for the delivery of high-quality perishable food products to trains in need. This paper proposes a novel model for integrating location decision making with daily rail catering operations, which are affected by various aspects of rail planning, to meet time-sensitive passenger demands. A three-echelon location routing problem with time windows and time budget constraints (3E-LRPTWTBC) is thus proposed toward formulating this integrated distribution system design problem. This model attempts to determine the capacities/locations of distribution centers and to optimize the number of meals delivered to stations. The model also attempts to generate a schedule for refrigerated cars traveling from distribution centers to rail stations for train loading whereby meals can be catered to trains within tight time windows and sold before a specified time deadline. By relaxing the time-window constraints, a relaxation model that can be solved using an off-the-shelf mixed integer programming (MIP) solver is obtained to provide a lower bound on the 3E-LRPTWTBC. A hybrid cross entropy algorithm (HCEA) is proposed to solve the 3E-LRPTWTBC. A small-scale case study is implemented, which reveals a 9.3% gap between the solution obtained using the HCEA and that obtained using the relaxation model (RM). A comparative analysis of the HCEA and an exhaustive enumeration algorithm indicates that the HCEA shows good performance in terms of computation time. Finally, a case study considering 156 trains on the Beijing-Shanghai high-speed corridor and a large-scale case study considering 1130 trains on the Chinese railway network are addressed in a comprehensive study to demonstrate the applicability of the proposed models and algorithm.     

Optimization of grid bus transit systems with elastic demand

Current analytic models for optimizing urban bus transit systems tend to sacrifice geographic realism and detail in order to obtain their solutions. The models presented here shows how an optimization approach can be successful without oversimplifying spatial characteristics and demand patterns of urban areas and how a grid bus transit system in a heterogeneous urban environment with elastic demand is optimized. The demand distribution over the service region is discrete, which can realistically represent geographic variation. Optimal network characteristics (route and station spacings), operating headways and fare are found, which maximize the total operator profit and social welfare. Irregular service regions, many‐to‐many demand patterns, and vehicle capacity constraints are considered in a sequential optimization process. The numerical results show that at the optima the operator profit and social welfare functions are rather flat with respect to route spacing and headway, thus facilitating the tailoring of design variables to the actual street network and particular operating schedule without a substantial decrease in profit. The sensitivities of the design variables to some important exogenous factors are also presented.     

Analyzing the theoretical capacity of railway networks with a radial-backbone topology

In this work we propose a mechanism to optimize the capacity of the main corridor within a railway network with a radial-backbone or X-tree structure. The radial-backbone (or X-tree) structure is composed of two types of lines: the primary lines that travel exclusively on the common backbone (main corridor) and radial lines which, starting from the common backbone, branch out to individual locations. We define possible line configurations as binary strings and propose operators on them for their analysis, yielding an effective algorithm for generating an optimal design and train frequencies. We test our algorithm on real data for the high speed line Madrid–Seville. A frequency plan consistent with the optimal capacity is then proposed in order to eliminate the number of transfers between lines as well as to minimize the network fleet size, determining the minimum number of vehicles needed to serve all travel demand at maximum occupancy.     

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.     

Network impacts of a road capacity reduction: Empirical analysis and model predictions

In spite of their widespread use in policy design and evaluation, relatively little evidence has been reported on how well traffic equilibrium models predict real network impacts. Here we present what we believe to be the first paper that together analyses the explicit impacts on observed route choice of an actual network intervention and compares this with the before-and-after predictions of a network equilibrium model. The analysis is based on the findings of an empirical study of the travel time and route choice impacts of a road capacity reduction. Time-stamped, partial licence plates were recorded across a series of locations, over a period of days both with and without the capacity reduction, and the data were ‘matched’ between locations using special-purpose statistical methods. Hypothesis tests were used to identify statistically significant changes in travel times and route choice, between the periods of days with and without the capacity reduction. A traffic network equilibrium model was then independently applied to the same scenarios, and its predictions compared with the empirical findings. From a comparison of route choice patterns, a particularly influential spatial effect was revealed of the parameter specifying the relative values of distance and travel time assumed in the generalised cost equations. When this parameter was ‘fitted’ to the data without the capacity reduction, the network model broadly predicted the route choice impacts of the capacity reduction, but with other values it was seen to perform poorly. The paper concludes by discussing the wider practical and research implications of the study’s findings.     

An advanced solution for efficient logistics management at both company and network level

This paper proposes an advanced solution for efficient logistics management in urban areas based on a unified scheme able to address both static and dynamic decision making at a company and network level. The proposed solution generates the most efficient urban distribution plan utilizing an evolutionary metaheuristic approach and a backpressure framework that provide competitive scheduling and routing decisions. An empirical study based on real data is conducted assessing the performance of the proposed advanced solution and the reported results of the evaluation experiments demonstrate its generality and robustness.     

Simultaneous estimation of an origin–destination matrix and link choice proportions using traffic counts

A procedure for the simultaneous estimation of an origin–destination (OD) matrix and link choice proportions from OD survey data and traffic counts for congested network is proposed in this paper. Recognizing that link choice proportions in a network change with traffic conditions, and that the dispersion parameter of the route choice model should be updated for a current data set, this procedure performs statistical estimation and traffic assignment alternately until convergence in order to obtain the best estimators for both the OD matrix and link choice proportions, which are consistent with the survey data and traffic counts.Results from a numerical study using a hypothetical network have shown that a model allowing θ to be estimated simultaneously with an OD matrix from the observed data performs better than the model with a fixed predetermined θ. The application of the proposed model to the Tuen Mun Corridor network in Hong Kong is also presented in this paper. A reasonable estimate of the dispersion parameter θ for this network is obtained.     

Modeling stochastic perception error in the mean-excess traffic equilibrium model

In this paper, we extend the α-reliable mean-excess traffic equilibrium (METE) model of Chen and Zhou (Transportation Research Part B 44(4), 2010, 493-513) by explicitly modeling the stochastic perception errors within the travelers’ route choice decision processes. In the METE model, each traveler not only considers a travel time budget for ensuring on-time arrival at a confidence level α, but also accounts for the impact of encountering worse travel times in the (1 − α) quantile of the distribution tail. Furthermore, due to the imperfect knowledge of the travel time variability particularly in congested networks without advanced traveler information systems, the travelers’ route choice decisions are based on the perceived travel time distribution rather than the actual travel time distribution. In order to compute the perceived mean-excess travel time, an approximation method based on moment analysis is developed. It involves using the conditional moment generation function to derive the perceived link travel time, the Cornish-Fisher Asymptotic Expansion to estimate the perceived travel time budget, and the Acerbi and Tasche Approximation to estimate the perceived mean-excess travel time. The proposed stochastic mean-excess traffic equilibrium (SMETE) model is formulated as a variational inequality (VI) problem, and solved by a route-based solution algorithm with the use of the modified alternating direction method. Numerical examples are also provided to illustrate the application of the proposed SMETE model and solution method.