Conical Volume-Delay Functions

Heinz Spiess

EMME/2 Support Center
Haldenstrasse 16, CH-2558 Aegerten, Switzerland


October 1989
(Appendices 1 and 2 added August 1997)

This paper (without the appendices) also appeared in
Transportation Science, Vol 24., No. 2, 1990.

Abstract:

The widely used BPR volume-delay functions have some inherent drawbacks. A set of conditions is developed which a ``well behaved'' volume delay function should satisfy. This leads to the definition of a new class of functions named conical volume-delay functions , due to their geometrical interpretation as hyperbolic conical sections. It is shown that these functions satisfy all conditions set forth and, thus, constitute a viable alternative to the BPR type functions.

A PDF version of this document is also available.


Contents


Introduction

In most traffic assignment methods, the effect of road capacity on travel times is specified by means of volume-delay functions t(v) which used to express the travel time (or cost) on a road link as a function of the traffic volume v. Usually these functions are expressed as the product of the free flow time multiplied by a normalized congestion function f(x)

equation266

where the argument of the delay function is the v/c ratio, c being a measure of the capacity of the road.

Many different types of volume-delay functions have been proposed and used in practice in the past (for a review article see Branston [1]). By far the most widely used volume delay functions are the BPR functions (Bureau of Public Roads [2]), which are defined as

equation268

With higher values of tex2html_wrap_inline498 , the onset of congestion effects becomes more and more sudden. This can be seen in Figures 1, a and b, which show the BPR type congestion function

equation270

for exponents tex2html_wrap_inline498 =2, 4, 6, 8, 10 and 12. This range of alpha values is also indicative of the wide range that is used in practice, but note that the values of tex2html_wrap_inline498 are usually not restricted to integers.

The simplicity of these BPR functions is certainly one reason for their wide spread use. It is also very convenient that for any value tex2html_wrap_inline498 we have tex2html_wrap_inline506 , i.e. when traffic volume equals the capacity, the speed is always half the free flow speed.

fig 1a

fig 1b
Fig. 1. BPR functions for (A) small and (B) large v/c ratios

Unfortunately, these BPR functions also have some inherent drawbacks, especially when used with high values of tex2html_wrap_inline498 :

a)
While for any realistic set of travel volumes, we can assume that tex2html_wrap_inline510 (or at least not much larger than 1) this is usually not the case during the first few iterations of an equilibrium assignment. Values of v/c may well reach values of 3, 5 or even more. To illustrate this, the link time of a link with tex2html_wrap_inline514 and a v/c ratio of 3 is increased by a factor of tex2html_wrap_inline518 , which means that every minute free flow time becomes roughly one year of congested time! These aberrations slow down convergence by giving undue weight to overloaded links with high tex2html_wrap_inline498 -values and can also cause numerical problems, such as overflow conditions and loss of precision.
b)
For links that are used far under their capacity, the BPR functions, especially when high values of alpha are used, yield always free flow times independent of actual traffic volume. To illustrate this, consider again a link with tex2html_wrap_inline514 and a capacity of 1000. Whether the volume is 0 or 300, the volume delay function yields exactly the same numeric value (assuming single precision calculation). Therefore, the equilibrium model will locally degenerate to a all-or-nothing assignment, where the slightest change (or error) in free flow time may result in a complete shift of volume from one path to another path. Also, the solution is no longer guaranteed to be unique on the level of link flows, since the volume-delay functions are no strictly increasing functions of the volume any more.
c)
Even though the formula of the BPR function is very simple, its evaluation requires the computation of two transcendental functions, i.e. a logarithm and an exponential function to implement the power tex2html_wrap_inline524 , which require a fair amount of computing resources.


Requirements for a Well Behaved Congestion Function

Are there other types of congestion functions that are not (or are less) subject to the drawbacks of the BPR functions? If yes, how would such a ``designer'' volume-delay function look like? Let us first set forth some conditions these functions need to satisfy:

  1. f(x) is strictly increasing. Necessary condition for the assignment to converge to a unique solution.
  2. f(0) = 1 and f(1) = 2. These conditions ensure compatibility with the well known BPR type functions. The capacity is thus still defined as the volume at which congested speed is half the free flow speed.
  3. f'(x) exists and is strictly increasing. This ensures convexity of the congestion function - not a necessary, but a most desirable property.
  4. tex2html_wrap_inline534 . tex2html_wrap_inline498 is, similar to the exponent in BPR functions, the parameter that defines how sudden the congestion effects change when the capacity is reached.
  5. tex2html_wrap_inline538 , where M is a positive constant. The steepness of the congestion curve is limited. This in turn limits also the values of the volume delay function not to get too high when considering v / c ratios higher than 1, avoiding the problems mentioned in a) above.
  6. f'(0) > 0. This condition guarantees uniqueness of the link volumes. It also renders the assignment stable regarding small coding errors in travel time and distributes volumes on competing uncongested paths proportional to their capacity.
  7. The evaluation of f(x) should not take more computing time than the evaluations of the corresponding BPR functions take.

