bluuebunny/crossref_metadata_2025 huggingface dataset:
Dynamic Processes and Equilibrium in Transportation Networks: Towards a Unifying Theory
Authors: Cantarella G. E. , Cascetta E.
Published: October 2008

Traditionally, traffic assignment models, both for within-day static and dynamic demand, have been formulated following an equilibrium approach in which a state ensuring internal consistency between demand (flows) and costs is sought. However, equilibrium analysis is significant under some assumptions on its “representativeness” (coincidence or closeness with the actual attractor of the system) and analytical properties, such as existence, uniqueness, and stability. Moreover, transients due to modifications of demand and/or supply cannot be simulated through equilibrium models, nor can a statistical description of the state of the system, i.e. means, modes, moments and, more generally, frequency distributions of flows over time be obtained. In this paper, interperiodic (day-to-day) dynamic modeling of transportation networks is addressed following two different approaches, namely deterministic and stochastic processes. In both cases several theoretical results are shown by making use of a formal framework covering most models discussed in the literature as well as some possible extensions. Most of the results reported can be extended to cover within-day dynamic models but these models are not explicitly dealt with. Within the framework of deterministic processes the relevance of day-to-day dynamic models for demand/supply interaction in comparison with the traditional user equilibrium approach is discussed, and conditions for coincidence of fixed-point attractors and equilibrium states are stated. Conditions for existence and uniqueness of fixed-point attractors are proposed, generalizing and extending those presented in the literature for user equilibrium. Conditions for stability of both fixed-points and equilibrium states were formulated by making use of results from non-linear dynamic system theory. Moreover, it is possible to devise a new family of “dynamic” algorithms which simulate the system convergence to a fixed-point in order to obtain an equivalent equilibrium state, as opposed to conventional “optimisation” algorithms. In this case the fixed-point stability analysis can be viewed as a convergence analysis for the algorithms specified this way. Conditions for stochastic process regularity are proposed ensuring, among other things, existence and uniqueness of a stationary probability distribution of system states. These conditions generalize and extend results presented in the literature to a wider class of possible dynamic models. Relationships between a deterministic process, together with corresponding fixed-points or equilibrium states, and stochastic probability distribution are also briefly addressed. Finally, some numerical examples confirming theoretical results are reported for a small test network.
Computational Approaches to Stochastic Vehicle Routing Problems
Authors: Bertsimas Dimitris , Chervi Philippe , Peterson Michael
Published: October 2008

We report computational test results for several graph-based a priori heuristics for the Euclidean plane versions of two well-known stochastic optimization problems, the probabilistic traveling salesman problem (PTSP) and the probabilistic (or stochastic) vehicle routing problem (PVRP). These heuristics are termed a priori because they design vehicle routes prior to realization of demands. Our tests compare the quality of such solutions to sample averages of a posteriori solutions of the deterministic realizations—the underlying TSPs and VRPs. Our results indicate that the simplest implementations give average cost performance within 5% of the latter, while the best implementations show a gap of only about 1%. Since running times are modest, we conclude that the a priori approaches offer a large potential benefit to the practitioner seeking to obtain good performance in a situation where solving repeated deterministic instances of the TSP or VRP is impractical or otherwise undesirable.
Properties of Vehicle-Actuated Signals: I. One-Way Streets
Authors: Newell Gordon F.
Published: October 2008

Fluid and diffusion queuing approximations are used to analyze the behavior of vehicle-actuated signals at the intersection of two one-way streets at which there is no turning traffic. The arriving traffic is assumed to be a stationary stochastic process with a flow rate just slightly below that which saturates the intersection. Certain qualitative properties of the queues suggests that to minimize delay the signal should (in most cases) switch as soon as the queue vanishes, defined roughly as the time when the expected flow rate across the intersection drops below the discharge rate of a queue. The mean and variance of the cycle time and the mean delay are evaluated for this strategy. The average delay per car is shown to be less than for a fixed-cycle signal by about a factor of 3. The distribution of cycle time is shown to have approximately a Γ distribution.
A Stochastic Multiperiod Multimode Transportation Model
Authors: Midler Joseph L.
Published: October 2008

This paper develops a dynamic programming model for selecting an optimal combination of transportation modes over a midtiperiod planning horizon. The formulation explicitly incorporates uncertainty regarding future requirements or demands for a number of commodity classes. In addition to determining the optimal modes to employ, the model assigns individual commodity classes to various modes, determines which supply points serve which destinations, and reroutes carriers from destinations to alternative sources where they will be most effective. The model is formulated as an optimal discrete time stochastic control problem where cost is quadratic and dynamic equations linear in the state and control variables. This model may be solved in closed form by an efficient dynamic programming algorithm that permits the treatment of relatively large scale systems. Also developed is an alternative, generally suboptimal method of solution, based upon solving a sequence of convex programming problems over time. This technique may be employed for a more general class of problems. In both methods the use of “shadow prices” that arise is discussed.
Letter to the Editor—Polar and Rectangular Road Networks for Circular Cities
Authors: Holroyd E. M.
Published: October 2008

