Search

Technical and economic investigations of automated highway systems (AHS) are addressed. It has generally been accepted that such systems show potential to alleviate urban traffic congestion, so most of the AHS research has been focused instead on technical design and implementation issues. It is demonstrated that, despite making a number of assumptions that are favorable to AHS, the actual viable implementation opportunities for AHS are scarce, and that most existing congested urban areas can be disqualified on the basis of at least one criterion developed herein. Technical investigations are described, including realistic estimates of AHS capacity, interfacing with the local street system, and storage issues. Discussion then turns to identifying criteria to help establish the types of urban areas that might be likely candidates for AHS technology. These criteria relate to the nature of the surrounding infrastructure and the traffic demands placed on it, as well as the economic realities of AHS implementation. Certain “boutique” locations where AHS might be beneficial are identified, but it is uncertain whether enough benefit could be realized to make AHS palatable to the general public. AHS technology is not dismissed, but the simple analyses contained herein should warn that much more research into these areas is required before fully informed decision making about the future of AHS technologies can be accomplished.

Although the “first order” continuum theory of highway traffic proposed by Lighthill and Whitham (1955) and Richards (1956)—the LWR model—can predict some things rather well, it is also known to have some deficiencies. In an attempt to correct some of these, “higher order” theories have been proposed starting in the early 70s. Unfortunately, the usefulness of these improvements can be questioned. This note describes the logical flaws in the arguments that have been advanced to derive higher order continuum models, and shows that the proposed high order modifications lead to a fundamentally flawed model structure. The modifications can actually make things worse. As an illustration of this, it is shown that any continuum model of traffic flow that smooths out all discontinuities in density will predict negative flows and negative speeds (i.e., “wrong way travel”) under certain conditions. Such unreasonable predictions are made by all existing models formulated as a quasilinear system of partial differential equations in speed, density, and (sometimes) other variables but not by the LWR model. The note discusses the available empirical evidence and ends with a (hopefully positive) commentary on what can be accomplished with first-order models.

This article shows that if the kinematic wave model of freeway traffic flow in its general form is approximated by a particular type of finite difference equation, the finite difference results converge to the kinematic wave solution despite the existence of shocks in the latter. This result, which applies to initial and boundary condition problems with and without discontinuous data, is shown not to hold for other commonly used finite difference schemes. In the proposed approximation, the flow between two neighboring lattice points is the minimum of the two values returned by: 1. (a) a “sending” function evaluated at the density prevailing at the upstream lattice point and 2. (b) a “receiving” function evaluated at the downstream lattice point. The sending and receiving functions correspond to the increasing and decreasing branches of the freeway's flow-density curve. The article presents an asymptotic formula for the errors introduced by the proposed finite difference approximation and describes quantitatively the finite difference's shock-capturing behavior. Errors are shown to be approximately proportional to the mesh spacing with a coefficient of proportionality that depends on the wave speed, on its rate of change with density, and on the slope and curvature of the initial density profile. The asymptotic errors are smaller than those of Lax's first-order, centered difference method which is also convergent. More importantly though, the proposed procedure never yields negative flows, and this makes it attractive in practical engineering applications when the mesh cannot be made arbitrarily small.

This article shows that certain congestion reduction schemes have the potential for not penalizing anyone. The traditional social welfare approach is modified to address the distribution of gains and losses across the population. As a first step in this line of research, we consider a transportation system where congestion delay is simply given by a function of its user flow. We show that a particular pricing scheme with variable tolls, that can be viewed as hybrid between rationing and pricing, can benefit everyone (unlike pure pricing alone) even if the collected revenues are not returned to the population. The simple conditions under which this is possible are identified. Few data are needed to choose a beneficial policy. Examples are given.

This article examines a general form of link travel time functions considered in the dynamic traffic assignment literature and shows that it only makes some physical sense in the special case where each function denotes either a link with no spatial dimension containing a point queue or a link with constant travel time and no queueing. Roadway segments exhibiting both phenomena must be represented by two links in series.

