bluuebunny/crossref_metadata_2025 huggingface dataset:
Design of Regular Intercity Driver Routes for the LTL Motor Carrier Industry
Authors: Crainic Teodor Gabriel , Roy Jacques
Published: October 2008

The load plan of a LTL motor carrier determines the services it operates and the frequencies it offers. To satisfy the stable part of the demand for transportation, regular driver routes have to be built. These routes must cover the planned services and abide by the laws, regulations and conventions that regulate the drivers' workload, while guaranteeing the timely delivery of goods at the destination terminal. The objective is to minimize costs and to ensure an efficient fleet utilization. We describe the problem, examine its characteristics, and propose a modeling and algorithmic approach based on set covering ideas. Results of an actual application are also presented.
Optimal Positioning of Service Units Along a Coordinate Line
Authors: Anderson Larry R. , Fontenot Robert A.
Published: October 2008

In this article, we consider the optimal positioning of multiple servicing units along a coordinate line, under the assumption that demand for service occurs probabilistically at any point along the coordinate line. We show that, under very general circumstances, it is best for the servicing units to be stationary, and we provide an algorithm for finding these stationary positions.
Bibliographic Section
Authors: Hurdle Vanolin F. , Assad Arjang A. , Goldschmidt Olivier
Published: October 2008

Theory of Highway Traffic Signals, Gordon F. Newell, Institute of Transportation Studies, University of California, Berkeley, 1989, 442 pp—reviewed by Vanolin F. Hurdle.

Operational Research '90, edited by Hugh E. Bradley, Pergamon Press, New York, 1991—reviewed by Arjang A. Assad.

Simulated Annealing and Boltzmann Machines, Emile Aarts and Jan Korst, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1988—reviewed by Olivier Goldschmidt.
Compatibility, Networks, and Competition: A Review of Recent Advances
Authors: Perrot Anne
Published: October 2008

This paper is a selective survey of the economic literature on the functioning of the markets where goods are subject to network externalities. Telecommunications, transports and computers give examples of markets where, for various reasons, these network effects appear. We first examine how the consumer's choices are affected by these network effects, as they are when switching costs are at work. On the markets of network goods, consumer's decisions depend either on the choices of previous generations, or on consumer's expectations, or both. The results are that choices may exhibit inefficiencies: a “wrong” good may be adopted because of the lack of coordination between individual decisions. We then turn to the study of a firm's strategies: when firms produce network goods, they may choose to make their product compatible or incompatible with the rival's good. Moreover, the nature of price competition is affected by the compatibility regime that prevails. This explains why consumers, who would always choose compatibility if prices were constant, might in fact prefer incompatibility if this regime intensifies price competition. In conclusion, compatibility choices by the firms and welfare implications are briefly examined.
Traffic Equilibrium with Responsive Traffic Control
Authors: Smith M. J. , van Vuren T.
Published: October 2008

This paper presents a theory of traffic equilibrium which involves responsive signal control policies; in this theory drivers' route choices and the control policy's choice of green times are treated in a symmetrical manner. The central theme of the paper is the iterative optimization assignment algorithm. This algorithm may be considered as a means of calculating equilibria which are consistent with a given responsive control policy. But it may also be regarded as a highly idealized model of the day to day dynamics of drivers' route choices when a responsive signal setting policy is employed; on “day” 1 the signals are held fixed and drivers settle down to an equilibrium flow pattern, on “day 2” the flow pattern is held fixed and the signals are updated according to the control policy for the fixed flow pattern, on “day” 3 the signals are held fixed and drivers settle down to an equilibrium flow pattern…. We state natural but strong conditions on the responsive control policy which guarantee that this algorithm is bound to converge to a convex set of (flow, control) pairs such that (i) the flow is a user equilibrium and (ii) the control parameters satisfy the responsive control policy; and we give a proof of convergence under these conditions—we do not seek to minimize total travel cost. Our conditions involve the delay or cost formula used; with the BPR cost formula, modified in a natural way to allow for green times, the traditional policy of choosing control parameters which minimize delay for the observed traffic pattern does satisfy these conditions in full. However, with Webster's delay formula traditional control policies are a long way from satisfying our conditions; and seeking to satisfy them with this delay formula leads us to two novel control policies. We assume throughout that demand is determined by a fixed OD matrix, giving the steady total flow rates for each OD pair. We also suppose that network characteristics do not change; so that incidents are not considered and saturation flows, for example, are constant.
An Approach for Predicting Latent Infrastructure Facility Deterioration
Authors: Ben-Akiva Moshe , Ramaswamy Rohit
Published: October 2008