The main purpose of this note is to point out that the conclusion that the polar network gives shorter average distances than the rectangular network may be extended to any city possessing circular symmetry in which origins and destinations of journeys are distributed independently.
Scheduling Local and Express Service
Authors: Nemhauser George L.
Published: October 2008

A common carrier transportation service, say a train, operates between points A and B. There are two classes of service—an express that goes directly from A to B and a local that makes one or more intermediate stops. The local, quite naturally, takes longer than the express. A model is developed for finding a jointly optimal schedule of local and express service. The model is solved by dynamic programming.
Properties of Vehicle-Actuated Signals: II. Two-Way Streets
Authors: Newell G. F. , Osuna E. E.
Published: October 2008

The methods of analysis used in part I are extended to the analysis of a vehicle-actuated signal at the intersection of two two-way streets (four-way intersection) at which there is no turning traffic. The main conclusion is that the high efficiency of a vehicle-actuated signal as compared with a fixed-cycle signal for one-way streets as discussed in part I, does not necessarily extend to the case of two-way streets. In particular, if the flows in opposite direction on the two-way street are nearly equal and the intersection is nearly saturated, then it is very inefficient (even worse than a fixed-cycle) for a vehicle-actuated signal to follow a policy of holding a signal green until the last of the two discharging queues has vanished (it is even worse to switch when only one queue has vanished). In all cases, the competition between incompatible desirable policies for the two opposing traffic streams leads to compromise strategies that give considerably higher delays on all approaches than occurs on one-way streets.
A Study of Gate Use at Honolulu International Airport
Authors: Edwards Jack W. , Newell Gordon F.
Published: October 2008

Records of actual aircraft arrival times, departure times, and gate occupancies at Honolulu International Airport are analyzed to determine what factors influence gate requirements. Aircraft movements were decomposed into scheduled and nonscheduled operations. The former were compared with the scheduled arrival and departure times as given in the International Airline Guide. An analysis of data for three Saturdays over the 24-hour day showed that actual gate requirements correspond closely to scheduled requirements. The average variance to mean ratio for number of gates occupied at corresponding times on the three days was about 0.14 (if arrivals and departures were completely random, this would have a value of 1). A similar analysis for number of gates occupied by nonscheduled aircraft agreed very well with a Poisson distribution.
The Multiple Terminal Delivery Problem with Probabilistic Demands
Authors: Tillman Frank A.
Published: October 2008

A heuristic approach is presented for solving the multiterminal delivery problem with constraints on the system and probabilistic demands. The algorithm is basically the same whether a commodity is being collected or delivered. This is a practical method that results in “near optimal” solutions to a difficult problem.
A Comparison of Motorist Delays for Different Merging Strategies
Authors: McNeil D. R. , Smith J. T.
Published: October 2008

Investigations of motorist delays at the intersection of a major and minor road have involved variations of one or the other of two merging strategies: (i) Miller's (Miller, A. J. 1961. A queueing model for road traffic flow. J. R. Statist. Soc. B 23 64–75.) model that assumes that a minor-road motorist makes consecutive decisions consistently, and (ii) that of Weiss and Maradudin’ (Weiss, G. H., A. A. Maradudin. 1962. Some problems in traffic delay. Opns. Res. 10 74–104.) that assumes that a different, independent decision is made for each headway. In this paper we show that results for both models may be obtained easily, using the results of queuing theory, if certain reasonable assumptions are made. Simple expressions for the Laplace-Stieltjes transforms and means of the delays are derived in the case of independent major-road headways with a common, general distribution. For exponential headways, a numerical study shows the mean Miller delay to increase with the variation in the merge times, while the mean Weiss-Maradudin delay decreases. To illustrate the application of the expressions obtained, we investigate the reduction in the delay achieved by inserting a traffic island between two streams of major-road traffic.
Surveillance and Control of Tunnel Traffic by an On-Line Digital Computer
Authors: Gazis Denos C. , Foote Robert S.
Published: October 2008