This article shows how the evolution of multi-commodity traffic flows over complex networks can be predicted over time, based on a simple macroscopic computer representation of traffic flow that is consistent with the kinematic wave theory under all traffic conditions. The method does not use ad hoc procedures to treat special situations. After a brief review of the basic model for one link, the article describes how three-legged junctions can be modeled. It then introduces a numerical procedure for networks, assuming that a time-varying origin-destination (O-D) table is given and that the proportion of turns at every junction is known. These assumptions are reasonable for numerical analysis of disaster evacuation plans. The results are then extended to the case where, instead of the turning proportions, the best routes to each destination from every junction are known at all times. For technical reasons explained in the text, the procedure is more complicated in this case, requiring more computer memory and more time for execution. The effort is estimated to be about an order of magnitude greater than for the static traffic assignment problem on a network of the same size. The procedure is ideally suited for parallel computing. It is hoped that the results in the article will lead to more realistic models of freeway flow, disaster evacuations and dynamic traffic assignment for the evening commute.

This paper presents a simple representation of traffic on a highway with a single entrance and exit. The representation can be used to predict traffic's evolution over time and space, including transient phenomena such as the building, propagation, and dissipation of queues. The easy-to-solve difference equations used to predict traffic's evolution are shown to be the discrete analog of the differential equations arising from a special case of the hydrodynamic model of traffic flow. The proposed method automatically generates appropriate changes in density at locations where the hydrodynamic theory would call for a shockwave; i.e., a jump in density such as those typically seen at the end of every queue. The complex side calculations required by classical methods to keep track of shockwaves are thus eliminated. The paper also shows how the equations can mimic the real-life development of stop-and-go traffic within moving queues.

This paper develops an analytical model to evaluate serial and parallel designs for an assembly system. The purpose is to identify when each design is cost-effective, using minimal data. The analysis shows that the design alternatives are based on a trade-off between labour and equipment utilization. Equations are derived for a simple system to illustrate this trade-off. Results indicate that the optimal trade-off depends simply on the ratio of labour to equipment costs. The trade-off analysis provides a first step towards establishing basic principles for assembly system design.

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 presents a handling cost model for a warehouse that supplies one or more stores with a large number of items and examines operating strategies whose objective is to minimize the sum of handling, transportation and inventory costs. Decisions must be made regarding the frequency of shipments to the store(s) (i.e. the transportation schedule) and the specific items and lot sizes included in each shipment. The paper shows that, conditional on a transportation schedule, lot sizes for the different items (i.e. their delivery frequency consistent with the transportation schedule) can be determined separately across items and independently for each store. The paper also examines how these lot sizes and the best transportation schedule can be identified. The results, unlike those of other inventory models such as the economic order quantity (EOQ) model, exhibit peculiarities caused by the nonsmooth nature of handling costs. For example, the optimal lot size for individual items sent to a specific store is not a continuous function of the value or size of the items. This suggests the need for practical routing and inventory control procedures that recognize handling explicitly.

Many types of storage systems require goods to be stacked in a storage area. The amount of handling effort required to retrieve individual items from the stacks depends on stack heights and on the adopted storage strategy. The paper focuses on container import operations at marine terminals. It presents methods for measuring the amount of handling effort required when two basic strategies are adopted, one that tries to keep all stacks the same size and another than segregates containers according to arrival time. The strategies are compared in an idealized situation. The methods should be easy to modify for the analysis of similar systems.

This paper describes handling and storage strategies for export containers at marine terminals and quantifies their performance according to the amount of space and number of handling moves they require. Identifying a “best” strategy is complicated because the optimization problem is combinatorial in nature—strategies are characterized, among other things, by the order in which future ship arrivals claim preferential space in the storage area. Given a certain traffic, the paper first examines the minimal storage space needed to implement the recommended strategies. This analysis may be of use for long-term planning, helping, for example, with the selection of a handling technology, site locations, or proposed service expansions. At the operational level (i.e. for a given traffic and amount of storage space), the paper also describes how to minimize and predict the amount of handling work.

This chapter summarizes recent findings on the bullwhip effect in decentralized multi-echelon supply chains based on a system-control approach. The influence of the supply chain operation (e.g., ordering policy and lead time) is separated from that of the customer demand. Robust results that hold for any customer demand are derived for both deterministically and stochastically operated chains. We demonstrate the importance of robust analysis. It is shown that instability is an inherent property of the system, e.g., of the ordering policies used by the suppliers, but it is independent of customer demand. We first present analytical stability conditions for deterministically operated chains. The demand can be arbitrary and random. These chains are modeled and their stability is evaluated in the frequency domain. We unify some techniques used in the literature, and present analytical results with or without the knowledge of customer demand. We also allow additional randomness to arise from unpredictably varying factors in the operating environment, such as supplier behavior and transportation lead times. We then develop linear matrix inequality stability conditions to predict the bullwhip effect and bound its magnitude. Examples are shown for both types of chains. We also show the effect of advance demand information on the bullwhip effect.