A pavement deterioration model predicts the performance of a pavement over time as a function of traffic, pavement characteristics and environmental factors. The most important performance characteristics of a pavement are its ability to bear traffic loads and its ability to provide a smooth ride. However, there is no unambiguous approach to directly measure these performance characteristics. Therefore, we consider pavement performance to be unobservable. The problem of designing pavement deterioration models is the problem of defining the above unobservable characteristics in terms of what is observed, i.e., in terms of measured extents and severities of different damage components. The methodology presented in this paper describes a statistical technique to estimate latent pavement performance from observed pavement damage. No constraints are placed on the number or type of measurements required, so the methodology is flexible enough to include different measurement techniques and data collection strategies. The estimation procedure simultaneously fits a deterioration model and a performance index calibration model to data, thereby producing much better fits to data than traditional deterioration models. The methodology presented in this paper will be useful for deriving more realistic predictive models of pavement deterioration and for defining better data collection strategies.
TSS Dissertation Abstracts—Abstracts for the 1992 Transportation Science Section Dissertation Prize Competition
Authors: Nagurney Anna
Published: October 2008

Nine dissertations were submitted to the 1992 Transportation Science Section dissertation prize competition. The paper presents extended abstracts of those dissertations. Participants were Julien Bramel (first prize) (Analytical Results and Algorithms for Vehicle Routing Problems with Bin-Packing Features), Peter B. Vranas (honorable mention) (The Multi-Airport Ground-Holding Problem in Air Traffic Control), Mustafa C. Pinar (letter of commendation) (Decomposition and Parallel Solution of Network-Structured Optimization Problems), Haitham Mohammed Al-Deek (The Role of Advanced Traveler Information Systems in Incident Management), Mohammed Saleh Al-Malik (An Investigation and Development of a Combined Traffic Signal Control-Traffic Assignment Model), Chandra Bhat (Toward a Model of Activity Program Generation), Bernardo J. de Castilho (High-Throughput Intermodal Containers Terminals Technical and Economic Analysis of New Direct-Transfer System), Melody Dzwo-Min Dai (Delay Estimation on Congested Waterways), and Jia Hao Wu (A Study of Monotone Variational Inequalities and Their Application to Network Equilibrium Problems).
Landings at Logan Airport: Describing and Increasing Airport Capacity
Authors: Venkatakrishnan C. S. , Barnett Arnold , Odoni Amedeo R.
Published: October 2008

To understand how greatly new computer-based Decision Support Systems can benefit air traffic control, we study air traffic delays for landing aircraft at Boston. First, we develop an empirical model for present day Landing Time Intervals (LTIs) between aircraft in terms of two factors that significantly affect them: the landing runway configuration and the weight-class categories of the aircraft. Next, we develop three increasingly rich models of Boston's terminal airspace and apply, on airflow data, sequencing algorithms meant to expedite the landing of incoming aircraft. Comparing sequences suggested by the algorithms to those now used by controllers, we estimate that better sequencing can reduce delays by 30% in some instances. However, such improvements must be balanced against the effects such algorithms would have on workloads and other aspects of the air traffic control environment.
Errata
Authors: Nagurney Anna , Zhao Lan
Published: October 2008

Corrections to “Variational Inequalities and Networks in the Formulation and Computation of Market Equilibria and Disequilibria: The Case of Direct Demand Functions”.
The Multi-Item Joint Replenishment Problem with Transportation and Container Effects
Authors: Ben-Khedher Nejib , Yano Candace A.
Published: October 2008