An experimental surveillance and control system was in operation for one lane of the Lincoln Tunnel in New York City, during most of the year 1967. The system shared in the use of an IBM 7040 computer located at the IBM Research Center, forty miles away from the tunnel. The computer received via a telephone line signals from pairs of detectors located at four observation points along the tunnel. From these signals were determined the number of vehicles in the three sections of the tunnel between the four observation points, as well as the speed and throughput over these four points. The control system reduced the input of traffic into the tunnel when needed in order to prevent congestion, which has been known to reduce appreciably the throughput of the tunnel. It has been shown that knowledge of the exact number of vehicles in the three sections of the tunnel permits much more timely action than has been possible in the past, resulting in longer periods of sustained high flow at comfortable speeds. A discussion is given of the algorithms used for control, and an analysis of the experimental data is presented showing the improvement of controlled versus uncontrolled traffic.
The Oversaturated Signalized Intersection—Some Probabilistic Aspects
Authors: Thedéen Torbjörn
Published: October 2008

In two papers by C. J. Ancker, Jr., A. F. Gafarian, and R. K. Gray, the structure of the headways at the passage of an oversaturated signalized intersection were studied. The statistical analysis performed by these authors seems to confirm the hypothesis that these headways are independent random variables. In this paper we consider the following simple model. Let the spacings and reaction times of the vehicles stopped at the intersection all be independent and let the trajectory relative to the start position and start time be the same for all stopped vehicles. It is shown that the headways at the intersection are independent if and only if this trajectory is linear in a certain region specified in the paper.
A New Approach for Airport Access Surveys
Authors: Theodore Chris A. , Hodder James C.
Published: October 2008

Satisfactory solutions to congestion within and at the access routes of an airport may require data beyond the response to standard origin-destination questions and for all subgroups of airport users. An airport is considered as a closed system generating vehicle and person trips sampled within randomly or systematically selected observation time periods. Sampling at airport egress points may be most effective, but least feasible administratively. An alternative presented in this paper consists of developing a model for estimating the hourly volume of vehicle and person trips from machines counts at egress points and surveying four strata of airport users for collecting additional data with estimation based on post-stratification.
Evaluation of User Benefits Arising from Changes in Transportation Systems
Authors: Beckmann Martin J. , Wallace James P.
Published: October 2008

This paper investigates the welfare implication of changes in the transportation system in two special areas. The first is when the origin-destination demand for transportation may be assumed to be fixed and the second case is where, considering only work trips, origins may vary but destinations may not. A technique is described that could be used to forecast the new origin-destination demand resulting from a change in the transportation system. The technique also provides an appropriate measure of the welfare implications. A particular objective of the paper is to point out the pitfalls of using transportation (generalized) cost saving as a welfare measure whenever origin-destination demand may not be assumed fixed. In this situation it is shown that the welfare measure must take into consideration the benefit derived from the increased choice in available housing sites.
Optimal Locations for Centers in a Network
Authors: Goldman A. J.
Published: October 2008

The problem treated is that of locating n centers (processing facilities) in a network, so as to minimize the total transportation cost associated with their use. On the assumption that all movements occur between a vertex and a center nearest it, Hakimi has shown that only vertex locations for the centers need be considered. The present paper shows that this conclusion remains valid under alternative assumptions more appropriate for some applications.
Dynamic Systems, Variational Inequalities and Control Theoretic Models for Predicting Time-Varying Urban Network Flows
Authors: Friesz Terry L. , Bernstein David , Stough Roger
Published: October 2008

In this paper, we set forth certain axioms for a positive theory of dynamic urban network flows. We then show that mathematical models which fulfill these axioms may be created by adapting and extending certain fundamental notions from microeconomics and nonlinear systems theory. We further show that models created in this fashion, using concepts of fast and slow dynamic processes, may be manipulated into a variety of mathematical forms, thereby providing a synthesis of dynamic systems, variational inequality and control theoretic perspectives for predicting dynamic urban network flows. We close with a discussion of the implications of this synthesis for route guidance and intelligent vehicle infrastructure. Throughout, our presentation is at a conceptual level; the mathematical arguments are purposely not rigorous to embrace the widest possible readership.
Non-Convex Traffic Assignment on a Rectangular Grid Network
Authors: Newell G. F.
Published: October 2008

We consider here an idealized infinite rectangular grid of roads with a translationally symmetric O-D distribution. The total cost of travel on all links approaching each junction is approximated by a quadratic function of the four flows N, S, E, and W at that junction. If any of the four eigenvalues of this quadratic form is negative, the system optimal assignment problem is non-convex. If there are economies of scale (due possibly to construction costs) then all eigenvalues could be negative and the optimal assignment will lead to a hierarchical type of flow distribution (city streets, arterials, freeways, etc.). If costs arise only from congestion, however, it is possible that one or more of the eigenvalues is negative particularly if the cost of travel N, for example, is more sensitive to the flows E and/or W than to the flow N, or is more sensitive to the flow S than N. If it is more sensitive to the flow E-W an efficient assignment would seem to be one in which the space is divided into subregions such that in certain subregions traffic will be predominantly N or S and in other subregions it is predominately E or W. The optimal assignment is expected to be highly unstable to changes in the O-D distribution. If it is more sensitive to the flow S, a user optimal assignment may be stable and translationally symmetric but not the system optimal. The conclusion is that a non-convex assignment problem is not only a computational nightmare, but may be inconsistent with social objective or impractical to implement.
Optimal Allocation of Two Fixed Service Units Acting as M/G/1 Queues
Authors: Filippi Carlo , Romanin-Jacur Giorgio
Published: October 2008

