Search

This paper addresses the problem of finding the optimal routing policies with only trajectory information in a stochastic time-dependent network where all link travel times are temporally and spatially correlated. Two equivalent definitions are given for trajectory-adaptive routing policy. The first definition follows the mapping definition in a series of previous studies, where the trajectory information is included in the state variable. With that definition, any subpolicy of an optimal routing policy must also be optimal, and the algorithm developed in previous studies could serve as an exact solution, but the nature of the definition that trajectory information is included in the state variable determines that the number of states is prohibitively huge. Therefore, a second definition is given as a recursive definition, where the trajectory information is not included in the state variable. It is shown that, with the second definition, a subpolicy of an optimal/nondominated routing policy is not necessarily optimal/nondominated, but any subpolicy of a pure routing policy must also be pure which is a new property defined based on nondominance. An exact algorithm is designed to find optimal trajectory-adaptive routing policies based on the aforementioned property of pure routing policy. A comparison is made between the optimal trajectory-adaptive routing policies and the optimal paths in the same test networks to investigate the benefit of being adaptive. The results show that the benefit of being adaptive to trajectory information is more significant with a higher risk aversion, a higher correlation, and/or a larger network. [ABSTRACT FROM AUTHOR]

Logistics is a cost sensitive industry with large and fast growing routing networks. In this paper we devise a computational, robust optimization method for the strategic routing decisions of a logistics' customer, i.e., a company that uses the services of different freight forwarders to meet its transportation demands between several sources, sinks, and hubs. The costs of such transports are determined by tariff systems that typically show economies of scale and reward the consolidation of goods that complement each other in properties relevant for transport, such as weight and volume. In the strategic planning phase, routes and hubs have to be chosen roughly one year ahead, in particular, before the actual demand is known. Our method anticipates the fluctuation of demands by minimizing the worst-case cost over a restricted scenario set. The combination of a realistic cost function, a robust modeling of uncertainty, and large-scale networks leads to highly intractable models. We show that the corresponding adversary problem is NP-hard. To nevertheless find solutions for real instances with very good worst-case cost we derive a carefully relaxed and simplified mixed-integer linear program that solves well for large instances because of its powerful linear programming relaxation. We test the method for real-world instances. The results show that robust optimization can significantly reduce worst-case cost. Furthermore, we derive from our method two heuristic techniques to solve even larger networks and report on the corresponding computational results. Neglecting the typical uncertainty about demand values can cause significant cost in logistic routing problems. This paper provides for a practical method to avoid such costs. [ABSTRACT FROM AUTHOR]

In Part I of this paper, we presented a large-scale airspace-planning and collaborative decision-making (APCDM) model that is part of a Federal Aviation Administration (FAA)-sponsored effort to enhance the management of the National Airspace System (NAS). Given a set of flights that must be scheduled during some planning horizon, along with alternative surrogate trajectories for each flight, we developed a mixed-integer programming model to select a set of flight plans from among these alternatives, subject to flight safety, airtraffic control workload, and airline equity considerations. The present paper offers insights related to, and a detailed description of, implementing this APCDM model, including the development of a comprehensive cost model, a study for prescribing a set of appropriate parameter values for the overall model, and an investigation on incorporating a suitable set of valid inequalities in the model formulation. Computational results are presented based on several test cases derived from the Enhanced Traffic Management System (ETMS) data provided by the FAA. The results indicate that under plausible probabilistic trajectory error assumptions and with the incorporation of star subgraph convex hull-based valid inequalities, the model offers a viable tool that can be used by the FAA for both tactical and strategic applications. [ABSTRACT FROM AUTHOR]

We present a large-scale, airspace planning and collaborative decision-making model (APCDM) to enhance the management of the U.S. National Airspace System (NAS). Given a set of flights that must be scheduled during some planning horizon, along with alternative surrogate trajectories for each flight as prompted by various airspace restriction scenarios imposed by dynamic severe weather systems or space launch special use airspaces (SUA), we develop a mixed-integer programming model to select a set of flight plans from among these alternatives, subject to flight safety, air traffic control workload, and airline equity constraints. The model includes a three-dimensional probabilistic conflict analysis, the derivation of valid inequalities, the development of air traffic control workload metrics, and the consideration of equity among airline carriers in absorbing costs related to rerouting, delays, and possible cancellations. The resulting APCDM model has potential use for both tactical and strategic applications, such as air traffic control in response to severe weather phenomena or spacecraft launches, FAA policy evaluation (separation standards, workload restrictions, sectorization strategies), Homeland Defense contingency planning, and military air campaign planning. The model can also serve a useful role in augmenting the FAA's National Playbook of standardized flight profiles in different disruption-prone regions of the national airspace. The present paper focuses on the theory and model development; Part II of this paper will address model parameter estimations and implementation test results. [ABSTRACT FROM AUTHOR]