We address the problem of scheduling the delivery of multiple items from a single supplier to a manufacturer. The items are packaged into containers, and the containers are shipped by truck. There is a fixed charge per truck shipment, and inventory holding costs are charged on end-of-period inventory. We seek to minimize the sum of transportation and inventory costs. The problem is a combination of a bin-packing problem (due to the presence of containers and finite-capacity trucks) and a multi-item joint replenishment problem. We present a heuristic solution procedure which starts with the optimal solution of the problem in which the integrality of the containers is relaxed. (A solution procedure for this relaxed problem appears in N. Ben-Kheder and C. A. Yano, “The Multi-Item Joint Replenishment Problem with Volume-Sensitive Transportation Costs,” Technical Report 89-19, Department of Industrial & Operations Engineering, The University of Michigan, Ann Arbor, MI (1989a). We develop a method to modify this solution to account for the integrality of containers. This modification scheme involves sequentially considering each item and optimally scheduling the fractional containers in the relaxed solution. To solve this single-item problem, we devise a procedure that accounts for the availability of “free” remaining capacity of trucks that have been partially filled with other items. In a computational study, our heuristic is compared with a lower bound, with variations of our heuristic, and with simple rule-of-thumb policies. The results suggest that our heuristic performs very well, especially in problems where considering tradeoffs between inventory and transportation costs is important.
Technical Note—The Discrete Anti-P-Center Problem
Authors: Klein C. M. , Kincaid R. K.
Published: October 2008

The discrete anti-p-center problem, DACPM, is to find p facility locations which will maximize the minimum distance between demand points and their respective nearest facilities. Typically this problem is used to model the location of obnoxious facilities such as incinerator plants, hazardous waste sites, unsightly factories, or correctional facilities. For the version of the discrete anti-p-center problem given by Moon and Chaudhry a practical polynomial algorithm is given.
Bibliographic Section
Authors: Mannering Fred
Published: October 2008

Dimensions of Automobile Demand: A Longitudinal Study of Household Automobile Ownership and Use, David A. Hensher, Nariida C. Smith, Frank W. Milthrope, Peter O. Barnard, Volume 22 of Studies in Regional Science and Urban Economics, North-Holland, Amsterdam, 1992, 281 pp.—reviewed by Fred Mannering.
TSS Dissertation Abstracts—Abstracts for the 1993 Transportation Science Section Dissertation Prize Competition
Authors: Bertsimas Dimitris
Published: October 2008

Nine dissertations were submitted to the 1993 Transportation Science Section dissertation prize competition. Two honorable mentions were awarded: Raymond K. Cheung (Dynamic Networks with Random Arc Capacities: Solution Methods and Applications) and Rekha Pillai (The Traveling Salesman Subset-tour Problem with One Additional Constraint). Extended abstracts are presented. (1) Dynamic Networks with Random Arc Capacities: Solution Methods and Applications by Raymond K. Cheung; (2) The Traveling Salesman Subset-tour Problem with One Additional Constraint (TSSP + 1) by Rekha Pillai; (3) A Model for Roadway Traffic Control Software by Darcy M. Bullock; (4) L'Optimisation des Frequences d'un Reseau de Transport en Commun by Isabelle Constantin; (5) Learning Heuristics for Repetitive Combinatorial Optimization Problems: With an Application in Train Scheduling by David R. Kraay; (6) Modeling Route Choice Behavior in the Presence of Information Using Concepts from Fuzzy Set Theory and Approximate Reasoning by Tsippy Lotan; (7) Air Carrier, Fare Class, and Flight Demand: An Individual Choice Approach by Kimon E. Proussaloglou; (8) Dynamic Transportation Network Models for Advanced Traveler Information Systems by Bin Ran; (9) Multicommodity Network Flows: The Impact of Formulation on Decomposition by Kimberly Lynn Ross.
Solving Structured Multifacility Location Problems Efficiently
Authors: Chhajed Dilip , Lowe Timothy J.
Published: October 2008

A generic multifacility location problem is considered which subsumes, as special cases, several NP-hard location problems that have appeared in literature. A unified algorithm is presented which solves the generic problem in polynomial time when problem structure, as defined by interactions between pairs of facilities, satisfies certain properties.
The Multimedian Location Problem on a Network Exploiting Block Structure
Authors: Xu Y. , Francis Richard L. , Lowe Timothy J.
Published: October 2008

The multimedian problem is to locate “distinguishable” new facilities on a connected network G so as to minimize a total cost, which is a sum of costs directly proportional to (a) network distances between new facilities and existing facilities at vertex locations and (b) distances between pairs of new facilities. By solving a related multimedian problem in polynomial time on the “blocking graph” of G, which is a tree, we obtain information which localizes each optimal new facility location to some vertex or block (maximal nonseparable subgraph) of G. The problem then decomposes into independent multimedian problems, one for each localizing block, which can be solved by using branch and bound and a vertex-optimality property.
On the Set of Optimal Points to the Weber Problem: Further Results
Authors: Durier Roland , Michelot Christian
Published: October 2008

In a recent paper, Z. Drezner and A. J. Goldman address the problem of determining the smallest set among those containing at least one optimal solution to every Weber problem based on a set of demand points in the plane. In the case of arbitrary mixed gauges (i.e., possibly nonsymmetric norms), the authors have shown that the set of strictly efficient points which are also intersection points always meets the set of Weber solutions. As shown by Drezner and Goldman, this set is optimal with the ℓ1 or ℓx distance but is not optimal with the ℓp distance, 1 < p < ∞. In this latter case they identify the smallest one. This paper generalizes these results for any strictly convex norm or any polyhedral norm. An example shows that in the case of an arbitrary norm there may exist an infinity of smallest sets and some of them contain points which are neither strictly efficient nor intersection points. In the ℓp distance case, we disprove a conjecture of Drezner and Goldman about the possibility of extending their result to more than two dimensions. The paper contains a different view of the problem: whereas Drezner and Goldman use algebraic-analytical approach, the authors use a geometrical approach which permits us to obtain more general results and also clarifies the geometric nature of the problem.
The Traveling Repairperson Home Base Location Problem
Authors: Jamil Mamnoon , Batta Rajan , Malon David M.
Published: October 2008

This paper considers the problem of locating the home base of a traveling server on a network. Calls for service arrive solely at nodes via independent, time-homogeneous Poisson processes. Calls finding the server busy enter a finite capacity queue which is depleted in a First-Come-First-Served (FCFS) manner. The server travels from his/her home base serving calls back-to-back, returning home only when he/she finds the system empty upon the completion of a service. The objective we consider is to minimize the average response time to an accepted call. The queueing system is analyzed via a busy period analysis, which uses a decoupling scheme to simplify the task of optimizing the home base location. Computational experience is discussed and a numerical example is presented. Generalizations of the model are also discussed.
Technical Note—Routing and Location-Routing p-Delivery Men Problems on a Path
Authors: Averbakh Igor , Berman Oded
Published: October 2008

In this note, we discuss routing and location-routing delivery men problems on a path. The objective of the delivery men problem is to find service tours so as to minimize the total waiting time of all customers. We present an O(n2) time algorithm for the location-routing problem with a single server. This algorithm is further used in polynomial time algorithms that are developed for routing and location-routing problems with p servers. Also considered is the sales-delivery men problem for which in addition to the delivery men criterion, also the traveling salesman criterion (which is of primary importance) is used.
Technical Note—A Polynomial Algorithm for the Equal Capacity p-Center Problem on Trees
Authors: Jaeger Mordechai , Goldberg Jeff
Published: October 2008

The uncapacitated p-center problem has been shown to be NP-Hard for the case of a general network, yet polynomial algorithms exist for the case of a tree network. We extend the results for trees to include the case where each center can serve a limited number of customers and show that the capacitated p-center problem on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. We show that the addition of center capacities to either the vertex center problem or the absolute center problem requires a multiplicative factor of O(n) more work, relative to that required for the uncapacitated problems, to solve the related covering problems (n is the number of vertices in the tree).
Martin J. Beckmann—Robert Herman Lifetime Achievement Award in Transportation Science Transportation Science Section Operations Research Society of America April 25, 1994 Boston, Massachusetts
Authors: Boyce David
Published: October 2008

On Monday, April 25, 1994, Martin J. Beckmann was awarded the Robert Herman Lifetime Achievement Award in Transportation Science for his numerous contributions to the field. The award committee consisted of Amedeo Odoni (Chairman), David Boyce, Gilbert Laporte, Hani Mahmassani, and H. Donald Ratliff. The award was presented to Professor Beckmann by Professor Robert Herman at the Transportation Science Section Meeting held during the TIMS/ORSA Meeting in Boston, MA. The citation below was prepared by David Boyce.
Nonlinear Tariffs and Freight Network Equilibrium
Authors: Hurley W. J. , Petersen E. R.
Published: October 2008

An equilibrium solution for the freight network problem is obtained. The system consists of multiple shippers and carriers, each acting as profit maximizing agents. The flow pattern maximizing total system profits is called the vertically efficient flows. We show that if the carrier or coalition of carriers use vertically efficient nonlinear pricing schedules, the vertically efficient flows are the equilibrium flows. The division of surplus associated with each shipment is obtained by solving a linear programming problem. Vertically efficient nonlinear tariff schedules are of a form that is commonly used in the transportation industry.
Dynamic Ground-Holding Policies for a Network of Airports
Authors: Vranas Peter B. M. , Bertsimas Dimitris , Odoni Amedeo R.
Published: October 2008

The yearly congestion costs in the U.S. airline industry are estimated to be of the order of $2 billion. In P. B. Vranas, Dimitris J. Bertsimas, and A. R. Odoni, The multi-airport ground-holding problem in air traffic control, Operations Research, Vol. 42, pp. 249–261, 1994, we introduced and studied generic integer programming models for the static multi-airport ground-holding problem (GHP), the problem of assigning optimal ground holding delays in a general network of airports, so that the total (ground plus airborne) delay cost of all flights is minimized. The present paper is the first attempt to address the multi-airport GHP in a dynamic environment. We propose algorithms to update ground-holding decisions as time progresses and more accurate weather (hence capacity) forecasts become available. We propose several pure IP formulations (most of them 0–1), which have the important advantages of being remarkably compact while capturing the essential aspects of the problem and of being sufficiently flexible to accommodate various degrees of modeling detail. For example, one formulation allows the dynamic updating of the mix between departure and arrival capacities by modifying runway use. These formulations enable one to assign and dynamically update ground holds to a sizeable portion of the network of the major congested U.S. or European airports. We also present structural insights on the behavior of the problem by means of computational results, and we find that our methods perform much better than a heuristic which may approximate, to some extent, current ground-holding practices.
A Decomposition Algorithm for the All-Pairs Shortest Path Problem on Massively Parallel Computer Architectures
Authors: Habbal Mayiz B. , Koutsopoulos Haris N. , Lerman Steven R.
Published: October 2008

Network optimization on parallel computer architectures has attracted significant interest in recent years. In this paper, we examine the solution of the shortest path problem on massively parallel architectures. We propose a network decomposition strategy that is amenable to parallel implementation and suggest efficient data structures and mappings of the data to the processors that facilitate the solution of the problem. We discuss computational results for the solution of networks of various sizes on the Connection Machine CM-2 (a representative massively parallel architecture) and compare the performance of the algorithm to the performance of serial algorithms implemented on the CRAY X-MP supercomputer and VAXstation 3100. We also present an “idealized” analysis of the algorithm and draw conclusions on properties of decomposition strategies that optimize its performance.
The Variance-Constrained Shortest Path Problem
Authors: Sivakumar Raj A. , Batta Rajan
Published: October 2008

This paper discusses the variance-constrained shortest path problem. This problem can be used to model any application in which the travel costs on a link are not deterministic, but follow a distribution that has possible correlation with travel cost on other links. Exact solution methods are proposed, and results are reported from computational experiments on data sets derived from a real-life routine scenario involving the transportation of liquefied-gas hazardous materials.
The Capacitated Carrier Transportation Problem: An Application of the Axial Three-Dimensional Transportation Problem with Heuristic
Authors: Current John , Imai Akio , Pirkul Hasan
Published: October 2008

The classic transportation problem assumes that either (1) there is a single carrier who can transport all of the required shipments at the given, per unit O-D costs or (2), there are multiple carriers and each O-D pair can be served by its least cost carrier. These assumptions, however, are unrealistic for logistics problems in which the transportation needs exceed the short-term capacity of any one available carrier. In such cases, it cannot be assumed that every potential O-D pair can be served by its least costly carrier. For example, firms in the paper product and tire industries conduct promotional activities (e.g., specials or truck-load sales). Such activities result in extremely large, short-term peaks in their transportation requirements which cannot be met by their private fleets and/or contracted common carriers within the necessary time constraints. We refer to this problem as the capacitated carrier transportation problem (CCTP).

In this paper we formulate the CCTP as an integer version of the axial three-dimensional transportation problem and present a heuristic based upon Lagrangian relaxation for solving it. Test problem results indicate that the heuristic identifies near optimal solutions in reasonable time.
Bibliographic Section
Authors: Jaillet Patrick , Bernstein David , Leonard John D. , Taylor Dean
Published: October 2008

Network Flows: Theory, Algorithms, and Applications, by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Prentice-Hall, Englewood Cliffs, NJ, 1993, xv + 846 pp.—reviewed by Patrick Jaillet.

Network Economics: A Variational Inequality Approach by Anna Nagurney, Kluwer Academic Publishers, Boston, MA, 1993, xxi + 326 pp.—reviewed by David Bernstein.

Proceedings of the Twelfth International Symposium on Transportation and Traffic Theory edited by C. F. Daganzo, Elsevier Science Publishers, B. V., Amsterdam, The Netherlands, 1993, 596 pp.—reviewed by John D. Leonard II.

The Bicycle and City Traffic, edited by Hugh McClintock, Bellhaven Press, London, 1992—reviewed by Dean Taylor.
Optimized Transfer Opportunities in Public Transport
Authors: Knoppers Peter , Muller Theo
Published: October 2008

This research note investigates the possibilities and limitations of coordinated transfers in public transit. The object is to minimize passenger's transfer time. It will be shown that optimum transfer times can be defined only if fluctuations in passenger arrival times at the boarding point can be contained within certain time limits.
Single-Vehicle Routing and Scheduling to Minimize the Number of Delays
Authors: Gendreau Michel , Laporte Gilbert , Solomon Marius M.
Published: October 2008

In this paper we examine the following problem arising in vehicle routing and in production scheduling. Consider a single uncapacitated vehicle and n customers j with deadlines dj. The objective is to minimize the number of deliveries completed after their deadline. This problem is NP-hard, but a class of solvable cases can be characterized. An integer linear programming formulation is proposed, and the problem is solved optimally by means of a specialized enumerative algorithm. Computational results are presented for problems involving up to 100 customers.
Modelling Vehicular Traffic Using the Discrete Time Markovian Arrival Process
Authors: Alfa Attahiru Sule , Neuts Marcel F.
Published: October 2008

A discrete time Markovian Arrival Process which models platooned arrivals in road traffic is presented. It takes into account the bunching of traffic and correlation between headways. Several examples involving different types of probability distributions for interplatoon and intraplatoon headways, and platoon sizes are presented. An application of the MAP to a traffic signal queue is carried out and a numerical example is presented. The example confirmed the intuition that ignoring correlation in the arrival process results in the underestimation of performance measures such as the mean queue length, especially at high traffic intensities.
Longitudinal and Lateral Throughput on an Idealized Highway
Authors: Hall Randolph W.
Published: October 2008

Highway automation has recently enjoyed renewed research interest as a method for solving highway congestion problems. To determine the feasibility of automated highways, it will be essential to estimate the automated highway benefits. A critical task in the analysis of automated highway benefits is to estimate the potential increase in highway capacity. This paper uses deterministic approximations to model highway throughput, accounting for both longitudinal requirements (i.e., lane flow) and lateral requirements (i.e., lane changing). The model also accounts for trip length distributions, and the effect of these distributions on the lane “flux” (i.e., the rate at which vehicles move between adjacent lanes, per unit length of highway). Based on these representations, the model identifies conditions under which lane changes have an appreciable effect on capacity, assuming certain idealized conditions are met. For typical highway parameters (mean trip length of 20 km, and mean speed of 30 m/s), and an increased nominal capacity (i.e., not factoring in lane changes) of 7200 vehicles per hour, the incremental effect of lane changes only appears to be significant (i.e., cause a capacity reduction in excess of 20%) when the time-space requirement exceeds 1000 m-s. As an example, this requirement could imply a lane change maneuver that lasts 10 seconds and requires 100 m of lane-space during execution. This calculation does not factor in queueing effects. To ensure that all or most vehicles succeed in exiting at their desired locations, the actual capacity will have to be decreased somewhat further.
An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers
Authors: Gendreau Michel , Laporte Gilbert , Séguin René
Published: October 2008

In this article, the following stochastic vehicle routing problem is considered. Each customer has a known probability of presence and a random demand. This problem arises in several contexts, e.g., in the design of less-than-truckload collection routes. Because of uncertainty, it may not be possible to follow vehicle routes as planned. Using a stochastic programming framework, the problem is solved in two stages. In a first stage, planned collection routes are designed. In a second stage, when the set of present customers is known, these routes are followed as planned by skipping the absent customers. Whenever the vehicle capacity is attained or exceeded, the vehicle returns to the depot and resumes its collections along the planned route. This generates a penalty. The problem is to design a first stage solution in order to minimize the expected total cost of the second state solution. This is formulated as a stochastic integer program, and solved for the first time to optimality by means of an integer L-shaped method.
Heuristic Bounds and Test Problem Generation for the Time-Dependent Traveling Salesman Problem
Authors: Vander Wiel Russ J. , Sahinidis Nikolaos V.
Published: October 2008

The Time-Dependent Traveling Salesman Problem (TDTSP) is a generalization of the Traveling Salesman Problem (TSP) in which the cost of travel between two cities depends on the distance between the cities and the position of the transition in the tour. There exists a number of applications of the TDTSP in the fields of distribution and scheduling. We present a new mixed-integer linear programming (MILP) formulation for the TDTSP. A directed multi-partite graph representation of this model facilitates the development of a local search heuristic which extends the well known Lin-Kernighan tour improvement heuristic to the TDTSP. A second upper bound is derived by applying a Benders-decomposition-based heuristic to the MILP formulation. The Benders master problem is further approximately solved to provide a lower bound. We also develop a method for generating TDTSP instances with known optimal solutions. Finally, computational experience with the heuristics and problem generator is presented for problems with up to 100 cities. The results demonstrate that the heuristics can achieve optimal or very good near-optimal solutions on a variety of problem classes with minimal computational effort.
Probabilistic Sales-Delivery Man and Sales-Delivery Facility Location Problems on a Tree
Authors: Averbakh Igor , Berman Oded
Published: October 2008

Suppose that customers situated at nodes of a network generate calls for service with known probabilities. There is a server, who must perform a service tour that includes all customers requiring service. The order of providing service to customers for each potential list of calls is uniquely defined by some a priori fixed basic sequence of all the customers (a priori tour). The problems considered in this paper are to find an optimal home location for the server and (or) an optimal basic sequence so as to minimize the expected total waiting time or the expected maximal waiting time of customers, subject to the constraint that the expected total length of the tour is minimal. For these problems on a tree, polynomial algorithms are presented with complexity O(n log n) for general trees and O(n) for trees with bounded vertex degree. Reoptimization variants of these problems on a tree (when the server can reoptimize his tour for each list of calls) are also investigated.
Linearly-Constrained Entropy Maximization Problem with Quadratic Cost and Its Applications to Transportation Planning Problems
Authors: Fang S. C. , Tsao H.-S. J.
Published: October 2008

Many transportation problems can be formulated as a linearly-constrained convex programming problem whose objective function consists of entropy functions and other cost-related terms. In this paper, we propose an unconstrained convex programming dual approach to solving these problems. In particular, we focus on a class of linearly-constrained entropy maximization problem with quadratic cost, study its Lagrangian dual, and provide a globally convergent algorithm with a quadratic rate of convergence. The theory and algorithm can be readily applied to the trip distribution problem with quadratic cost and many other entropy-based formulations, including the conventional trip distribution problem with linear cost, the entropy-based modal split model, and the decomposed problems of the combined problem of trip distribution and assignment. The efficiency and the robustness of this approach are confirmed by our computational experience.
The Effect of Spatial Structure on p-Median Results
Authors: Peeters Dominique , Thomas Isabelle
Published: October 2008

We test the sensitivity of the solutions of the p-median model to the shape of the underlying communication network. More precisely, the p-median problem is applied to 17 different networks representing various regular, radial, and circum-radial configurations. This study leads to interesting conclusions in the domain of regional economics and land planning and to striking illustrations of already discussed theoretical problems. This exploratory analysis hopefully opens up a broad avenue for further investigations.
Bibliographic Section
Authors: Wegener Michael
Published: October 2008

A Billion Trips a Day: Tradition and Transition in European Travel Patterns, edited by Ilan Salomon, Piet Bovy and Jean-Pierre Orfeuil, Kluwer Academic Publishers, Dordrecht/Boston/London, ISBN 0-7923-2297-5. xxiv + 460 pp., 111 figures, 122 tables, Df1 190.00 (US$ 116.00)—reviewed by Michael Wegener.
A Technique for Estimating V/STOL Market Shares
Authors: Sommers Alexis N.
Published: October 2008

A theory and technique is presented for estimating the business travel market shares of future V/STOL aircraft as functions of the nondemographic mode choice factors of time, cost, safety, comfort, convenience, and weather reliability. A linear mathematical model is described. Inputs to the model are derived directly from questionnaire surveys incorporating semantic differential and multiple choice questions. The technique is demonstrated on a city-pair 112 miles apart where business travel currently favors automobiles. Two V/STOL aircraft types competing with conventional modes in a hypothetical 1985 environment are predicted to attract 48 per cent of the business travel in this city-pair market.
A Column Generation Algorithm for a Ship Scheduling Problem
Authors: Appelgren Leif H.
Published: October 2008

This paper describes an algorithm for a ship scheduling problem, obtained from a Swedish shipowning company. The algorithm uses the Dantzig-Wolfe decomposition method for linear programming. The subprograms are simple network flow problems that are solved by dynamic programming. The master program in the decomposition algorithm is an LP problem with only zero-one elements in the matrix and the right-hand side. Integer solutions are not guaranteed, but generation and solution of a large number of problems indicates that the frequency of fractional solutions is as small as 1–2 per cent. Problems with about 40 ships and 50 cargoes are solved in about 2.5 minutes on an IBM 7090. In order to resolve the fractional cases, some integer programming experiments have been made. The results will be reported in a forthcoming paper.
Computer Generated Time-Tables and Bus Schedules for a Large Bus Transport Network
Authors: Seshagiri N. , Narasimhan R. , Mehndiratta S. L. , Chanda B. K.
Published: October 2008

This report describes a method developed for analyzing a large bus transport on a digital computer with a view to improving the utilization of buses and the duty allocation for the crew without making elaborate structural changes in the existing setup. With the a priori statistics concerning the alighting and boarding of passengers at each stage of a route for different times of the day and the a posteriori statistics concerning the waiting time of the passengers at various stages of the route as the information supplied by the transport organization, a computer program has been developed to realize time-tables and bus schedules that can optimize the fixed plus variable cost of operation subject to the requirements and constraints imposed on the optimization procedure by the passengers, the crew, and the management.
The Effect of Short Cars on Flow and Speed in Downtown Traffic: A Simulation Model and Some Results
Authors: McClenahan John W. , Simkowitz Howard J.
Published: October 2008

The flow of vehicles down one lane of a straight, signalized urban street with fixed cycle traffic lights at 500 ft intervals was simulated by means of a Fortran IV computer program. A car-following model and a simple model of lead-driver behavior were used to model driver responses. Flow and speed measurements were made for “levels of congestion” in which, on average, 5, 10, 15, and 20 cars were queued at each traffic light; 10 ft cars, 20 ft cars, and mixtures of these two lengths were simulated. With 15 cars queued at each light a 70 per cent increase inflow can be obtained by the substitution of 10 ft cars for 20 ft cars. Average speed increases by about 57 per cent, from 3.5 ft/sec to 5.5 ft/sec. That the number of vehicles queued per light remains constant has been assumed. Complete results of our simulation are presented in Table III and Figures 2, 3, and 4. Validation of the simulation model was provided by traffic flow counts and speed measurements on Walnut Street in downtown Philadelphia; correspondence between model and reality was close.
Letters to the Editor—Comments on “A Preliminary Investigation of Railway Signaling Methods by Computer Simulation Studies”
Authors: Waterman John F.
Published: October 2008

A common assumption, carried over from previous technologies and retained by Askew, Beardwood, and Newby, is questioned. Its elimination would permit existing cab-signaling technology to be used to maximize capacity on high-density railroad routes. But technological and economic ramifications need to be investigated. The authors' reply by J. R. Askew, J. E. Beardwood, and D. Newby of Atomic Energy Establishment, Winfrith, Dorchester, Dorset, U.K. follows.
Timetables for a Suburban Rail Transit System
Authors: Salzborn Franz J. M.
Published: October 2008

In this paper a scientific method for the construction of timetables for a suburban railway line without branches is developed. It is shown that such timetables are largely determined by stop-schedules. Two criteria for stop-schedules have been considered: the number of intermediate passenger stops and the number of carriage miles. A mathematical formulation is presented and it is shown that the problems of finding optimal stop-schedules can be solved with dynamic programming. Zone-stop-schedules, a type of stop-schedule with several operational advantages, have received special attention.
A Simulation Study of the Operational Performance of Left-Turn Phasing and Indication Sequences
Authors: Asante Seth A. , Ardekani Siamak A. , Williams James C.
Published: October 2008

In this paper, the operational performance of left-turn phasing and indication sequence is presented. The study contributes to the selection of an optimal left-turn phasing and indication sequence. Presently, there are no comprehensive guidelines to assist traffic engineers in this task. The operational performance of six different phase patterns and three intersection geometries are addressed using simulations. The threshold values to identify traffic conditions under which each phase pattern performs best and beyond which another phase pattern should be considered are also formulated. The efficiency of leading and lagging sequences are addressed. The study shows that when some left-turn protection is needed, the less restrictive protected/permissive phase should be used unless there is a severe safety problem which necessitates the use of protected only phase. The permissive only phase is recommended for low left-turn and opposing volumes.
Depth-First Solutions for the Deliveryman Problem on Tree-Like Networks: An Evaluation Using a Permutation Model
Authors: Webb Ian R.
Published: October 2008

The Deliveryman Problem, or DMP (also referred to as the Traveling Repairman Problem TRP), requires a single traveling service unit with a specified home location to serve a set of customers, each of which has a weight or priority. The objective is to find a tour which minimizes a weighted average of the times the customers wait for service. This paper examines the effectiveness of depth-first routes for the DMP on tree and cactus networks. Depth-first routes involve traversing the tree or cactus network in depth-first manner. The best depth-first solution for the DMP can be found very quickly. The evaluation of depth-first routes on general tree and cactus networks is based on a novel formulation for the DMP which employs permutation decision variables and includes as constraints necessary optimality conditions based on network structure. We are unaware of any previous explicit use of these permutation variables in the routing literature. This formulation leads to a Lagrangian relaxation which can be solved as a single-machine minimum weighted-completion time problem with forest precedence constraints. This subproblem is embedded in a subgradient optimization procedure and lower bounds on the costs of optimal DMP solutions are calculated. Computational tests were carried out to determine the quality of the depth-first solutions and the sharpness of the permutation lower bounds. Problem characteristics considered were problem size, variability in arc lengths, variability in customer weights, size of cycles and percentage of nodes in cycles.
Composite Regions of Feasibility for Certain Classes of Distance Constrained Network Location Problems
Authors: Tansel Barbaros Ç. , Yeşïlkökçen Gülcan N.
Published: October 2008

Distance constrained network location involves locating m new facilities on a transport network G so as to satisfy upper bounds on distances between pairs of new facilities and pairs of new and existing facilities. The problem is 𝒩𝒫-complete in general, but polynomially solvable for certain classes. While it is possible to give a consistency characterization for these classes, it does not seem possible to give a global description of the feasible set. However, substantial geometrical insights can be obtained on the feasible set by studying its projections onto the network. The j-th projection defines the j-th composite region which is the set of all points in G at which new facility j can be feasibly placed without violating consistency. We give efficient methods to construct these regions for solvable classes without having to know the feasible set and discuss implications on consistency characterization, what if analysis, and recursive solution constructions.
Bibliographic Section
Authors: Hauer Ezra , Kaysi Isam A.
Published: October 2008

Target Risk by G. J. S. Wilde, PDE Publications, Toronto, 1994—reviewed by Ezra Hauer

Beyond Traffic Safety by J. P. Rothe, Transaction Publications, New Brunswick, MA and London, 1994—reviewed by Ezra Hauer

Urbon Travel Demand Modeling: From Individual Choices to General Equilibrium by Norbert Oppenheim, John Wiley and Sons, New York, 1995, xx + 480 pp., ISBN 0-471-55723-4—reviewed by Isam A. Kaysi
Bicriterion Traffic Assignment: Basic Theory and Elementary Algorithms
Authors: Dial Robert B.
Published: October 2008

This paper describes a bicriterion equilibrium traffic assignment model that accurately forecasts path choices and consequent total arc flows for a stochastically diverse set of trips. Called T2, its develops around a linear generalized cost model, which generalizes classical traffic assignment by relaxing the value-of-time parameter from a constant to a random variable with an arbitrary probability distribution. For the case where arc time and/or cost are flow dependent, this paper formulates conditions and algorithms for stochastic bicriterion user-optimal equilibrium arc flows, which reflect every trip's exclusive use of a path that minimizes its particular perception of generalized cost.
Routing Trains Through Railway Stations: Model Formulation and Algorithms
Authors: Zwaneveld Peter J. , Kroon Leo G. , Romeijn H. Edwin , Salomon Marc , Dauzère-Pérès Stéphane , Van Hoesel Stan P. M. , Ambergen Harrie W.
Published: October 2008

In this paper we consider the problem of routing trains through railway stations. This problem occurs as a subproblem in a project which the authors are carrying out in cooperation with the Dutch railways. The project involves the analysis of future infrastructural capacity requirements in the Dutch railway network. Part of this project is the automatic generation and evaluation of timetables. To generate a timetable a hierarchical approach is followed: at the upper level in the hierarchy a tentative timetable is generated, taking into account the specific scheduling problems of the trains at the railway stations at an aggregate level. At the lower level in the hierarchy it is checked whether the tentative timetable is feasible with respect to the safety rules and the connection requirements at the stations. To carry out this consistency check, detailed schedules for the trains at the railway yards have to be generated. In this paper we present a mathematical model formulation for this detailed scheduling problem, based on the Node Packing Problem (NPP). Furthermore, we describe a solution procedure for the problem, based on a branch-and-cut approach. The approach is tested in an empirical study with data from the station of Zwolle in The Netherlands.