bluuebunny/crossref_metadata_2025 huggingface dataset:
A Technique for Control of Traffic at Critical Intersections
Authors: Gordon Robert L.
Published: October 2008

An algorithm for control of queue lengths at oversaturated intersections oriented towards delaying spillback across upstream intersections as long as possible is described. It is based on determining the change in queue and the allotment of available green time so as to keep the ratio of the actual queues to the maximum link storage space on both phases equal. The mathematical development of the algorithm is described in terms of a Z transform analysis, and the conditions for stability are derived. The resulting mathematical model is linear with the exception of a saturation type nonlinearity caused by the physical requirement to limit split. A describing function analysis is used to demonstrate loop stability in the presence of the nonlinearity.
Some Aspects of a Switching Policy for Commuter Flow
Authors: Hartley M. G.
Published: October 2008

A wide range of signal switching policies may be adopted for control of traffic flow between a pair of intersections. One of the most important traffic situations is that in which rush-hour commuter traffic travels towards or away from a city center along radial roads. Under these circumstances opposing and tangential flow may be light. Earlier papers have shown that a modified form of the Dunne-Potts switching policy might be applied to pairs of intersections carrying commuter flow. Efficient and flexible operation of the system under a wide variety of flow conditions, and with the minimum of computer surveillance, was demonstrated. The present paper reports the results of further simulation experiments and discussed tentative solutions of some of the practical problems associated with the proposed scheme.
Transportation Network Policy Modeling with Goal Targets and Generalized Penalty Functions
Authors: Nagurney Anna , Ramanujam Padma
Published: October 2008

In this paper we develop a transportation network policy model that determines the equilibrium flow pattern and the transportation link tolls or taxes/subsidies in the presence of imposed transportation goals on the links of the network. The penalties (and subsidies) are functions of the deviations from the targets. The governing equilibrium conditions are shown to satisfy a variational inequality problem and existence and uniqueness results are presented using this methodology. A decomposition algorithm is proposed that resolves the problem into series of traffic network equilibrium problems and two simpler subproblems. Convergence results are also given. Finally, the algorithm is applied to numerical examples that illustrate how the model can be utilized for transportation pricing policy, as well as the numerical performance of the algorithm. This work extends recent research in spatial market policy modeling with goal targets on bipartite networks and with fixed penalties.
Models and Algorithms for Distribution Problems with Uncertain Demands
Authors: Cheung Raymond K.-M. , Powell Warren B.
Published: October 2008

We consider the problem of distributing goods from one or more plants through a set of warehouses in anticipation of forecasted customer demands. Two results are provided in this paper. First, we present a methodology for approximating stochastic distribution problems that are computationally tractable for problems of realistic size. Comparisons are made to standard deterministic formulations and shown to give superior results. Then, we compare logistics networks with varying degrees of redundancy represented by the number of warehouses which serve each customer. Overlapping service regions for warehouses provides additional flexibility to handle real-time demands. We quantify the expected savings that might result from such strategies.
The Multiple Vehicle TSP with Time Windows and Equity Constraints over a Multiple Day Horizon
Authors: Dell Robert F. , Batta Rajan , Karwan Mark H.
Published: October 2008

This paper considers the multiple vehicle traveling salesman problem cast over a multiple day routing scenario, with time windows and equity constraints. It develops an optimal column generation procedure and heuristic variations which solve test problems derived from the overnight delivery business. Extensive empirical testing indicates the judicious chose of a few routes for each day can incorporate equity at little or no additional cost.
Row-Column Aggregation for Rectilinear Distance p-Median Problems
Authors: Francis R. L. , Lowe T. J. , Rayco M. B.
Published: October 2008

For large-scale p-median problems, it is common to aggregate the demand points. This size reduction via aggregation makes the problem easier to solve, but introduces error. Doing this aggregation well is provably difficult. We present a median-row-column aggregation algorithm, MRC, with provable properties including an error bound, an (attainable) upper bound on the maximum objective function error. MRC adjusts spacing of individual rows and columns to exploit problem structure. For e demand points, r rows, and c columns, the algorithm has computational order e(c + r + log e), and order e storage requirements. We report encouraging computational experience.
Swapping Applications in a Daily Airline Fleet Assignment
Authors: Talluri Kalyan T.
Published: October 2008