Baggage transfer is a critical factor in determining connecting schedules at hub airports. This paper examines the potential benefits of “ramp transfers”-bags that bypass the hub sorting facility because they have been presorted at their point of origin. It presents three idealized baggage presorting strategies for containerized (wide-bodied) aircraft. These strategies are compared under a range of conditions, and are then integrated in a computer tool that can handle more complex problems. Presorting baggage at the origin by final destinations or groups of final destinations may be advantageous in some instances; indeed, this “zonal” transfer has already been widely adopted by the airline industry.

This paper describes the network shapes and operating characteristics that allow a transit system to deliver an accessibility level competitive with that of the automobile. To provide exhaustive results for service regions of different sizes and demographics, the paper idealizes these regions as squares with uniform demand, and their possible networks as a broad and realistic family that combines the grid and the hub-and-spoke concepts. The paper also shows how to use these results to generate master plans of transit systems for real cities. The analysis reveals which network structure and technology (Bus, Bus Rapid Transit, or Metro) delivers the desired performance with the least cost. It is found that the more expensive the system's infrastructure, the more it should tilt toward the hub-and-spoke concept. Bus Rapid Transit (BRT) competes effectively with the automobile unless a city is big and its demand low. This happens despite the uniform demand assumption, which penalizes collective transport. It is also found that if a city has enough suitable streets on which to run Bus and BRT systems, these outperform Metro even if the city is large and the demand high. Agency costs are always small compared with user costs; and both decline with the demand density. In all cases, increasing the spatial concentration of stops beyond a critical level increases both, the user and agency costs. Too much spatial coverage is counterproductive.

The paper explores some of the impacts of setting aside road lanes for the exclusive use of select vehicle classes. We examine first the case of lanes that are reserved for carpools, and then extend the analysis to bus-only lanes. In doing so, the paper makes three contributions. The first is methodological: it illustrates the importance of analyzing freeway data in full spatiotemporal detail. The second is physical: data reveal that carpool lanes are not as damaging as previously reported. In fact, these lanes are found to smooth traffic in adjacent lanes so much (by diminishing disruptive vehicle interactions near bottlenecks) that even substantially underutilized carpool lanes can increase bottleneck discharge flows. The third contribution is theoretical: it uses the smoothing phenomenon to show how the judicious deployment of bus-only lanes on freeways and city streets can favorably affect not just buses, but also cars.

This paper shows how the geometric concepts examined in the first paper perform for baggage operations, recognizing that passengers and bags travel different distances through the airport. The paper shows that the most effective geometry (minimizing total passenger walking plus baggage travel costs) can be selected by focusing on passenger walking alone, provided that one first calculates an equivalent percentage of transfers with a simple formula. The paper also introduces a “sun” terminal concept, consisting of a circular concourse (open or closed) with both gates and piers (possibly with branches), which generalizes the geometries of part one to some advantage. Finally, the paper introduces and compares the results of two techniques that are useful for more refined analyses. The first of these, calculus of variations, was used to develop simple approximate formulae for the optimal shape of parallel-pier terminals. The second technique, simulated annealing, does not lead to formulae but can be used without simplifications; e.g., to refine a preliminary design with the aid of a computer, recognizing real-world complications.

This paper examines whether it is cost-effective to synchronize production and transportation schedules on a production network. The network considered consists of one origin and many destinations. The origin produces parts that are shipped directly to each destination. Trade-offs between production set-up, freight transportation, and inventory costs on the network are analyzed, and total costs are compared for synchronized and independent schedules. The paper focuses on a simple production system, which can be modeled analytically and which allows the basic issues in synchronizing schedules to be addressed. Results suggest that cost savings from synchronization can be sufficiently large to warrant further research into more realistic albeit more complex production systems.