We consider a districting problem placed in the general context of optimal allocation of urgent services in the presence of congestion. Customers are located in fixed points of a physical space and ask for urgent service according to Poisson processes. Two facilities, located in fixed points, supply the service by acting as M/G/1 queues. Each customer shall be assigned to one of the two facilities so that the mean expected response time is minimized, where the response time is the sum of the transportation time, the wait-in-queue time and the service time. We formalize the problem as an integer nonlinear programming model and we exactly solve it by a suitable branch-and-bound procedure. We show that the problem, if relaxed with respect to integrality constraints, can be reduced to an equivalent convex minimization problem with only one variable. Actually, each step of the branch-and-bound procedure is performed by quickly solving a continuous single-variable minimization problem. We randomly generate a large amount of instances of practical size, and we solve them on a workstation. Short computing times (<50 secs CPU for the worst experimented case) are evidenced. Since the problem is recognized to be NP-hard, we also suggest a simple heuristic method with low complexity.
Capacitated Location Problems on a Line
Authors: Mirchandani Prakash , Kohli Rajeev , Tamir Arie
Published: October 2008

This paper examines capacitated facility location problems on a straight line. To serve a customer, a facility must be located within a corresponding customer neighborhood. The fixed costs of locating facilities and the unit production costs of serving a customer from a facility can depend upon their locations on the line. We discuss the computational complexity of several capacitated location models. For capacitated problems on a line with non-nested customer intervals, and for general capacitated problems that satisfy a certain “monotonicity” property, we develop polynomial-time dynamic programming algorithms for (i) locating minimum cost facilities to serve all customers, and (ii) maximizing the profit by locating up to q facilities that serve some or all customers with idiosyncratic returns, penalties and demands.
TSS Dissertation Abstracts—Abstracts for the 1995 Transportation Science Section Dissertation Prize Competition
Authors: McGill Jeffrey I.
Published: October 2008

This is the report of the TSS dissertation prize committee on the 1995 competition. The first prize winner was Dr. Bernard Gendron for his thesis “Nouvelles Méthodes de Résolution de Problèmes de Conception de Réseaux et leur Implantation en Environnement Parallèle.” An honorable mention was awarded to Dr. Xu Jun Eberlein. Abstracts of seven dissertations in the competition are provided, in alphabetical order by author.
A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems
Authors: Murthy Ishwar , Sarkar Sumit
Published: October 2008

In this paper a form of the stochastic shortest path problem is considered where the optimal path is one that maximizes the expected utility which is concave and quadratic. The principal contribution of this paper is the development of a relaxation based pruning technique which is incorporated into a label setting procedure. The basic label setting procedure solves the problem by generating all Pareto-optimal paths. However, the number of such paths can grow exponentially with the size of the problem. The relaxation based pruning technique developed here is able to recognize and discard most of the Pareto-optimal paths that do not contribute to the optimal path. Our computational results show that the label setting procedure that incorporates the pruning technique consistently outperforms the basic label setting procedure, and is able to solve large problems very quickly.
Maintenance and Crew Considerations in Fleet Assignment
Authors: Clarke L. W. , Hane C. A. , Johnson E. L. , Nemhauser G. L.
Published: October 2008

Given a flight schedule, which is a set of flight segments with specified departure and arrival times, and a set of aircraft, the fleet assignment problem is to determine which aircraft type should fly each flight segment. The objective is to maximize revenue minus operating costs. In the basic fleet assignment problem considered by Hane et al. (Hane, C. A., C. Barnhart, E. L. Johnson, R. E. Marsten, G. L. Nemhauser, G. Sigismondi. 1995. The fleet assignment problem: Solving a large-scale integer program. Math. Programming 70 211–232.) a daily, domestic fleet assignment problem is modeled and solved with up to eleven fleets and 2,500 flight legs. This paper provides modeling devices for including maintenance and crew considerations into the basic model while retaining its solvability.
Production, Transportation, and Distribution Planning in a Multi-Commodity Tri-Echelon System
Authors: Pirkul Hasan , Jayaraman Vaidyanathan
Published: October 2008