In a recent paper, R. Gopalan, K. Kolluri, R. Batta and M. Karwan (1990) consider a model to route a set of hazardous materials shipments from an origin to a destination, so as to minimize the global risk to the community while simultaneously maintaining a desired level of equity between zones within the community. If one follows the routes produced via their solution methodology, the overall risk is small and equity between zones is achieved after all the shipments are over. However, equity may be severely violated at an intermediate stage of the shipment process. Since an accident can occur at any stage, this is not a desirable situation. Motivated by this, in this paper we consider the problem of equitably sequencing a given set of hazardous materials shipments. We presume, of course, that the set of routes are such that they engender low overall risk to the community as a whole, and once they are all traversed the risk is equitably distributed among the zones of the community - Gopalan, Kolluri, Batta, and Karwan's paper provides such routes for the case of a single origin and destination; their procedure is easily adaptable for the case of multiple origins and destinations. The objective function considered in this paper is to minimize the sum of the maximum differences in risk that exist between any two zones, where the sum is taken over the trips made. We formulate the resulting equitable sequencing problem as an integer programming problem and as a dynamic programming problem. Optimal solution strategies are examined for small-sized problems. Several heuristic solution strategies are proposed to obtain the upper bounds needed for dynamic programming fathoming and for obtaining reasonable solutions to large-sized problems. The proposed solution methods are tested on a real data set from the City and County of Albany, New York, as well as on a randomly generated data set. [ABSTRACT FROM AUTHOR]

This paper proposes a new formulation for the school bus scheduling problem (SBSP), which optimizes school start times and bus operation times to minimize transportation cost. The goal is to minimize the number of buses to serve all bus routes such that each route arrives in a time window before school starts. We show that introducing context-specific features, common in many school districts, can lead to a new time-indexed integer linear programming (ILP) formulation. Based on a strengthened version of the linear relaxation of the ILP, we develop a dependent randomized rounding algorithm that yields near-optimal solutions for large-scale problem instances. The efficient formulation and solution approach enable quick generation of multiple solutions to facilitate strategic planning, which we demonstrate with data from two public school districts in the United States. We also generalize our methodologies to solve a robust version of the SBSP. [ABSTRACT FROM AUTHOR]

This paper studies the resilience of the regional highway transportation system of the San Francisco Bay Area. Focusing on peak periods for commuter traffic, traffic patterns are computed from a model that includes nonlinear increases in travel times due to congestion and reflects actual travel demands as captured by U.S. Census demographic data. We consider the consequences associated with loss of one or more road, bridge, and/or tunnel segments, where travelers are allowed to reroute to avoid congestion or potentially not travel at all if traffic is bad. We use a sequential game to identify sets of road, bridge, or tunnel segments whose loss results in worst-case travel times. We also demonstrate how the model can be used to quantify the operational resilience of the system, as well as to characterize trade-offs in resilience for different defensive investments, thus providing concise information to guide planners and decision makers. [ABSTRACT FROM AUTHOR]

Optimized profile descent (OPD) is an arrival procedure for the Next Generation Air Transportation System, which has been demonstrated to effectively decrease noise, emissions, and fuel costs. Implementation of OPD operations requires effective metering policies because of the increased role of uncertainty in aircraft trajectories during descent. While optimal sequencing and spacing of OPD flights have been studied in the literature, any potential savings resulting from possible changes in metering point configurations have not been addressed. In this paper, we develop models to further increase the value of OPD operations over conventional arrival procedures by optimizing metering point configurations, which include identification of the optimal number and locations of metering points to use during OPD. We derive an algorithmic framework based on implementations of a stochastic dynamic programming model and a nonlinear stochastic integer program to identify best metering point configurations where resulting computational difficulties are addressed through convex approximation and Lagrangian decomposition procedures. We also describe numerical results based on actual traffic information at major U.S. airports, which indicate that the total potential savings in the top 10 major airports could be up to $22 million a year if the proposed policies are implemented. [ABSTRACT FROM AUTHOR]

The U.S. truck driver scheduling problem (US-TDSP) is the problem of visiting a sequence of λ locations within given time windows in such a way that driving and working activities of truck drivers comply with U.S. hours-of-service regulations. In the case of single time windows it is known that the US-TDSP can be solved in O(λ³) time. In this paper, we present a scheduling method for the US-TDSP that solves the single time window problem in Oλ²) time. We show that in the case of multiple time windows the same complexity can be achieved if the gap between subsequent time windows is at least 10 hours. This situation occurs, for example, if, because of opening hours of docks, handling operations can only be performed between 8.00 a.m. and 10.00 p.m. Furthermore, we empirically show that for a wide range of other problem instances the computational effort is not much higher if multiple time windows are considered. [ABSTRACT FROM AUTHOR]

Railroad transportation of hazardous materials did not receive as much attention as highway transportation in the academic literature, although comparable volumes are shipped via these two transport modes in North America and Europe. In this paper, we present an optimization methodology for the railroad tactical planning problem with risk and cost objectives. We determine the routes to be used for each shipment, the yard activities, and the number of trains of different types needed in the network. The transport risk assessment component of our model incorporates the differentiating characteristics of railroad operations. We develop a memetic algorithm-based solution methodology, which combines genetic and local searches, to solve the biobjective model. The railroad infrastructure in the midwestern United States is used as a basis for generating problem instances of the size encountered in real life. Our analyses of the solutions of instances indicate that it is possible to achieve significant reductions in population exposure without incurring unacceptable increases in operational costs. [ABSTRACT FROM AUTHOR]

In this paper, we investigate toll setting as a policy tool to regulate the use of roads for dangerous goods shipments. We propose a mathematical formulation as well as a solution method for the hazardous materials toll problem. Based on a comparative analysis of proposed mathematical models, we show that toll policies can be more effective than the popular network design policies that identify road segments to be closed for vehicles carrying hazardous materials. We present a summary of computational experiments on a problem instance from Western Ontario, Canada. [ABSTRACT FROM AUTHOR]