An airline's schedule consists of a set of flight legs that it is scheduled to fly. A fleet assignment is an assignment of equipment types (such as a 757, 767, F100 etc.) to each of the flight legs. The fleet assignment is called a daily fleet assignment if the same assignment of equipment types is used every day of the week. The daily fleet assignment has to satisfy certain coverage, balance, and equipment availability constraints. Given a daily fleet assignment, we consider the problem of changing the assignment of a specified flight leg to a different equipment type while still satisfying all the constraints. We give a simple algorithm for making this swap that will not affect the equipment type composition of aircraft overnighting at the various stations. We describe two further applications of our swapping procedure in the airline schedule development process.
Technical Note—A Sequential Location Scheme for the Distance-Constrained Multifacility Location Problem on a Tree
Authors: Averbakh Igor , Berman Oded
Published: October 2008

The problem of locating p distinguishable facilities on a tree network with n nodes, subject to interfacility distance constraints, is considered. Each facility must be located within its own feasible region, that is selected in advance based on previous analysis. The main difference from the variants of the problem studied earlier is that more general feasible regions are allowed. A sequential location scheme for solving the problem is formulated, and sufficient conditions for the applicability of the scheme are presented. For the special case where the feasible regions are finite (sets of selected nodes of the tree), it is demonstrated that the sufficient conditions can be checked in O(pn) time; if they hold, the sequential location scheme can be implemented in O(np2) time (for the case of finite feasible regions).
Bibliographic Section
Authors: Southworth Frank , Wynter Laura
Published: October 2008

Gravity Models of Spatial Interaction Behavior, by Ashish Sen and Tony E. Smith, Springer-Verlag, Berlin, 1995, 572 pp.—reviewed by Frank Southworth

The Traffic Assisnment Problem: Models and Methods, Michael Patriksson, VSP, Utrecht, 1994, 223 pp.—Laura Wynter
Stochastic Modeling for Automated Material Handling System Design and Control
Authors: Johnson M. Eric , Brandeau Margaret L.
Published: October 2008

Material handling systems (MHSs) are micro-transportation systems that share many of the same challenges in design and operation as their larger-scale transportation counterparts. However, because of the automation technology employed in material handling, such systems also present many new challenges. Over the past decade, progress in automation technology has led to the replacement of many non-automated MHSs with automated systems. Use of an automated MHS can lead to significantly lower overall material handling cost, and thus overall production cost. However, the installation cost of such a system can be significant, and an MHS that does not function properly can lead to significant losses in productivity and profits. Analysis of design and control problems for such systems must take into account the fact that MHSs typically operate in a stochastic environment, with stochastic demands for material handling, flexibility in vehicle routing, variable processing times and other random elements. This paper reviews research on design and control of automated MHSs, with emphasis on analytical models that incorporate stochastic elements. We focus on models of automated storage and retrieval systems and automated guided vehicle systems. In addition to evaluating the existing literature, we describe areas where further research is needed.
Designing A Single-Vehicle Automated Guided Vehicle System with Multiple Load Capacity
Authors: Thonemann Ulrich W. , Brandeau Margaret L.
Published: October 2008

Automated guided vehicle systems (AGVSs) play an important role in today's factories. When properly designed and controlled they can provide significant cost savings in material handling cost and work-in-process inventory. We introduce an analytical approach for the design of a single-vehicle AGVS with multiple load capacity operating under a simple “go-when-filled” dispatching rule. The AGVS supplements an existing non-automated material handling system. It delivers containers with raw material from a central depot to workcenters on the factory floor. The demand of the workcenters and the time until delivery are stochastic. We develop a non-linear binary integer program to determine which workcenters warrant automated guided vehicle delivery and the consequent path layout subject to constraints on maximum allowable mean waiting time for material delivery. We present an efficient branch-and-bound algorithm that solves the model optimally. Without the analytical solution method, one would have to simulate the system for all possible configurations of open and closed workcenters in order to determine the optimal AGVS design—an approach likely to be infeasible for most problems. We also discuss how our model can be used to design a zoned multiple-vehicle AGVS where each zone is served by a single dedicated vehicle.
Heuristic Algorithms for the Handicapped Persons Transportation Problem
Authors: Toth Paolo , Vigo Daniele
Published: October 2008