To achieve high productivity in manufacturing plants and warehouses, an orderly and flexible flow of materials is essential. The interaction between the manufacturing plants and warehouses and issues related to distribution of multiple commodities to customers from warehouses represents a crucial step toward an integrated and systematic facilities' design. In this paper we develop a mixed integer programming model for the plant and warehouse location problem where the objective is to minimize the total transportation and distribution costs and the fixed costs for opening and operating plants and warehouses. We employ Lagrangian relaxation to the model, and also present a heuristic to produce an effective feasible solution for the problem. This problem has resulted from a study conducted by the authors for a large company manufacturing health-care products. The paper reports on the development of a model structure that can be used to predict the performance of the company.
Routing Two-Machine Flowshop Problems on Networks with Special Structure
Authors: Averbakh Igor , Berman Oded
Published: October 2008

We consider a version of the routing two-machine flowshop problem, where n jobs located at different nodes of a transportation network must be executed by two machines traveling between the jobs. Each job must be processed by both machines in the order, machine 1 first, machine 2 second. The goal is to minimize the makespan given that the total distance traveled must be as small as possible. Properties of the problem are discussed, and algorithms with complexity O(n log n) are developed for the problem on trees and cactuses.
Predicting On-Time Line-Haul Performance in Scheduled Railroad Operations
Authors: Hallowell Susan Fraley , Harker Patrick T.
Published: October 2008

This paper considers the problem of predicting on-time performance on a partially double-tracked rail line with scheduled traffic. In particular, the model presented herein explicitly incorporates the uncertainty in train departure times along with more complex line structures than have been considered previously. Extensive Monte Carlo simulations are used to validate the predictions made by the proposed model under an optimal meet/pass planning process.
A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem
Authors: Xu Jiefeng , Kelly James P.
Published: October 2008

We develop a new local search approach based on a network flow model that is used to simultaneously evaluate several customer ejection and insertion moves. We use this approach and a direct customer swap procedure to solve the well-known Vehicle Routing Problem. The capacity constraints are relaxed using penalty terms whose parameter values are adjusted according to time and search feedback. Tabu Search is incorporated into the procedure to overcome local optimality. More advanced issues such as intensification and diversification strategies are developed to provide effective enhancements to the basic tabu search algorithm. Computational experience on standard test problems is discussed and comparisons with best-known solutions are provided.
In Memoriam—William S. Vickrey, 1914–1996
Authors: Arnott Richard , de Palma André
Published: October 2008

Overview of life and numerous contributions of William S. Vickrey (1914–1996), recipient of the Nobel Price in Economics in 1996.
Analytical Models for Vehicle/Gap Distribution on Automated Highway Systems
Authors: Tsao H.-S. Jacob , Hall Randolph W. , Chatterjee Indrajit
Published: October 2008

Highway congestion has in recent years become a pervasive problem for urban and suburban areas alike. The concept of Automated Highway Systems is based on the belief that integration of sensing, communication, and control technologies into vehicles and highways can lead to a large improvement in capacity and safety without requiring a significant amount of additional highway right-of-way. A fundamental determinant of Automated Highway Systems capacity is the vehicle-following rule, the rule that governs the behavior of vehicles traveling along a common lane (e.g., the spacing between any two longitudinally adjacent vehicles). Vehicle following affects the longitudinal capacity (achievable flow within a lane), the lateral capacity (achievable flow between lanes) and the conflicting relationship between the longitudinal flow and lateral capacity. The issues are investigated by developing probabilistic models for vehicle/platoon and gap distributions, for vehicles that travel in platoons, in slots, or as free-agents. Mathematical models are also developed to estimate the completion time of a lane change, which can be used as a surrogate for the lateral capacity. Numerical results for the three major vehicle-following rules and their comparison are also provided.
An Endogenous Segmentation Mode Choice Model with an Application to Intercity Travel
Authors: Bhat Chandra R.
Published: October 2008

This article uses an endogenous segmentation approach to model mode choice. This approach jointly determines the number of market segments in the travel population, assigns individuals probabilistically to each segment, and develops a distinct mode choice model for each segment group. The author proposes a stable and effective hybrid estimation approach for the endogenous segmentation model that combines an Expectation-Maximization algorithm with standard likelihood maximization routines. If access to general maximum-likelihood software is not available, the multinomial-logit based Expectation-Maximization algorithm can be used in isolation. The endogenous segmentation model, and other commonly used models in the travel demand field to capture systematic heterogeneity, are estimated using a Canadian intercity mode choice dataset. The results show that the endogenous segmentation model fits the data best and provides intuitively more reasonable results compared to the other approaches.
Airline Scheduling for the Temporary Closure of Airports
Authors: Yan Shangyao , Lin Chung-Gee
Published: October 2008

