A computational model for the probit‐based dynamic stochastic user optimal traffic assignment problem

This paper focuses on computational model development for the probit‐based dynamic stochastic user optimal (P‐DSUO) traffic assignment problem. We first examine a general fixed‐point formulation for the P‐DSUO traffic assignment problem, and subsequently propose a computational model that can find an approximated solution of the interest problem. The computational model includes four components: a strategy to determine a set of the prevailing routes between each origin–destination pair, a method to estimate the covariance of perceived travel time for any two prevailing routes, a cell transmission model‐based traffic performance model to calculate the actual route travel time used by the probit‐based dynamic stochastic network loading procedure, and an iterative solution algorithm solving the customized fixed‐point model. The Ishikawa algorithm is proposed to solve the computational model. A comparison study is carried out to investigate the efficiency and accuracy of the proposed algorithm with the method of successive averages. Two numerical examples are used to assess the computational model and the algorithm proposed. Results show that Ishikawa algorithm has better accuracy for smaller network despite requiring longer computational time. Nevertheless, it could not converge for larger network. Copyright © 2010 John Wiley & Sons, Ltd.     

Conflict‐free time‐based trajectory planning for aircraft taxi automation with refined taxiway modeling

To mitigate airport congestion caused by increasing air traffic demand, the trajectory‐based surface operations concept has been proposed to improve surface movement efficiency while maintaining safety. It utilizes decision support tools to provide optimized time‐based trajectories for each aircraft and uses automation systems to guide surface movements and monitor their conformance with assigned trajectories. Whether the time‐based trajectories can be effectively followed so that the expected benefits can be guaranteed depends firstly on whether these trajectories are realistic. So, this paper first deals with the modeling biases of the network model typically used for taxi trajectory planning via refined taxiway modeling. Then it presents a zone control‐based dynamic routing and timing algorithm upon the refined taxiway model to find the shortest time taxi route and timings for an aircraft. Finally, the presented algorithm is integrated with a sequential planning framework to continuously decide taxi routes and timings. Experimental results demonstrate that the solution time for an aircraft can be steadily around a few milliseconds with timely cleaning of expired time windows, showing potential for real‐time decision support applications. The results also show the advantages of the proposed methodology over existing approaches. Copyright © 2015 John Wiley & Sons, Ltd.     

A bi‐level programming approach — Optimal transit fare under line capacity constraints

The fare of a transit line is one of the important decision variables for transit network design. It has been advocated as an efficient means of coordinating the transit passenger flows and of alleviating congestion in the transit network. This paper shows how transit fare can be optimized so as to balance the passenger flow on the transit network and to reduce the overload delays of passengers at transit stops. A bi‐level programming method is developed to optimize the transit fare under line capacity constraints. The upper‐level problem seeks to minimize the total network travel time, while the lower‐level problem is a stochastic user equilibrium transit assignment model with line capacity constraints. A heuristic solution algorithm based on sensitivity analysis is proposed. Numerical example is used to illustrate the application of the proposed model and solution algorithm.     

Strategic evacuation planning with pedestrian guidance and bus routing: a mixed integer programming model and heuristic solution

This paper presents a mathematical model to plan emergencies in a densely populated urban zone where a certain numbers of pedestrians depend on transit for evacuation. The proposed model features an integrated operational framework, which simultaneously guides evacuees through urban streets and crosswalks (referred to as “the pedestrian network”) to designated pickup points (e.g., bus stops), and routes a fleet of buses at different depots to those pick‐up points and transports evacuees to their destinations or safe places. In this level, the buses are routed through the so‐called “vehicular network.” An integrated mixed integer linear program that can effectively take into account the interactions between the aforementioned two networks is formulated to find the maximal evacuation efficiency in two networks. Because the large instances of the proposed model are mathematically difficult to solve to optimality, a two‐stage heuristic is developed to solve larger instances of the model. Results from hundreds of numerical examples analysis indicate that proposed heuristic works well in providing (near) optimal or feasibly good solutions for medium‐scale to large‐scale instances that may arise in real transit‐based evacuation situations in a much shorter amount of computational time compared with cplex (can find optimal/feasible solutions for only five instances within 3 hours of running). Copyright © 2016 John Wiley & Sons, Ltd.     

Pick‐up locations and bus allocation for transit‐based evacuation planning with demand uncertainty

