bluuebunny/crossref_metadata_2025 huggingface dataset:
Finding Two-Centers of a Tree: The Continuous Case
Authors: Handler Gabriel Y.
Published: October 2008

An efficient algorithm for finding the absolute single-center (minimax-distance criterion) of a tree is extended to the location of two-centers, where these may be located anywhere on the continuum of points defined by the tree network. A graph-theoretic analysis transforms this bivariate problem into three unwariaie single-center problems. The resultant algorithm, whose complexity is a linear function of the number of nodes, requires an additional effort of about 25% over the single-center algorithm to locate an optimal pair of venters. Two varieties of the problem are considered; in the first, demand for service can occur anywhere on the network; in the second, demand is restricted to the set of nodes.
On the Existence of Equilibria in Asymmetrical Multiclass-User Transportation Networks
Authors: Braess D. , Koch G.
Published: October 2008

When studying multiclass-user transportation networks Dafermos made a strong assumption on symmetry in order to prove existence of a user-optimizing flow pattern. In this paper existence is proved without the symmetry-hypothesis and it is shown that the methods of convex programming are not applicable.
The Team/Fleet Models for Simultaneous Facility and Equipment Siting
Authors: Schilling David , Elzinga D. Jack , Cohon Jared , Church Richard , ReVelle Charles
Published: October 2008

A number of new location models which utilize the notion of coverage were developed, tested and utilized in a study of the Baltimore City Fire Protection System. These models extend the location decision to include not only specification of the sites of the basic facilities but also the distribution of specialized equipment and/or manpower among those sites. They are seen as more realistic representations of the location decisions which are required in public sector applications.
The Use of Disaggregate Choice Models in Semi-Markov Process Models of Trip Chaining Behavior
Authors: Lerman Steven R.
Published: October 2008

Travel demand models currently used in practice generally ignore the phenomenon of trip chaining. However, there is growing evidence that the possibility of forming more efficient trip tours may be a principal mechanism by which travelers adapt their behavior when confronted with gasoline shortages or severe price increases. This paper tries to synthesize two different analysis methodologies, disaggregate choice models and semi-Markov processes, to develop an operational, policy sensitive model of non-work trip chaining. The theory of each of these methods is briefly described. A model of trip chaining is then formulated. An example of the model, implemented for Rochester, New York, is then presented, and conclusions regarding potentially fruitful extensions are drawn.
Sufficient Conditions for Optimal Facility Locations to Coincide
Authors: Juel Henrik , Love Robert F.
Published: October 2008

In some cases multifacility location problems may be solved by verifying a few simple inequalities involving the interfacility weights. This paper develops certain inequalities which are sufficient conditions for optimality in some multifacility problems. In the problems considered here, distances are represented by a symmetric metric and there are no constraints on the location of the new facilities.
A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem
Authors: Psaraftis Harilaos N.
Published: October 2008

An investigation of the single-vehicle, many-to-many, immediate-request dial-a-ride problem is developed in two parts (I and II). Part I focuses on the “static” case of the problem. In this case, intermediate requests that may appear during the execution of the route are not considered. A generalized objective function is examined, the minimization of a weighted combination of the time to service all customers and of the total degree of “dissatisfaction” experienced by them while waiting for service. This dissatisfaction is assumed to be a linear function of the waiting and riding times of each customer. Vehicle capacity constraints and special priority rules are part of the problem. A Dynamic Programming approach is developed. The algorithm exhibits a computational effort which, although an exponential function of the size of the problem, is asymptotically lower than the corresponding effort of the classical Dynamic Programming algorithm applied to a Traveling Salesman Problem of the same size. Part II extends this approach to solving the equivalent “dynamic” case. In this case, new customer requests are automatically eligible for consideration at the time they occur. The procedure is an open-ended sequence of updates, each following every new customer request. The algorithm optimizes only over known inputs and does not anticipate future customer requests. Indefinite deferment of a customer’s request is prevented by the priority rules introduced in Part I. Examples in both “static” and “dynamic” cases are presented.
Scheduling Bus Systems with Interchanges
Authors: Salzborn F. J. M.
Published: October 2008

The paper discusses some rules for scheduling a bus system consisting of an intertown route linking a string of interchanges each of which is the center of a set of feeder routes. Some of these rules are straightforward. However, the problem of distributing the feeder bus departures and arrivals evenly over the available timeslots is solved using an interesting new result in combinatorial group theory. Many concrete numerical examples are given.
Schedule Delay and Departure Time Decisions in a Deterministic Model
Authors: Hendrickson Chris , Kocur George
Published: October 2008