We examine the problem of determining an optimal schedule for a fleet of vehicles used to transport handicapped persons in an urban area. The problem is a generalization of the well-known advance-request Pickup and Delivery Problem with Time Windows. Due to the high level of service required by this kind of transport, several additional operational constraints must be considered. The problem is NP-hard in the strong sense, and exact approaches for the solution of real-life problems (typically with hundreds of users to be transported) are not practicable. We describe a fast and effective parallel insertion heuristic algorithm which is able to determine good solutions for real-world instances of the problem in a few seconds on a personal computer. We also present a Tabu Thresholding procedure which can be used to improve the starting solution obtained by the insertion algorithm. The application of the proposed procedures to a set of real-life instances for the city of Bologna, involving about 300 trips each, is also discussed. The heuristic algorithms obtain very good results compared with the hand-made schedules, both in terms of service quality (all the service requirements are met) and overall cost.
TSS Dissertation Abstracts—Abstracts for the 1996 Transportation Science Section Dissertation Prize Competition
Authors: Jaillet Patrick
Published: October 2008

Report on the Transportation Science Section Dissertation Prize Competition for 1996. The awards were announced at the Fall meeting of INFORMS in Atlanta. The first prize winner was Dr. Tassio Carvalho of Princeton University for his thesis “Dynamic Control of Spatial Resource Allocation Problems.” Honorable mentions went to Dr. Christopher Caplice of the Massachusetts Institute of Technology, Dr. Kerry Malone of the Massachusetts Institute of Technology, and Dr. Erik Verhoef of the University of Amsterdam.
Transit Service and Path Choice Models in Stochastic and Time-Dependent Networks
Authors: Hickman Mark D. , Bernstein David H.
Published: October 2008

This paper develops a new path choice model that incorporates both time-dependent and stochastic transit service characteristics, and allows passengers to update path choice decisions while waiting. To develop this model, a new transit service model is proposed that represents route segments using a shuttle model. Such a model balances requirements for stochastic and time-dependent service modeling with the ability to aggregate to a larger transit corridor or network. This service model leads to a dynamic model of transit path choice, in which the passenger may wait until a vehicle is about to depart before making a boarding decision. A formal definition of this dynamic path choice model is given, and its differences with previous path choice models are noted. Based on this definition, two mathematical formulations of the dynamic model are developed. The first formulation assumes that the passenger will use the dynamic model for all possible vehicle departure times in the future, and is formulated as an optimal control problem. It is shown mathematically that this problem formulation is a less-constrained version of previous path choice models. However, because of some analytic and behavioral difficulties with this first model, a more well-behaved constrained formulation is also presented. A small corridor example demonstrates the significant differences in path choices and travel times between the constrained dynamic model and more traditional path choice models. Limitations of these dynamic path choice models are also discussed.
A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows
Authors: Taillard Éric , Badeau Philippe , Gendreau Michel , Guertin François , Potvin Jean-Yves
Published: October 2008

This paper describes a tabu search heuristic for the vehicle routing problem with soft time windows. In this problem, lateness at customer locations is allowed although a penalty is incurred and added to the objective value. By adding large penalty values, the vehicle routing problem with hard time windows can be addressed as well. In the tabu search, a neighborhood of the current solution is created through an exchange procedure that swaps sequences of consecutive customers (or segments) between two routes. The tabu search also exploits an adaptive memory that contains the routes of the best previously visited solutions. New starting points for the tabu search are produced through a combination of routes taken from different solutions found in this memory. Many best-known solutions are reported on classical test problems.
Facility Location and Reliable Route Planning in Hazardous Material Transportation
Authors: Helander Mary E. , Melachrinoudis Emanuel
Published: October 2008

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.
Low Probability—High Consequence Considerations in Routing Hazardous Material Shipments
Authors: Sherali Hanif D. , Brizendine Laora D. , Glickman Theodore S. , Subramanian Shivaram
Published: October 2008

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.
Objectives Derived form Viewing Hazmat Shipments as a Sequence of Independent Bernoulli Trials
Authors: Jin Honghua , Batta Rajan
Published: October 2008

This paper derives six objectives for routing hazardous material by viewing shipments as a sequence of independent Bernoulli trials. An example that compares these objectives is presented. Suitable approximations toward the use of these objectives in an optimization framework are provided. The paper also discusses the objectives from the viewpoint of their use to make actual hazardous material routing decisions.
On the Airline Schedule Perturbation Problem Caused by the Ground Delay Program
Authors: Luo Songjun , Yu Gang
Published: October 2008