Conditions 1 to 4 hold, of course, for the BPR function and are stated to ensure compatibility with them. Conditions 5, 6 and 7 are imposed in order to overcome the BPR functions' drawbacks a), b) and c) mentioned above.

At least one class of congestion functions exists indeed, as we will show in the remaining part of this note.


Conical Congestion Functions

Consider an obtuse three-dimensional cone intersected with the two-dimensional X-Y plane. Figure 2 shows the projection of the cone, as well as one possible resulting hyperbolic section. These hyperbolic cone sections have all the desired properties and constitute the base for the conical congestion functions, as we shall name them.

The name ``hyperbolic congestion functions'' would also be appealing, but it has been used in the past for functions of the form tex2html_wrap_inline548 , see Branston [1]. Furthermore, this name could lead to confusion with the transcendental hyperbolic functions sinh and cosh.

fig 2 Fig. 2. Hyperbolic conical sections.

Since the mathematical derivation is quite simple but lengthy and only involves basic geometry and elementary algebra, we shall simply state the resulting function and show that it indeed satisfies the conditions 1 to 7 set forth above.

Let the class of conical congestion functions be defined as

equation276

where tex2html_wrap_inline550 is given as

equation279

and tex2html_wrap_inline498 is any number larger than 1.

In order to prove that the desired properties hold for tex2html_wrap_inline554 , we need to evaluate the the first derivative of tex2html_wrap_inline554 , which is

equation283

Let us now show, point by point, that the properties 1 to 7 indeed hold for tex2html_wrap_inline554 :

  1. By rewriting tex2html_wrap_inline560 we obtain

    equation290

    Using Pythagoras' theorem, it is easy to see that the second term is strictly contained between -1 and 1. Thus tex2html_wrap_inline562 and it follows that tex2html_wrap_inline564 is strictly increasing.

  2. For the function value at x=0 we obtain tex2html_wrap_inline568 . Using (5), it follows that

    equation298

    which, once substituted under the square root, shows that indeed we have tex2html_wrap_inline570 .

  3. The existence of tex2html_wrap_inline572 has already been shown when proving 1). To show that tex2html_wrap_inline572 is a strictly increasing function, it suffices to show that the second derivative of tex2html_wrap_inline564 is strictly positive. The details of this proof are left as an exercise for the interested reader.
  4. From (7), it follows immediately that tex2html_wrap_inline578 .
  5. Using the same reasoning as used to prove 1), we show that tex2html_wrap_inline580 . This means that for large v/c ratios, the congestion behaves as a quasi-linear function, with a gradient that approaches but never exceeds twice the gradient at capacity.
  6. Again using (6) and (8), we obtain tex2html_wrap_inline584 which can be developed using (4) to obtain

    equation312

  7. As for the computation time, we note that the evaluation of tex2html_wrap_inline564 needs: 2 multiplications, 1 square root and 4 additions. This compares very favorably with the 2 transcendentals, 1 multiplication and 1 addition needed to compute the BPR type function. Note that for a given value of tex2html_wrap_inline498 , the values of tex2html_wrap_inline550 and tex2html_wrap_inline592 are constants that can be evaluated once ahead of time.

Figure 3, a and b, show the functions tex2html_wrap_inline564 for values of tex2html_wrap_inline498 =2, 4, 6, 8, 10 and 12. Note the quasi-linear behavior for x > 1 when comparing Figure 3b to the BPR functions in Figure 1b. The non-zero gradient of the functions at x=0 can be seen clearly.

fig 3a

fig 3b Fig. 3. Conical functions for (A) small and (B) large v/c ratios

We implemented both the BPR and the conical volume-delay function using a little program written in C, in order to compare execution times. The program was compiled and run on the three major families of micro-computers. The results in Table I show that the conical functions can be evaluated more efficiently than the BPR functions, in spite of the apparently more complex formula.

TABLE I: Computational Efficiency
Computer installationExecution time (msec)
CPU / FPUSpeedCompiler tex2html_wrap_inline602 tex2html_wrap_inline564
NSC 32016/3208110MhzBSD 4.21.22.98
Intel 80286/8028710MhzMS 5.0.65.37
Motorola 68020/6888117MhzSVS.13.09