Delays and disruptions in airline operations annually result in billions of dollars of additional costs to airlines, passengers, and the economy. Airlines strive to mitigate these costs by creating schedules that are less likely to get disrupted or schedules that are easier to repair when there are disruptions. In this paper, we present a robust optimization model for the crew pairing problem, which generates crew schedules that are less likely to get disrupted. Our model allows adding robustness without requiring detailed knowledge of the underlying delay distributions. Moreover, our model allows us to capture in detail the delay propagation through crew connections and the complex cost structure of the pay-and-credit crew salary scheme, thus enabling us to find a good trade-off between the deterministic component of the planned costs on the one hand and the expected delay and disruption costs on the other hand. Our robust crew pairing model is based on a deterministic crew pairing model formulated as a mixed-integer linear program. The robust version that we propose retains the linearity of the constraints and objective function and thus can be handled by commercial solvers, which facilitates its implementation in practice. We propose and implement a new solution algorithm for solving our model to optimality. Several optimal solutions with varying robustness levels are compared for the network of a moderate-size airline in the United States. We test the model's solutions in a simulation environment using real-world delay data. Our simulation results show that the robust crew pairing solutions lead to lower delays and fewer instances of operational infeasibilities, thus requiring fewer recovery actions to address them. We find that, with the inclusion of robustness, it is possible to generate crew pairing solutions that significantly reduce the delay and disruption costs with only a small increase in planned costs. [ABSTRACT FROM AUTHOR]

In this paper, we study an airspace flow program in the context of weather-related disruptions by augmenting the airspace planning and collaborative decision-making model (APCDM). The proposed model selects among alternative flight plans for the affected flights while integrating slot exchange mechanisms induced by multiple ground delay programs (GDPs) to permit airlines to improve flight efficiencies through a mediated bartering of assigned slots, and simultaneously considering issues related to sector workloads and airspace conflicts, as well as overall equity concerns among the involved airlines in regard to accepted slot trades and flight plans. The APCDM is enhanced to include (a) the selection of slot exchange trade offers suggested by the airlines based on their allotted slots under a GDP; (b) connections between continuing flights; and (c) several alternative equity concepts. Both full and light versions of this model are developed and tested using realistic data derived from the enhanced traffic management system data provided by the Federal Aviation Administration. [ABSTRACT FROM AUTHOR]

The airline industry currently has a $40-billion plus market and is expected to grow rapidly with the population growth and growth in the overall economy. Everyday, thousands of aircrafts undergo maintenance, repair, and overhaul. The aircraft maintenance problem is one of the important logistic problems in the airline industry. It is aimed at scheduling the aircrafts' routing so that enough maintenance opportunities are provided to every aircraft in the fleet. In this paper, we present a new compact network representation of the aircraft maintenance routing problem (AMR) and propose a new mixed-integer linear programming formulation to solve the problem. The quality of this model was assessed on four real test instances from a major U.S. carrier, and compared with the flight string model proposed in the literature. The computational results show that the proposed model is able to obtain the optimal solutions to all test instances in reasonable time. This study suggests that this model can be applied to integrated problems of the AMR and other planning problems such as the fleet assignment problem and crew pairing problem. [ABSTRACT FROM AUTHOR]

Passenger screening is a critical component of aviation security systems. This paper introduces the sequential stochastic security design problem (SSSDP), which models passenger and carry-on baggage-screening operations in an aviation security system. SSSDP is formulated as a two-stage model, where in the first stage security devices are purchased subject to budget and space constraints, and in the second stage a policy determines how passengers that arrive at a security station are screened. Passengers are assumed to check in sequentially, with passenger risk levels determined by a prescreening system. The objective of SSSDP is to maximize the total security of all passenger-screening decisions over a fixed time period, given passenger risk levels and security device parameters. SSSDP is transformed into a deterministic integer program, and an optimal policy for screening passengers is obtained. Examples are provided to illustrate these results, using data extracted from the Official Airline Guide. [ABSTRACT FROM AUTHOR]

Congestion in air traffic networks is a serious problem and has received a lot of attention both from the aviation authorities (Federal Aviation Administration, Eurocontrol, etc.) and from the scientific research community. In past years, one way of reducing the amount of congestion has been the adoption of ground holding policies, i.e., a ground hold is imposed to selected aircraft, prior to their departure, so that congestion may be smoothed away. Many airlines in the United States have been complaining about these policies and are pushing toward the new concept of "free flight," where the airlines are almost "free" to choose for each of their flights, when to depart, which route to follow, at what speed, etc., as long as the arrival at the destination airport matches a given time, decided by a central authority (the Federal Aviation Administration in the United States). In this new perspective, to avoid congestion, or at least to reduce it, the central authority has to schedule the arrival times of all flights, with possible delays for some of them. In this paper, we describe an exact algorithm, based on the integration of a heuristic algorithm with an integer linear programming model. This approach provides exact solutions in a much shorter computation time than previous algorithms proposed in the literature. We will report on our computational experiences using large instances based on actual Official Airline Guide data for the United States air traffic network. [ABSTRACT FROM AUTHOR]

This paper develops a model that is being used by the City of New York to design a new logistics system to transport municipal sewage sludge from city-operated wastewater treatment plants to a new ocean dumping site 106 miles offshore. The model provides an integrative framework for considering such strategic planning issues as fleet sizing, choice of vessel size, sizing local inventory holding capacities, and analyzing system behavior with and without transshipment. A unique feature of the model is that plant visitation frequencies are determined naturally by the characteristics of the problem (vessel size, inventory holding capacities, statistics of sludge production, proximity of other plants), rather than stated as exogeneous constraints. The formulation should be useful in a more general class of depot-to-customer distribution systems, including the distribution of industrial gases. The paper concludes with a description of additional research that is required in refining both the assumptions and the mechanisms of execution of the model. [ABSTRACT FROM AUTHOR]

