bluuebunny/crossref_metadata_2025 huggingface dataset:
On the Modeling of Pedestrian Flow on the Jamarat Bridge
Authors: Selim Shokri Z. , Al-Rabeh Ala H.
Published: October 2008

During the Moslem pilgrimage season the Jamarat bridge becomes congested with pilgrims, due to space and time constraints. This paper aims at developing a model for regulating pedestrian flow into the bridge. The model may provide facility designers and managers with a quantitative tool for predicting the level of congestion at specific regions on the bridge given the specific demand flow data and a particular control strategy. Thus various alternatives for controlling the flow can be examined. The model is also a tool for determination of the optimal level of flow such that the number of persons in those specific regions does not exceed some predetermined limit. An optimization model is constructed and an example is included.
Locating Emergency Vehicle Bases When Service Time Depends on Call Location
Authors: Goldberg Jeffrey , Paz Luis
Published: October 2008

This paper deals with the problem of locating emergency vehicles in an urban area. We formulate an optimization model that extends previous work by allowing stochastic travel times, unequal vehicle utilizations, various call types, and service times that depend on call location. The basis of the model is a procedure for approximating the performance of spatially distributed queueing systems. In previous work the model has been validated using data from the Tucson Emergency Medical Services (EMS). We test the computational effectiveness of pairwise interchange heuristics on 192 test problems. Demand and service time components of the test data are generated using characteristics of the Tucson data set. For these test problems, simple pairwise interchange techniques yield reasonable solutions with little computational effort. Also, solutions obtained from the model differ from those generated using methods previously presented in the literature.
Optimization Models for Comparing Conventional and Subscription Bus Feeder Services
Authors: Chang Shyue Koong , Schonfeld Paul M.
Published: October 2008

Analytic models are developed and used in comparing fixed route conventional bus and flexible route subscription bus systems for providing feeder services to a single point (such as a transportation terminal). In the mathematical models for these two systems, vehicle size and service zone size are the optimizable decision variables, and total system cost, including operator and user costs, is the objective function to be minimized. Average cost per trip is the criterion used to determine which system is preferable and how it should be optimized in various circumstances. With an approximation for subscription services, closed form solutions for optimal vehicle size and service zone area are obtained for both alternatives. The analytic results for optimized conventional services indicate that constant ratios should be maintained at all demand densities between vehicle size and route spacing and between fleet size and user wait time. Analytic solutions are extended to conditions where (1) demand and costs are time dependent, requiring multiperiod optimization and (2) the maximum load factor may differ from 1.0 to allow for standees and stochastic demand fluctuations. A method for comparing the two systems when their service levels generate different passenger volumes is also presented. Sensitivity analyses indicate that the relative advantage of subscription bus services generally increases with smaller service areas, higher speeds, lower fixed bus cost, lower incremental costs of vehicle size, higher values of access and wait time, and lower values of in-vehicle time.
Technical Note—A Dynamic Programming Framework for the Global Flow Control Problem in Air Traffic Management
Authors: Wang Helen
Published: October 2008

This paper presents a network model which can serve as a framework for generating optimal global congestion-relieving strategies for the flow control problem in air traffic management. The general network model presented here addresses the global problem of optimally combining a number of local strategies to relieve multiple interdependent occurrences of congestion. While several algorithms and techniques have been or are being developed which deal with congestion at one air traffic control element for one time period, the actual flow control problem is concerned with congestion in a dynamic setting occurring at a number of different elements which are interrelated in a complex manner. The network model presented here is designed to work with the Enhanced Traffic Management System (ETMS) project under development at the Transportation Systems Center (TSC) for the Federal Aviation Administration (FAA).
Bibliographic Section
Authors: Mannering Fred L. , Cervero Robert , Goodwin Phil B.
Published: October 2008

Modelling Transport, by Juan de Dios Ortuzar and Luis G. Willumsen, John Wiley & Sons, West Sussex, England, 1990, 375 + xv pp.—reviewed by Fred L. Mannering.

Rail Mass Transit for Developing Countries, Institution of Civil Engineers, Thomas Telford, London, 1990, 397 pp.—reviewed by Robert Cervero.

Euromobile: Transport, Communications and Mobility in Europe, Edited by Peter Nijkamp, Shalom Reichman and Michael Wegener, Avebury Press, Aldershot, England, 1990, 413 pp.—reviewed by Phil B. Goodwin.
A Simulated Annealing Approach to the Network Design Problem with Variational Inequality Constraints
Authors: Friesz Terry L. , Cho Hsun-Jung , Mehta Nihal J. , Tobin Roger L. , Anandalingam G.
Published: October 2008