The ground delay program is one of several programs that the Federal Aviation Administration is currently administering for efficient and equitable use of scarce airspace and airport capacity. In this paper, we study airline schedule perturbation problem caused by the ground delay program with the goal of improving airline dependability statistics defined by Department of Transportation as percentage of flights delayed more than 15 minutes. The problem is modeled as an integer program. To solve the model, we have derived valid inequalities for the integer programming formulation for strengthening the LP relaxation bound. The number of integer variables was reduced dramatically based on analysis of the model and its impact on the problem solubility was shown to be of significant importance. A heuristic procedure based on solving a restricted version of the model has been designed for finding good feasible solutions. Computational results indicate the effectiveness of the model reduction and the valid inequalities. Realistic problems have been solved to optimality within seconds on microcomputers. Improvement on airline dependability statistics has been shown to be substantial.
Instantaneous Power Peak Reduction and Train Scheduling Desynchronization in Subway Systems
Authors: Sansó Brunilde , Girard Pierre
Published: October 2008

In a subway system, when a train leaves one station to go to another, power consumption increases and, at one point, reaches a peak. When such peaks occur simultaneously, the total power peak of the system can be very large. On the other hand, if departures are totally desynchronized, it could affect the overall operation of the system. This paper deals with the problem of finding a procedure to desynchronize train departures during a typical rush hour operation so that overall power peaks are minimized and the frequency, safety, and operational constraints of the system are respected. A formulation of the problem and a heuristic approach are proposed. Results, using operational data from the Montreal subway system, are presented.
Modeling Vehicular Traffic Flow using M/G/C/C State Dependent Queueing Models
Authors: Jain Rajat , Smith J. Macgregor
Published: October 2008

In this paper, M/G/C/C state dependent queueing models are proposed for modeling and analyzing vehicular traffic flows. Congestion aspects of traffic flow are represented by introducing state dependent service rates as a function of number of vehicles on each road link. Analytical models for unidirectional and multisource flows are presented. Finally, queueing models to analytically determine the optimal capacity and performance measures of the road links are incorporated into a series of software programs available from the authors.
The Traffic Equilibrium Problem with Nonadditive Path Costs
Authors: Gabriel Steven A. , Bernstein David
Published: October 2008

In this paper we present a version of the (static) traffic equilibrium problem in which the cost incurred on each path is not simply the sum of the costs on the arcs that constitute that path. We motivate this nonadditive version of the problem by describing several situations in which the classic additivity assumption fails. We describe existence and uniqueness conditions for this problem, and we also present convergence theory for ageneric algorithm for solving nonadditive problems.
Selecting an Optimum Configuration of One-Way and Two-Way Routes
Authors: Drezner Zvi , Wesolowsky George O.
Published: October 2008

This paper considers a network with established transportation flows between nodes which take place along shortest paths. Links on the network may be one-way or two-way. One-way links, although lengthening some shortest paths, are faster, effectively reducing the travel time in the permitted direction. The objective is to select the optimum configuration of one-way and two-way routes to minimize the total flow-weighted transportation time (distance) in the system.
The Four-Day Aircraft Maintenance Routing Problem
Authors: Talluri Kalyan T.
Published: October 2008

Federal aviation regulations require that all aircraft undergo maintenance after flying a certain number of hours. Most major U.S. airlines observe the maintenance regulations by requiring that aircraft spend a night at a maintenance station after at most three or four days of flying. In addition, some airlines require that every aircraft goes through a special maintenance station for what is commonly called a balance check. Airlines usually schedule routine maintenance only at night so as not to cut into aircraft utilization. The maintenance routing problem is to find a routing of the aircraft that satisfies the short-term routine maintenance requirements. In Gopalan, R. and Talluri, K. T. (“The Aircraft Maintenance Routing Problem,” Opns. Res. in press) we modeled this problem as one of generating an appropriate directed graph (called a line-of-flight-graph), and of finding a special Euler Tour called the k-day Maintenance Euler Tour (k-MET, for k = 3, 4, …) in that directed graph—for finding a maintenance routing in which the aircraft would spend at most k days of flying before overnighting at a maintenance station and have an opportunity for a balance-check. In the same paper we gave a polynomial-time algorithm for finding a 3-MET, if one exists, in the directed graph. In this paper we consider the routing problem when the requirement is to overnight at a maintenance station after at most four days of flying and to undergo the balance check every n days, where n is the number of planes in the fleet of the equipment type under consideration. We show that this problem is NP-complete; in fact, that the k-MET problem is NP-complete for all k ≥ 4. When the number of maintenance stations is exactly one, we show that the 4-MET problem can be solved by solving an appropriate bipartite matching problem; and hence in polynomial time. As a corollary to this result, we show that when there is no balance check station visit requirement, the four-day routing problem, in a given LOF-graph, can be solved (without any restrictions on the number of maintenance stations) in polynomial time. We show how our polynomial-time algorithms for the 3-MET problem and the restricted 4-MET problem can be used to design effective heuristics for the 4-MET problem.
Implicit Enumeration of Hyperpaths in a Logit Model for Transit Networks
Authors: Nguyen Sang , Pallottino Stefano , Gendreau Michel
Published: October 2008

