An heuristic algorithm for dynamic network loading

Copyright © IFAC Transponation Systems Chania, Greece, 1997 AN HEURISTIC ALGORITHM FOR DYNAMIC NETWORK LOADING E. Codina, J. Barce16 Polythecnic University of Catalonia. Spain. Dept. of Statistics and O.R . e-mail:[email protected].es Abstract : This paper describes an heuristic procedure for the problem of determining the time evolution of traffic flows and routes on a road net work with the key requirement that its computational costs must be appealing so as to include it as part of a real time Traffic Management System. Keywords: Road Traffic, Dynamic Models, Heuristics, Path Planning, Delay Estimation . 1. INTRODUCTION In the last years several research and developement programmes have included projects aiming to the developement of Traffic Management and Information Systems to help in the real time estimation and prediction of traffic conditions in road networks, to assist in real-time traffic management and to provide the basic information to be broadcasted to road users or displayed at the variable message signals. To achieve the goal of having a system with a real time response the application requires the use of proven optimization and simulation algorithms that present proper characteristics to numerically handle the traffic models fast enough. In principle the migration to a parallel computing environment has appeared as the unique practical alternative to achieve this goal and some research efforts have been done in this direction (Chabini et al. , 1992) as well as projects as part of R & D programmes such as PETRI (PETRI Project 1993, 1995) IVHS and AMTICS. A key component of a real-time Traffic Management System consists, amongst others, of a Dynamic Traffic Assignment module. 531 The Dynamic Traffic Assignment problem has been posed under deterministic and stochastic approaches and formulated in a variety of ways using continuous or discretized optimal control models and variational inequality models (Friesz et al., 1989; Merchant and Nemhauser, 1978; Bernstein and Friesz, 1993 and others) or by means of heuristic models (Janson, 1991; de Romph and Hammerslag, 1992). Also, questions related to the extension of the Wardrop principles to the dynamic case and to the concept of a dynamic equilibrium have been examined in Smith (1993) and the consistency of some models has been examined in Codina and Barcel6 (1995). Although several algorithmic proposals for the optimal control formulations have emerged (Codina and Barcel6, 1992,1995),only from the heuristic and simulation approaches (Barcel6 and Martin, 1994) computational results on full size networks have been presented up to now. This paper describes an heuristic procedure whose computational requirements rely basically on the computation of shortest paths on a transportation network and on approximately solving the simple continuum model in order to model the traffic flow dynamics. Also a remarcable aspect of the heuristic is that the evaluation of travel times relies on predictions for the traffic densities on the links of the network. 2. DESCRIPTION OF THE HEURISTIC PROCEDURE Let us denote by 9 = (N, A) a graph modeling an urban network with N the set of nodes and A the set of links. Let us denote by p~(t) the number of trips per unit of time that enter the network at node 0 E () in the set of origins, at time instant t with destination node q E D in the set of destinations D of the network. In order to describe traffic flows we shall use two magnitudes: traffic flows and traffic densities at a given link segment. We shall denote the total flow on a link by ja and the total density on a link by Xa and we shall supose that they are functions of the link position Za and the time instant t, Xa = xa(za, t), ja = ja(za, t). Also we shall decompose traffic flows and densities into flows and densities per destination: x a = Lq ED x~ , ja = Lq ED jg and that there exists a speed-flow relationship for each of the links of the network of the type speed = wa(xa). In Codina and Barcel6 (1995), it has been shown that many of the existing dynamic traffic assignment models describe the evolution of traffic flows on a multidestination network with mathematical models that approximate the following hyperbolic PDE system: aX~ + aJ~ = 0, Va E A at aZa B+l(O- , t) - B-l (Z+, t) + + eqsq(t) = pq(t) V q E D Jq(Za , t) ~ 0 ( xa(za, t) = LqED xHza, t) ) (Known initial (1) Another set of constraints, expressing a limited throughput of links like LqED J~(Za+ , t) ~ Va, and a maximum admittance for input flows like LqED JHO-, t) ~ Ua, Va E. A , could b.e added to the equations representmg the feasIble set of flows. Nonnegativity constraints on the densities xq( Za, t) ~ 0 are redundant if 532 the speed density relationships Wa ( . ) are decreasing in [0 , xal and verify wa(O) > 0 and wa(xa) = O. It can be easily shown that total flows on links obey to the classical hyperbolic PDE that describes the simple continuum model: Xt + <p(x )xz = 0 , <p(x) = d( x~(x)) . The conditions that determine a unique solution of Xt + <p( x)x z = 0 on a link are the initial density on the link at time t = to, the input flow at the beginning of the link j(O-, t) = u(t) and the exit flow at the end of the link, j(za+, t) = v(t). The approximation of the system (1) is usually full of dangers, specially in the case of nonconstant propagat ion speed Wa and , additionally, the computation of the solutions of the approximating schemes is time consuming. If the solution x*(za, t) of the previous PDE is known then it is possible to calculate timespace trajectories of total flows as solutions of ia = w(x(za, t)). In this continuum model it can be shown that a given trajectory is only influenced by previous and neighbor trajectories. However, it is known that the formulation of dynamic traffic assignemnt models is based on the knowledge of the evolution of the demands along a given time horizon. To evercome this problem the heuristic assumes that predictions on the traffic densities on the links of the network are available and they are used when traffic flows reach an intersection. Let b be a time length similar in magnitude to the shortest travel time of a link in the network (b = 10 to 30 seconds). We shall refer to b as JL-time slice. If each the O-D volumes bp~ for a given origin 0 E () is considered as a unit or "pseudo-platoon" when loaded on the set of time-dependent shortest paths rooted on 0 a packet of trajectories will be originated on the links contained in the tree . When performing this operation for each origin 0 each link will contain a set of packets of trajectories. Some of these packets will join making up a greater one and others will remain isolated. For a given origin 0 in the set of origins () of the network and packet l-th . d b;t l Tl -l l on link a, let us enote y ta,t a, a' Ta ' Ta' X~ , j! the following magnitudes: - i~, t; . The entry instant at link a E A of the first and last car of packet i . - T~. The departure time from the head of link a E A of the first car in packet i. - f~ , T~. The instants at which the head of the link a E A is reached by the first and last car of packet f-th . - x~ , j~. Density and flow at the tail of link a E A for cars in packet l-th at the time that the packet passes through link a E A. The density x~ at time t :::::: t~ is evaluated having into account predictions based on counts for similar traffic conditions and j~ is taken as ·l _ l ( l ) A d· I l hl d Ja - xa·w xa· ccor mgy, Ya ' a are ensity and flow at the head of the link. Let us also assume that for each link a E A in the network the time-space evolution of the packets of cars that entered in the network during i-th I-l-time slice coming from each origin 0 E 0 is approximately known, i. e: t~ , f~ are known for packets that originated at link a due to cars entered at time i-th. These two instants of time can be determined using a time dependent shortest path algorithm as pointed out in Kaufman and Smith (1993), as time-dependent link travel time functions can be approximated by ca(t) = la/wa(xa(t)) and let us supose that functions ca(t) verify the consistency assumption also outlined in Kaufman and Smith (1993), i.e: sup { (ca(s)- Ca (t)) -(t - s)} ~ 0 for 0 ~ s ~ t. Let us denote now by 7r~ the number of cars into one of these packets on link a E A that entered during i-th I-l-time slice to the network. We shall call to the process of determining the magnitudes depicted in figure 1 for the i + 1-th I-l-time slice for the incoming and outgoing links of a node "to solve the node ". We shall next describe an heuristic to solve a node on which no a priori precedence rules or signal timing exist and for which two flows only mix if they arrive simultaneously to the node. Let us denote by 7rf the number of cars in a packet £' of link b incoming to link a that interacts with packet 7r; . Also, it is assumed that if traffic volume 7rb is composed of volumes diverting to the allowed movements, then all cars in 7rf are delayed by the slowest turning flow. "Solving a node" . Let now be kEN and let us denote by: - [(k) , I(k) the set of emerging and incoming links from node k. - If b E I(k) , then E(b) ~ [(k) is the set of links outgoing from link b, i.e. the movement (b --+ a) is allowed. If a E [(k) then lea) ~ I(k) is the set of links incoming to link b, (i.e. the movement (b --+ a) is allowed). 533 (a) to <_ £i1!~ !e_n~t_h_ -= _Z,:> , Za t · , t , r · , Fig. 1. (a) A typical trajector y when there are no discontinuities in the total density. (b) Magnitudes used by the heuristic network loading. -If traffic volume 7rb is decomposed into its allowed movements , 7rb = LaEE(b) 7rba , then by E+(b) = { a E E(b) I 7rba > 0 } it is denoted the set of all outgoing links that will receive a nonull flow from link b and by l+(a) = {b E lea) I 7rba > O} it is denoted the set of all links that send nonull flow to link a. For links a E E(k) and b E l(k) it is reasonable to assume that t~+ 1 and T: are determined by the time instants t~, accordingly to: t~+l Max{t~/la/E n E+(b)} bEI+ (a) (2) T;+I = Max{[~tIlal E E+(b)} Also it is possible to calculate the amount of time O~+I needed by the 7r~ cars to enter the link as OHI = 7r HI /J · 1. if [HI = t l. a a a a a (j~+I = j~ ) and by O~+I = 7r~+I /}~+I if t~+I > t~ (}a being the maximum flow admitted by link a). So the last car enters the link at time t~+I = ~+I + (}~+1. An "easy to compute " approximation of the trajector y Z~+l(t) using an integration method based on the characteristics of Xt + <p(x)xz = 0 determines f~ and T~. Finally for links entering at node k: T~+l = Max{ t~+l I a E E+(b)} (3) As an evaluation of THl fHl THl l"or the b , b ' b I' incoming links at node k has been made, then "t+ 1 I ( T~+ 1 - T~+ 1 ) approximates the exit flow and it is necessary to examine if there exists spillback on link b. The Heuristic Network Loading. The algorithm followed by the heuristics is presented below. For simplicity the spillbak phenomenon on a link b incoming to a node k has been excluded. In case of spillback the tail node k' of link b must be solved again as well as the nodes in the "forward star " of k'. (i) For the i-th J.L-time slice calculate the time-dependent shortest path trees (spt 's) on the network for each 0 E O. (ii) Load the network with O-D flows b·(p~)' on the spt's calculated in 1). Determine the entry and exit times t~ , f~ for the new packets 1l"~. Determine the sets E+ (b) and 1+ (a) for incoming links b and emerging links a of each node . (iii) Determine t~, T~ for the newly generated packets. Initialize the sets A 0, N+ : AO={aEAla~ U£(n)} , nEN N+ = { n E NI I(n) ::f 0 }, (4) NO= {n E NII(n)nA°::f 0} (iv) While not (N+ = 0) -Take kENO n N+ ; - "Solve node" k having into account predictions for traffic densities x~+l , a E £(k) (Determine f~+l,T~+l, "la E £(k), Vb E T~+l E I( k) and the rest of previous magnitudes); -For a E £(k), set AO = AO u {a}; -SetN+ = N+-{k} . (v) Computation of best and worst O-D travel times (~)i, (u~)i for J.L-time slice i-th accordingly to ta, fa and ta , Ta· (vi) i ~ i + 1. GOTO step 1) 534 The outputs of the heuristic are thus refined bounds on the O-D travel times for cars entering the network and arrival times to the network nodes at each J.L-time slice. 3. REFERENCES Barcel6 J. ,R. Martin (1994a). Assesment of vehicle guidance systems and strategies by simulation. Preprints of the TRISTAN II Conference, Capri 199.4Italy. I. pp. 239-255. Bernstein D., T. L. Friesz (1993). A variational control formulation of the simultaneous route and departure-time choice equilibrium problem. In: Transportation and Traffic Theory. (C.F. Daganzo, Ed.) Elsevier Science. Chabini 1. , O. Drisi Kai"touni and M. Florian (1992). Solving the network equilibrium problem on a network of transputers . In: Publication du CRT 876. Codina E., J. Barcel6 (1995a). An algorithm for extremals calculations in optimal control problems with applications to the dynamic traffic assignment problem. In: Urban Traffic Networks (N.H. Gartner , G. Improta, Eds.), Chap . 12 , pp . 311-331. Springer Verlag, Berlin. Codina E., J. Barcel6 (1995). A system optimal dynamic traffic assignment model with distributed parameters . In: Advanced Methods in Transportation Analysis (L. Bianco, P. Toth, Eds.), Chap. 13, pp. 299-320. Springer Verlag, Berlin. Codina E., J. Barcel6 (1995b). Dynamic traffic assignment: considerations on some deterministic modelling approaches. Annals of Operations Research, 60 , pp. 1-58 Friesz T.L., F.J.Luque, R.L.Tobin and B.W.Wie (1989). Dynamic network traffic assignment considered as a continuous time optimal control problem. Op. Res., 37-6 , pp.58-69. Janson B.N. (1991). Dynamic traffic assignment for urban road networks. Transp. Res., 25B pp . 143-161. Kaufman D.E., R.L. Smith (1993). Fastest paths in time-dependent networks for intelligent highway systems application. IVHS Journal. 1(1) pp. 1-11. Merchant D. K. , G.L.Nemhauser (1978). A model and an algorithm for the dynamic traffic assignment problem. Transp. Sci. , 12, No 3. Technical annex guidelines for PETRI project (1993). Parallel Computing for Spain (PACOS). PCI Project (EP-9602). PETRI Project (1995). Parallel Computing for Spain (PACOS) PCI Project (EP9602). Municipality of Barcelona, UPC, UITESA. Deliverable 1 - Detailed System Design. de Romph E ., H.J.M. van Grol,R. Hamerslag (1992). 3DAS -3-Dimensional AssignmentA dynamic assignment model for short predictions. Preprints of the 89th Meeting of the RSA!, Chicago, USA. Smith M.J. (1993). A new dynamic traffic model and the existence and calculation of dynamic user equilibria on congested capacity-constrained road networks. Transp. Res., 27B , No 1. pp. 4963. 535