Search

Loading ships as they are unloaded (double cycling) can improve the efficiency of a quay crane and container port. This paper describes the double-cycling problem, and presents solution algorithms and simple formulae to determine reductions in the number of operations and operating time using the technique. We focus on reducing the number of operations necessary to turn around a row of a ship. The problem is first formulated as a scheduling problem, which can be solved optimally. A simple lower bound for all strategies is then developed. We also present a greedy algorithm that yields a simple and tight upper bound. The gap between the upper and lower bounds is so small that the formula for either bound is an accurate predictor of crane performance. The analysis is then extended to double cycling when ships have deck hatches. Results are presented for many simulated vessels, and compared to empirical data from a real-world trial. The research demonstrates that double cycling can create significant efficiency gains in crane productivity, typically reducing the number of cycles by about 20% and the operational time by about 10% when double cycling only below deck.

Bounds and approximate formulae are developed for the average optimum distance of the transportation linear programming (TLP) problem with homogeneously, but randomly distributed points and demands in a region of arbitrary shape. It is shown that if the region size grows with a fixed density of points, then the cost per item is bounded from above in 3+ dimensions (3+-D), but not in 1-D and 2-D. Lower bounds are also developed, based on a mild monotonicity conjecture. Computer simulations confirm the conjecture and yield approximate formulae. These formulae turn out to have the same functional form as the upper bounds. Curiously, the monotonicity conjecture implies that the cost per item does not depend on zone shape asymptotically, as problem size increases, for 2+-D problems but it does in 1-D. Therefore, the 2-D case can be viewed as a transition case that shares some of the properties of 1-D (unbounded cost) and some of the properties of 3-D (shape independence). The results are then extended to more general network models with subadditive link costs. It is found that if the cost functions have economies of scale, then the cost per item is bounded in 2-D. This explains the prevalence of the “last mile” effect in many logistics applications. The paper also discusses how the results were used to estimate costs under uncertainty for a vehicle repositioning problem.

Observations of freeway traffic flow are usually quite scattered about an underlying curve when plotted versus density or occupancy. Although increasing the sampling intervals can reduce the scatter, whenever an experiment encompasses a rush hour with transitions in and out of congestion, some outlying data stubbornly remain beneath the “equilibrium” curve. The existence of these nonequilibrium points is a poorly understood phenomenon that appears to contradict the simple kinematic wave (KW) model of traffic flow. This paper provides a tentative explanation of the phenomenon, based on experimental evidence. The evidence was a FIFO queue that grew and receded over two detector stations, generating typical flow-density scatter plots at both locations. The locations were far from other interacting traffic streams. The data revealed that a transition zone where vehicles decelerated gradually existed immediately behind the queue. The transition zone was quite wide (about 1 km at both locations), moved slowly (approximately with the “shock” velocity of KW theory), and as a result spent many minutes over each detector station. Disequilibrium flow-density points arose only when the transition zone was over the detectors, suggesting that the transition zone explains their occurrence. The disequilibrium points drifted gradually from one branch of the curve to the other, as KW theory would have predicted if “shocks” had a characteristic width equal to the dimension of the transition zone. Nothing was found in the data to contradict this view. This paper also shows that in our case, if one neglects the shocks' physical dimension, the position of every vehicle can be predicted with KW theory to within approximately five vehicle spacings. Thus, it appears that KW theory can predict rather accurately traffic behavior at the back of FIFO queues, i.e., when the lanes are equally attractive to all drivers. We end with a discussion offering some perspective on how the findings of this paper related to the traffic thinking found in the current literature.

This paper is concerned with the performance of multicommodity capacitated networks in a deterministic but time-dependent environment. For a given time-dependent origin-destination table, this paper asks if it is easy to find a way of regulating the input flows into the network to avoid queues from growing internally, i.e., to avoid capacity violations. Problems of this type are conventionally approached in the traffic/transportation field with variational methods such as control theory (if time is continuous) and with mathematical programming (if time is discrete). However, these approaches can only be expected to work well ifthe set off easible solutions is convex. Unfortunately, it is found in this paper that this is not the case. It is shown that continuous-time versions of the problem satisfying the smoothness conditions of control theory can have a finite but very large number off easible solutions. The same happens for the discrete time case. These difficulties arise even with the simplest versions of the problem (with unique origin-destination paths, perfect information, and deterministic travel times). The paper also shows that the continuous-time feasibility problem is NP-hard, and that if we restrict our attention to (practical) problems whose data can be described with a finite number ofbits (e.g., in discrete time), then the problem is NP-complete. These results are established by showing that the problem instances of interest can be related to the Directed Hamiltonian Path problem by a polynomial transformation.