This paper develops a decision‐support model for transit‐based evacuation planning under demand uncertainty. Demand uncertainty refers to the uncertainty associated with the number of transit‐dependent evacuees. A robust optimization model is proposed to determine the optimal pick‐up points for evacuees to assemble, and allocate available buses to transport the assembled evacuees between the pick‐up locations and different public shelters. The model is formulated as a mixed‐integer linear program and is solved via a cutting plane scheme. The numerical example based on the Sioux Falls network demonstrates that the robust plan yields lower total evacuation time and is reliable in serving the realized evacuee demand. Copyright © 2012 John Wiley & Sons, Ltd.     

Optimal control strategies with an extended cell transmission model for massive vehicular‐pedestrian mixed flows in the evacuation zone

This paper presents an integrated model to design routing and signal plans for massive mixed pedestrian‐vehicle flows within the evacuation zone. The proposed model, with its embedded formulations for pedestrians and vehicles in the same evacuation network, can effectively take their potential conflicts into account and generate the optimal routing strategies to guide evacuees toward either the pickup locations or their parking areas during an evacuation. The proposed model, enhancing the cell transmission model with the notion of sub‐cells, mainly captures the complex movements in the vehicle‐pedestrian flows and can concurrently optimizes both the signals for pedestrian‐vehicle flows and the movement paths for evacuees. An illustrating example concerning the evacuation around the M&T Bank Stadium area has been used to demonstrate the application potential of the proposed model. Copyright © 2013 John Wiley & Sons, Ltd.     

Network equilibrium for congested multi‐mode networks with elastic demand

This paper proposes an elastic demand network equilibrium model for networks with transit and walking modes. In Hong Kong, the multi‐mode transit system services over 90% of the total journeys and the demand on it is continuously increasing. Transit and walking modes are related to each other as transit passengers have to walk to and from transit stops. In this paper, the multi‐mode elastic‐demand network equilibrium problem is formulated as a variational inequality problem where the combined mode and route choices are modeled in a hierarchical logit structures and the total travel demand for each origin‐destination pair is explicitly given by an elastic demand function. In addition, the capacity constraint for transit vehicles and the effects of bi‐directional flows on walkways are considered in the proposed model. All these congestion effects are taken into account for modeling the travel choices. A solution algorithm is developed to solve the multi‐mode elastic‐demand network equilibrium model. It is based on a Block Gauss‐Seidel decomposition approach coupled with the method of successive averages. A numerical example is used to illustrate the application of the proposed model and solution algorithm.     

Validation of a schedule‐based capacity restraint transit assignment model for a large‐scale network

This paper describes the application of a capacity restraint trip assignment algorithm to a real, large‐scale transit network and the validation of the results. Unlike the conventional frequency‐based approach, the network formulation of the proposed model is dynamic and schedule‐based. Transit vehicles are assumed to operate to a set of pre‐determined schedules. Passengers are assumed to select paths based on a generalized cost function including in‐vehicle and out‐of‐vehicle time and line change penalty. The time‐varying passenger demand is loaded onto the network by a time increment simulation method, which ensures that the capacity restraint of each vehicle during passenger boarding is strictly observed. The optimal‐path and path‐loading algorithms are applied iteratively by the method of successive averages until the network converges to the predictive dynamic user equilibrium. The Hong Kong Mass Transit Railway network is used to validate the model results. The potential applications of the model are also discussed.     

A multi‐class mean‐excess traffic equilibrium model with elastic demand

Recent empirical studies have revealed that travel time variability plays an important role in travelers' route choice decisions. To simultaneously account for both reliability and unreliability aspects of travel time variability, the concept of mean‐excess travel time (METT) was recently proposed as a new risk‐averse route choice criterion. In this paper, we extend the mean‐excess traffic equilibrium model to include heterogeneous risk‐aversion attitudes and elastic demand. Specifically, this model explicitly considers (1) multiple user classes with different risk‐aversions toward travel time variability when making route choice decisions under uncertainty and (2) the elasticity of travel demand as a function of METT when making travel choice decisions under uncertainty. This model is thus capable of modeling travelers' heterogeneous risk‐averse behaviors with both travel choice and route choice considerations. The proposed model is formulated as a variational inequality problem and solved via a route‐based algorithm using the modified alternating direction method. Numerical analyses are also provided to illustrate the features of the proposed model and the applicability of the solution algorithm. Copyright © 2012 John Wiley & Sons, Ltd.     