We develop a simple approach for modeling schedule delay in a deterministic setting based on user equilibrium concepts and deterministic queuing theory. Several cases of peak period commuting or travel to scheduled events (such as sporting events) are analyzed as illustrations. The results demonstrate the importance of schedule delay for departure time decisions. The analysis framework can be used to improve the transportation planning and evaluation process, and we have identified several related research issues which could provide further insights into departure time decisions and the performance of transportation systems.
A Hierarchical Objective Set Covering Model for Emergency Medical Service Vehicle Deployment
Authors: Daskin Mark S. , Stern Edmund H.
Published: October 2008

The use of hierarchical and multiobjective programming in public decision making is reviewed. The conventional set covering (CSC) problem is formulated for locating emergency medical service (EMS) vehicles. Its computational and practical limitations are discussed. The desire to account for inter-district responses leads to the formulation of a hierarchical objective set covering (HOSC) problem in which we find the minimum number of vehicles needed to cover all zones while simultaneously maximizing the extent of multiple coverage of zones. Several important properties of the HOSC problem are derived, including the fact that for certain values of the relative weights associated with the two objectives, no dominated zones are included in the solution. The CSC and HOSC formulations are applied to a 33-zone problem for Austin, Texas, and computational experiences are indicated.
A Note on Garfinkel, Neebe and Rao's LP Decomposition for the p-Median Problem
Authors: Galvão Roberto Diéguez
Published: October 2008

The convergence problems of Garfinkel, Neebe and Rao's linear programming decomposition algorithm for the relaxed p-median problem are analyzed and traced back to the very degenerate nature of the LP formulation. Extensive computational experience with this algorithm is described. One surprising outcome of the tests conducted with the decomposition algorithm was that convergence was obtained more consistently when a random (and usually worse) initial solution was used instead of a “good” initial solution provided by heuristic methods.
Attitudinal Analysis of Work/School Travel
Authors: Koppelman Frank S. , Lyon Patricia K.
Published: October 2008

This report describes the analysis of the choice of travel mode for trips to work or school through the study of attitudinal and behavioral responses. Travel behavior (mode choice) is linked to attitudes about the alternative modes through an intermediate preference construct. Individual attitudes are analyzed to obtain measures of perceptions of and feelings toward available transportation modes. These measures are related to mode preference, and preferences and situational constraints are related to choice. Differences in the perception-feelings-preference-choice formulation between travelers making local work trips and those making suburb-to-CBD work trips are identified and interpreted. The paper identifies (1) similarities and differences in the way perceptions are formulated and used to evaluate travel alternatives for local and suburb-to-CBD commuter trips and (2) the importance of including feelings measures in models of travel mode preference and choice.
Statistical Aspects of Injury Severity Part III: Making Allowance for Differences in the Assessment of Level of Trauma
Authors: Hutchinson T. P. , Lai P. W.
Published: October 2008

When accident data is collected by many people or organizations separately, the collectors may differ systematically in the way they assess injury severity. A statistical method of allowing for this is proposed and applied to a set of road accident data classified according to four sets of circumstances, five police force areas, and three severities of injury. It is concluded that appreciable improvements in the sensitivity of analysis can be obtained by allowing for possible differences in the grading of injury severity.
Deficit Function Bus Scheduling with Deadheading Trip Insertions for Fleet Size Reduction
Authors: Ceder Avishai , Stern Helman I.
Published: October 2008

This paper begins with a brief review of the operational aspects of bus scheduling at Egged (The Israel National Bus Carrier), and their experience with an optimal bus scheduling algorithm. Due to the limitations of this algorithm, Egged Management has decided it is still not justified to replace the manually and currently used planning procedures (comprised of 60 schedulers using Gantt charts). Consequently, an approximate procedure incorporating a man/computer interface was requested which would allow the inclusion of practical considerations that experienced schedulers may wish to introduce in the schedule. Due to its visual nature, the deficit function was selected as a natural tool to form the basis of such a man-machine interactive scheduling procedure. A deficit function defines the net number of departures required at each terminal up to and including time t. According to the well-known fleet size formula, the minimum number of vehicles required to service a multiterminal fixed schedule of trips is equal to the sum of the maximal deficits at all terminals. As deficit function theory stops at a fixed schedule of trips, it was necessary to develop procedures to (1) primarily determine when and where to insert deadheading trips, and (2) secondarily include such considerations as garage limitations, inclusion of refueling trips, and driver limitations. The final algorithm is capable of generating schedules automatically in a purely computer mode. In an interactive mode it allows the user to select one of several computer suggested improvements or to interject his own suggestions and immediately see the effects on the final schedule through observation of the deficit functions on a CRT or computer generated output.
Locating Central Paths in a Graph
Authors: Slater Peter J.
Published: October 2008