The equilibrium network design problem can be formulated as a mathematical program with variational inequality constraints. We know this problem is nonconvex; hence, it is difficult to solve for a globally optimal solution. In this paper we propose a simulated annealing algorithm for the equilibrium network design problem. We demonstrate the ability of this algorithm to determine a globally optimal solution for two different networks. One of these describes an actual city in the midwestern United States.
Obtaining Network Cost(s) from One Link's Output
Authors: Frank Marguerite
Published: October 2008

Consider user-optimization on a directed network whose link costs remain unevaluated, but are assumed to be positive affine symmetric functions of link flows. We focus instead on the equilibrium output variations, locally, of one arbitrary link resulting from variations in either its intrinsic cost or in the demand of the Origin/Destination pair under consideration. With only this local information as output, our algorithm generates, for that particular O/D-pair, the user equilibrium cost as a complete (piecewise-linear) function of O/D-demand, from any one initiating segment: such a segment may be obtained by an independent decomposition procedure.
Introduction to the Special Issue
Authors: Nagurney Anna
Published: October 2008

Introduction to the Special Issue on Network Equilibrium.
Parallel and Serial Successive Overrelaxation for Multicommodity Spatial Price Equilibrium Problems
Authors: Güder Faruk , Morris James G. , Yoon Seok H.
Published: October 2008

Computational experience is reported for various serial implementations of successive overrelaxation (SOR) applied to a linear multicommodity spatial price equilibrium problem posed as linear complementarity problem. Computational schemes that neglect the vast majority of the variables during most iterations are shown to be relatively efficient. A parallel implementation based on the same neglect is shown to exhibit encouraging average speedup over the single processor case. The SOR approach is shown empirically to converge for nonsymmetric problems. Dense network problems with up to 60 regions (each a potential supply or demand region) and 10 commodities, representing on the order of 36,000 variables, as well as sparse network problems with up to 140 regions, are typically solved in a few seconds of CPU time.
A Dynamic Traffic Assignment Model and a Solution Algorithm
Authors: Drissi-Kaïtouni Omar , Hameda-Benchekroun Abdelhamid
Published: October 2008

This paper is concerned with the modeling of the Dynamic Traffic Assignment Problem (DTAP) for predicting the flows of urban transportation networks, mainly at peak periods. During the past 40 years, most of the research has been for the Static Traffic Assignment Problem (STAP) where it is assumed that demand is constant over time. This assumption is realistic for the analysis of intercity freight transportation networks over long periods of time, but it does not hold in an urban area, for simulating the flow variations during short periods (peak hours). Hence, during the past 20 years, the interest to the DTAP has been increasing. The seventies have been a transition period between heuristic models (where the demand is assigned to instantaneous minimum cost paths), and optimization models that take into account the demand over the whole study horizon of time, but all of them incorporate important limitations (only one destination; unrealistic conditions on the cost functions so that the flow “reaches” the destination; possible violation of the link capacities; etc.). In this paper, we propose a Dynamic Traffic Assignment Model which is mainly based on the following assumption: the time spent by a vehicle on a link may be decomposed into a fixed travel time plus a waiting time. The fixed travel time corresponds to the free or uncongested travel time over the link. Then the vehicle is put in an exit queue (which resides on the same link) until it becomes possible to enter a forward link; this decision is based on the link costs and their capacities. We show that this model leads to a network structure (a temporal expansion of the base network, including the queues) and therefore the DTAP may be viewed as a “simple” STAP over the expanded network. Hence, all the theories developed during the past 40 years for the STAP may be used to solve the DTAP.
Stochastic Inventory Routing: Route Design with Stockouts and Route Failures
Authors: Trudeau Pierre , Dror Moshe
Published: October 2008

The stochastic inventory routing problem involves the distribution of a commodity such as heating oil over a long period of time to a large set of customers. The customers maintain a local inventory of the commodity which they consume at a daily rate. Their consumption varies daily and seasonally and their exact demand is known only upon the arrival of the delivery vehicle. This paper presentes a detailed analysis of this problem incorporating the stochastic nature of customers' consumptions and the possibility of route failures when the actual demand on a route exceeds the capacity of a vehicle. A number of solution procedures are compared on a large set of real life data for a period of 12 consecutive weeks. The winning strategy, though computationally more expensive, provides the best system performance and reduces (almost eliminates) the stockout phenomena.
Interacting New Facilities and Location-Allocation Problems
Authors: Aykin Turgut , Brown Gary F.
Published: October 2008