Real data show that reserving a lane for carpools on congested freeways induces a smoothing effect that is characterized by significantly higher bottleneck discharge flows (capacities) in adjacent lanes. The effect arises because disruptive vehicle lane changing diminishes in the presence of a carpool lane. The effect is reproducible across days and freeway sites: it was observed, without exception, in all cases tested. Queueing analysis shows that the effect greatly reduces the times spent by people and vehicles in queues. By ignoring the smoothing effect at one of the sites we analyzed, for example, one would predict that its carpool lane increased both the people-hours and the vehicle-hours traveled by well over 300%; when in reality the carpool lane and its attendant smoothing reduced both measures. The effect is so significant, in fact, that even a severely underused carpool lane can in some instances increase a freeway bottleneck’s total discharge flow. This happens for the site we analyzed when carpool demand is as low as 1200 vph. It follows that strategies designed to induce smoothing by other means also hold promise for managing congestion, both for freeways that have carpool lanes and those that do not. Possible strategies of this kind are discussed.

This paper shows how idealized models can be used to obtain cost-effective, implementable solutions to large and complex logistics problems. It advocates the use of fine tuning software to translate the guidelines produced by idealized models into specific feasible solutions. The “traveling salesman” (TSP) and “vehicle routing” (VRP) problems were used to test the approach. For sufficiently large problems the proposed procedure leads to solutions that improve on those produced by either idealized models or numerical methods alone. Simulated annealing (SA) was chosen for fine tuning. This optimization procedure is ideally suited for this purpose because of its general applicability, and as the research demonstrates, a prototype software package can be quickly produced. The experiments also revealed that the TSP and VRP tour lengths predicted by the idealized models are close (surprisingly so in some cases) to those of actual tours.

Typical cargo ships spend 60% of their time in port, costing their owners about $1000 per hour. In this paper, we attack such costs with a method to speed loading and unloading. We model the need for container handling as generic “work,” which cranes can do at a constant rate. Each hold of each ship has a given amount of this work and cranes can interrupt their work on individual holds without any loss of efficiency. In the parlance of scheduling theory, this constitutes an “open shop” with parallel, identical machines, where jobs consist of independent, single-stage, preemptable tasks. Practical problems often involve only a few ships but many holds; the complication of preemptable tasks makes them very complex. The paper presents a branch and bound method which, for this model, minimizes delay costs (weighted tardiness). As part of the method, we extend previous solutions to the feasibility problem of preemptive machine scheduling (to cases where multiple machines can work simultaneously on a single task). Computational results and extensions to more complicated problems are offered. Certain concepts developed here may also be applicable to other problems, both in scheduling and elsewhere. In particular, they may lead to optimal solutions of problems for which feasibility determination methods already exist.

A field experiment in Yokohama (Japan) reveals that a macroscopic fundamental diagram (MFD) linking space-mean flow, density and speed exists on a large urban area. The experiment used a combination of fixed detectors and floating vehicle probes as sensors. It was observed that when the somewhat chaotic scatter-plots of speed vs. density from individual fixed detectors were aggregated the scatter nearly disappeared and points grouped neatly along a smoothly declining curve. This evidence suggests, but does not prove, that an MFD exists for the complete network because the fixed detectors only measure conditions in their proximity, which may not represent the whole network. Therefore, the analysis was enriched with data from GPS-equipped taxis, which covered the entire network. The new data were filtered to ensure that only full-taxi trips (i.e., representative of automobile trips) were retained in the sample. The space-mean speeds and densities at different times-of-day were then estimated for the whole study area using relevant parts of the detector and taxi data sets. These estimates were still found to lie close to a smoothly declining curve with deviations smaller than those of individual links – and entirely explained by experimental error. The analysis also revealed a fixed relation between the space-mean flows on the whole network, which are easy to estimate given the existence of an MFD, and the trip completion rates, which dynamically measure accessibility. 2008 Elsevier Ltd. All rights reserved.

Recent empirical observations at freeway merge bottlenecks have revealed (i) a drop in the bottleneck discharge rate when queues form upstream, (ii) an increase in lane-changing maneuvers simultaneous with this “capacity drop”, and (iii) a reversal of the drop when the ramp is metered.

In this paper, the authors report on research that shows that high occupancy vehicle (HOV) lanes do not reduce the capacity of general purpose (GP) lanes. Empirical evidence, complemented with simulations, enable the authors to describe how to estimate total bottneleck capacity and how deploy HOV lanes without hindering vehicle flow. The authors also offer a dynamic strategy that increases a bottleneck's total discharge rate.

This paper proposes an algorithm that automatically translates the "continuum approximation" (CA) recipes for location problems into discrete designs. It is applied to terminal systems but can also be used for other logistics problems. The study also systematically compares the logistics costs predicted by the CA approach with the actual costs for discrete designs obtained with the automated procedure. Results show that the algorithm systematically finds a practical set of discrete terminal locations with a cost very close to that predicted. The paper also gives conditions under which the CA cost formulae are a tight lower bound for the exact minimal costs.