While, to our best knowledge, the class of conical congestion functions proposed here constitutes a new approach, it is interesting to note that a very similar functional form was proposed in an unpublished report prepared in the context of a transportation study for the City of Winnipeg (Traffic Research Corporation [5], Florian and Nguyen [3]). The functions used in that study can also be interpreted as conical sections, but they use more parameters and do not, in general, satisfy the conditions we set forth in the preceding section. For Branston [1] , it was ``doubtful whether these functional form could be of more general user'' and in his article he proceeded to show that these should be approximated by BPR-type functions -- a questionable ``progress'' in the light of our findings.

In a recent transportation study for the City of Basel, Switzerland, the proposed conical volume-delay functions have been used successfully in practice. A dramatic improvement in the convergence of the equilibrium assignment was observed when switching from the previously used BPR functions to the corresponding conical functions, with no practically significant changes in the resulting network flows. This study was carried out using the EMME/2 transportation planning software (Spiess [4]).


Conclusions

In trying to overcome the known disadvantages of the BPR functions, we have developed a new class of volume-delay functions, the conical functions. The interpretation of the parameters used to characterize the specific congestion behavior of a road link, i.e. capacity c and steepness tex2html_wrap_inline498 , is the same for both BPR and conical function, which makes the transition to conical functions particularly simple. Since the difference between a BPR function and a conical function with the same parameter tex2html_wrap_inline498 is very small within the feasible domain, i.e. v/c <1, the BPR parameters can be transferred directly in most cases.

Further research would be needed to develop statistical methods for directly estimating the parameters of the conical functions, using observed speeds and volumes.


References

1
Branston D. (1976). Link Capacity Functions: A Review. Trans. Res. 10, 223-236.

2
Bureau of Public Roads (1964). Traffic Assignment Manual. U.S. Dept. of Commerce, Urban Planning Division, Washington D.C.

3
Florian M. and Nguyen S. (1976). An Application and Validation of Equilibrium Trip Assignment Methods. Trans. Sci. 10, 374-390.

4
Spiess H. (1984). Contributions à la théorie et aux outils de planification de réseaux de transport urbain. Ph.D. thesis, Département d'informatique et de recherche opérationnelle, Centre de recherche sur les transports, Université de Montréal, Publication 382.

5
Traffic Research Corporation (1966). Winnipeg Area Transportation Study. Report prepared for the Streets and Transit Division of the Metropolitan Corporation of Greater Winnipeg (unpublished).


This paper (without the following appendices) also appeared in Transportation Science, Vol 24., No. 2, 1990.


Appendix 1: Marginal Cost Functions

(Added August 1997)

When performing system optimum assignments according to Wardrop's first principle, it is necessary to compute the corresponding marginal cost functions. For a given volume-delay function t(v) the corresponding marginal cost function is defined as

displaymath616

The marginal cost includes on top of the cost perceived by the traveler himself t(v) also the increase in cost t'(v) his traveling causes to for all other v travelers on the same link.

For the BPR function

equation322

the marginal cost is simply

equation324

For the conical function

  equation326

the marginal cost can be computed using the first derivate

equation335

as

equation345

After some rearrangements, the above functions can be simplified to

  equation363

The conical volume-delay functions used in practice include sometimes shifts along the volume axis (e.g. to represent a fixed precharged volume) and also along the time axes (e.g. to use saturated vs free flow time ratios other than 2). These variations are represented by the more general formulation

  equation378

In the above formula tex2html_wrap_inline624 represents a arbitrary shift along the time axis, which for standard conical functions corresponds to tex2html_wrap_inline626 . The coefficient s, which is 1 for standard conical functions, can be reduced to tex2html_wrap_inline630 , if a part of the link capacity is taken up by a fixed precharge volume tex2html_wrap_inline632 that is not included in the objective function of the system optimum assignment.

In this more general case, the marginal cost functions can be written as

  equation387


Appendix 2: Efficient Coding of Conical Functions in EMME/2

(Added August 1997)

As conical volume-delay functions are often used with the EMME/2 transportation planning software (Spiess [4]), it might be useful to show how such functions can be efficiently implemented as EMME/2 function expressions making use, in particular, of the intrinsic functions put() and get() to optimize the evaluation of repeated subexpressions.

The standard formulation (12) for the conical volume-delay function can be implemented in a very general way with the following EMME/2 function definition