This paper investigates the application of a logit model to urban transit networks where every set of competitive transit lines is described by a particular graph structure called hyperpath. It shows that a sequential form of the logit model transcends the inherent limitations of the global form while retaining the algorithmic advantages similar to those obtained with the ordinary logit model for private vehicle networks.
Acceptance and Dispatching Policies for a Distribution Problem
Authors: Kleywegt Anton J. , Papastavrou Jason D.
Published: October 2008

A dynamic and stochastic distribution problem with a number of terminals and a fleet of vehicles is analyzed. Customers request the transportation of batches of loads between different origins and destinations. A request can be accepted or rejected; if the request is accepted, a reward is received. Holding costs for vehicles and loads at terminals as well as transportation costs are included in the model. The objective is to determine a policy for accepting transportation requests and for dispatching vehicles that maximizes the expected value (rewards minus costs) of operating the distribution system. A Markov decision process model is developed, optimal policies are characterized, and algorithms that exploit the structure of the problem are developed.
A Two-Stage Stochastic Network Model and Solution Methods for the Dynamic Empty Container Allocation Problem
Authors: Cheung Raymond K. , Chen Chuen-Yih
Published: October 2008

Containerized liner trades have been growing steadily since the globalization of world economies intensified in the early 1990s. However, these trades are typically imbalanced in terms of the numbers of inbound and outbound containers. As a result, the relocation of empty containers has become one of the major problems faced by liner operators. In this paper, we consider the dynamic empty container allocation problem where we need to reposition empty containers and to determine the number of leased containers needed to meet customers' demand over time. We formulate this problem as a two-stage stochastic network: in stage one, the parameters such as supplies, demands, and ship capacities for empty containers are deterministic; whereas in stage two, these parameters are random variables. We need to make decisions in stage one such that the total of the stage one cost and the expected stage two cost is minimized. By taking advantage of the network structure, we show how a stochastic quasi-gradient method and a stochastic hybrid approximation procedure can be applied to solve the problem. In addition, we propose some new variations of these methods that seem to work faster in practice. We conduct numerical tests to evaluate the value of the two-stage stochastic model over a rolling horizon environment and to investigate the behavior of the solution methods with different implementations.
Dynamic Control of Logistics Queueing Networks for Large-Scale Fleet Management
Authors: Powell Warren B. , Carvalho Tassio A.
Published: October 2008

Dynamic fleet management problems are normally formulated as networks over dynamic networks. Additional realism usually implies the inclusion of complicating constraints, typically producing exceptionally large integer programs. In this paper, we present for the first time the formulation of dynamic fleet management problems in an optimal control setting, using a novel formulation called a Logistics Queueing Network (LQN). This formulation replaces a single, large optimization problem with a series of very small problems that involve little more than solving a single sort at each point in space and time. We show that this approach can produce solutions that are within a few percent of a global optimum but provide for considerably more flexibility than standard linear programs.
An Approximate Model and Solution Approach for the Long-Haul Crew Pairing Problem
Authors: Barnhart Cynthia , Shenoi Rajesh G.
Published: October 2008

The crew pairing problem requires the coverage of a set of long-haul flights by a minimum cost set of crew pairings. A crew pairing is a sequence of flights flown by one crew, starting and ending at the same location, and satisfying a variety of work regulations and collective bargaining agreements. We present a new solution approach that solves first an approximate model of the problem and then uses its solution as an advanced start solution for conventional approaches. Using data provided by a long-haul airline, we demonstrate that our new approach can be used with a deadhead selector to identify deadheads quickly that might improve significantly the quality of the crew pairing solution. Deadheads, flights to which crews are assigned as passengers, reposition crews for better utilization. We speed up the solution process by using our advanced start solution and by quickly providing good lower bounds on the optimal solution values. Our experiments show that the lower bounds are on average within 0.85% of the optimal solution value. Further, we show that compared to existing methods, we reduce solution costs and run times by an average of 20% and over 80%, respectively.
Railway Timetabling Using Lagrangian Relaxation
Authors: Brännlund U. , Lindberg P. O. , Nõu A. , Nilsson J.-E.
Published: October 2008