This paper presents a numerical method to model kinematic wave (KW) traffic streams containing slow vehicles. The slow vehicles are modeled discretely as moving boundaries that can affect the traffic stream. The proposed scheme converges in flows, densities and speeds without oscillations, and therefore can be readily used in situations where one wishes to model the effect of the traffic stream on the bottlenecks too. The approach is more accurate than Godunov's method in situations where the latter can be applied.

This chapter develops approximate formulae for the operating costs of flex-time (flexible commitment) and discrete-time (rigid commitment) policies, and shows how to choose policies that minimize cost.

Chapter 4 showed how to test algorithms for stability in the small and presented examples of stable and unstable (linear) algorithms. The chapter also discussed the monotonicity and reliability of linear order-based algorithms. However, it did not examine in detail the general (non-linear) case. To be useful, general policies should avoid negative orders, be reliable in the sense of (1.5), be strongly stable, and stay close to dynamic target inventory levels while tracking the customer demand. Designing useful policies is more an art than a science. In the next few sections we present the simplest policy we have been able to envision with all these properties.

This chapter examines how gain and the anticipation level of commitment-based policies affect the stability and monotonicity of homogeneous supply chains; i.e., chains where suppliers use the same policy: F j ≡ F,H j ≡ H. Stability and monotonicity are desirable properties, but separate issues. Instability can lead to the bullwhip effect, and lack of monotonicity to order cancellations. Therefore, they are studied separately. Section 4.1 defines the two forms of stability considered in these notes, “stability in the small” and “stability in the large”, and their connection with the bullwhip effect. Sec. 4.2 develops a stability test, which is illustrated with several examples in Sec. 4.3. A monotonicity test for order-based policies is then presented in Sec. 4.4. Together, Sections 4.1-4 show that historical policies (without commitments) and positive gains are problematic, both, from the standpoint of stability and monotonicity. Since as a rule, suppliers prefer policies with positive gain, this explains the prevalence of the bullwhip effect. The last section of the chapter (Sec. 4.5) extends the results to queuing systems.

This paper studies the possible integration of long-haul operations by transportation mode and service level (defined by guaranteed delivery time) for package delivery carriers. Specifically, we consider the allocation of deferred items to excess capacity on alternative modes in ways that allow all transportation modes to be utilized better. Model formulation and solution techniques are discussed. The solution techniques presented produce solutions for large-scale problem instances with up to 141 consolidation terminals and 17 breakbulk terminals. Allowing deferred items to travel by air reduces long-haul transportation costs. These savings increase with the amount of excess air capacity.

The paper examines the effects of slow moving obstructions on a traffic stream. The main determinants of these effects identified are: the maximum rate at which a queue held back by the moving bottleneck discharges; and the density of the queue for a given discharge rate. All moving bottleneck theories are described, and the experimental basis for the new theory is presented. A case study of a steadily moving bottleneck on Freeway I-880 in Oakland, California, identified and characterized from loop detector data, including the behavior of the traffic stream around it, is presented. Also described are two batteries of floating vehicle experiments involving a slow test vehicle that revealed a relationship between maximum passing rate and bottleneck speed for one lane obstructions in two- and three-lane highways. A possible extension of the theory is detailed.

This paper examines the stability of decentralized, multistage supply chains under arbitrary demand conditions. It looks for intrinsic properties of the inventory replenishment policies that hold for all customer demand processes and for policies with desirable properties. It is found that the overall conditions experienced by suppliers several stages removed from the final customer, e.g., the variances of the orders they receive and the inventories they keep, depend on the policy much more than on the demand process. A policy-specific but demand-independent upper bound for the order variance amplification factor of any decentralized policy is shown to exist, and its formula is presented. The bound is always tight for the suppliers at the end of a long chain so that a policy exhibits the “bullwhip effect” if and only if its bound is greater than 1. A simple necessary condition for bullwhip avoidance is also identified in terms of a policy's “gain.” Gain is the marginal change in average inventory induced by a policy when there is a small but sustained change in the demand rate. It is shown that all policies with positive gain produce the bullwhip effect if they do not use future order commitments. Because manufacturers can reduce costs by operating with positive gain, this explains the prevalence of the bullwhip effect. A family of commitment-based policies that can dynamically maintain any desired inventory level for any demand rate (e.g., achieve positive gain) without the bullwhip effect is also presented. The family includes just-in-time strategies as a special case. Simulation results are used as an illustration.