Concepts which measure the centrality of a vertex in a graph (eccentricity, distance and branch weight) are extended to paths in a graph. Locating paths with minimum eccentricity and distance, respectively, may be viewed as multicenter and multimedian problems, respectively, where the facilities are located on vertices that must constitute a path. The third problem is to find a path P in a graph for which the number of vertices in the largest component of G-P is minimized. The relationships among these concepts are studied. Most of the results presented are for trees, and, in particular, linear algorithms for finding paths in trees of minimum eccentricity and of minimum branch weight are presented. These problems arise in determining a “most accessible” linear route in a network according to several plausible criteria.
The Convergence of Equilibrium Algorithms with Predetermined Step Sizes
Authors: Powell Warren B. , Sheffi Yosef
Published: October 2008

The focus of this paper is on a certain class of equilibrium traffic assignment problems characterized by a path formulation of the associated mathematical programs. In such cases the equilibration iterations would require path enumeration, and are therefore prohibitively expensive. In this paper we prove that a predetermined sequence of step sizes (in a descent direction) would guarantee, under certain regularity conditions, convergence to the equilibrium solution. This algorithm was suggested in the literature without a proof of convergence, which we give here.
Queuing Models of Classification and Connection Delay in Railyards
Authors: Turnquist Mark A. , Daskin Mark S.
Published: October 2008

The major components of delay to rail cars in passing through yards are waiting for classification and connection to an appropriate outbound train. This paper proposes queuing models for each of these components which provide expressions for both the mean and variance of delay times. The models are then used in an example application to draw inferences regarding the effectiveness of alternative strategies for dispatching trains between yards.
Solution Algorithms for Network Equilibrium Models with Asymmetric User Costs
Authors: Fisk Caroline , Nguyen Sang
Published: October 2008

We consider algorithms proposed for solving the fixed demand user optimized network equilibrium problem with asymmetric user costs. Because the Jacobian matrix for the costs is asymmetric, no known equivalent convex optimization problem exists and alternative solution methods to nonlinear programming techniques must be sought. The purpose of this paper is to compare the performance of several existing methods for determining the equilibrium network flows of a small realistic network model in which intersection controls are incorporated which lead to particularly asymmetric cost functions.
An Investigation of the Accuracy of the Clark Approximation for the Multinomial Probit Model
Authors: Horowitz Joel L. , Sparmann Jürg M. , Daganzo Carlos F.
Published: October 2008

The Clark approximation, in which the maximum of two normally distributed random variables is approximated by a third normally distributed random variable, forms the basis of a relatively inexpensive technique for evaluating the choice probabilities of multinomial probit models. This paper reports the results of a series of numerical experiments in which the accuracy of probit computations based on the Clark approximation was investigated. In contrast to previous investigations, these experiments dealt with the accuracy of the results obtained when the Clark approximation is used for econometric estimation of the values of probit models' parameters and for prediction of choice probabilities using the estimated parameter values. It was found that the accuracy of the results obtained with the Clark approximation varies greatly from model to model. In many of the experiments the approximation performed quite satisfactorily, but in others it produced errors that probably would be causes for concern in practical work. It is difficult or impossible to judge the accuracy of results obtained using the Clark approximation without knowledge of the results that would be obtained using a computational technique that is known to be accurate. Consequently, in practical empirical work it often will not be possible to obtain reliable indicators of the Clark approximation's accuracy. However, it is likely that the errors resulting from use of the Clark approximation to estimate a probit model are small compared to the errors that would result from using the simpler logit model in a situation where the correct model specification is probit
A Biobjective Multifacility Minimax Location Problem on a Tree Network
Authors: Tansel Barbaros C. , Francis Richard L. , Lowe Timothy J.
Published: October 2008

In this paper we consider a biobjective multifacility minimax location problem on a tree network, which involves as objectives the maximum of the weighted distances between specified pairs of new and existing facilities, and the maximum of the weighted distances between specified pairs of new facilities. We establish necessary and sufficient conditions for a location vector to be efficient. We also give an algorithm for finding the efficient frontier of the problem, and provide an example illustrating the use of the algorithm. In addition, we consider a broad class of multiobjective location problems and give general necessary and sufficient conditions for a location vector to be efficient.
Combined Mode Split-Assignment and Distribution-Model Split-Assignment Models with Multiple Groups of Travelers
Authors: Leblanc Larry J. , Abdulaal Mustafa
Published: October 2008

We show how to model combined mode-route choice and location-destination-mode-route choice problems with interdependent travel impedances. Our models realistically extend the well known route choice equilibrium conditions to include mode choice as well. These models extend earlier combined models to the case where flows by different modes affect each other’s impedances. Our combined models consider distinct classes of travelers. By formally stratifying travelers into different groups, a more accurate analysis of the time-cost tradeoff in mode choice is possible. An extension to the combined distribution-mode split-assignment problem is also given, using entropy terms to model dispersion among different origin-destination pairs. We examine the computational aspects of these models and suggest algorithms for solution.
Coincident Optima for Two-Facility Weber Problems
Authors: Juel Henrik
Published: October 2008