The article presents abstracts for the 1997 Transportation Science Section (TSS) Dissertation Prize Competition. The TSS Dissertation Prize Competition is the oldest and most prestigious competition for doctoral dissertations in the transportation science area. Eligible doctoral dissertations were those completed and submitted between June 1, 1996 and May 31, 1997 in the area of transportation science. To be considered, a dissertation had to be nominated by the thesis supervisor. The paper Dynamic Network Flow With Uncertain Arc Capacities, holds that a directed graph is dynamic if each node has a time value and each arc is directed forward in time. A dynamic network flow model is a kind of network flow model where the associated network graph is dynamic. In many real-world problems, current decisions are based on an uncertain future. The author extend the dynamic network flow model to use a set of arc capacity scenarios, which represent a discrete random capacity distribution.

Delivering automobiles, vans, and trucks to auto dealerships is a unique problem among the routing and scheduling problem class. A subproblem is that of loading the vehicles onto an auto-carrier (equipment specially designed for this purpose). Allocation of the vehicles to this equipment has typically been done by means of trial and error and heuristic methods. This paper shows how the loading aspect of the delivery problem can be solved using optimizing methods. The approach has the potential of replacing the empirical methods currently used in practice. [ABSTRACT FROM AUTHOR]

This paper attempts to provide some insight into the structure of' a large class of fleet scheduling problems. Scheduling under fixed due date constraints is shown to be easily solved using a new formulation of the problem. Scheduling under flexible due date constraints is shown to be inherently complex, and strong evidence is given for asserting that no efficient (polynomial bounded) algorithm, exists for solving this problem exactly. A fast heuristic approach is described which has worked well in some school bus scheduling applications. [ABSTRACT FROM AUTHOR]

This paper presents the motivation for the construction of a digital computer simulation of the American military's strategic airlift system, the author's analysis of that system preparatory to the simulation design, and the currently anticipated application of the model to studies of strategic mobility. Emphasis is placed on the estimation of the airlift productivity function for its subsequent utilization in appropriate strategic mobility models employed by the Joint Chiefs of Staff and by the Office of the Assistant Secretary of Defense (Systems Analysis). Those variables suspected of being primary contributors to gains in marginal airlift productivity are delineated in a description of the modules constituting the model. Finally, a sketch of an hypothetical experimental design, permitting the systems analyst to specify sequentially model iterations so as to obtain valid statistical estimates of desired marginal productivities, serves as a conclusion to the paper. [ABSTRACT FROM AUTHOR]

Crew costs are a significant portion of rail operating expenses, and so effective deployment of train crews is an important priority for freight railroads. This paper proposes an optimization model and develops an effective solution approach to assign crews to trains and decide when to deadhead crew members in double-ended crew districts in U.S. freight railways. To solve this model quickly, we develop several modeling and methodological enhancements including methods to reduce the problem size, strengthen the model, and generate good heuristic solutions. Computational testing and validation using 140 real-life problem instances demonstrate that our algorithm can find optimal and implementable solutions very quickly (typically within one minute), making it well-suited for practical use to provide real-time decision support to crew planners. [ABSTRACT FROM AUTHOR]

Citizens' preferences concerning bus transportation in Boulder, Colorado, were ascertained by two different but related techniques. The primary method was through a coputerized game ('CARTFED,' or Computer-Aided-Real-Time-Feedback Decision) in which subjects are asked to design a desirable bus system by choosing values for system characteristics. Subjects enter these in a portable computer-terminal and the computer calculates and reports the associated deficit, whereupon subjects reiterate making trade-offs to reduce the deficit to an acceptable level. In order to program the computer to calculate the deficits associated with a wide variety of systems, it was necessary to estimate cost and revenue functions. Sicne the latter depends upon the demand, a prerequisite to the CARTFED program was the estimation of citizens' preferences by a different technique, which took the form of a questionnaire survey in which respondents were presented with randomly-generated profiles of possible bus systems and asked how often they would use such a system. Multiple regression analysis of the responses yielded the demand function necessary for the CARTFED program. This paper describes both techniques and their results. [ABSTRACT FROM AUTHOR]

This paper is concerned with the development and analysis of a mathematical model for determining a route that attempts to reduce the risk of low probability-high consequence accidents related with the transportation of hazardous materials. The approach adopted considers trade-offs between the conditional expectation of a catastrophic outcome given that an accident has occurred, and more traditional measures of risk dealing with the expected value of the consequence and the accident probability on a selected path. More specifically, the problem we address involves finding a path that minimizes the conditional expectation objective value, subject to the expected value of the consequence being lesser than or equal to a specified value v, and the probability of an accident on the path being also constrained to be no more than some value η. The values v and η are user-prescribed and could be prompted by the solution to the shortest path problems that minimize the respective corresponding linear risk functions. The proposed model is a discrete, fractional programming problem that is solved using a specialized branch-and-bound approach. A numerical example is provided for the sake of illustration, and some computational experience on randomly generated test cases is provided to study the effort required to solve this problem in different instances. The model is also tested using realistic data associated with a case concerned with routing hazardous materials through the roadways of Bethlehem, Pennsylvania. Data acquisition as well as algorithmic computational issues are discussed. [ABSTRACT FROM AUTHOR]