Online calibration of an integrated framework for information‐based evacuation operations

This study seeks to online calibrate the parameters of aggregate evacuee behavior models used in a behavior‐consistent information‐based control module for determining information strategies for real‐time evacuation operations. It enables the deployment of an operational framework for mass evacuation that integrates three aspects underlying an evacuation operation: demand (evacuee behavior), supply (network management), and disaster characteristics. To attain behavior‐consistency, the control module factors evacuees' likely responses to the disseminated information in determining information‐based control strategies. Hence, the ability of the behavior models to predict evacuees' likely responses is critical to the effectiveness of traffic routing by information strategies. The mixed logit structure is used for the aggregate behavior models to accommodate the behavioral heterogeneity across the population. An online calibration problem is proposed to calibrate the random parameters in the behavior models by using the least square estimator to minimize the gap between the predicted network flows and unfolding traffic dynamics. Background traffic, an important but rarely studied issue for modeling evacuation traffic, is also accounted for in the proposed problem. Numerical experiments are conducted to illustrate the importance of the calibration problem for addressing the system consistency issues and integrating the demand, supply, and disaster characteristics for more efficient evacuation operations. Copyright © 2016 John Wiley & Sons, Ltd.     

Optimization of bus routing strategies for evacuation

Efficient transportation of evacuees during an emergency has long been recognized as a challenging issue. This paper investigates emergency evacuation strategies that rely on public transit, where buses run continuously, rather than fixed route, based upon the spatial and temporal information of evacuee needs. We formulated an optimal bus operating strategy that minimizes the exposed casualty time rather than operational cost, as a deterministic mixed‐integer program, and investigated the solution algorithm. A Lagrangian‐relaxation‐based solution algorithm was developed for the proposed model. Numerical experiments with different problem sizes were conducted to evaluate the method. Copyright © 2013 John Wiley & Sons, Ltd.     

Truck capacity analysis in a cross‐dock transportation network considering direct shipment

In a transportation network, decision making parameters may change and may cause the optimum value of objective function to vary in a specific range. Therefore, managers try to identify the effects of these changes by sensitive analysis to find appropriate solutions. In this paper, first, a model for cross‐dock transportation network considering direct shipment is presented, and then an algorithm based on branch and bound algorithm and dual price concept for sensitive analysis is developed. When managers encounter problems such as budget limit, they may decide to change the capacity of trucks as a procedure to reduce the transportation costs of the network. The algorithm provides a useful lower bound on the solutions of the problems and makes it easy for the managers to eliminate inappropriate options of truck capacities, which cannot lead to cost reduction. To verify the algorithm, an example will be given at the end of the paper. Copyright © 2013 John Wiley & Sons, Ltd.     

Evacuation Modelling in the United States: Does the Demand Model Choice Matter?

Abstract

This paper reviews the literature on the evacuation demand problem, with an emphasis on the impact of various modelling approaches on network‐wide evacuation performance measures. First, a number of important factors that affect evacuee behaviour are summarized. Evacuation software packages and tools are also investigated in terms of the demand generation model they use. The most widely used models are then selected for performing sensitivity analysis. Next, a cell‐transmission‐based system optimal dynamic traffic assignment (SO‐DTA) model is employed to assess the effects of the demand model choice on the clearance time and average travel time. It is concluded that evacuation demand models should be selected with care, and policy makers should make sure the selected demand curve can replicate real‐life conditions with relatively high fidelity for the study region to be able to develop reliable and realistic evacuation plans.     

A network‐based dynamic air traffic flow model for short‐term en route traffic prediction

This paper presents a dynamic network‐based approach for short‐term air traffic flow prediction in en route airspace. A dynamic network characterizing both the topological structure of airspace and the dynamics of air traffic flow is developed, based on which the continuity equation in fluid mechanics is adopted to describe the continuous behaviour of the en route traffic. Building on the network‐based continuity equation, the space division concept in cell transmission model is introduced to discretize the proposed model both in space and time. The model parameters are sequentially updated based on the statistical properties of the recent radar data and the new predicting results. The proposed method is applied to a real data set from Shanghai Area Control Center for the short‐term air traffic flow prediction both at flight path and en route sector level. The analysis of the case study shows that the developed method can characterize well the dynamics of the en route traffic flow, thereby providing satisfactory prediction results with appropriate uncertainty limits. The mean relative prediction errors are less than 0.10 and 0.14, and the absolute errors fall in the range of 0 to 1 and 0 to 3 in more than 95% time intervals respectively, for the flight path and en route sector level. Copyright © 2017 John Wiley & Sons, Ltd.     