The location problem with two new facilities in continuous space is considered, with distance measured by arbitrary norms. Necessary and sufficient conditions for a proposed solution to be optimal are given for several cases. These cases include situations where the cost function is nondifferentiable because facilities coincide.
A Matching Based Heuristic for Scheduling Mass Transit Crews and Vehicles
Authors: Ball Michael , Bodin Lawrence , Dial Robert
Published: October 2008

In this paper, we describe a computerized procedure for scheduling mass transit crews and vehicles. The procedure differs from previous methods in that rather than first scheduling vehicles and then crews, it schedules vehicles and crews simultaneously. Several of the subproblems are solved as matching problems on graphs. A computational test of this procedure using a database from the Baltimore Metropolitan Transit Authority has produced solutions of lower cost than those used by the transit authority.
Computational Procedures for Location Problems on Stochastic Networks
Authors: Weaver Jerry R. , Church Richard L.
Published: October 2008

Mirchandani and Odoni have extended the concept of median location to stochastic networks, that is, networks where the distances (times) on some arcs and/or the demands at some nodes may be discrete random variables. Computational procedures for the solution of such median location problems on stochastic networks are developed; limited testing gave encouraging results.
Network Aggregation Effects upon Equilibrium Assignment Outcomes: An Empirical Investigation
Authors: Bovy P. H. L. , Jansen G. R. M.
Published: October 2008

The level of spatial detail (i.e. zone size and network detail) used in transportation analyses is commonly regarded as an important factor affecting the accuracy of the resulting estimates of the impacts of a transportation plan. The precise effects of the level of detail are, however, largely unknown. To investigate these effects empirically for the car traffic assignment module, an experiment was designed to allow especially the study of the individual as well as combined effects of the level of detail and the type of assignment model. It involves the application of various assignment models at different levels of detail. Three network models were developed for the road network of Eindhoven (population: 200,000): a fine, a medium and a coarse network model. In this article the results of the equilibrium assignments are presented, which are occasionally compared with all-or-nothing outcomes. Mainly load figures are dealt with here. The experiment indeed showed a significant effect of the level of detail on most assignment outcomes. This effect proved to be consistent but diminishing: an increase in the level of detail always yielded better results but only marginal improvement could be obtained beyond a certain level. Compared with all-or-nothing assignment results, equilibrium loads agree much better with the counts at all levels of spatial detail.
The Prevalence of Braess' Paradox
Authors: Steinberg Richard , Zangwill Willard I.
Published: October 2008

In a noncongested transportation network where each user chooses his quickest route, the creation of an additional route between some origin-destination pair clearly cannot result in an increase in travel time to users traveling between that o-d pair. It seems reasonable to assume the same can be said of congested networks. In 1968, D. Braess presented a remarkable example demonstrating this is not the case: a new route can increase travel time for all. The present paper gives, under reasonable assumptions, necessary and sufficient conditions for “Braess' Paradox” to occur in a general transportation network. As a corollary, we obtain that Braess' Paradox is about as likely to occur as not occur.
Statistical Comparison of Non-Nested Probabilistic Discrete Choice Models
Authors: Horowitz Joel L.
Published: October 2008

The development of empirical probabilistic discrete-choice models frequently entails comparing two non-nested models (i.e., models with the property that neither can be obtained as a parametric special case of the other) to determine which is most likely to provide a correct explanation of a particular choice situation. Conventional statistical procedures, such as the likelihood ratio test, do not apply to comparisons of nonnested models. This paper describes three procedures for carrying out such comparisons and explores the ability of each to distinguish between correct and incorrect models. The procedures are: tests against a composite model, the Cox test of separate families of hypotheses, and comparisons based on the likelihood ratio index goodness-of-fit statistic. A modification of the likelihood ratio index is proposed that corrects for the effects of differences in the numbers of estimated parameters in the compared models. The abilities of the various procedures to reject incorrect models and accept correct ones are explored analytically and through numerical experiments. It is shown analytically that, in large samples, the modified likelihood ratio index has greater ability to distinguish between correct and incorrect models than do composite model procedures. The results of the numerical experiments suggest that the modified likelihood ratio index also has greater ability to distinguish between correct and incorrect models than does the Cox test. The numerical results give encouraging indications of the ability of the modified likelihood ratio index to choose the correct model in comparisons of models whose choice probabilities differ by at least 10–15%.
An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows
Authors: Psaraftis Harilaos N.
Published: October 2008