The New York City Department of Sanitation operates the world's largest refuse marine transport system. Waste trucks unload their cargo at land-based transfer stations where refuse is placed in barges and then towed by tugboats to the Fresh Kills Landfill in Staten Island. In the early 1980s, the city commissioned the development of a computer-based model for use in fleet sizing and operations planning. As a result of the complexities introduced by environmental regulation and technological innovation, the marine transport system operations changed and the existing model became obsolete. Based on the success achieved with the first model in 1993, the city commissioned the development of a new model. In this paper, we present a PG-based model developed to meet the increased complexity of the system. Analysis performed for validation and calibration of the model demonstrates that it tracks well the operations of the real system. We illustrate through a detailed design exercise how to use the model to configure the system in a way that meets the requirements of the refuse marine transport system. [ABSTRACT FROM AUTHOR]

This paper considers integrated location and routing models for minimizing the expected number of hazardous material transport accidents. Two different routing policies are considered: (1) most reliable route planning and (2) multiple routing with random selection. Path reliability measurements are used to derive the expected number of accidents over a given planning horizon, where reliability refers to the probability of completing a journey without accident. Corresponding to the two routing policies, two location models are introduced: the reliable 1-median and a location framework for considering multiple routes. Based on realistic assumptions for assigning accident probabilities to segments created when an edge location is considered, vertex optimality results for both problems are obtained. An example to illustrate reliable routing and location in Massachusetts is provided. [ABSTRACT FROM AUTHOR]

The yearly congestion costs in the U.S. airline industry are estimated to be of the order of $2 billion. In [6] we introduced and studied generic integer programming models for the static multi-airport ground-holding problem (GHP), the problem of assigning optimal ground holding delays in a general network of airports, so that the total (ground plus airborne) delay cost of all flights is minimized. The present paper is the first attempt to address the multi-airport GHP in a dynamic environment. We propose algorithms to update groundholding decisions as time progresses and more accurate weather (hence capacity) forecasts become available. We propose several pure IP formulations (most of them 0-1), which have the important advantages of being remarkably compact while capturing the essential aspects of the problem and of being sufficiently flexible to accommodate various degrees of modeling detail. For example, one formulation allows the dynamic updating of the mix between departure and arrival capacities by modifying runway use. These formulations enable one to assign and dynamically update ground holds to a sizeable portion of the network of the major congested U.S. or European airports. We also present structural insights on the behavior of the problem by means of computational results, and we find that our methods perform much better than a heuristic which may approximate, to some extent, current ground-holding practices. [ABSTRACT FROM AUTHOR]

The equilibrium network design problem can be formulated as a mathematical program with variational inequality constraints. We know this problem is nonconvex; hence, it is difficult to solve for a globally optimal solution. In this paper we propose a simulated annealing algorithm for the equilibrium network design problem. We demonstrate the ability of this algorithm to determine a globally optimal solution for two different networks. One of these describes an actual city in the midwestern United States. [ABSTRACT FROM AUTHOR]

This paper presents the development of a mathematical programming model for evaluating options for the continuance of the Essential Air Services (EAS) program, a provision of the Airline Deregulation Act of 1978. The EAS program was established to guarantee continued air service to small communities that suffered air service losses as a result of carrier withdrawals permitted by the Deregulation Act. The model has been designed to aid decision makers in allocating subsidized air services to communities in a region, given the goal of maximizing access to the air transportation system. In order to provide information on optimal service locations, service characteristics, and patterns of access, the authors have utilized a maximal covering formulation and incorporated elements of hierarchical and weighted benefit models. In addition, a stopover service option has been included in the model to permit evaluation of potential gains in economic efficiency that may be realized by utilizing stopover service, when appropriate, in place of more costly nonstop service. In addition to the coverage objective, a second objective of systemwide cost minimization is employed. By using a multiobjective approach, the trade-offs between the conflicting objectives of coverage and cost can be explored and the spatial patterns of service associated with each combination of coverage level and cost can be examined. The model is applied to a sample study of small community air service in North and South Dakota. [ABSTRACT FROM AUTHOR]

In this paper, different empirical models for explaining car travel to Canadian provinces by American citizens are estimated. The results indicate interesting substitution and complementarities in travel that have important policy implications. Furthermore, the results have implications for future travel to Canada given rising incomes and the shifting of the United States' population center. [ABSTRACT FROM AUTHOR]

As large medical centers become ever more capable, the existence of well equipped, well staffed and rapid emergency ambulance service becomes increasingly important. This paper presents a method for determining the optimum location of ambulance stations to minimize the average response time to emergency calls. A new point-to-point driving time model is introduced, and a computer optimization algorithm used to determine the optimum locations. A constraint that the average response time to any point in the service area be less than some specified minimum is also considered. The method is applied to Washtenaw County, Michigan. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to estimate cost functions for the U.S. passenger airline industry in order to determine the sources of recent observed productivity, increases. A cost function is derived from the Cobb-Douglas production function, and the parameters of that reduced form equation are estimated. Special attention is given to effect of technology on costs. In general, it was found that there seem to be no scale economies present in the production of available seat miles, but that the level of technology has a substantial impact on cost and productivity. [ABSTRACT FROM AUTHOR]