This paper examines the location-allocation problems involving interacting new facilities on a plane and on a sphere. Specifically, we consider a situation in which flows between the existing facilities are channeled through the new facilities. The new facilities interact and the level of interactions between them is determined by the flows between the existing facilities they serve. Although special cases of this problem with one, two and three new facilities on a plane have been considered by the researchers, the general problem with p new facilities remains unsolved. In this study, we formulate this problem both on a plane and on a sphere. An algorithm that solves the location and the allocation phases separately in an iterative manner is formulated for the planar problem. Modifications needed in the algorithm for solving the spherical problem are discussed. Computational results with two versions of the proposed algorithm spanning a range of problem sizes are reported.
Variational Problems for Determining Optimal Paths of a Moving Facility
Authors: Sherali Hanif D. , Kim Seong-In
Published: October 2008

This paper is concerned with some variational calculus/optimization problems involving the determination of constrained optimal path functions or routes of a single moving facility, which traverses a region encompassing a set of existing facilities. Situations of this type may involve a reconnaisance plane maintaining a surveillance of certain locations, a patrol car traveling in radio contact with several stations with the possibility of being dispatched to answer service calls originating over several designated regions, or an aircraft determining a flight plan over a region containing enemy missile sites. We formulate the general problem of maximizing total benefits, or maximizing the benefits per unit travel time, subject to constraints on the travel path function. The specific problems analyzed involve a direct distance related benefit (or cost) function, employing rectilinear or squared-Euclidean distance measures, and they constrain the paths to be straight lines between parallel boundaries or across rectangular regions, with both ends free or with one end fixed, or to be general paths between fixed end-points. In each case, the problem is reduced to a finite dimensional optimization problem. Illustrative examples and computational results on a personal computer are provided, and several extensions are proposed for future research.
Technical Note—On the Complexity of Some Classes of Location Problems
Authors: Tamir Arie
Published: October 2008

We present complexity bound improvements for four location models: the planar 1-center rectilinear roundtrip location model, the 1-center rectilinear asymmetric distance location model, the equity maximizing facility location model, and the maximal direct covering tree problem.
The Existence of Equilibria in the 3-Facility Hotelling Model in a Tree
Authors: Eiselt H. A. , Laporte Gilbert
Published: October 2008

This paper considers the location of three market share maximizing facilities on a tree network. Assume that the demand originates at the vertices of the tree and that the facilities can locate at the vertices or on the edges of the tree. It is shown that the problem may have agglomerated, dispersed, or have no equilibria at all. Conditions for these cases are developed in the paper.
Competitive Location Models: A Framework and Bibliography
Authors: Eiselt H. A. , Laporte Gilbert , Thisse Jacques-François
Published: October 2008

This paper presents a taxonomy for competitive location models based on the following five components: the space, the number of players, the pricing policy, the rules of the game, and the behavior of the customers. The components are briefly discussed and based on these, an annotated bibliography comprising more than 100 selected titles follows.
Competitive Spatial Price Discrimination with Capacity Constraints
Authors: Hamilton Jonathan H. , Thisse Jacques-François
Published: October 2008

A model of duopolistic spatial price discrimination on a network is extended by adding capacity constraints on firms' outputs. With zero-one consumer demands, some configurations of capacity levels and locations do not have pure strategy Nash equilibria in price schedules, in particular when firms have some excess capacity but not enough to serve the entire market individually. An alternative to the mixed strategy Nash equilibrium in price schedules—the core of the market game among producers and consumers—is described and shown to have allocations corresponding to pure strategies for all location and capacity configurations. If both firms have some excess capacity, price schedules are identical to those in the uncapacitated problem. Equilibrium prices are no higher than the lowest prices in the mixed strategy Nash equilibria.
Equilibrium in Competing Networks with Differentiated Products
Authors: de Palma André , Leruth Luc
Published: October 2008

We study “positive network externalities” in a horizontally differentiated industry. We show that a symmetric Nash equilibrium in prices exists if and only if the degree of product differentiation is sufficiently large. We also study the impact of larger or lower compatibility on equilibrium prices.
On the Core of Cost Allocation Games Defined on Location Problems
Authors: Tamir Arie
Published: October 2008