This paper modifies the exact Dynamic Programming algorithm developed by the author for the single vehicle many-to-many immediate request Dial-A-Ride problem to solve the problem where each customer has specified upper and lower bounds for his pickup and delivery times and where the objective is to minimize the time needed to service all customers. The major difference between the two algorithms is the substitution of backward recursion with forward recursion. The new algorithm requires the same computational effort as the old one (0(N23N) for N customers) and is able to recognize infeasible problem instances.
An Econometric Analysis of Automobile Scrappage
Authors: Manski Charles F. , Goldin Ephraim
Published: October 2008

It has been suggested that a used car is scrapped when its price net of repair costs falls below its scrap value. This simple hypothesis captures the essence of the important idea that the life spans of durable goods are determined by both economic and technical considerations. We present empirical evidence based on an explicit econometric model of the scrappage decision. Analyzing make-model-vintage specific scrappage rates in Israel for 1979, we find that the hypothesized inverse relationship between price and scrappage probability exists and is of striking magnitude. This finding, when combined with the fact that new car prices in Israel are almost triple CIF prices, may explain why the median life expectancy of a vehicle in Israel is so much longer than that of a similar vehicle in Western Europe or the United States.
A Probabilistic Model of Bus Route Performance
Authors: Powell Warren B. , Sheffi Yosef
Published: October 2008

This paper addresses the problem of describing bus route performance as a first step toward developing strategies for improving service reliability. Previous work in the area has consisted of costly simulation models or analytical treatments of highly simplified problems. An alternative approach is proposed here based on the idea of numerically calculating probability distributions of the time each bus arrives to and departs from each stop. A set of recursive relationships is developed, together with a reasonable set of assumptions, which allows the efficient calculation of all the necessary distributions. An important feature of the model is that it incorporates the effect of the trajectory of one bus on that of the following bus, thereby modeling the well known phenomenon of bus bunching. Numerical experiments demonstrate that the model performs quite well in this respect. It is expected that the methodology will be extremely cost effective, and without the statistical problems associated with interpreting the outputs of a simulation model.
Characterizing Traffic Conditions in Urban Areas
Authors: Herman Robert , Ardekani Siamak
Published: October 2008

A series of vehicular traffic experiments conducted in Austin, Texas, shows the reasonableness of the two assumptions in the two-fluid (moving and stopped vehicles) model of town traffic. The observational data support the assumption that the average speed in an urban street network is proportional to the fraction of the vehicles moving raised to a power and is also in agreement with the supposition that during relatively uniform periods the traffic is ergodic. An important consequence is that the average of the fraction of time stopped for a test vehicle circulating in a street network is approximately equal to the average fraction of the vehicles stopped in the system during the same test period. The parameters of the two-fluid model and the observed ranges of trip time and stop time per unit distance have been shown to be effective in assessing or rank ordering the relative quality of traffic service in a number of Texas cities; comparisons are made with various cities around the world. The two-fluid methodology appears to be useful in a preliminary “before”/“after” study during which signal timing changes were made. Finally, a preliminary analysis of aerial photographic data in two cities allows the determination of an additional two-fluid model parameter, p, in the relation stating that the fraction of vehicles stopped is given by the ratio of concentration to the jam or maximum concentration raised to a power, p. It is suggested that this parameter may be useful in describing the relative quality of various traffic systems.
An Efficient Method for Computing Traffic Equilibria in Networks with Asymmetric Transportation Costs
Authors: Nguyen Sang , Dupuis Clermont
Published: October 2008

In the presence of several user categories or transportation modes, or when transportation costs on each arc of a network depend on the flows on adjacent arcs, the traffic equilibrium problem may be expressed as a variational problem. Methods for determining traffic equilibria are then adaptations of techniques for solving variational inequalities. In this paper, we present a new convex optimization formulation for the general traffic equilibrium problem, and propose a simple iterative method for calculating traffic equilibria, which essentially involves postoptimizing a linear sub-problem at each iteration. Preliminary computational results are reported.
Bibliographic Section
Authors: Pas Eric I.
Published: October 2008

Transportation Demand Analysis by Adib Kanafani (McGraw-Hill, 1983)—reviewed by Eric I. Pas.
Approximate Formulas for Average Distances Associated with Zones
Authors: Vaughan Rodney
Published: October 2008

This paper develops formulas for estimating average distances associated with zones. The average distance between two points, one located at random in a zone and another located at random in another, is first investigated. The average distance from a fixed point to a point located at random in a zone, and the average distance between two points located at random in the same zone, are also examined. The accuracy of the approximations for these average distances are found by examining some simple cases.
Location-Relocation of Mobile Facilities on a Stochastic Network
Authors: Berman O. , LeBlanc B.
Published: October 2008

