Transportation Science

This paper focuses on how to optimally route transfer cranes in a container yard during loading operations of export containers at port terminals. Decision variables are the number of containers that a transfer crane picks up at each yard-bay and the sequence of yard-bays that a transfer crane visits during a loading operation. This routing problem is formulated as a mixed integer program. The objective function of the formulation is to minimize the total container handling time of a transfer crane, which includes setup time at each yard-bay and travel time between yard-bays. Based on the mixed integer program, an optimizing algorithm is developed.

The problem of minimizing the time taken to load the containers from the container stack yard onto the ship is called the transtainer routing problem. We first do a theoretical investigation of the problem to understand the structural properties of the problem. We then use these results to prove that the problem is NP-Complete. The problem is then formulated as an integer program. A branch-and-bound based enumerative method is developed to obtain an exact solution to the problem. An algorithm to solve the matching problem on a line at the root node of the branch-and-bound tree is developed. Several lower bounds to prune the size of the tree are also developed. A result which states that there cannot exist a polynomial time heuristic with a bounded worst case unless P = NP is proved. Based on this result, an enumerative heuristic with a worst-case performance ratio of 1.5 is designed. Computational tests on randomly generated problems are conducted to evaluate the exact and heuristic algorithms.

This article proposes an optimization model for simultaneous estimation of an origin-destination (O-D) matrix and a travel-cost coefficient for congested networks in a logit-based stochastic user equilibrium (SUE). The model is formulated in the form of a standard differentiable, nonlinear optimization problem with analytical stochastic user equilibrium constraints. Explicit expressions of the derivatives of the stochastic user equilibrium constraints with respect to origin-destination demand, link flow, and travel-cost coefficient are derived and computed efficiently through a stochastic network-loading approach. A successive quadratic-programming algorithm using the derivative information is applied to solve the simultaneous estimation model. This algorithm converges to a Karusch-Kuhn-Tucker point of the problem under certain conditions. The proposed model and algorithm are illustrated with a numerical example.

This paper proposes different “dynamic” estimators using time-varying traffic counts to obtain (discrete) time-varying OD flows or average OD flows. All the estimators can combine counts with other available information, e.g., out-dated matrices and surveys, on a general network and can be formulated as optimization problems. In the case of time-varying OD flows, two types of estimators are proposed. Simultaneous estimators produce joint estimates of the whole set of OD matrices, one for each time slice, whereas sequential estimators produce a sequence of OD estimates for successive time slices. A particular type of simultaneous and sequential estimator (namely Generalized Least Squares) was tested on the Italian Brescia–Padua motorway for which “true” OD flows over a whole day were available. Results were generally satisfactory, showing that also in the “no a priori information” case significant estimates could be obtained.

This paper presents a new suite of models for the estimation and prediction of time-dependent Origin-Destination (O-D) matrices. The key contribution of the proposed approach is the explicit modeling and estimation of the dynamic mapping (the assignment matrix) between time-dependent O-D flows and link volumes. The assignment matrix depends upon underlying travel times and route choice fractions in the network. Since the travel times and route choice fractions are not known with certainty, the assignment matrix is prone to error. The proposed approach provides a systematic way of modeling this uncertainty to address both the offline and real-time versions of the O-D estimation/prediction problem. Preliminary empirical results indicate that generalized models with a stochastic assignment matrix could provide better results compared to conventional models with a fixed matrix.

The use of prediction error and maximum likelihood techniques to estimate intersection turning and through movement probabilities from entering and exiting counts is considered here. A maximum likelihood estimator for situations when full information on turning movement counts is available is derived and used as a component for a maximum likelihood algorithm which only requires entering and exiting counts. Several algorithms based on minimizing the error between observed and predicted exiting counts are also developed. Some actual traffic data are collected and used to develop realistic simulations for evaluating the various estimators. Generally, the maximum likelihood algorithm produced biased but more efficient estimates, while prediction error minimization approaches produced unbiased but less efficient estimates. Constraining the recursive version of the ordinary least-squares estimator to satisfy natural constraints did not affect its long run convergence properties.

