55 Luce Accuracy (sidt2009)

SIDT 2009 International Conference

1

On the accurate convergence of deterministic assignment when comparing scenarios for large networks: investigating the LUCE algorithm Guido Gentile 1 1

1.

Dipartimento di Idraulica Trasporti e Strade, Sapienza Università di Roma [email protected]

Introduction

In this paper we investigate a new algorithm (Gentile, 2009) to solve the static assignment problem to multimodal transport networks with deterministic route choice, called Linear User Cost Equilibrium (LUCE), that has been recently adopted in the software VISUM. To find a descent direction, local shifts of flows that satisfy the total cost lowering rule are determined exploiting the inexpensive information provided by the derivatives of the link costs with respect to link flows. LUCE achieves a very high convergence speed that compares favourably to the other methods, while it assigns the demand flow of each o-d couple on several paths at once. This algorithm is therefore particularly suitable when the aim is to simulate the effects of supply or demand changes on large networks, since in this case a relatively small inaccuracy of the solution and a poor set of loaded paths can lead to relevant design mistakes; indeed, very often in practice the stop criterion is based on a run-time budget instead that on predefined convergence goals. Although traffic assignment is a rather mature issue in transport modelling, to find an accurate equilibrium on real networks is still a difficult problem to be solved. In practice, the algorithms currently available are not truly satisfactory for many applications: they simply don’t converge in reasonable time fine enough to allow consistent comparisons between design scenarios. Indeed, apparently small errors in the iterative procedure do not allow to appreciate the real differences among

Guido Gentile

2

Milan 29-30 June 2009

equilibria and may lead to false conclusions in relevant projects, thus vanishing any modelling effort. This is a well recognized problem by the recent literature (see, for example, Boyce et al., 2004), but is not really acceptable by practitioners, who are asking researchers and developers to enhance the algorithm convergence. To satisfy this necessity and overcome such a drawback, the main software producers in the world are in these days changing their traffic assignment procedures (e.g. VISUM, TRANSCAD, EMME), thus animating the international debate and the competition on this topic. In this context, LUCE gives a noticeable contribution: it converges between 10 and 100 times faster than other recent algorithms and allows on large networks to reach in few minutes and iterations the relative gap of 10E-8, that is considered enough for any application. This result conveys a considerable advance in modelling practice, more than in algorithm theory. The LUCE algorithm is here applied to several networks (elementary, toy and real) with different levels of congestion, to show the importance of an accurate convergence when comparing different simulated scenarios.

2.

Main aspects of the algorithm

Specularly to Origin-Based methods, the assignment problem is partitioned by destinations. The main idea is to seek at every node a deterministic equilibrium (Wardrop, 1952) for the local route choice of users directed toward a same destination among the links of its forward star that belong to the current bush – a bush is an acyclic sub-graph that connects each origin to the destination at hand. The cost function associated to each one of these travel alternatives expresses the average impedance to reach the destination by continuing the trip with that link, linearized at the current flow pattern. It can be proved that the solution to such linear program in terms of destination flows, recursively applied for each node of the bush in topological order, provides a descent direction with respect to the classical sum-integral objective function (Beckmann et. al., 1956). The network loading is then performed through the corresponding splitting rates, thus avoiding explicit path enumeration. To grasp immediately the concept underlying LUCE, we can refer to the simplest Guido Gentile

SIDT 2009 International Conference

3

network where one o-d pair with demand D is connected by two links with cost function c1( f1) and c2( f2), respectively. At the current flow pattern f ′ = (D/2, D/2), it is c1′ < c2′ (see Figure 1, below), so that an all or nothing approach would lead to a descent direction (D, 0), which is far away from the equilibrium f* (black circle in the Figure). Our approach, instead, is to consider the first order approximations of the cost functions at the current flow pattern, i.e. ca′ + ∂ca( fa)/∂fa ⋅ ( fa - fa′), and determine a user equilibrium e among these lines (white circle in the Figure): this descent direction efficiently approaches the equilibrium f*, and in most cases can be taken as the new iterate with a step one. f′

e f* c2 c2′

c1′

c2( f2) c1( f1)

f1

D/2

f2

D Figure 1. Linear Cost User Equilibrium between two paths.

Contrary to the classical All Or Nothing assignment to shortest paths, the network loading map resulting from the application of the LUCE algorithm a) assigns (implicitly) the demand flow of each o-d couple on several paths at once and b) is a one-to-one function that combined with the link cost function yields a well-defined fixed point operator, thus offering both computational and theoretical advantages. For each iteration, the proposed algorithm requires no shortest path calculations and two visits of the bush links for each destination, that is equal to the complexity of the STOCH single pass procedure (Dial, 1971) for the Logit network loading. Guido Gentile