Evaluating airlines with slack‐based measures and meta‐frontiers

This study develops a new performance evaluation model, called the meta dynamic network slack‐based measure (MDN‐SBM). This model incorporates the concept of meta‐frontiers to facilitate comparisons of performance of decision making units, while at the same time it generalizes the slack‐based measure (SBM), network SBM, and dynamic SBM. This MDN‐SBM model is capable of dealing with two important special features of the transportation industry: unfavorable accidents and non‐storable goods, i.e. available seat‐kilometers that are wasting assets that lose value completely if unsold before departure. Hence, this generalized model contains higher differentiable capability than all its SBM‐related submodels in the literature. To demonstrate, 35 international airlines with two divisions (production and consumption) in three terms (one‐year time periods from 2007 to 2009) have been analyzed using meta‐performance efficiency measures (ME) for all decision making units and have also been compared by geographical area (Asia‐Pacific, N. America/Europe). The numerical example and comparison validate the proposed MDN‐SBM model and suggest the airlines should put more focus on input resources reduction for productivity improvement. Copyright © 2016 John Wiley & Sons, Ltd.     

Model and a solution algorithm for the dynamic resource allocation problem for large-scale transportation network evacuation

Allocating movable resources dynamically enables evacuation management agencies to improve evacuation system performance in both the spatial and temporal dimensions. This study proposes a mixed integer linear program (MILP) model to address the dynamic resource allocation problem for transportation evacuation planning on large-scale networks. The proposed model is built on the earliest arrival flow formulation that significantly reduces problem size. A set of binary variables, specifically, the beginning and the ending time of resource allocation at a location, enable a strong formulation with tight constraints. A solution algorithm is developed to solve for an optimal solution on large-scale network applications by adopting Benders decomposition. In this algorithm, the MILP model is decomposed into two sub-problems. The first sub-problem, called the restricted master problem, identifies a feasible dynamic resource allocation plan. The second sub-problem, called the auxiliary problem, models dynamic traffic assignment in the evacuation network given a resource allocation plan. A numerical study is performed on the Dallas–Fort Worth network. The results show that the Benders decomposition algorithm can solve an optimal solution efficiently on a large-scale network.     

Solving train formation problem using simulated annealing algorithm in a simplex framework

The train formation plan (TFP) determines the train services and their frequencies and assigns the demands. The TFP models are often formulated as a capacitated service network design problem, and the optimal solution is normally difficult to find. In this paper, a hybrid algorithm of the Simplex method and simulated annealing is proposed for the TFP problem. The basic idea of the proposed algorithm is to use a simulated annealing algorithm to explore the solution space, where the revised Simplex method evaluates, selects, and implements the moves. In the proposed algorithm, the neighborhood structure is based on the pivoting rules of the Simplex method that provides an efficient method to reach the neighbors of the current solution. A state‐of‐the‐art method is applied for parameters tuning by using the design of experiments approach. To evaluate the proposed model and the solution method, 25 test problems have been simulated and solved. The results show the efficiency and the effectiveness of the proposed approach. The proposed approach is implemented to develop the TFP in the Iranian railway as a case study. It is possible to save significant time and cost through solving the TFP problem by using the proposed algorithm and developing the efficient TFP plan in the railway networks. Copyright © 2012 John Wiley & Sons, Ltd.     

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.     

An augmented Lagrangian origin‐based algorithm for link‐capacitated traffic assignment problem

The origin‐based algorithm is embedded into the augmented Lagrangian method for the link‐capacitated traffic assignment problem. In order to solve the “nonexistence” problem due to the second partial derivatives of the augmented Lagrangian function at some specific points, the approximate expressions of the second partial derivatives are amended in the origin‐based algorithm. The graph of last common nodes is developed on the basis of the restricted single‐origin network. A method is proposed for finding n–1 last common nodes of the restricted single‐origin network, resulting in computational complexity of O(n²) in finding last common nodes. Numerical analysis on the Sioux Falls network and Chicago Sketch network demonstrated the effectiveness and characteristics of the proposed algorithm. Copyright © 2014 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.