The literature on location theory has dealt mainly with finding “optimal” locations for centers which are to serve given demand points. No attention was given to the problem of allocating the costs of establishing the centers among the users, i.e., the demand points. In this paper we address this issue relating it to game theory concepts.
Dual-Ascent Procedures for Multicommodity Location-Allocation Problems with Balancing Requirements
Authors: Crainic Teodor Gabriel , Delorme Louis
Published: October 2008

The multicommodity location-allocation problem with balancing requirements is related to one of the major logistics issues faced by distribution and transportation firms: the management of the fleet of vehicles over a medium to long-term planning horizon. We present a dual-ascent approach for this formulation which may be used either to obtain a good heuristic solution, or to compare sharp bounds in a branch-and-bound scheme. We present and compare two variants of this approach, and analyze their performances both on a large number of randomly generated problems and on a large-scale application to the strategic/tactical planning of the land operations of an international maritime container shipping firm. Our results demonstrate that a dual-ascent approach is highly effective in this context.
A Model for Dynamic Airline Seat Inventory Control with Multiple Seat Bookings
Authors: Lee Tak C. , Hersh Marvin
Published: October 2008

It is common for the airlines to sell a pool of identical seats at different prices according to different booking classes to improve revenues in a very competitive market. Under this practice, a complex yet very crucial problem is to determine whether a booking request for seats in a certain booking class occurring at some point in time during the booking period should be accepted or denied. This paper develops a discrete-time dynamic programming model for finding an optimal booking policy, which can be reduced to a set of critical values. Unlike many existing models, this model does not require any assumptions about the arrival pattern for the various booking classes. Furthermore, multiple seat bookings, which are a practical issue in airline seat inventory control, are also incorporated into the model. In this paper, the basic properties of the model are studied. Numerical examples are presented. Computational issues, including the computational efficiency of the model, are also discussed.
One-to-Many Distribution with Transshipments: An Analytic Model
Authors: Campbell James F.
Published: October 2008

This paper presents and optimizes two cases of an approximate analytic model of distribution from a single origin to many destinations via transshipment terminals. Linehaul vehicles carry items from the origin to terminals and local vehicles make deliveries on peddling routes from the terminals. It has been shown that transshipments are not desirable when local vehicles can be as large as linehaul vehicles. This paper limits the size of local vehicles and explores conditions under which transshipments are desirable. This paper focuses on situations in which local vehicles operate on multi-stop tours. The tradeoffs between the transportation, inventory and terminal cost components determine optimal values for the number of terminals, the number of stops per vehicle route and the distribution cost. The optimal type of distribution system is shown to depend on the ratio of the linehaul to local vehicle load size. Examples are presented that show how distribution via terminals can reduce the total cost.
General Considerations on the Use of the Weighted lp Norm as an Empirical Distance Measure
Authors: Brimberg J. , Love R. F.
Published: October 2008

In this paper, we present a general procedure for fitting the weighted lp norm in order to estimate travel distances in a distribution system. An important finding of our study is that the search for the best-fitting value of the parameter p can be restricted to the interval (0, 2], provided the reference axes of the distance function are oriented to match the directional bias inherent in the transportation network. The advantages of our methodology and particularly the importance of properly aligning the reference axes are demonstrated through a case study of the road system in Southern Ontario. Although attention is restricted to the weighted lp norm, the concepts presented are readily extended to other distance functions such as the block norms of Ward and Wendell.
Location Models with Routing Considerations for a Single Obnoxious Facility
Authors: Stowers Curtis L. , Palekar Udatta S.
Published: October 2008

The problem of optimally locating obnoxious facilities such as hazardous waste repositories, dump sites, or chemical incinerators has been the source of much controversy. Often, the final decision on where to locate the facility has been based on criteria that are difficult to quantify. Previous efforts have focused on where to locate such a facility to minimize the total population which will be exposed to the facility. Similarly, efforts have been made to route the waste as to minimize the exposed population. Attempts at combining the two elements of risk to determine locations have been restricted to selecting from a given set of candidate locations. In this paper a combined model is developed that quantifies the total exposure of the population during transportation as well as long term storage. Some properties of the exposure function are developed that help in the solution of special cases of the problem. We show that the problem admits a nodal optimality result when there are no location risks. The result extends even for biobjective problems involving exposure and cost. When location risks are considered and population is concentrated at nodes, the problem exhibits a finite dominating set. With uniform population distribution on arcs and node populations, it is possible to partition the arcs of the network and search for the global optimum solution.
Dynamic Estimators of Origin-Destination Matrices Using Traffic Counts
Authors: Cascetta Ennio , Inaudi Domenico , Marquis Gérald
Published: October 2008

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