The poor scheduling of flights or a fleet resulting from temporary closure of airports may cause a substantial loss of profit and decreased levels of service for airline carriers. This research develops a framework in order to help carriers handle schedule perturbations resulting from the temporary closure of airports. The framework is based on a basic model constructed as a time-space network from which several strategic network models are developed for scheduling. These network models are formulated as pure network flow problems or network flow problems with side constraints. The former are solved using the network simplex method whereas the latter are solved using a Lagrangian relaxation-based algorithm. To test how well the model may be applied in the real world, a case study regarding the international operations of a major Taiwan airline was performed. The results show that the framework could be useful in actual operations.
A General Fixed-Point Approach to Multimode Multi-User Equilibrium Assignment with Elastic Demand
Authors: Cantarella Giulio Erberto
Published: October 2008

This paper presents a fixed-point formulation of multi-mode multi-user equilibrium assignment with elastic demand. Users of different classes may have different behavioral characteristics as well as sets of available routes and modes. They may also behave according to different deterministic and/or probabilistic choice models with different utility specifications. Demand elasticity is dealt with without using the inverse of demand function; in addition, the mode choice can be explicitly dealt with. Conditions for existence and uniqueness of solutions are stated, which generalize and extend those in the literature. A general framework for solution algorithms is also developed, and a simple new algorithm is proposed to solve asymmetric (stochastic) multi-mode multi-user equilibrium with elastic demand.
Advances in the Optimization of Airline Fleet Assignment
Authors: Rushmeier Russell A. , Kontogiorgis Spyridon A.
Published: October 2008

We present an advanced model for the formulation and solution of large scale fleet assignment problems that arise in the scheduling of air transportation. Fleet assignment determines the type of aircraft to operate each flight in a given schedule, subject to a variety of side constraints, due to marketing, operational, maintenance and crew restrictions. We model the problem as mixed-integer multicommodity flow on networks encoding activities linking flight departures. We focus on fully representing flight connection possibilities, while accurately capturing complex operational rules. We also provide a unified framework for the expression of resource constraints via piecewise linear penalties, which permits a profitability-based tradeoff between operational goals and revenue. Computational results on actual schedules show that high quality assignments for one-day problems can be obtained within an hour of computation. The use of the model at USAir results in an annual benefit of at least $15 million.
A Generalized Traveling Salesman Problem Approach to the Directed Clustered Rural Postman Problem
Authors: Dror Moshe , Langevin André
Published: October 2008

In this paper, we examine the directed Clustered Rural Postman Problem (CRPP). The CRPP is a restricted version of the Rural Postman Problem in which each connected component of arcs to be serviced has to be completely serviced before servicing another component. We present an enumerative solution approach for the CRPP based on transforming the CRPP into a version of a Generalized Traveling Salesman Problem. This work also represents a simple yet elegant unifying view for some classes of arc and node routing problems.
Fully Loaded Direct Shipping Strategy in One Warehouse/N Retailer Systems without Central Inventories
Authors: Jones Philip C. , Qian Tianbing
Published: October 2008

In this paper, we consider one warehouse/multiple retailer systems with transportation costs. The planning horizon is infinite and the warehouse keeps no central inventory. It is shown that the fully loaded direct shipping strategy is optimal among all possible shipping/allocation strategies if the truck capacity is smaller than a certain quantity, and a bound is provided for the general case.
Decomposition of Path Choice Entropy in General Transport Networks
Authors: Akamatsu Takashi
Published: October 2008

This paper shows that the LOGIT type stochastic assignment/stochastic user equilibrium assignment can be represented as an optimization problem with only link variables. The conventional entropy function defined by path flows in the objective can be decomposed into a function consisting only of link flows. The idea of the decomposed formulation is derived from a consideration of the most likely link flow patterns over a network. Then the equivalence of the decomposed formulation to LOGIT assignment is proved by using the Markov properties that underlie Dial's algorithm. Through the analyses, some useful properties of the entropy function and its conjugate dual function (expected minimum cost function) have been derived. Finally, it is discussed that the derived results have a potential impact on the development of efficient algorithms for the stochastic user equilibrium assignment.
On The Overspecification of Multinomial and Nested Logit Models Due to Alternative Specific Constants
Authors: Bierlaire Michel , Lotan Tsippy , Toint Philippe
Published: October 2008