Lane-changing algorithms have attracted increased attention during recent years. However, limited research has been conducted to address the probability of changing lanes as a function of driver characteristics and lane-changing scenarios. This study contributes to the development of a comprehensive framework for modeling drivers' lane-changing maneuver on arterials by using driver behavior-related data. Focus group studies and “in-vehicle” driving tests were performed to investigate the effects of driver type under various lane changes on urban arterials and to collect microscopic vehicular data. With these field collected values, a model was developed to estimate the probability of changing lanes under various lane-changing scenarios and to estimate the corresponding gap acceptance characteristics. The lane-changing probability for each scenario was modeled as a function of the factors identified from the focus group discussions, as well as the driver types. In the gap acceptance modeling, a sequence of “hand-shaking negotiations” was introduced to describe vehicle interactions that may occur during lane-changing maneuvers. The proposed lane-changing model was implemented in the CORSIM (CORrider SIMulation) micro-simulator. The simulation capabilities of the newly developed model were compared to the original lane-changing algorithm in CORSIM and to the field observations. The validation results indicated that the new model better replicates the observed traffic under various levels of flow.

We address the problem of determining how to reroute aircraft in the air traffic control system when faced with dynamically changing weather conditions. The overall objective of this problem is the minimization of delay costs. This problem is of primary concern in the European air traffic control system and in particular regions within the US air traffic control system. We present an integrated mathematical programming approach that consists of several methodologies. To address the high dimensionality, we begin by presenting an aggregate model, in which the problem is formulated as a dynamic, multicommodity, integer network flow problem with certain side constraints. Using Lagrangian relaxation, we generate aggregate flows. We decompose the aggregate flows into a collection of flight paths for individual aircraft using a randomized rounding heuristic. This collection of paths is then used in a packing integer programming formulation, the solution of which generates feasible and near-optimal routes for individual flights. The overall Lagrangian Generation Algorithm is used to solve real problems in the southwestern portion of United States. In computational experiments, the solutions returned by our algorithm are within 1% of the corresponding lower bounds.

When air traffic demand is projected to exceed capacity, the Federal Aviation Administration implements traffic flow management (TFM) programs. Independently, these programs maintain a first-scheduled, first-served invariant, which is the accepted standard of fairness within the industry. Coordinating conflicting programs requires a careful balance between equity and efficiency. In our work, we first develop a fairness metric to measure deviation from first-scheduled, first-served in the presence of conflicts. Next, we develop an integer programming formulation that attempts to directly minimize this metric. We further develop an exponential penalty approach and show that its computational performance is far superior and its tradeoff between delay and fairness compares favorably. In our results, we demonstrate the effectiveness of these models using historical and hypothetical scenarios. Additionally, we demonstrate that the exponential penalty approach exhibits exceptional computational performance, implying practical viability. Our results suggest that this approach could lead to system-wide savings on the order of $25 to $50 million per year.

Air traffic flow management (ATFM) attempts to maintain a safe and efficient flow of aircraft given demand-capacity mismatches while ensuring an equitable distribution of delays among stakeholders. There has been extensive research addressing network effects (such as the presence of multiple airports, sectors, and connectivity requirements) in ATFM, but it has not explicitly incorporated the equitable distribution of delays, as well as work on the equitable distribution of delays in a single-airport setting, such as ration-by-schedule (RBS) as introduced under the collaborative decision-making paradigm. In this paper, we develop a two stage approach for network ATFM that incorporates fairness and airline collaboration. In Stage 1, we propose a discrete optimization model that attempts to incorporate an equitable distribution of delays among airlines by introducing a notion of fairness in network ATFM models—controlling the number of reversals and total amount of overtaking, which is a natural generalization of RBS. For two flights f and f′, a reversal occurs when flight f′ arrives before f, when f was scheduled to arrive before f′. In the event a reversal occurs, the number of time periods between the arrival times constitutes overtaking. In Stage 2, we allow for airline collaboration by proposing a network model for slot reallocation. We provide extensive empirical results of the proposed optimization models on national-scale, real-world data sets spanning six days that show interesting trade-offs between fairness and efficiency. We report computational times of less than 30 minutes for up to 25 airports and provide theoretical evidence that illuminates the strength of our approach.