Recently a number of models for the estimation of origin-destination trip matrices from traffic counts have been presented. One class of models assumes knowledge of the proportional usage of each link by the interzonal traffic. These models result in an underspecified, and often inconsistent, system of linear equations. Several authors have addressed the problem of inconsistency by, in different ways, changing the traffic count data so as to achieve consistency. We argue that, modeling-wise, this is not a sound approach because inconsistent data is a natural part of any origin-destination matrix estimation problem. By using a stochastic programming approach the inconsistent input data becomes a natural part of the estimation process. This is done by viewing the traffic counts as realizations of some unknown underlying distribution of traffic flows.
Modeling Travelers' Postwork Activity Involvement: Toward a New Methodology
Authors: Hamed Mohammad M. , Mannering Fred L.
Published: October 2008

The objective of this study is to develop a methodology capable of modeling travelers' postwork activity patterns and thus tracing the movements of travelers through space and time. After reviewing the state of the art in activity participation and scheduling, a modeling system consisting of a set of discrete/continuous models and duration-based models is specified and estimated. The discrete/continuous models are used to predict the travelers activity-type preference (discrete), the travel time to the activity and back home (continuous), and activity duration (continuous). Duration models are used to model the travelers home-stay duration capturing the factors that motivate travelers to terminate their home-stay and undertake additional out-of-home activities.
Technical Note—Two Properties of the Nested Logit Model
Authors: Daganzo Carlos F. , Kusnic Michael
Published: October 2008

This paper presents simple formulae for the utility covariances of the nested logit (NL) model, and based on these defines a “scaled tree” that can be used as an aid for the interpretation of estimation results. The paper also shows that the full information log-likelihood function of linear-in-the-parameters NL models is concave in the utility parameters. Thus, conditional on the scaling parameters, full information maximum likelihood (FIML) searches cannot get trapped in local maxima.
Minimizing Trailer-on-Flat-Car Costs: A Network Optimization Model
Authors: Dial Robert B.
Published: October 2008

This paper discusses the mathematical and computational underpinnings of an optimization model that reduces United Parcel Service, Inc.'s trailer-on-flat-car (TOFC) usage costs by $4 million per year. It includes an informal statement of the TOFC problem, an integer linear program (ILP) formulation, and a transformation of this ILP into a pure minimum cost network flow program, whose software implementation provides the TOFC planner with a rich set of practical features.
Technical Note—Optimal Locations on a Line with Random Utilities
Authors: de Palma André , Liu Qin , Thisse Jacques-François
Published: October 2008

This note deals with the optimal locations of a given number of facilities when customers' behavior is described by a probabilistic choice model. In this context, the principle of median location is generalized. The optimal locations are determined in the case of the multinomial logit for different numbers of facilities.
Technical Note—Algorithms for Weber Facility Location in the Presence of Forbidden Regions and/or Barriers to Travel
Authors: Aneja Y. P. , Parlar M.
Published: October 2008

We describe algorithms for optimal single facility location problems with forbidden regions and barriers to travel. The former are those where location is not permitted, but one can travel through them, e.g., a lake. The latter are the regions where neither location nor travel is permitted, e.g., large parks in a city. Using the convexity properties of the objective function, in the first case, we develop an algorithm for finding the optimal solution. The objective function in the barrier case is shown to be non-convex. We use the concept of visibility to create a network with the location point as the source and use Dijkstra's algorithm to compute the shortest distance to all the other demand points. Using simulated annealing we find an approximate optimal solution. Numerical examples illustrate the implementation of the algorithms.
Location of Competing Facilities in a User-Optimizing Environment with Market Externalities
Authors: Brandeau Margaret L. , Chiu Samuel S.
Published: October 2008

In many location models, it is assumed that customers select the facility they will patronize based on the distance to that facility, or perhaps on a function of distances between the customer and the different available facilities. We consider a location problem in which customers select a facility based not only on travel time or distance to the facility, but also on negative externalities associated with the market share of the facility. A customer from any particular location frequents the facility that minimizes his travel time to that facility plus an externality cost that depends on the aggregated actions of all customers in the system. We consider the case of two competing facilities, each of which wishes to locate to maximize its market share. We specialize our analysis to the case of a tree network. We characterize the optimal facility locations, and develop an O(n2) algorithm for finding them.
The Augmented Lagrangian Method for Solving Dynamic Network Traffic Assignment Models in Discrete Time
Authors: Wie Byung-Wook , Tobin Roger L. , Friesz Terry L.
Published: October 2008