Discrete choice models as demand forecasting techniques have been used for transportation applications for more than thirty years. The multinomial and nested logit models are probably the most widely applied in this context. Alternative specific constants, although playing an important role in these models, have received very little attention in theoretical studies. In this paper, we try to fill this gap by providing an analysis of the overspecification caused by alternative specific constants to the log-likelihood function of multinomial and nested logit models. The theoretical results lead directly to a particular strategy of alternative specific constant specification, called here the orthogonal strategy. The analysis of the relationship between any two arbitrary strategies and the derivation of an interesting geometrical property of the orthogonal strategy provide a motivation to prefer the latter.
An Exact Algorithm for the Vehicle Routing Problem with Backhauls
Authors: Toth Paolo , Vigo Daniele
Published: October 2008

The Vehicle Routing Problem with Backhauls is an extension of the capacitated Vehicle Routing Problem where the customers' set is partitioned into two subsets. The first is the set of Linehaul, or Delivery, customers, while the second is the set of Backhaul, or Pickup, customers. The problem is known to be NP-hard in the strong sense and finds many practical applications in distribution planning. In this paper we consider, in a unified framework, both the symmetric and the asymmetric versions of the vehicle routing problem with backhauls, for which we present a new integer linear programming model and a Lagrangian lower bound which is strengthened in a cutting plane fashion. The Lagrangian lower bound is then combined, according to-the additive approach, with a lower bound obtained by dropping the capacity constraints, thus obtaining an effective overall bounding procedure. A branch-and-bound algorithm, reduction procedures and dominance criteria are also described. Computational tests on symmetric and asymmetric instances from the literature, involving up to 100 customers, are given, showing the effectiveness of the proposed approach.
An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows
Authors: Pesant Gilles , Gendreau Michel , Potvin Jean-Yves , Rousseau Jean-Marc
Published: October 2008

This paper presents a constraint logic programming model for the traveling salesman problem with time windows which yields an exact branch-and-bound optimization algorithm without any restrictive assumption on the time windows. Unlike dynamic programming approaches whose performance relies heavily on the degree of discretization applied to the data, our algorithm does not suffer from such space-complexity issues. The data-driven mechanism at its core more fully exploits pruning rules developed in operations research by using them not only a priori but also dynamically during the search. Computational results are reported and comparisons are made with both exact and heuristic algorithms. On Solomon's well-known test bed, our algorithm is instrumental in achieving new best solutions for some of the problems in set RC2 and strengthens the presumption of optimality for the best known solutions to the problems in set C2.
Shortest Path Algorithms: An Evaluation Using Real Road Networks
Authors: Zhan F. Benjamin , Noon Charles E.
Published: October 2008

The classic problem of finding the shortest path over a network has been the target of many research efforts over the years. These research efforts have resulted in a number of different algorithms and a considerable amount of empirical findings with respect to performance. Unfortunately, prior research does not provide a clear direction for choosing an algorithm when one faces the problem of computing shortest paths on real road networks. Most of the computational testing on shortest path algorithms has been based on randomly generated networks, which may not have the characteristics of real road networks. In this paper, we provide an objective evaluation of 15 shortest path algorithms using a variety of real road networks. Based on the evaluation, a set of recommended algorithms for computing shortest paths on real road networks is identified. This evaluation should be particularly useful to researchers and practitioners in operations research, management science, transportation, and Geographic Information Systems.
Real-Time Optimization of Containers and Flatcars for Intermodal Operations
Authors: Powell Warren B. , Carvalho Tassio A.
Published: October 2008

We propose a dynamic model for optimizing the flows of flatcars that considers explicitly the broad range of complex constraints that govern the assignment of trailers and containers to a flatcar. The problem is formulated as a logistics queueing network which can handle a wide range of equipment types and complex operating rules. The complexity of the problem prevents a practical implementation of a global network optimization model. Instead, we formulate a global model with the specific goal of providing network information to local decision makers, regardless of whether they are using optimization models at the yard level. Thus, our approach should be relatively easy to implement given current rail operations. Initial experiments suggest that a flatcar fleet that is managed locally, without the benefit of our network information, can achieve the same demand coverage as a fleet that is 10 percent smaller, but is managed locally with our network information.
Improved Empty Freight Car Distribution
Authors: Holmberg Kaj , Joborn Martin , Lundgren Jan T.
Published: October 2008

In this paper we consider the problem of distributing empty freight cars in a railway company. We describe and analyze the current planning process, identify the shortcomings of the process, and stress the importance of a reliable distribution process for satisfying customer demand and reducing capital costs. We show how the process can be improved using an optimization model which includes capacity constraints on the trains and adheres explicitly to the arrival and departure times of the trains. The optimization model can be characterized as a multicommodity network flow model with integer requirements. Computational tests show that the model can be solved in acceptable time for real size problems, and indicate that the model generates distribution plans that can improve the quality of the planning process.
Optimizing Auto-Carrier Loading
Authors: Agbegha Gerald Y. , Ballou Ronald H. , Mathur Kamlesh
Published: October 2008

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.
A Decomposition Approach to the Inventory Routing Problem with Satellite Facilities
Authors: Bard Jonathan F. , Huang Liu , Jaillet Patrick , Dror Moshe
Published: October 2008