In this paper we deal with networks whose link travel times are not constant but undergo random changes. As a result of these changes the network may be in a finite number of discrete states. The paper contains a heuristic that finds the optimal set of locations for a set a facilities (servers), which may be moved, at a cost, in response to changes in the state of the network. The heuristic is suitable for a general number of facilities (previous research dealt with a single facility). The heuristic, which executes in polynomial time, is compared to the exact solution of the integer linear programming version of the problem for a series of small examples. For larger examples, the solution of the heuristic is compared to several bounds. An efficient method for performing sensitivity analysis is also indicated.
The Planar Two-Center and Two-Median Problems
Authors: Drezner Zvi
Published: October 2008

We present algorithms for the solution of planar location-allocation problems with two new facilities. Euclidean distances are assumed. We address both the minimax (or “two-center”), and minisum (or “two-median”) problems. Computational results are presented.
The Uniqueness of a Time-dependent Equilibrium Distribution of Arrivals at a Single Bottleneck
Authors: Daganzo Carlos F.
Published: October 2008

Motorists going through a bottleneck during the morning rush hour have to time their departure times to ensure they arrive to work at a reasonable time. Traffic and congestion levels at the bottleneck depend on the motorists' work schedule and the disutility of unpunctuality. This paper shows that, under certain conditions, there is only one equilibrium order of arrivals; an order under which motorists do not have an incentive to jockey for position in the queue.
Probabilistic and Economic Factors in Highway Geometric Design
Authors: Ben-Akiva Moshe , Hirsh Moshe , Prashker Joseph
Published: October 2008

This paper presents an integrated approach to geometric highway design which incorporates probabilistic and economic factors. It assumes that the characteristics of the traffic flow on the road are stochastic in nature. These traffic flow variables are inputs into physical and behavioral relationships that determine the properties of alternative designs. The choice of a specific design among the many possibilities is based on the minimization of an expected cost function that includes an explicit tradeoff between road users cost on the one hand and construction and maintenance costs on the other. The approach is demonstrated by an application to the design of a climbing lane. We postulate distributions of car and truck speeds on upgrades, formulate an expected cost function, and obtain a closed form solution for the optimal location of the climbing lane. It is shown that the current AASHO procedure, as an example, is a special case of the optimal solution based on simplified truck performance assumptions and a choice of a critical speed difference. A numerical example demonstrates the use of the proposed approach and the potential savings from an optimal location of a climbing lane.
A Median Location Model with Nonclosest Facility Service
Authors: Weaver Jerry R. , Church Richard L.
Published: October 2008

This paper deals with the location of service facilities on a transportation network where the closest (in distance, time or cost) facility is known not to service some significant portion of demand. The concept of vector assignment of demand nodes to facilities is introduced to account for nonclosest facility service. A generalized formulation of the p-median problem incorporating vector assignment is presented. It is shown that an optimal solution to this vector assignment p-median problem exists which consists entirely of nodes of the graph; however, there may be more than one facility per node. Three different solution procedures are discussed for the vector assignment p-median problem. Computational experiments for three different moderately sized data sets give encouraging results. A locational example is included which gives a comparison of an optimal p-median solution and an optimal p-median solution with vector assignment.
0(N log N) Algorithm for the Rectilinear Round-Trip Location Problem
Authors: Drezner Zvi
Published: October 2008

A shorter and simpler algorithm of complexity of 0(N log N) is presented. The results yield an algorithm for the rectilinear round-trip location problem.
Preface
Authors: Odoni Amedeo R.
Published: October 2008

Preface to the Special Issue of Transportation Science.
Airline Scheduling: An Overview
Authors: Etschmaier Maximilian M. , Mathaisel Dennis F. X.
Published: October 2008

The flight schedule is the central element of an airline’s planning process, aimed at optimizing the deployment of the airline’s resources in order to meet demands and maximize profits. In this paper, we present an overview of contributions to airline scheduling made by operations research professionals during the past 20 years or so. The overview follows the development of airline scheduling methodology from an early emphasis on standard quantitative optimization techniques to the recent trends toward a structured planning process in which all parts of the airline participate in the “construction” and “evaluation” of schedules, combining exact mathematical programming algorithms and heuristics.
Airspace Conflict Equations
Authors: Geisinger Kenneth E.
Published: October 2008

In this paper, equations are developed for computing the number of potential conflicts at an intersection of flight paths. A “potential conflict” is defined as the simultaneous violation of minimum (not necessarily equal) vertical and horizontal separation requirements. The assumption is made that the aircraft continue straight-line, constant-speed flight through the intersection (“blind flying”). Fortunately, in most cases pilots or air traffic controllers will detect the threat and a course change will be made, avoiding an actual conflict. The number of potential conflicts serves as a measure of relative risk, or as a measure of the workload placed on a separation assurance system.
The Application of Semi-Markov Decision Processes to Queueing of Aircraft for Landing at an Airport
Authors: Rue Robert C. , Rosenshine Matthew
Published: October 2008