We develop and test an augmented Lagrangian method for solving dynamic traffic assignment models formulated as optimal control problems. Our presentation is in terms of the discrete time, system optimal traffic assignment problem. However, the basic ideas presented here are readily applied to continuous time models and to other behavioral assumptions regarding traffic assignment which may be expressed as optimal control problems. The proposed algorithm obviates the need for path enumeration and exploits the natural decomposition of the traffic assignment problem by time period which is possible when an optimal control formulation is employed.
Equilibria for Networks with Lower Semicontinuous Costs: With an Application to Congestion Pricing
Authors: Bernstein David , Smith Tony E.
Published: October 2008

Network equilibrium models traditionally rely on the assumption of continuous travel cost functions. However, there are times when this assumption is not appropriate. For example, some proposed congestion pricing schemes make use of discontinuous step-function tolls. Hence, the purpose of this paper is to explore the existence of network equilibria in the presence of discontinuities. In particular it is shown that when such costs are at least lower semicontinuous, a behaviorally meaningful notion of user equilibrium can still be defined which reduces to Wardrop equilibrium in the continuous case. In addition, it is shown that such equilibria are guaranteed to exist under fairly general conditions. Finally, these results are applied to construct a class of lower semicontinuous congestion pricing schemes which ensure the existence of such equilibria.
On a Rail Transportation Model with Scheduled Services
Authors: Özekici Süleyman , Şengör Selim
Published: October 2008

A safety precaution used in rail transportation is to ensure that only one train occupies the track connecting two stations at any time. We consider a train station where passengers arrive according to a prescheduled timetable, and the transportation authority tries to dispatch the trains on their scheduled departure times. However, if the track to the next station is occupied by a preceding train at such a departure instant, then the departure of the next train is delayed, or even cancelled, to achieve safety in transportation. Under such circumstances, the dispatcher may choose to cancel overdelayed trains intentionally so that the succeeding trains can depart on time, or to dispatch some trains with faster speed to decrease service time. We analyze this rail transportation model to identify the relationships between various dispatching strategies, the arrival pattern of the passengers, and the performance measures involving the service delay and passenger waiting time. The steady-state distribution of the service delay is characterized as the solution of a system of linear equations and an explicit computational formula for the average passenger waiting time is derived. Interesting intuitive and counterintuitive examples are also provided in the context of an optimal dispatching problem.
An Analytic Model for Design and Analysis of Single-Vehicle Asynchronous Material Handling Systems
Authors: Johnson M. Eric , Brandeau Margaret L.
Published: October 2008

Most research to date on asynchronous material handling systems such as automated guided vehicle systems (AGVSs) has involved simulation studies. In this paper we develop an optimal design model for a single-vehicle AGVS that analytically accounts for the stochastic nature of real manufacturing systems. The model determines which stations and routes to include in the network to maximize the benefit of the network subject to a constraint that the average waiting time in the system not exceed a prescribed limit. In the absence of an analytical model, one would have to simulate all possible combinations of stations and routes in order to find the configuration that maximizes the benefit of the AGVS. Our contribution is to solve the problem analytically. We develop analytic expressions for key performance measures such as the full and empty trip distribution, vehicle utilization, and expected waiting time in the network. The model is formulated as a linear binary integer program with one nonlinear constraint. To solve the problem we develop bounds on the expected waiting time, which we use as part of an exact implicit enumeration solution procedure. We illustrate the model with an example of an AGVS design problem at Hewlett-Packard and we present computational experience for other representative problems.
Solving a General Routing and Scheduling Problem by Chain Decomposition and Tabu Search
Authors: Hooker J. N. , Natraj N. R.
Published: October 2008

We modify the classical chain decomposition model for vehicle routing in order to formulate a very general class of vehicle routing and scheduling problems with time windows, in which vehicles may pick up loads while on the way to deliver others. We use the model as a framework for a tabu search heuristic that exploits the constraint structure these problems have in common while accommodating complex side constraints and objective functions. We test the heuristic computationally on several random problems and a problem supplied by the U.S. Military Airlift Command.
The Airline Exception Scheduling Problem
Authors: Klincewicz John G. , Rosenwein Moshe B.
Published: October 2008