We present a novel optimization approach for the timetabling problem of a railway company, i.e., scheduling of a set of trains to obtain a profit maximizing timetable, while not violating track capacity constraints. The scheduling decisions are based on estimates of the value of running different types of service at specified times. We model the problem as a very large integer programming problem. The model is flexible in that it allows for general cost functions. We have used a Lagrangian relaxation solution approach, in which the track capacity constraints are relaxed and assigned prices, so that the problem separates into one dynamic program for each physical train. The number of dual variables is very large. However, it turns out that only a small fraction of these are nonzero, which one may take advantage of in the dual updating schemes. The approach has been tested on a realistic example suggested by the Swedish National Railway Administration. This example contains 18 passenger trains and 8 freight trains to be scheduled during a day on a stretch of single track, consisting of 17 stations. The computation times are rather modest and the obtained timetables are within a few percent of optimality.
A Survey of Optimization Models for Train Routing and Scheduling
Authors: Cordeau Jean-François , Toth Paolo , Vigo Daniele
Published: October 2008

The aim of this paper is to present a survey of recent optimization models for the most commonly studied rail transportation problems. For each group of problems, we propose a classification of models and describe their important characteristics by focusing on model structure and algorithmic aspects. The review mainly concentrates on routing and scheduling problems since they represent the most important portion of the planning activities performed by railways. Routing models surveyed concern the operating policies for freight transportation and railcar fleet management, whereas scheduling models address the dispatching of trains and the assignment of locomotives and cars. A brief discussion of analytical yard and line models is also presented. The emphasis is on recent contributions, but several older yet important works are also cited.
Airline Yield Management with Overbooking, Cancellations, and No-Shows
Authors: Subramanian Janakiram , Stidham Shaler , Lautenbacher Conrad J.
Published: October 2008

We formulate and analyze a Markov decision process (dynamic programming) model for airline seat allocation (yield management) on a single-leg flight with multiple fare classes. Unlike previous models, we allow cancellation, no-shows, and overbooking. Additionally, we make no assumptions on the arrival patterns for the various fare classes. Our model is also applicable to other problems of revenue management with perishable commodities, such as arise in the hotel and cruise industries. We show how to solve the problem exactly using dynamic programming. Under realistic conditions, we demonstrate that an optimal booking policy is characterized by state- and time-dependent booking limits for each fare class. Our approach exploits the equivalence to a problem in the optimal control of admission to a queueing system, which has been well studied in the queueing-control literature. Techniques for efficient implementation of the optimal policy and numerical examples are also given. In contrast to previous models, we show that 1) the booking limits need not be monotonic in the time remaining until departure; 2) it may be optimal to accept a lower-fare class and simultaneously reject a higher-fare class because of differing cancellation refunds, so that the optimal booking limits may not always be nested according to fare class; and 3) with the possibility of cancellations, an optimal policy depends on both the total capacity and the capacity remaining. Our numerical examples show that revenue gains of up to 9% are possible with our model, compared with an equivalent model omitting the effects of cancellations and no-shows. We also demonstrate the computational feasibility of our approach using data from a real-life airline application.
A Mathematical Programming Approach for the Solution of the Railway Yield Management Problem
Authors: Ciancimino A. , Inzerillo G. , Lucidi S. , Palagi L.
Published: October 2008

Railway passenger transportation plays a fundamental role in Europe, particularly in view of the growing number of trains offering valuable services such as high speed travel, high comfort, etc. Hence, it is advantageous to submit seat inventories to a Yield Management system to get the maximum revenue. We consider a deterministic linear programming model and a probabilistic nonlinear programming model for the network problem with non-nested seat allocation. A first comparative analysis of the computational results obtained by the two models, both in terms of the overall expected revenue and in terms of CPU time, is carried out. Furthermore, we describe a new nonlinear algorithm for the solution of the probabilistic nonlinear programming model that exploits the structure of the optimization problem. The numerical results obtained on a set of real data show that, for this class of problems, this algorithm is more efficient than other standard algorithms for nonlinear programming problems.
Dynamic Pricing in Airline Seat Management for Flights with Multiple Flight Legs
Authors: You Peng-Sheng
Published: October 2008