This paper presents a comprehensive decomposition scheme for solving the inventory routing problem in which a central supplier must restock a subset of customers on an intermittent basis. In this setting, the customer demand is not known with certainty and routing decisions taken over the short run might conflict with the long-run goal of minimizing annual operating costs. A unique aspect of the short-run subproblem is the presence of satellite facilities where vehicles can be reloaded and customer deliveries continued until the closing time is reached. Three heuristics have been developed to solve the vehicle routing problem with satellite facilities (randomized Clarke-Wright, GRASP, modified sweep). After the daily tours are derived, a parametric analysis is conducted to investigate the tradeoff between distance and annual costs. This leads to the development of the efficient frontier from which the decision maker is free to choose the most attractive alternative. The proposed procedures are tested on data sets generated from field experience with a national liquid propane distributor.
The Operational Airline Crew Scheduling Problem
Authors: Stojković Mirela , Soumis François , Desrosiers Jacques
Published: October 2008

This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. The problem consists of modifying, as necessary, personalized planned monthly assignments of airline crew members during day-to-day operations. It requires covering, at minimal cost, all flight segments from a given time period with available crew while minimizing the disturbances of crew members. To generate modified pairings for selected crew members, both the classical crew pairing problem and the problem of constructing personalized monthly assignments must be treated simultaneously. An optimization approach is proposed for the problem in which the flight schedule is fixed and represents input data. The problem is mathematically formulated as a Set Partitioning type problem, and a column generation method embedded in a branch-and-bound search tree has been implemented to solve it. Good results, from the point of view of both solution times and achieved objectives, have been obtained on generated test problems. Because the solution time is reasonable, several different scenarios of the same problem may be solved. A final decision can then be made by considering all scenarios and choosing the one whose solution is the best in the given situation.
The Multiple Connections Multi-Airport Ground Holding Problem: Models and Algorithms
Authors: Navazio Lisa , Romanin-Jacur Giorgio
Published: October 2008

In recent years air traffic has dramatically increased without a corresponding development of airports. Therefore, airports' limited capacity causes air traffic congestion and consequent expensive delays. The only strategy that can be applied in the short term with low investments aims at the optimal management of present resources; its principal device is Ground Holding, which consists of delaying an aircraft take off whenever it is foreseen it will not land in time because of congestion. We consider a traffic situation with “multiple connections” or “banking,” i.e., the situation where some flights are assigned a set of “preceding” flights; no “successive” flight can start until all its preceding flights have landed. The problem consists of distributing delays to flights, so as to minimize the total delay cost, by respecting airport capacity, connections, and time constraints imposed by airlines. We construct an integer linear programming model and we solve it to optimality with CPLEX. Because the computation time is too high (hours) for real-world instances, we propose an alternative heuristic algorithm, which shows a very low computation time (seconds) and acceptable errors when tested on 30 realistic instances with strongly diversified data.
Scheduling of Time-Shared Jet Aircraft
Authors: Keskinocak Pinar , Tayur Sridhar
Published: October 2008

Motivated by a real application, we consider the following aircraft scheduling problem. At any time, the aircraft are at different locations or are serving a customer and new customer requests arrive, each consisting of a departure location, departure time, and destination. Our objective is to satify these requests (by subcontracting extra aircraft if necessary) at minimum cost under additional constraints of maintenance requirements and previously scheduled trips. We show that the jet aircraft scheduling problem is NP complete and discuss three special cases. We show that the second and third special cases are also NP complete. We provide a polynomial time network flow based algorithm for the first special case and a pseudo-polynomial time dynamic programming algorithm for the second special case. We formulate the problem as a 0–1 integer program and observe that most small and medium size problems can be solved by Cplex. For larger and difficult instances, we provide a fast heuristic with good performance.
Freight Handling Personnel Scheduling at Air Cargo Terminals
Authors: Nobert Yves , Roy Jacques
Published: October 2008

More than ever before, the airline industry must manage its operations very carefully if it is to adapt to the changes in its environment. One important planning problem is the scheduling of freight handling employees at air cargo terminals. Indeed, this area is particularly critical for achieving cost reductions while maintaining customer service levels. This paper presents a new model and an appropriate solution approach for the work-scheduling problem. In particular, a demand leveling procedure is introduced to take advantage of the flexibility that is often encountered in such problems. Experimental results obtained with actual data from a major airline are also presented.