In the paper "Sources of Productivity Increases in the U.S. Passenger Airline Industry," a log-linear cross-section function was estimated with several independent variables of the "dummy" or "shift" form. In this type of estimating procedure, the dummy variable is interpreted as a shift in the intercept due to some discrete event that is thought to influence the dependent variable. However, the intercept of the estimated linear transformed equation is a multiplicative factor in the equation before transformation. The nontransformed equation, of course, has no intercept. For this reason, the impact of technical change on cost cannot be determined from the equation directly. Using some values for each of the continuous independent variables, use the equation to calculate cost. In this case the mean values of the logarithm were used. If the value of each of the dummy variables is zero, then this calculated cost is interpreted as the expected annual cost of running a propeller driven plane for the sample geometric seat miles, fuel-cost, etc. Replicate this procedure with the addition of a value of unity for the first dummy variable. This is interpreted as the expected annual cost of running a turboprop plane for the sample geometric mean values of the continuous independent variables.

In a typical aviation environment today, the precise landing times of en route aircraft are not set until each aircraft approaches the airspace adjacent to the destination airport. In times of congestion, it is not unusual for air traffic controllers to subject arriving aircraft to various maneuvers so as to create an orderly flow of aircraft onto an arrival runway. Typical maneuvers might include flying in zigzag patterns and flying in circular holding patterns, as well as others. These maneuvers serve to delay the arrival time of the flight. On the other hand, if the arrival time was established much earlier, then that delay could be realized by having the aircraft fly slower while still at a higher altitude, which would burn much less fuel than the described maneuvers. Three integer programming models are proposed to assign delay to aircraft approaching a single airport, well in advance of each aircraft's entry into the terminal airspace. The baseline model is deterministic and seeks to maximize the available throughput at the runway over a rolling horizon. The latter two models are stochastic and account for uncertainty regarding the status and controllability of certain flights. The first stochastic model is scenario based, while the second relies on a functional approximation of uncertainty. The results of computational experiments show that these approaches can transfer a considerable portion of the delay that would otherwise occur in the terminal area to the en route phase of flight, and also that the stochastic models are noticeably more effective. The model relying on functional approximation shows particular promise because of its efficient run time. The delay transfer yielded by each model resulted in significant predicted fuel savings. The functional approximation model performed particularly well under declining operational conditions, demonstrating itself to be a promising means of achieving delay transfer. [ABSTRACT FROM AUTHOR]

In many real-life routing problems there is more uncertainty with respect to the required timing of the service than with respect to the service locations. We focus on a pickup and delivery problem with time windows in which the pickup and drop-off locations of the service requests are fully known in advance, but the time at which these jobs will require service is only fully revealed during operations. We develop a sample-scenario routing strategy to accommodate a variety of potential time realizations while designing and updating the routes. Our experiments on a breadth of instances show that advance time related information, if used intelligently, can yield benefits. Furthermore, we showthat it is beneficial to tailor the consensus function that is used in the sample-scenario approach to the specifics of the problem setting. By doing so, our strategy performs well on instances with both short time windows and limited advance confirmation. [ABSTRACT FROM AUTHOR]

This study addresses various formulations of the optimal reliability path problem on stochastic networks. Robust-Cost is adopted as the measure of reliability, which is defined as a weighted combination of the mean and standard deviation of travel time. The principal problem solved is the Minimum Robust-Cost Path (MRCP) problem in the presence of Correlated link travel times. It is shown that the subpath optimality and subpath non-dominance principles, which are conventionally adopted in the literature, cannot be used to solve this problem. In this light, this study proposes an algorithm based on the subpath pruning approach, which eliminates nonoptimal subpaths by using a pruning criterion. We construct the novel pruning criterion, which depends on only two independent objectives, by transforming the network and using efficient shortest path algorithms. The correctness of the algorithm is established, and its good practical performance is demonstrated on real-world networks. Furthermore, the pruning procedure is generalized with suitable modifications to solve three related problems: (i) the MRCP problem with independent link travel times, (ii) the K-best Robust-Cost Paths problem, and (iii) the MRCP problem with stochastic nondominance constraints. These extensions demonstrate the potential wider applications of the proposed solution approach. [ABSTRACT FROM AUTHOR]

Package carriers use sophisticated automated sorting facilities to efficiently process inbound packages and sort them to their down line destinations. During each of several daily processing windows, primary sorters perform high level sortation of the packages and direct them to one of several secondary sorters that are then used to segregate the packages by their outbound loading destinations. We examine the problem of assigning package destinations to the secondary sorters in a way that balances the workload in the facility, while incorporating the day-to-day fluctuation in package volumes and adhering to the outbound loading capacities of the various workcenters in the facility. We present a general stochastic modeling framework using chance constraints to balance the flows, and robust constraints to model the capacity limits. We propose and evaluate the performance of three alternative mixed integer nonlinear formulations for the problem and determine which is most effective. Significant improvement in package flow balance and loading capacity robustness is shown for the test sorting facilities by comparing the solutions from the proposed new model to those obtained when ignoring, partially or completely, the stochasticity in the package volumes. [ABSTRACT FROM AUTHOR]

This article studies a capacitated fixed-charge multiperiod location–transportation problem in which, while the location and capacity of each facility must be determined immediately, the determination of the final production and distribution of products can be delayed until actual orders are received in each period. In contexts where little is known about future demand, robust optimization, namely using a budgeted uncertainty set, becomes a natural method for identifying meaningful decisions. Unfortunately, it is well known that these types of multiperiod robust decision problems are computationally intractable. To overcome this difficulty, we propose a set of tractable conservative approximations for the problem that each exploit to a different extent the idea of reducing the flexibility of the delayed decisions. While all of these approximation models outperform previous approximation models that have been proposed for this problem, each also has the potential to reach a different level of compromise between efficiency of resolution and quality of the solution. A row generation algorithm is also presented to address problem instances of realistic size. We also demonstrate that full flexibility is often unnecessary to reach nearly, or even exact, optimal robust locations and capacities for the facilities. Finally, we illustrate our findings with an extensive numerical study where we evaluate the effect of the amount of uncertainty on the performance and structure of each approximate solution that can be obtain d. [ABSTRACT FROM AUTHOR]