This paper examines the behavior of multi-lane freeway traffic past on-ramps, building on the continuum model of part I and focusing on the onset of congestion. The main complication is that rabbits (fast vehicles) entering from an on-ramp usually stay on the shoulder lane(s) of the freeway for some distance before merging into the fast lane(s). An idealization is proposed, where this distance is taken to be the same for all vehicles. As a result, the system behaves as if there was a fixed buffer zone downstream of the on-ramp where entering rabbits cannot change lanes. The model of part I is extended to capture the peculiarities of traffic within such a buffer zone, including its two end-points: the “entrance” and the “merge”. The onset of congestion is described by means of waves. The paper shows that this highly idealized model (and its more realistic cousins) explains qualitatively all the puzzling facts discussed in part I without introducing obviously unreasonable phenomena. A typical sequence of events during the onset of congestion is predicted to be as follows: (i) increased on-ramp flows and the ensuing merging maneuvers into the median (passing) lane generate a (fast-moving) queue at the merge that grows on the median lane(s) of the buffer; (ii) when the speed in this queue drops below the level on the shoulder lanes, a 1-pipe queue forms at the merge, which then grows upstream across all lanes; (iii) if the front of this queue moves slowly forward, as per the model of part I, then the lane-flows at the merge would be at “capacity” from then on (with roughly the same speed across all lanes) but downstream of the front there would be a “discharge state” with less total flow . Therefore, an observer downstream of the merge would see this discharge state before the capacity state, and would record a drop in flow followed by a recovery. If the front of the queue would move slowly backward, then the sequence of events following (ii) is somewhat different.

Of all the chapters in this monograph, this is perhaps the one which is least related to the existing literature. Sections 6.2, 6.4.2 and 6.5.1 — considering respectively distribution with 0, 1, and 2 transshipments — are based on Daganzo (1987c). The results in this reference, however, are not presented literally; a more refined routing scheme, developed in the chapter, is used here. The discussion on detailed asymmetric strategies for distribution with only one terminal, at the end of Sec. 6.3.2, is based on Blumenfeld et.at. (1985a) and Hall (1987).

As we do in this chapter, Blumenfeld et al. (1987) describe the advantages of simple models; the opinions expressed in this reference are based on a case study where succinct models based on data summaries proved very effective; the reference is easy to read. Newell (1973) argues that a family of related transportation and location problems can be solved approximately with an approach that ignores “details”; this paper was the “seed” for the continuum approximation method to be presented in Chapter 3.

This document presents some recent results and ideas from the University of California (Berkeley) traffic operations group, and at the same time discusses the role of traffic flow modeling in traffic management and control. It stresses the steps that can be taken to reduce congestion and improve traffic efficiency, and how traffic models and theories fit within this picture.

This paper addresses some issues that arise in the planning and design of logistics systems when the environment in which they are to be operated cannot be modeled accurately with certainty. The paper describes the analytical difficulties introduced by explicitly considering uncertainty, and suggests possible modeling steps that may result in more efficient, uncertainty-friendly plans.

Newell (1971) shows how to find an optimal sequence of headways for a transportation route serving a changing demand over time with a continuum approximation method that avoids “details.” This problem is mathematically analogous to the problems with time dependent demand addressed in this chapter, which are traditionally solved with dynamic programming. Section 3.3, is based on this reference. Daganzo (1987) shows that a continuous approximation of a function and its variables can be more accurate than the exact, detailed and discontinuous world representation they replace. This result is discussed in Section 3.2.

Time-dependent shortest path problems arise in a variety of applications; e.g., dynamic traffic assignment (DTA), network control, automobile driver guidance, ship routing and airplane dispatching. In the majority of cases one seeks the cheapest (least generalized cost) or quickest (least time) route between an origin and a destination for a given time of departure. This is the “forward†shortest path problem. In some applications, however, e.g., when dispatching airplanes from airports and in DTA versions of the “morning commute problem†, one seeks the cheapest or quickest routes for a given arrival time. This is the “backward†shortest path problem. It is shown that an algorithm that solves the forward quickest path problem on a network with first-in-first-out (FIFO) links also solves the backward quickest path problem on the same network. More generally, any algorithm that solves forward (or backward) problems of a particular type is shown also to solve backward (forward) problems of a conjugate type.