Consider a multiple booking class airline-seat inventory control problem that relates to either a single flight leg or to multiple flight legs. During the time before the flight, the airline may face the problems of (1) what are the suitable prices for the opened booking classes, and (2) when to close those opened booking classes. This work deals with these two problems by only using the pricing policy. In this paper, a dynamic pricing model is developed in which the demand for tickets is modeled as a discrete time stochastic process. An important result of this work is that the strategy for the ticket booking policy can be reduced to sets of critical decision periods, which eliminates the need for large amounts of data storage.
A Randomized Linear Programming Method for Computing Network Bid Prices
Authors: Talluri Kalyan , van Ryzin Garrett
Published: October 2008

We analyze a randomized version of the deterministic linear programming (DLP) method for computing network bid prices. The method consists of simulating a sequence of realizations of itinerary demand and solving deterministic linear programs to allocate capacity to itineraries for each realization. The dual prices from this sequence are then averaged to form a bid price approximation. This randomized linear programming (RLP) method is only slightly more complicated to implement than the DLP method. We show that the RLP method can be viewed as a procedure for estimating the gradient of the expected perfect information (PI) network revenue. That is, the expected revenue obtained with full information on future demand realizations. The expected PI revenue can, in turn, be viewed as an approximation to the optimal value function. We establish conditions under which the RLP procedure provides an unbiased estimator of the gradient of the expected PI revenue. Computational tests are performed to evaluate the revenue performance of the RLP method compared to the DLP.
Yield Management Impacts on Airline Spill Estimation
Authors: Belobaba Peter P. , Farkas András
Published: October 2008

The correct estimation of spill, or passenger demand turned away, is an integral part of the determination of optimal aircraft capacities in the airline fleet assignment process. While making advances in the solution of the large-scale fleet assignment optimization problem, airlines have continued to use an aggregate approach to spill estimation. This aggregate approach ignores the effects of yield management practices that have been widely implemented by airlines during the past decade. In this paper, we illustrate the importance of incorporating the effects of yield management booking limits into the methodology used to estimate both the number of passengers spilled at a given aircraft capacity and their associated revenue value. We describe an approach to spill estimation that makes use of the detailed demand information provided by yield management systems, and we present recursive algorithms that can be used to obtain more accurate spill estimates in cases when multiple booking classes are used. Numerical examples are presented to illustrate the extent to which the outcomes of the different estimation approaches differ, suggesting that these differences can be large enough to have an impact on optimal fleet assignment.
Optimization of Area Traffic Control for Equilibrium Network Flows
Authors: Chiou Suh-Wen
Published: October 2008

A bilevel programming approach is used to tackle an optimization problem for area traffic control and equilibrium flows. The signal timing plan is defined by common cycle time, and by starts and durations of greens. The system performance index is defined as the sum of a weighted linear combination of rate of delay and number of stops per unit time for all traffic streams, which is evaluated by the traffic model from TRANSYT. User equilibrium traffic assignment is formulated as a variational inequality problem. Approximate mathematical expressions for various components of the performance index and the average delay to a vehicle at the downstream junction in the TRANSYT model for both undersaturated and oversaturated links have been derived. For a locally optimal search, the gradient projection method is used in deciding whether feasible descent directions leading to a Karush–Kuhn–Tucker point, which is potentially a local optimum, can be identified. A global search heuristic is proposed in this paper by which successively better Karush–Kuhn–Tucker points can be found with reasonable computation effort. The mixed search procedure, including the locally optimal search and global search heuristic, is proposed. Encouraging results for Allsop and Charlesworth's network have confirmed that the approximately optimizing mixed search procedure in solving the area traffic control optimization problem can achieve substantially better results than does the nonoptimizing calculations of mutually consistent signal timings and link flows.
Synchronized Development of Production, Inventory, and Distribution Schedules
Authors: Fumero F. , Vercellis C.
Published: October 2008

An integrated optimization model for production and distribution planning is proposed, with the aim of optimally coordinating important and interrelated logistic decisions such as capacity management, inventory allocation, and vehicle routing. The integrated model is solved via Lagrangean relaxation and both lower bounds and heuristic feasible solutions are obtained. Computational results on test problems of various sizes are provided to show the effectiveness of the proposed solution scheme. Moreover, the feasible solution obtained is compared to that generated by an alternative decoupled approach in which a production plan is first developed and a distribution schedule is consequently derived. Computational results seem to indicate a substantial advantage of the synchronized approach over the decoupled decision process.
Heavy Traffic Analysis of the Dynamic Stochastic Inventory-Routing Problem
Authors: Reiman Martin I. , Rubio Rodrigo , Wein Lawrence M.
Published: October 2008