We study an emergency response network design problem that integrates relief (supply) and evacuation (demand) sides under disaster location and intensity uncertainties which, in turn, dictate uncertainty in terms of the location and amount of demand. Representing these uncertainties by discrete scenarios, we present a stochastic programming framework in which two second stage objectives, the average and worst case costs, are combined. In our model, we minimize, over all of the scenarios, the fixed costs of opening supply centers and shelters, and the weighted sum of average and worst case flow costs. Thus, the model gives the decision maker the flexibility to put relative emphasis on the worst case and average flow cost minimization and explore outcomes in terms of total costs and network configurations. To solve large scale instances with varying relative weights, we devise alternative Benders Decomposition approaches. We implement these by using an advanced callback feature of the solver while simultaneously incorporating several performance-enhancing steps that help to improve runtimes significantly. We conduct a detailed computational study to highlight the efficiency of our proposed solution methodology. Furthermore, we apply our approach in a realistic case study based on Geographical Information Systems data on coastal Texas and present interesting insights about the problem and the resulting network structures for varying weights assigned to objectives. [ABSTRACT FROM AUTHOR]

We propose a robust optimization approach to minimize total propagated delay in the aircraft routing problem. Instead of minimizing the expected total propagated delay by assuming that flight leg delays follow specific probability distributions, our model minimizes the maximal possible total propagated delay when flight leg delays lie in a prespecified uncertainty set. We develop exact and tractable solution approaches for our robust model. The major contribution of our model is that it allows us to explicitly model and handle correlation in flight leg delays (e.g., because of weather or various air traffic management initiatives) that existing approaches cannot efficiently incorporate. Using both historical delay data and simulated data, we evaluate the performance of our model and benchmark against the state-of-the-research stochastic approach. In most of the cases, we observe that our model outperforms the existing approach in lowering the mean, reducing volatility, and mitigating extreme values of total propagated delay. In the cases where a deficit in one of the three criteria exists, gains in the other two criteria usually offset this disadvantage. These results suggest that robust optimization approaches can provide promising results for the aircraft routing problem. [ABSTRACT FROM AUTHOR]

Parcel services route vehicles to pick up parcels in the service area. Pickup requests occur dynamically during the day and are unknown before their actual request. Because of working hour restrictions, service vehicles only have a limited time to serve dynamic requests. As a result, not all requests can be confirmed. To achieve an overall high number of confirmed requests, dispatchers have to budget their time effectively by anticipating future requests. To determine the value of a decision, i.e., the expected number of future confirmations given a point of time and remaining free time budget, we present an anticipatory time budgeting heuristic (ATB) drawing on methods of approximate dynamic programming. ATB frequently simulates a problem's realization to subsequently approximate the values for every vector of point of time and free time budget to achieve an approximation of an optimal decision policy. Since the number of vectors is vast, we introduce the dynamic lookup table (DLT), a general approach adaptively partitioning the vector space to the approximation process. Compared with state-of-the-art benchmark heuristics, ATB allows an effective use of the time budget resulting in anticipatory decision making and high solution quality. Additionally, the DLT significantly strengthens and accelerates the approximation process. [ABSTRACT FROM AUTHOR]

There seem to be errors of two types in the paper "Sources of Productivity Increases in the U.S. Passenger Airline Industry." The errors of the first type are numerical. Table I gives the estimate 0.0311 for the parameter "h," associated with the common logarithm of the time shift variable Y, and -0.0511 for the parameter "g." The second type of error is much more fundamental. Not only is the assumption that a = 1 wrong in principle, but it may have influenced the major conclusion of the paper, which concerns economies of scale. Only by a recalculation, using the same data in the same model without demanding that a = 1, can one confirm or deny this surmise, but the paper's numerical results already suggest the existence of diseconomies of scale; that suggestion would be strengthened, and perhaps made statistically significant.

The monthly coal train reservations planning problem arises in the unit train business of North American railroads. It involves a variety of operational and tactical decisions such as train formation, routing, and scheduling. As a result of the extensive scope of coal transportation in the United States, models for this problem grow quickly to a size unmanageable by state-of-the-art optimization software. Therefore, we propose a two-model heuristic solution methodology that is time-efficient and produces good quality solutions. The first model is developed under simplifying assumptions and yields an upper bound on the number of reservations to be accepted during the month. It also assigns car consists to reservations based on aggregate supply and demand of resources. This model also provides a tentative schedule for trains, and sets precedence relations between reservations. These being given, a second procedure is used to construct a detailed monthly schedule through the solution of network flow models and through the solution of a job-shop scheduling problem. The resulting solution is then improved through a large-scale neighborhood search. We evaluate our approach computationally, both on randomly generated and practical instances. We show numerically that our approach outperforms current practice. [ABSTRACT FROM AUTHOR]