Socially optimal control of access to the landing queue of an airport is investigated in this paper. Semi-Markov decision process models, M/M/1 and M/Ek/1, for several classes of customers are used to determine how access should be controlled. Only commercial jet aircraft are considered and they are divided up into five classes based on aircraft type. Data from the Greater Pittsburgh International Airport are used to determine the parameters of the service time distribution. Data from several published sources are used to develop the cost, reward, and arrival rate parameters for each of the classes. Results are developed and presented for both models.
Optimizing Gate Assignments at Airport Terminals
Authors: Mangoubi R. S. , Mathaisel Dennis F. X.
Published: October 2008

The airport flight-to-gate assignment problem is solved using two methods: (1) a linear programming relaxation of an integer program formulation and (2) a heuristic. The objective is to minimize passenger walking distances within the airport terminal area through a judicious gate assignment policy. An actual flight schedule for an average day at Toronto International Airport is used to compare existing walking distances, obtained from the original assignment, with results from the two methods. The results indicated that the original assignment had a 32% higher average per passenger walking distance than the minimum possible distance given by the LP solution. The heuristic’s performance was near optimal; it gave an average walking distance which was only 3.9% greater than the minimum. Computation times for the heuristic are 3.4 CPU seconds per run, while the linear program consumes 386 seconds per run on an IBM 370/168. In addition, if the heuristic is solved first and its solution is used as an initial feasible basis for the LP relaxation of the IP, the total CPU used to obtain optimality is reduced to 42 seconds.
Optimal Location-Relocation Decisions on Stochastic Networks
Authors: Berman Oded , Rahnama Mina R.
Published: October 2008

This paper deals with stochastic transportation networks in which links' travel times are random variables. Transitions among states of the network (each state differs from any other state by at least one link with different travel time) are assumed Markovian. The problem is to find an optimal location-relocation decision for p mobile servers in such a network. The criterion is to minimize the long-term expected average cost in units of time per period taking into account both response times and relocation costs. The paper generalizes its predecessor (Berman, O., A. R. Odoni. 1982. Locating servers on a network with Markovian properties. Networks 12 73–86.), by permitting the chosen set of locations in a given state of the network to depend on the former state of the network. Markovian decision theory is employed with the problem's special structure used to reduce the complexity of the resulting algorithm.
Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling
Authors: Sexton Thomas R. , Bodin Lawrence D.
Published: October 2008

A set of n customers is given. Each customer has a desired point of pickup, a desired point of delivery and a desired time of delivery. The problem is to determine the order of pickup and delivery and the times of pickup and delivery of these n customers by a single vehicle in order to minimize total customer inconvenience. Here, a mathematical programming formulating of this problem is subjected to Benders' decomposition procedure. The result is a heuristic routing and scheduling algorithm which is shown to produce high quality solutions in reasonable computation time by testing on moderately sized real data bases from both Gaithers-burg, Maryland, and Baltimore, Maryland. This study is divided into two parts, the first detailing the scheduling analysis and the second focusing on the routing component.
Dependence between Shipment Size and Mode in Freight Transportation
Authors: Hall Randolph W.
Published: October 2008

This note examines the dependence between freight mode and shipment size when they are chosen simultaneously to minimize transportation and inventory cost. Transportation modes which consolidate freight over many origins and destinations are shown to be least expensive for small supplier production rates (i.e., flows between the supplier and customer); transportation modes which do not consolidate are least expensive for large production rates. Optimal shipment size is a discontinuous function of production rate. Thus, certain shipment sizes are never optimal.
Improved Efficiency of the Frank-Wolfe Algorithm for Convex Network Programs
Authors: LeBlanc Larry J. , Helgason Richard V. , Boyce David E.
Published: October 2008

We discuss methods for speeding up convergence of the Frank-Wolfe algorithm for solving nonlinear convex programs. Models involving hydraulic networks, road networks and factory-warehouse networks are described. The PARTAN technique and heuristic variations of the Frank-Wolfe algorithm are described which serve to significantly improve the convergence rate with no significant increase in memory requirements. Computational results for large-scale models are reported.
Selection of Offsets to Minimize Delay to Traffic in a Network Controlled by Fixed-Time Signals
Authors: Allsop R. E.
Published: October 2008

Hillier has described a method of selecting offsets to minimize delay in certain networks controlled by fixed-time signals. In this paper an attempt is made to extend the method by relaxing somewhat the restriction on the form of the network. The problem is expressed in terms of the theory of graphs, and an iterative process is developed for finding a set of offsets that minimizes delay over the whole network. At each stage, the part of the network already covered is extended by adding one or more links, and for the method to be viable these links must be chosen so that a certain set of intersections remains small. A method of selection of links that minimizes this set of intersections at each stage is developed. The selection of links and calculation of offsets have been programmed in Fortran. Having found one delay-minimizing set of offsets, some others that give the same total delay can be found if they exist.
Rotating Roster for a Transit System
Authors: Bennett Brian T. , Potts Renfrey B.
Published: October 2008