We analyze three queueing control problems that model a dynamic stochastic distribution system, where a single capacitated vehicle serves a finite number of retailers in a make-to-stock fashion. The objective in each of these vehicle routing and inventory problems is to minimize the long run average inventory (holding and backordering) and transportation cost. In all three problems, the controller dynamically specifies whether a vehicle at the warehouse should idle or embark with a full load. In the first problem, the vehicle must travel along a prespecified (TSP) tour of all retailers, and the controller dynamically decides how many units to deliver to each retailer. In the second problem, the vehicle delivers an entire load to one retailer (direct shipping) and the controller decides which retailer to visit next. The third problem allows the additional dynamic choice between the TSP and direct shipping options. Motivated by existing heavy traffic limit theorems, we make a time scale decomposition assumption that allows us to approximate these queueing control problems by diffusion control problems, which are explicitly solved in the fixed route problems, and numerically solved in the dynamic routing case. Simulation experiments confirm that the heavy traffic approximations are quite accurate over a broad range of problem parameters. Our results lead to some new observations about the behavior of this complex system.
Multimodal Express Package Delivery: A Service Network Design Application
Authors: Kim Daeki , Barnhart Cynthia , Ware Keith , Reinhardt Gregory
Published: October 2008

The focus of this research is to model and solve a large-scale service network design problem involving express package delivery. The objective is to find the cost minimizing movement of packages from their origins to their destinations, given very tight service windows, limited package sort capacity, and a finite number of ground vehicles and aircraft. We have developed a model for large scale transportation service network design problems with time windows. With the use of route-based decision variables, we capture complex cost structures and operating regulations and policies. The poor linear programming bounds limit our ability to solve the problem, so we strengthen our linear programming relaxation by adding valid inequalities. By exploiting problem structure using a specialized network representation and applying a series of novel problem reduction methods, we achieve dramatic decreases in problem size without compromising optimality of the model. Our solution optimization approach synthesizes column and row generation optimization techniques and heuristics to generate solutions to an express package delivery application containing hundreds of thousands of constraints and billions of variables, using only a small fraction of the constraint matrix. The results are potential savings in annual operating costs of tens of millions of dollars, reductions in the fleet size required, dramatic decreases in the time required to develop operating plans, and scenario analysis capabilities for planners and analysts. Through this and additional computational experiments, we conclude that, although state-of-the-art integer programming methods can work well for relatively small, uncongested service network design problems, they must be used in concert with heuristics to be effective for large-scale, congested problems encountered in practice.
The Effects of Trailer Scheduling on the Layout of Freight Terminals
Authors: Gue Kevin R.
Published: October 2008

Supervisors in a less-than-truckload freight terminal establish material flows inside the terminal by assigning incoming trailers to open doors. A common scheduling strategy is to look ahead into the queue of incoming trailers and assign them to doors to minimize worker travel. We develop a model of the resulting material flows and use it to construct layouts that exploit this type of scheduling policy. Based on data from a test site, our results suggest that look-ahead scheduling alone can reduce labor costs due to travel by 15–20% compared to a first-come–first-served policy. Layouts constructed with the material flow model provide further savings of 3–30% in labor cost due to travel, depending on the mix of freight on incoming trailers and the length of the queue of trailers from which the supervisor makes assignments.
A Grid Travel Time Model
Authors: Beimborn Edward A.
Published: October 2008

A model is developed to determine travel times between points in an urban area with a limited amount of input. The model uses a network consisting of grid shaped links and high speed, freeway links. The travel time over the grid shaped links is computed internally using a macroscopic description of travel velocities and paths. A minimum time algorithm is applied to the network to find the minimum travel times between all points in the network. A test of the procedure showed that the results of the grid travel time model closely agreed with travel times produced by the standard detailed network method. The grid model uses substantially less input and performs its computations in a very short period of time. It is possible to develop a model that closely agrees with the detailed network model with even greater simplification. The procedure developed seems to have promise for a number of applications in the transportation planning process.
Erratum—“Sherratt's Model and Commuter Travel”
Authors: Wilkins C. A.
Published: October 2008

Erratum to a formula given in Transportation Science 3, 93–98, 1969.