This research shows that certain time-dependent congestion reduction schemes involving tolls have the potential for benefiting every driver even if the collected revenues are not returned to the payers. The paper considers a population of commuters who use a single bottleneck during the morning rush hour and try to arrive at work on time. It is assumed that the number of commuters is fixed (independent of the control strategy) and that each commuter wishes to pass through the bottleneck at a given time, which may differ across commuters. Commuters are otherwise identical. Each of them chooses his/her arrival time at the bottleneck so as to minimize a linear combination of monetary cost (tolls), queuing time, and deviation from the desired passage time. A time-dependent toll is applied during a time window, but some commuters are exempted from paying it. Every day, each commuter is classified as either “free” or “paying.” The classification method is such that, in the long-run, the fraction of days, f, that a commuter is free is the same for all commuters, and the fraction of free commuters is f every day. Free commuters are allowed to use the bottleneck without paying the toll, whereas paying commuters can avoid the toll only if they pass through the bottleneck outside the time window. It is shown that, if commuters wish to pass through the bottleneck close together, then the toll, the window, and the fraction of free commuters can be chosen in a way that will benefit everyone by inducing an equilibrium where the “peak is smoothed out” in a particular way. Up to 25% of the total user cost can be eliminated in this way.

This paper explores some of the traffic phenomena that arise when drivers have to navigate a network in which queues back up past diverge intersections. If a diverge provides two alternative routes to the same destination and the shorter route has a bottleneck that generates a queue, one would expect that queue to stabilize at an equilibrium level where the travel time on both routes is roughly equal. If the capacity of the alternative route is unlimited then this network can accommodate any demand level. However, if the bottleneck is so close to the upstream end of the link that the equilibrium queue cannot be contained in the link, then the trip time on the queued route cannot grow to match that on the alternate route. This means that the alternative route can never be attractive, even if the queue spills back past the diverge, and that drivers approaching the diverge will act as if the alternative route did not exist. As a result, a steady flow into the system greater than the capacity of the bottleneck will cause a queue to grow all the way back to the origin (blocking it). The final result is an “oversaturated static state” where the queue regulates the input flow into the system. Curiously, if the bottleneck capacity of this network is reduced below a critical level (or is eliminated altogether) then the alternative route becomes attractive again and the system cannot reach the saturation point. This phenomenon is explored in the paper, where it is also shown that: i) a network can become permanently oversaturated/undersaturated as a result of a temporary increase/decrease in link capacity, ii) even under the most favorable assumptions, and in contrast to the equivalent assignment problem with point queues, a network can be stable both in an oversaturated and an under-saturated state, and iii) temporary endogenous disturbances can permanently reverse the saturation state of a network. These findings suggest that in certain situations the time-dependent traffic assignment problem with physical queues is chaotic in nature and that (as in weather forecasting) it may be impossible to obtain input data with the required accuracy to make reliable predictions of cumulative output flows.

This paper examines a routing problem in which vehicles from a single depot cover a large area, where randomly located customers request pickup and delivery service. The paper assumes that each vehicle must serve its deliveries before it collects any pickups, that vehicles do not need to return to the depot between delivery and collection, and that each vehicle can serve at most C deliveries, but an unlimited number of pickups. This paper does not propose a detailed algorithm; rather, it discusses the pros and cons of various broad routing schemes, and quantifies their performance with simple distance formulas. The broad schemes describe implementable solutions, which can in turn be used to initialize fine-tuning algorithms. The choice of a routing scheme only depends on two dimensionless parameters: the size of the service area, relative to the area covered by one delivery route; and the ratio of the number of pickup customers to the number of deliveries. The clusters of deliveries and pickups served by a vehicle should often be radically different; unlike deliveries, pickups should be clustered in zones that have been elongated as much as possible, reaching all the way to the depot if it is internally located. It also appears that in a majority of cases not much is lost by routing for deliveries first (ignoring pickups) and for pickups second. Instances where they should be considered jointly are identified.

This paper presents simple formulae for the utility covariances of the nested logit (NL) model, and based on these defines a “scaled tree” that can be used as an aid for the interpretation of estimation results. The paper also shows that the full information log-likelihood function of linear-in-the-parameters NL models is concave in the utility parameters. Thus, conditional on the scaling parameters, full information maximum likelihood (FIML) searches cannot get trapped in local maxima.