As part of its schedule planning task, a domestic airline must assign fleets (aircraft types) to legs (non-stop flight segments). Initially, for planning purposes, this fleet assignment is done for a daily, repetitive schedule, called a “skeleton” schedule, in which the same set of legs is assumed to fly daily. In practice, however, there are often significant changes in passenger demand patterns on weekends (and other days as well), warranting changes in scheduled legs and fleet assignments. Thus, the airline will include, in its actual schedule, certain variations or changes in the nominal “skeleton” schedule on particular days of the week. We refer to such changes as exceptions. A typical domestic airline may vary the fleet assignment of over 10% of its legs on the weekend alone. Thus, handling exceptions is an important airline scheduling function. We describe an approach, centered around formulating and solving a network flow problem, for efficiently scheduling such exceptions to the usual daily schedule. In addition, another procedure was developed to identify and suggest possible profitable exceptions. It implements graph theoretic methods to detect “cycles” of legs whose fleet assignment is unprofitable on a particular day. Some computational experience is discussed.
A Request Clustering Algorithm for Door-to-Door Handicapped Transportation
Authors: Ioachim Irina , Desrosiers Jacques , Dumas Yvan , Solomon Marius M. , Villeneuve Daniel
Published: October 2008

This paper examines whether there is a substantial additional payoff to be derived from using mathematical optimization techniques to globally define a set of mini-clusters. Specifically, we present a new approximate method to mini-clustering that involves solving a multi-vehicle pick-up and delivery problem with time windows by column generation. To solve this problem we have enhanced an existing optimal algorithm in several ways. First, we present an original network design based on lists of neighboring transportation requests. Second, we have developed a specialized initialization procedure which reduces the processing time by nearly 40%. Third, the algorithm was easily generalized to multi-dimensional capacity. Finally, we have also developed a heuristic to reduce the size of the network, while incurring only small losses in solution quality. This allows the application of our approach to much larger problems. To be able to compare the results of optimization-based and local heuristic mini-clustering, we also present a parallel insertion approach to mini-clustering. Our computational results highlight the success of our approach. On test problems with up to 250 requests, our optimization-based method reduced the travel time within the mini-clusters by an average of 10% over the parallel insertion approach. Furthermore, for an actual problem with 2545 requests, a substantial 5.9% improvement in total traveling time was achieved over the heuristic.
A Discrete Time, Nested Cost Operator Approach to the Dynamic Network User Equilibrium Problem
Authors: Wie Byung-Wook , Tobin Roger L. , Friesz Terry L. , Bernstein David
Published: October 2008

In this paper we formulate the dynamic network user equilibrium problem as a variational inequality problem in discrete time in terms of unit path cost functions. We then show how arc exit flow functions and nested cost operators can be used to calculate unit path costs given the departure time and route choices of network users. We also demonstrate that, assuming certain regularity conditions hold, a discrete time dynamic network user equilibrium is guaranteed to exist. Finally, a heuristic algorithm and numerical results are presented.
Confidence Intervals for lk,p,θ Distances
Authors: Love Robert F. , Walker John H. , Tiku Moti L.
Published: October 2008

Distance predicting functions have a number of uses when objects in space can be represented as points. When a predicted distance between two points is determined by a distance predicting function, the unknown distance between the points may be overestimated or underestimated due to the statistical nature of distance predicting functions. Since an analyst may desire a measure of the accuracy of the predicted distance, we have developed a procedure for calculating confidence intervals for unknown distances. The procedure utilizes information that is provided by the sample Pearson coefficients.
Solving an Instantaneous Dynamic User-Optimal Route Choice Model
Authors: Boyce David E. , Ran Bin , Leblanc Larry J.
Published: October 2008

Dynamic models of the behavior of automobile drivers in choosing routes through urban transportation networks are required for the design and operation of intelligent transportation systems generally, and traveler information systems in particular. In this paper, drivers' route choice behavior based on current, or instantaneous, information on network conditions is described using an optimal control theory formulation. The time-dependent origin-destination vehicle trip pattern is assumed to be known. The instantaneous dynamic user-optimal route choice problem is to allocate vehicle flows to the current minimal-cost routes, defined as the routes that minimize the route travel cost between each decision node (any node on the route including the origin) and the destination node based on the currently prevailing travel times. The continuous time formulation of the problem is transformed into a discrete time nonlinear programming (NLP) formulation. Each of a sequence of NLPs is then solved by an algorithm based on the Frank-Wolfe technique. In this sequence, approximate link travel times are updated iteratively in order to represent flow propagation over routes. Computational results from applying the algorithm to two test networks conclude the paper.
Hybrid Heuristics for the Vehicle Routing Problem with Time Windows
Authors: Russell Robert A.
Published: October 2008