The paper discusses the computer construction of the lists of weeks of work that form the basis of the rotating roster for crews operating buses for a transit system. There are two construction phases; the first consists of making a day-off pattern and the second consists of placing daily shifts in the lists under the constraint of the day-off pattern. Techniques used to attain objectives include integer linear programming and optimal assignment.
Driver-and-Vehiele Response in Freeway Deceleration Waves
Authors: Forbes T. W. , Simpson Miles E.
Published: October 2008

By a continuous circling technique, 35 mm air photo records were made during 10 peak traffic hours on two sections of an urban freeway, 5 on a four-lane, and 5 on a three-lane out bound section. Speeds, time headways, distance headways, and response times were analyzed from samples selected from the 1,000 ft of projected films to include deceleration waves. Each sample included from 40 to 150 pictures spaced 1 sec apart yielding 20 to 30 individual measurements for a total of 3,000 to 4,500 in each sample. All measurements were corrected by electronic computer for continuously changing camera angle and slant range (including altitude). Of the samples analyzed, eight from the four-lane section and two from the three-lane section showed typical deceleration waves. Three on the latter showed dissipation of “slowdowns” with increasing speeds and decreasing headways. The four-lane section included speed control signals but the three-lane section did not. On the former, incoming ramp vehicles, visible slowing ahead and signals apparently caused drivers to operate in an uncertainty mode more than on the latter. Weaving vehicles were more numerous on the latter. Longer average time headways were found after deceleration waves. Longer headways related to driver uncertainty are consistent with previous reports and are of importance for traffic flow theory and for freeway design, control, and operation.
Travel Assignment with a Nonlinear Travel-Time Function
Authors: Snell R. R. , Funk M. L. , Fan L. T. , Tillman F. A. , Wang J. J.
Published: October 2008

This work deals with the problem of traffic assignment with a nonlinear travel-time function. The nonlinear travel-time function makes it possible to simulate congestion on urban streets in a more realistic manner. The optimal traffic assignment pattern is obtained by using a variational technique for a multicopy network problem with nonlinear travel-time functions and turn penalties.
Letters to the Editor—Comments on “Significance Tests for Accident Reductions Based on Classical Statistics and Economic Consequences” by Stephen K. Dietz
Authors: Joksch Hans C.
Published: October 2008

Comments on “Significance Tests for Accident Reductions Based on Classical Statistics and Economic Consequences” by Stephen K. Dietz. Author's reply follows.
A Preliminary Investigation of Railway Signaling Methods by Computer Simulation Studies
Authors: Askew J. R. , Beardwood J. E. , Newby D.
Published: October 2008

This paper describes studies performed as an introduction to the problems of railway signaling. It includes a description of the digital computer model set up to deal with signaling procedures, together with the results of three exercises in its use. These exercises, in addition to demonstrating the usefulness of the model, have highlighted the interaction between the effectiveness of a signaling regime and the control strategy adopted in responding to it. It is thus possible that track-to-train communication could be used to transmit not only that information necessitated by the signaling regime but also the information needed to achieve the desired control strategy. Some actual problems that might be resolved by studies of this type are considered. In order to undertake these, however, a much fuller study reproducing all the relevant operating conditions would be needed.
Letter to the Editor—Report on the Fourth International Symposium on the Theory of Traffic Flow
Authors: Potts Renfrey B. , Herman Robert
Published: October 2008

The Fourth International Symposium on the Theory of Traffic Flow was held in Karlsruhe, Germany, June 18–20, 1968 and was attended by 154 participants from Australia, Austria, Belgium, Czechoslovakia, Denmark, France, Germany, Holland, India, Israel, Italy, Japan, Norway, Portugal, Spain, Sweden, Switzerland, United Kingdom, and the United States of America. The Symposium was organized by Professor W. Leutzbach and held at the Lehrstuhl für Verkehrswesen, Universität (TH) Karlsruhe. A total of 40 papers were presented in the six sessions of the Symposium.
A Constraint Qualification for a Dynamic Traffic Assignment Model
Authors: Carey Malachy
Published: October 2008

This note resolves a hitherto open question as to whether a dynamic traffic assignment model, which was developed and analyzed in earlier issues of this journal, satisfies a “constraint qualification.” It is shown that the model does in fact satisfy a constraint qualification, which establishes the validity of the optimality analysis presented by previous authors.
A Note on p-Center Problems in the Plane
Authors: Eiselt H. A. , Charlesworth G.
Published: October 2008

In this note three approximation methods for p-center problems in the plane are described. The performance of the methods is evaluated on the basis of an extensive series of tests.