This paper studies single server queueing systems where customers arrive according to a schedule, but not punctually, and where service might be provided in the scheduled order; thus, customers may leave the system in a sequence different to that of their arrivals. The situation arises in connection with maritime container terminals. The steady state solution to the problem follows an integral equation that may be solved numerically. When congestion is light (as is usual in well managed ports) approximate analytic solutions to the integral equation can be found. As an illustration, formulas are given that apply if the deviations from the schedule and the service times have some specific distributions. These expressions accurately predict the expected delay for systems with fairly unpunctual arrivals and occasional congestion. The paper also contains an exact analytical solution for the special case in which service times are constant and the deviations from the arrival schedule are independent Gumbel variables.

Review of books: (1) Proceedings of the Seventh International Symposium on Transportation and Traffic Theory, T. Sasaki and T. Yannaoka (Eds.), The Institute of Systems Science Research, Kyoto, 1977, 944 pages; (2) Mathematical Models: Mechanical Vibrations, Population Dynamics and Traffic Flow, Richard Haberman, Prentice-Hall, Englewood Cliffs, New Jersey, 402 pages, $18.95.

The purpose of this paper is to develop a simple formula to predict the distance traveled by fleets of vehicles in physical distribution problems involving a depot and its area of influence. Since the transportation cost of operating a break-bulk terminal (or a warehouse) is intimately related to the distance traveled, the availability of such a simple formula should facilitate the study of more complex logistics problems. A simple manual dispatching strategy intended to mimic what dispatchers do, but simple enough to admit analytical modeling is presented. Since the formulas agree rather well with the length of (nearly optimal) computer built tours, the predictions should approximate distances achievable in practice; the formulas seem realistic. The technique is a variant of the classical “cluster-first, route-second” approach to vehicle routing problems. In these approaches, the depot influence area is first partitioned into districts containing clusters of stops; one vehicle route is then constructed to serve each cluster. Our procedure is characterized by the way district shapes are chosen; ignoring shape during the clustering step can increase significantly travel distances. The technique is simple. To exercise it, one needs only a pencil, eraser, and a scale map showing the destinations. Once mastered, the technique takes only a few minutes. This time should increase only linearly with the number of destinations. For repetitive problems, the technique can be enhanced with the help of interactive computer graphics. A newspaper delivery problem for the city of San Francisco is used as an illustration.

In this paper, various strategies for minimizing the amount of switching done at a classification yard are examined. We investigate how the allocation of blocks (the sorting classes recognized at the yard) to classification tracks affects switching work. Given are the sorting classes, as well as the schedule and block makeup of the departing trains. Only static strategies are considered—strategies where every block has been assigned permanently to a classification track. Simple formulas are given for the minimum number of tracks needed to implement a strategy, and for the amount of switching work given a number of tracks. The total track length is also examined. The results are significantly influenced by the number of blocks recognized by the yard; given this number, the results are nearly independent of the train departure schedule, the number of departing trains, and the number of blocks of individual trains. This feature simplifies the study of larger problems (e.g., dynamic blocking strategies) and, most importantly, makes train formation and scheduling an easier job at every yard.

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

This paper discusses an element of forecasting with disaggregate demand models that has received little attention so far; namely, the extent to which the accuracy of the final prediction depends on the accuracy of the calibration process. The paper introduces a numerical technique to evaluate approximate confidence intervals for the expected number of people using a transportation facility and approximate prediction intervals for the actual usage. It is shown that, unless the magnitude of the variance of the estimated parameters is considerably small, the predictions that result may be biased and the resulting confidence intervals, inaccurate. The degree of accuracy that can be obtained with different parameter variances is illustrated numerically for the binary probit model.

In the field of logistics, a variable that is to be predicted (e.g., cost) often varies in a nonsmooth, irregular, but known manner, with various factors (e.g., distances, quantity, and density of material to be carried, etc.). This paper identifies conditions, where given approximate input factors, a prediction of the variable is less error prone if one uses a smooth approximation to the exact function of the factors. This phenomenon, which is quite prevalent, may enhance the appeal of continuous approximation models in some instances.

This paper contains a quantitative evaluation of probabilistic traffic assignment models and proposes an alternate formulation. First, the concept of stochastic-user-equilibration (S-U-E) is formalized as an extension of Wardrop's user-equilibration criterion. Then, the stochastic-network-loading (S-N-L) problem (a special case of S-U-E for networks with constant link costs) is analyzed in detail and an expression for the probability of route choice which is based on two general postulates of user behavior is derived. The paper also discusses the weaknesses of existing S-N-L techniques with special attention paid to Dial's multipath method and compares them to the suggested approach. The proposed model seems reasonable and does not exhibit the inherent weaknesses of the logit model when applied to sets of routes which overlap heavily. The discussion is supported by several numerical examples on small contrived networks. The paper concludes with the discussion of two techniques that can be used to approximate the link flows resulting from the proposed model in large networks.