Properly determining the driving range is critical for accurately predicting the sales and social benefits of battery electric vehicles (BEVs). This study proposes a framework for optimizing the driving range by minimizing the sum of battery price, electricity cost, and range limitation cost--referred to as the "range-related cost"--as a measurement of range anxiety. The objective function is linked to policy-relevant parameters, including battery cost and price markup, battery utilization, charging infrastructure availability, vehicle efficiency, electricity and gasoline prices, household vehicle ownership, daily driving patterns, discount rate, and perceived vehicle lifetime. Qualitative discussion of the framework and its empirical application to a sample (N = 361664) representing new car drivers in the United States is included. The quantitative results strongly suggest that ranges of less than 100 miles are likely to be more popular in the BEV market for a long period of time. The average optimal range among U.S. drivers is found to be largely inelastic. Still, battery cost reduction significantly drives BEV demand toward longer ranges, whereas improvement in the charging infrastructure is found to significantly drive BEV demand toward shorter ranges. The bias of a single-range assumption and the effects of range optimization and diversification in reducing such biases are both found to be significant. [ABSTRACT FROM AUTHOR]

Although the airline industry has benefited from advancements made in computational and operational A research methods, most implementations arise from the frictionless environment of the planning stage. Because 22% of all flights have been delayed and 3% have been cancelled in the United States since 2001, schedule perturbations are inevitable. The complexity of the operational environment is exacerbated by the need for obtaining a solution in as close to real-time as possible. Given some time horizon, the recovery process seeks to repair the right schedule, aircraft rotations, crew schedule, and passenger itineraries in a tractable manner. Each component individually can be difficult to solve, so early research on irregular operations has studied these problems in isolation, leading to a sequential process by which the recovery process is conducted. Recent work has integrated a subset of these four components, usually abstracting from crew recovery. We present an optimization-based approach to solve the fully integrated airline recovery problem. After our solution methodology is presented, it is tested using data from an actual U.S. carrier with a dense hub-and-spoke network using a single-day horizon. It is shown that in several instances an integrated solution is delivered in a reasonable runtime. Moreover, we show the integrated approach can substantially improve the solution quality over the incumbent sequential approach. To the best of our knowledge, we are the first to present computational results on the fully integrated problem. [ABSTRACT FROM AUTHOR]

Discrete time dynamic graphs are frequently used to model multicommodity flows or activity paths through constrained resources, but simple graphs fail to capture the interaction effects of resource transitions. The resulting schedules are not operationally feasible, and return inflated objective values. A directed hypergraph formulation is derived to address railway network sequencing constraints, and an experimental problem sample solved to estimate the magnitude of objective inflation when interaction effects are ignored. The model is used to demonstrate the value of advance scheduling of train paths on a busy North American railway. [ABSTRACT FROM AUTHOR]

Because of historically high fuel prices, the trucking industry's operating expenses are higher than ever and thus profit margins are lower than ever. To cut costs, the trucking industry is searching for and exploring new ideas. We investigate the potential of collaborative opportunities in truckload transportation. When carriers serve transportation requests from many shippers, they may be able to reduce their repositioning costs by exchanging one or more of them. We develop optimization models to determine the maximum benefit that can be derived from collaborating. We also develop various exchange mechanisms which differ in terms of information sharing requirements and side payment options that allow carriers to realize some or all of the costs savings opportunities. [ABSTRACT FROM AUTHOR]

Truckload carriers provide hundreds of billions of dollars worth of services to shippers in the United States alone each year. Internet auctions provide these shippers with a fast and easy way to negotiate potential contracts with a large number of carriers. Combinatorial auctions have the added benefit of allowing multiple lanes to be considered simultaneously in a single auction. This is important because it enables carriers to connect multiple lanes in continuous moves or tours, decreasing the empty mileage that must be driven, and therefore increasing overall efficiency. On the other hand, combinatorial auctions require bidding on an exponential number of bundles to achieve full economies of scope and scale, which is not tractable except for very small auctions. In most real-world auctions, bidding is instead typically limited to a very small subset of the potential bids. We present an implicit bidding approach to combinatorial auctions for truckload procurement that enables the complete set of all possible bids to be considered implicitly, without placing the corresponding burden of an exponential number of bids on the bidders or the auctioneer. We present the models needed to solve this problem. We then provide extensive computational results to demonstrate the tractability of our approach. Finally, we conclude with numerical analysis to assess the quality of the solutions that are generated and to demonstrate the benefits of our approach over existing bidding methods in practice. [ABSTRACT FROM AUTHOR]

The hours of service (HOS) regulations of the department of transportation severely restrict the set of feasible driver schedules. So much so that establishing whether a sequence of full truckload transportation requests, each with a dispatch window at the origin, can feasibly be executed by a driver is no longer a matter of simple forward simulation. We consider this problem and prove that the feasibility of a driver schedule can be checked in polynomial time by providing an O(n3) algorithm for establishing whether a sequence of full truckload transportation requests, each with a dispatch window at the origin, can be executed by a driver. [ABSTRACT FROM AUTHOR]

Demand stochasticity is a major challenge for the airlines in their quest to produce profit maximizing schedules. Even with an optimized schedule, many flights on departure have empty seats while others suffer a lack of seats to accommodate passengers who desire to travel. We approach this challenge, recognizing that demand forecast quality for a particular departure date improves as it approaches, by developing a dynamic scheduling approach that reoptimizes elements of the flight schedule during the passenger booking process. The goal is to match capacity to demand given the many operational constraints that restrict possible assignments. We leverage flight retiming as a new dynamic scheduling mechanism and develop a reoptimization model that integrates both flight retiming and refleeting. Our reoptimization approach, redesigning the flight schedule at regular intervals, uses information from both revealed booking data and improved forecasts available at later reoptimizations. We conduct experiments using data from a major U.S. airline and demonstrate that significant potential profitability improvements are achieved. [ABSTRACT FROM AUTHOR]