fdn= tex2html_wrap_inline634 *(2-put((put( tex2html_wrap_inline498 )-0.5)/(get(1)-1))-put(get(1)*(1-volau/c))
+sqrt(get(3)*get(3)+get(2)*get(2)))

where the function number n, the free flow time tex2html_wrap_inline634 and the function parameter tex2html_wrap_inline498 have to be replaced by the corresponding sub-expressions.

If, as is most often the case, tex2html_wrap_inline498 is defined as a constant value, there is no need to compute the values derived from tex2html_wrap_inline498 (such as tex2html_wrap_inline648 , tex2html_wrap_inline592 and tex2html_wrap_inline652 ) each time the function is evaluated. Rather, these values can be computed once ahead of time, so that the corresponding values are inserted directly as constants into the function definition. This allows the following, much more efficient function implementation:

fdn= tex2html_wrap_inline634 *( tex2html_wrap_inline624 -put( tex2html_wrap_inline498 *(1-volau/c))+sqrt(get(1)*get(1)+ tex2html_wrap_inline592 ))

If the volume-delay function is to take into account a given fixed precharged volume (e.g. to represent transit vehicles running on the same link), the term volau in the above formulae must simply be replaced by the sum of the auto volumes and the precharged volumes, e.g. assuming that the precharged fixed volumes are stored in the attribute ul1, then volau would have to be replaced by (volau+ul1).

For performing a system optimum assignment with EMME/2, the standard volume-delay functions tex2html_wrap_inline664 must be replaced by the corresponding marginal cost functions tex2html_wrap_inline666 . The following function definition corresponds to formula (15) for the marginal cost function tex2html_wrap_inline666 :

fdn= tex2html_wrap_inline634 *(2-put(put( tex2html_wrap_inline498 )*(1-2*put(volau/c)))
-put((get(1)-0.5)/(get(1)-1))
+(get(3)*put(get(1)*(1-get(2)))+put(get(4)*get(4)))
/sqrt(get(5)*get(5)+get(6)))

Again, if the function parameter tex2html_wrap_inline498 is a constant, the function expression can be substantially simplified by computing tex2html_wrap_inline550 , tex2html_wrap_inline592 and tex2html_wrap_inline624 once ahead of time and then inserting the resulting constants directly into the expression. This lead to the following more efficient implementation for the marginal cost function tex2html_wrap_inline666 :

fdn= tex2html_wrap_inline634 *( tex2html_wrap_inline624 -put( tex2html_wrap_inline498 *(1-2*put(volau/c)))
+(get(2)*put( tex2html_wrap_inline498 *(1-get(1)))+ tex2html_wrap_inline592 )/sqrt(get(3)*get(3)+ tex2html_wrap_inline592 ))

If the volume-delay function is specified with precharged volumes tex2html_wrap_inline632 , the formulation of the marginal cost function depend on whether the total travel cost of the precharged vehicles is considered a part of the system optimum objective function or not.

In the first case, the marginal cost also includes the increase in travel cost for the precharged vehicles. i.e. we have

displaymath702

As this case corresponds to a simple shift along the volume axis, the above formulae remain still valid, one has simply to replace volau by (volau+ul1) (assuming again the precharged volumes tex2html_wrap_inline632 are stored in ul1).

However, if the increase in travel costs for the precharged vehicles is not to be considered in the marginal cost function, i.e.

displaymath706

then we must use tex2html_wrap_inline630 in the general formulation (17). This leads to the following EMME/2 implementation of the marginal costs tex2html_wrap_inline666 for general values of tex2html_wrap_inline498 :

fdn= tex2html_wrap_inline634 *(2-put(put( tex2html_wrap_inline498 )*(put(1-(volau+ul1)/c)-volau/c))
-put((get(1)-0.5)/(get(1)-1))
+(get(3)*put(get(1)*get(2))+put(get(4)*get(4)))
/sqrt(get(5)*get(5)+get(6)))

Finally, for constant values of tex2html_wrap_inline498 , the following implementation is more efficient, since it avoids the evaluation of constant sub-expressions for tex2html_wrap_inline550 , tex2html_wrap_inline592 and tex2html_wrap_inline624 :

fdn= tex2html_wrap_inline634 *( tex2html_wrap_inline624 -put( tex2html_wrap_inline498 *(put(1-(volau+ul1)/c)-volau/c))
+(get(2)*put( tex2html_wrap_inline498 *get(1))+ tex2html_wrap_inline592 )/sqrt(get(3)*get(3)+ tex2html_wrap_inline592 ))



Heinz Spiess, EMME/2 Support Center, Tue Aug 5 11:59:19 MET DST 1997