This paper develops an analytic method for minimizing the cost of distributing freight by truck from a supplier to many customers. It derives formulas for transportation and inventory costs, and determines the optimal trade-off between these costs. The paper analyzes and compares two distribution strategies: direct shipping (i.e., shipping separate loads to each customer) and peddling (i.e., dispatching trucks that deliver items to more than one customer per load). The cost trade-off in each strategy depends on shipment size. Our results indicate that, for direct shipping, the optimal shipment size is given by the economic order quantity (EOQ) model, while for peddling, the optimal shipment size is a full truck. The peddling cost trade-off also depends on the number of customers included on a peddling route. This trade-off is evaluated analytically and graphically. The focus of this paper is on an analytic approach to solving distribution problems. Explicit formulas are obtained in terms of a few easily measurable parameters. These formulas require the spatial density of customers, rather than the precise locations of every customer. This approach simplifies distribution problems substantially while providing sufficient accuracy for practical applications. It allows cost trade-offs to be evaluated quickly using a hand calculator, avoiding the need for computer algorithms and mathematical programming techniques. It also facilitates sensitivity analyses that indicate how parameter value changes affect costs and operating strategies.

This paper presents transportation equilibrium results that apply to both discrete choice models and network problems. Specifically, it shows that many network equilibrium problems admit an unconstrained extremal formulation and that unconstrained optimization algorithms may be used for their solution. Similar results are derived for equilibrium problems involving discrete choice models. It also shows that a certain class of stochastic networks exhibit unique equilibria and that simulation algorithms with fixed step sizes converge almost surely to the equilibrium point.

This paper shows how distribution problems with delivery time constraints can be modeled approximately with just a few variables. Its objective is neither to develop a scheduling algorithm nor an exact predictive method; rather, it is to illustrate some trade-offs and principles that can be used for planning and algorithm development. A workday is divided into time periods. Time windows are modeled by specifying the period in which a vehicle should visit each customer. (The companion paper explores scenarios where many customers do not specify a time window, and thus, it is advantageous not to allocate all the customers to periods.) Travel distance expressions are provided for a “cluster-first, route-second” strategy, similar to some routing methods currently in use. Travel distance expressions are also provided for refinements of the strategy, including one in which tours are systematically staggered, overlapping. The consequent reductions in travel distance can be quite significant. We suggest here that more attention should be paid to the clustering part of algorithm construction, and point to ways in which the customers served by one vehicle should be selected.

It was shown in a previous publication that, in order to minimize the prediction error of a statistical model with a discrete dependent variable, it is possible to design an optimal survey by solving a nonlinear mathematical program with linear constraints. It is shown here that this mathematical program is a convex programming problem and that the gradient and Hessian of the objective function admit a closed form. Consequently, very efficient optimal seeking methods which guarantee a globally optimal sampling strategy can be used. As a byproduct of the analysis a simple test for multicollinearity was also developed.

Although baggage handling is a major airport expense and congestion of luggage claim areas is quite common, knowledge of how baggage claim devices perform their task under congested conditions is virtually nonexistent. In order to bridge this gap this paper describes a model that, for different demand conditions, can predict the performance of a claim device depending on its characteristics. The demand conditions considered include aircraft size, lag between arrival of passengers and bags, and the fraction of passengers that transfer. The characteristics of the claim device that affect performance are frontage length, cycle time, and maximum throughput. The proposed model can predict the accumulation of passengers around the claim device, the time it takes to handle a planeload, and the average passenger service time as the demand conditions and claim device characteristics change. Although the model is deterministic and makes a number of simplifying assumptions, it is also easy to apply if the arrival pattern of bags and people to the claim area is known. Thus, if predictive and/or normative models for these arrivals become available, fairly simple and realistic procedures to study a number of baggage claim area design and operation issues could be developed around the model. The model, which is based on data gathered at the American Airline, National Airline, and Western Airline terminals at San Francisco International Airport, was able to reproduce the observed light congestion phenomena quite well; especially in the case that consisted of a rather large planeload. Unfortunately, lack of resources prevented us to observe a variety of terminals, including situations with much congestion and many bags per passenger. Because of this, further refinements and/or fine tuning of the formulas is definitely recommended.