This paper addresses the development of effective heuristics for solving the vehicle routing and scheduling problem with time window constraints. Both tour construction and local search tour improvement heuristics are developed. A major premise of the paper is that embedding global tour improvement procedures within the tour construction process can lead to improved solutions. Computational results are reported on test problems from the literature as well as real world applications. The hybrid construction/improvement heuristic is more effective in reducing vehicle fleet size requirements than previously reported heuristics.
Networking Policies for Hub-and-Spoke Systems with Application to the Air Transportation System
Authors: Aykin Turgut
Published: October 2008

Recently, hub-and-spoke networks employing central hub facilities to channel flows between interacting nodes have become popular with successful applications in ground and air transportation. In this paper, we introduce a framework for the design of this type of distribution network with networking policies and models together with exact and heuristic solution procedures. We consider two networking policies: (i) Nonstrict hubbing, in which channeling flows through hubs is not required but chosen if found cost efficient and (ii) strict and restrictive hubbing, in which all flows to/from a node are channeled through the same hub. Variations of these policies are discussed together with various aspects of air passenger and cargo transportation, effects of network organization on demand and network design under continuous economies of scale. The performances of the proposed algorithms and the effects of the networking policy implemented on the hub locations and the route structure are studied using data on air passenger flows between the top forty U.S. cities in 1989.
Markovian Decision Processes in Shipment Consolidation
Authors: Higginson James K. , Bookbinder James H.
Published: October 2008

Shipment consolidation is a logistics strategy that combines two or more orders or shipments so that a larger quantity can be dispatched on the same vehicle. This paper discusses a discrete-time Markovian decision process (MDP) approach for determining when to release consolidated loads. We assume that the shipper controls the timing of each load dispatch. Thus, whenever a customer places an order, a choice must be made between dispatching this order (plus all others waiting) immediately, or continuing to consolidate until at least the arrival of the next order. Our MDP models of shipment consolidation consider movement by for-hire transportation (common carriage) or by a firm's own vehicles (private fleet). Small but realistic numerical examples illustrate the application of these models and the data-aggregation issues that must be resolved. Two minimization criteria are considered: cost per unit time, or cost per hundredweight per unit time. For private carriage, the optimal policy is of the control-limit type; for common carriage, it may not be. These potential differences in form of the optimal policy are true for either objective function. The possibly contrasting optimal policies are interpreted in light of the costs encountered by an industrial firm's private fleet compared to the freight charges of a public trucking company.
Dynamic Allocations for Multi-Product Distribution
Authors: Bassok Yehuda , Ernst Ricardo
Published: October 2008

Consider the problem of allocating multiple products by a distributor with limited capacity (truck size), who has a fixed sequence of customers (retailers) whose demands are unknown. Each time the distributor visits a customer, he gets information about the realization of the demand for this customer, but he does not yet know the demands of the following customers. The decision faced by the distributor is how much to allocate to each customer given that the penalties for not satisfying demand are not identical. In addition, we optimally solve the problem of loading the truck with the multiple products, given the limited storage capacity. This framework can also be used for the general problem of seat allocation in the airline industry. As with the truck in the distribution problem, the airplane has limited capacity. A critical decision is how to allocate the available seats between early and late reservations (sequence of customers), for the different fare classes (multiple products), where the revenues from discount (early) and regular (late) passengers are different.
TSS Dissertation Abstracts—Abstracts for the 1994 Transportation Science Section Dissertation Prize Competition
Authors: Mahmassani Hani S.
Published: October 2008

Twelve dissertations were submitted to the 1994 Transportation Science Section dissertation prize competition. The first prize was awarded to Dr. SRINIVAS PEETA for his dissertation titled: “System Optimal Dynamic Traffic Assignment in Congested Networks with Advanced Information Systems.” The committee also awarded two honorable mentions: to Dr. RENÉ SÉGUIN, “Problèmes Stochastiques de Tournées de Véhicules”; and Dr. ATHANASIOS ZILIASKOPOULOS, “Optimum Path Algorithms on Multidimensional Networks: Analysis, Design, Implementation and Computational Experience.” The abstracts of the twelve theses submitted to the competition are given.