4

Milan 29-30 June 2009

3.

Comparison with other algorithms

LUCE presents a higher convergence speed, both in terms of computing time and iterations, than the most advanced Origin-Based methods recently proposed. In the following Figure 2 we compare the convergence performances of five different algorithms on the Chicago network, which is one of the best known benchmark with 1768 zones and 39018 links. Convergence of different algorithms for Chicago 1.E-03 LUCE FW

relative gap

1.E-04

OBA B

1.E-05

PG 1.E-06 1.E-07 0

50

100

150 200 250 300 350 run time on a 2.0GHz CPU [min]

400

450

500

Figure 2 – Performance comparison of LUCE to other four assignment algorithms on the Chicago network, whose convergence patterns are retrieved from papers and presentations.

Frank Wolfe by LeBlanc (1973) and Nguyen (1973) is here reported just to recall that an accurate solution of the assignment problem requires in practice more specialized procedures. Bar-Gera’s OBA (2002) takes into account link and node cost derivates with the aim of calculating Newton-type flow shifts among the paths of the bush, thus obtaining a descent direction in the space of link flows. LUCE exploits the same information, but instead of seeking some parallelism to non-linear optimization techniques like the OBA, it adopts an ad-hoc approach founded on the intuitive ideas of local equilibrium and first-order approximation.

Guido Gentile

SIDT 2009 International Conference

5

Algorithm B proposed by Dial (2006) is a link based procedure that shifts trips from max- to min-paths to make their cost difference minima. The Projected Gradient algorithm, recently revised by Florian (2009), is a path based method that regards their costs as the gradient of the sum integral objective function.

4.

Conclusions

We summarize below the main properties of the proposed algorithm to solve the classical equilibrium problem with fixed demand, deterministic route choice and separable arc cost functions. LUCE is formally proved to converge at equilibrium. We tested that it is actually capable of solving numerically the traffic assignment problem with any wanted accuracy, under the condition that the computer arithmetic precision is twice as much the aimed relative gap. The convergence shows to be linear, but its rate decreases with the level of congestion and with the sharpness of cost functions. To alleviate this problem, that affects any algorithm, a hyperbolic shape and a piecewise linear shape of the arc cost function can replace the power based BPR. LUCE appears to be at least 10 times faster than the most advanced methods recently proposed in the literature. Few iterations, say 20, are usually enough to reach a convergence suitable for most applications. LUCE has a linear complexity in terms of links and zones, unlike many other methods that are path based or require shortest path searches on cyclic graphs. In particular, the runtime is not sensitive to the number of o-d couples but only to the number of destinations, given the implicit path enumeration. LUCE does not need to store in memory single o-d paths but only destination bushes, that however offer a much richer finite set of used alternatives, whose probabilities can be easily obtained ex-post. LUCE allows for a fixed point formulation of the equilibrium problem also in the deterministic case without introducing one to many maps. LUCE is based on a simple idea that can be understood with a single chart and exploits the concept of derivatives that is familiar to any engineer. LUCE is implemented in VISUM, one of the most widespread software for transport planning. Guido Gentile

6

Milan 29-30 June 2009

References Beckmann M., McGuire C., Winston C. (1956) Studies in the economics of transportation. Yale University Press, New Haven, CT. Bar-Gera H. (2002) Origin-based algorithm for the transportation assignment problem. Transportation Science 36, 398-417. Boyce D., Ralevic-Dekic B., Bar-Gera H. (2004) Convergence of traffic assignments: how much is enough? ASCE Journal of Transportation Engineering 130, 49-55. Dial R. (1971) A probabilistic multipath assignment model than obviates path enumeration. Transport Research 5, 83-111. Dial R. (2006) A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration. Transport Research B 40, 917-936. Florian M. (2009) New look at projected gradient method for equilibrium assignment. Transportation Research Board Annual Meeting 2009, Paper #09-0852. Gentile G. (2009) Linear User Cost Equilibrium: a new algorithm for traffic assignment, submitted to Transportation Research B. LeBlanc L. (1973) Mathematical programming algorithms for large scale network equilibrium and network design problems. Ph.D. Dissertation. Department of Industrial Engineering and Management Sciences, Northwestern University. Nguyen S. (1973) A mathematical programming approach to equilibrium methods of traffic assignment with fixed demands. Publication 138, Département d’Informatique et de Recherche Opérationnelle, Université de Montréal, Québec. Nguyen S., Pallottino S. (1988) Equilibrium traffic assignment for large scale transit networks. European Journal of Operational Research 37, 176-186. Wardrop J. (1952) Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers, Part 2, 325-378.

Guido Gentile