The transportation planning forecasting process has been traditionally performed on a sequential, disconnected, heuristic basis, using different methodologies for each one of the stages. In an attempt to improve this situation, a first step toward developing a unified transportation forecasting methodology is described in this paper. This is done by showing how many, seemingly different, problems can be cast as analogous route choice problems on abstract networks and studied with the same methodology. As a consequence of this analogy, it is possible to perform equilibrium analyses and to study several problems simultaneously, by choosing an adequate topology for the abstract network. The bulk of this paper is devoted to presenting an algorithm within which many of these transportation equilibrium analyses can be carried out. The conditions of equilibrium are identified and defined, and an efficient algorithm for the solution of the equilibration problem is introduced. The solution method, which uses the multinomial probit model for allocation of flow to routes, can increase the accuracy and reduce the cost of many transportation equilibrium analyses.

Even though multinomial probit models have many attractive theoretical features and have been proposed for diverse choice problems (such as modal split and route choice in the transportation field), they have never been used in practice due to the lack of an adequate numerical technique for their application. The purpose of this paper is to introduce such a technique and to demonstrate the feasibility of forecasting with multinominal probit models. Our limited computational experience with the proposed numerical technique indicates that it is accurate, and can be efficiently applied to large choice problems.

This paper extends the results of a previous study concerning distribution with time windows. It is recognized that customers who do not need to be allocated to a time window should receive different service than the rest. Three strategies were studied to accomplish that: stratified service, discriminating service, and staggered and discriminating service. Of these, the last strategy yields the lowest local distribution distance per customer, a distance which can be less than half that for the strategy explained in the previous paper (joint service). Stratified service, however, can yield a lower line-haul distance per customer than staggered and discriminating service. In a specific case, a numerical comparison between stratified service and staggered and discriminating service should determine the overall best choice. This choice notwithstanding, the best strategy involves overlapping vehicle tours. The conventional wisdom of dividing customers into non-overlapping clusters for vehicle routing does not seem attractive for distribution problems with time windows.

Investigations in this area have been directed at finding the delay to a motorist who arrives at an intersection and wishes to cross a high-priority traffic stream. In this paper two conceptual errors that have appeared in some past publications are identified and corrected.

This study illustrates a statistical procedure that can be used to estimate the fraction of a given population experiencing a “rare” event during a long time period, given a few days of observation. In an automobile usage context, the rare event could be the occurrence of an automobile occupancy of four or more persons and/or a travel distance of 100 miles or more on any given day. The technique, which can be important for the design of durable goods, is illustrated with four numerical examples.

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.

Automobile and truck production at General Motors involves shipping a broad variety of materials, parts, and components from 20,000 supplier plants to over 160 GM plants. To help reduce logistics costs at GM, the decision tool TRANSPART was developed. In its initial application for GM's Delco Electronics Division, TRANSPART identified a 26 percent logistics cost savings opportunity ($2.9 million per year). Today, TRANSPART II—a commercial version of the tool—is being used in more than 40 GM plants.

This paper examines the structure of many-to-many logistics networks. Using as little data as possible, it attempts to answer macroscopic questions such as: How many terminals should be used? Should they be used at all? What should be the frequency of service? Although such a problem could be formulated with a large number of parameters and data, we show that near-optimal network structures can be characterized by two dimensionless constants which can be determined from the data (e.g., from the value of the items carried, the number of origins, the size of the service region, etc …). The number of stops made by vehicles, for example, is proportional to powers of the dimensionless constants, the powers depending on the number of transhipments allowed. Similar expressions are given for other network descriptors and for the resulting cost. The simple formulas and principles embodied in the paper can lead to quick cost estimates and rough design plans, with a minimum of data, that can be fine-tuned with existing tools. We also highlight the difference between many-to-many and one-to-many (or many-to-one) networks: we describe the (break-bulk) role of terminals as swapping points, and quantify the benefits and disadvantages of routing vehicles through a terminal that lies in their desired general direction of travel.

This paper discusses a family of general link cost functions that can be used to model multimodal transportation network equilibrium problems. The family includes as a special case the currently favored family of monotonically increasing functions but does not necessarily have to have a symmetric or semi-definite Jacobian. In this way multimodal networks can be modeled somewhat more realistically. The paper also allows stochastic link costs for some or all the links and modes. It is shown that under mild conditions the equilibrium exists and is unique, but more importantly, that there is a simple, single-equilibrium algorithm that is proven to converge for stochastic networks with the link cost family discussed in the paper. Finally, it is pointed out that many variable demand problems also exhibit unique equilibria, but that there are some which do not. An example which illustrates this fact is given.