Transportation Planning
Applied Optimization Volume 64
Series Editors: Panos M. Pardalos University of Florida, U.S.A. Donald Hearn University of Florida, U.S.A.
The titles published in this series are listed at the end of this volume.
Transportation Planning State of the Art
Edited by
Michael Patriksson Department of Mathematics, Chambers University of Technology, Gothenburg, Sweden and
Martine Labbé ISRO and SMG, Université de Bruxelles, CP 210-01, Bruxelles, Belgium
KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
eBook ISBN: Print ISBN:
0-306-48220-7 1-4020-0546-6
©2004 Kluwer Academic Publishers New York, Boston, Dordrecht, London, Moscow Print ©2002 Kluwer Academic Publishers Dordrecht All rights reserved
No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher
Created in the United States of America
Visit Kluwer Online at: and Kluwer's eBookstore at:
http://kluweronline.com http://ebooks.kluweronline.com
Contents
Preface
ix
1 Origin-Based Network Assignment Hillel Bar-Gera, David Boyce Introduction 1.1 Problem statement 1.2 1.3 Review of solution methods for TAP An origin-based method for TAP 1.4 Experimental results 1.5 1.6 Discussion Conclusions 1.7 2 On Traffic Equilibrium Models with a Nonlinear Time/Money Relation Torbjörn Larsson, Per Olov Lindberg, Michael Patriksson, Clas Rydergren 2.1 Introduction 2.2 The time-based traffic equilibrium problem 2.3 Solution approaches 2.4 A route generation algorithm 2.5 Numerical tests 3 Stochastic Network Equilibrium Under Stochastic Demand David Watling Introduction 3.1 Notation 3.2 3.3 Critique of SUE in the context of day-to-day variability 3.4 Equilibrium conditions: fixed demand Equilibrium conditions: stochastic demand 3.5 3.6 Solution algorithm 3.7 Numerical tests 3.8 Conclusion 4 Stochastic Assignment with Gammit Path Choice Models Giulio Erberto Cantarella, Mario Giuseppe Binetti Introduction 4.1 4.2 Review of stochastic assignment
v
1 1 2 4 6 7 13 14
19 20 21 23 26 27 33 33 35 37 40 44 45 46 49 53 53 55
vi
TRANSPORTATION PLANNING 4.3 4.4 4.5
Probabilistic path choice models Numerical examples Conclusions
5 Estimation of Travel Time Reliability Chris Cassir, Michael G.H. Bell Introduction 5.1 Logit SUE model 5.2 Logit SUE sensitivity analysis 5.3 5.4 Approximation of travel times variances Example 5.5 Conclusion 5.6 6 A Joint Model of Mode/Parking Choice with Elastic Parking Demand Pierluigi Coppola 6.1 Background and objectives The parking choice sub-model 6.2 The mode choice sub-model 6.3 Simulation of realistic parking policies 6.4 7 A New General Equilibrium Model Yanling Xiang, Michael J. Smith, Miles Logie Introduction 7.1 DREAM—The general equilibrium model 7.2 An outline of the DREAM model 7.3 Features of the general equilibrium model 7.4 Test Results 7.5 8 Macroscopic Flow Models J.P. Lebacque, M.M. Khoshyaran 8.1 Introduction 8.2 The basic model LWR model for a link Partial flow models for links 8.3 8.4 Intersection modeling 8.5 Intersection models as solutions of optimization problems 8.6 An experimental validation Conclusion 8.7 9 AIMSUN 2 Simulation of a Congested Auckland Freeway John T Hughes Introduction and objectives 9.1 9.2 Simulation model 9.3 AIMSUN 2 simulation process 9.4 Study area and scope Model development 9.5 Geometric information 9.6 9.7 Traffic flow information
59 63 66 69 69 72 72 77 77 83 85 85 88 95 97 105 106 108 109 113 116 119 119 120 122 126 133 136 137 141 141 142 144 144 146 146 147
vii
Contents 9.8 9.9 9.10 9.11 9.12 9.13 9.14 9.15 9.16 9.17 9.18 9.19
Trip matrices Driver and vehicle information Maximum vehicle acceleration Motorway model Model outputs Lane utilisation Motorway speeds Greenlane Northbound on-ramp Calibration parameters Run times Conclusion Postscript
10 Fuzzy Traffic Signal Control Jarkko P. Niittymäki 10.1 Introduction 10.2 Fuzzy traffic signal control 10.3 Fuzzification interface 10.4 Defuzzification of outputs 10.5 Conclusions 11 An Urban Bus Network Design Procedure S. Carrese, S. Gori 11.1 Introduction 11.2 The main transit network (MTN) 11.3 The main transit lines (MTL) 11.4 Feeder lines 11.5 Model application and results 11.6 Conclusions 12 The Cone Projection Method Michael J. Smith, A. Battye, A. Clune, Y. Xiang 12.1 Introduction 12.2 Achieving the complementarity formulation 12.3 A cone field method of calculating equilibria 12.4 The cone projection method 12.5 A simple method 12.6 Conclusion 13 A Park & Ride Integrated System Chafik Allal, Benoit Colson, Bernard Fortz 13.1 Introduction 13.2 A Park & Ride Integrated system 13.3 Routing model 13.4 Travel time prediction 13.5 Computational results 13.6 Conclusion
147 147 149 151 153 153 154 155 156 159 159 160 163 163 163 166 170 174 177 177 178 181 185 186 193 197 198 198 203 205 207 209 213 214 215 217 221 225 227
viii
TRANSPORTATION PLANNING 14 229 Longitudinal Analysis of Car Ownership in Different Countries Akli Berri 14.1 Introduction 229 230 14.2 An age-cohort-period model 233 14.3 A multinational comparison 14.4 A comparative analysis for homogeneous zones 239 241 14.5 Long term forecasting using the demographic approach 242 14.6 Summary and conclusions Index
247
Preface
This book collects selected presentations of the Meeting of the EURO Working Group on Transportation, which took place at the Department of Mathematics at Chalmers University of Technology, Göteborg (or, Gothenburg), Sweden, September 9–11, 1998. [The EURO Working Group on Transportation was founded at the end of the 7th EURO Summer Institute on Urban Traffic Management, which took place in Cetraro, Italy, June 21–July, 1991. There were around 30 founding members of the Working Group, a number which now has grown to around 150. Meetings since then include Paris (1993), Barcelona (1994), and Newcastle (1996).] About 100 participants were present, enjoying healthy rain and a memorable conference dinner in the Feskekôrka. The total number of presentations at the conference was about 60, coming from quite diverse areas within the field of operations research in transportation, and covering all modes of transport: Deterministic traffic equilibrium models (6 papers) Stochastic traffic equilibrium models (5 papers) Combined traffic models (3 papers) Dynamic traffic models (7 papers) Simulation models (4 papers) Origin–destination matrix estimation (2 papers) Urban public transport models (8 papers) Aircraft scheduling (1 paper) Ship routing (2 papers) Railway planning and scheduling (6 papers) Vehicle routing (3 papers)
Traffic management (3 papers) Signal control models (3 papers) Transportation systems analysis (5 papers) ix
x
TRANSPORTATION PLANNING
Among these papers, 14 were eventually selected to be included in this volume. A further selection of papers from the Meeting are being edited for a special issue of Transportation Research, B, devoted to public transport problems. The 14 papers are described shortly as follows. Chapter 1, written by BarGera and Boyce, describes a very promising approach to the traffic assignment problem which is founded on a fundamental property of user equilibrium flows, that for each origin the flows describe an ayclic subnetwork. Chapter 2, written by Larsson et al., illustrates that when combining time delays and money outlays into a generalized cost, user equilibrium flows resulting from the conversion time money will be different from the result of using the conversion money time. A convex programming formulation is presented for the latter case, together with an algorithm for its solution. Chapter 3, written by Watling, proposes a variation of the stochastic user equilibrium (SUE) model to represent day–to–day stochastic variations in travel demands, and shows that the effect of such variations is a relatively stable mean link flow, but an increased link flow and total travel cost variance. Chapter 4, written by Cantarella and Binetti, analyzes the additive Gammit SUE model which is based on a Gamma distribution of route cost perception. This model satisfies stipulated conditions on probabilistic route-choice models, and is shown to yield results close to probit-based SUE models. Chapter 5, written by Cassir and Bell, presents a methodology for evaluating the reliability of transportation networks, which could be used to support the design of networks that are robust to everyday disturbances. In the case of the logit SUE route-choice model, reliability measures related to travel times are shown to be available efficiently, and are illustrated by means of numerical examples. Chapter 6, written by Coppola, notes that in previous models of parking management policies, parking search time is a neglected attribute which in reality should be a function of parking demand. A joint, nested logit model of mode and parking choice is then developed, and evaluated with data taken from an EC project. Chapter 7, written by Xiang et al., describes a general multi-modal traffic equilibrium model which embraces the classical four-step procedure into one combined model, including controls and stochastic travel costs. The main motivation for developing such a comprehensive model is to support the assessment of demand management strategies. Chapter 8, written by Lebacque and Khoshyaran, adapts the continuous Lighthill-Whitham-Richards model to dynamic traffic assignment. Included in the adaptation are specifications of partial and inhomogenous flows on links as well as several alternatives for intersection modeling. Chapter 9, written by Hughes, describes the application of the AIMSUN2 microscopic traffic simulation package to a section of a congested urban freeway in Auckland, New Zealand. Preliminary results show a good reproduction of speed and flow relationships, but less so for transient effects. Chapter 10, written by
PREFACE
xi
Niittymäki, develops a fuzzy traffic signal control model for a signal control scenario with several conflicting optimization criteria. Several approaches to the fuzzification and defuzzification phases of fuzzy traffic signal control are discussed. Chapter 11, written by Carrese and Gori, describes a coordinated process for the design of a bus transit network, including both lines and frequences. Heuristic methods construct the final plan through the sequential identification of a skeleton network, the main transit lines, and feeder lines. The model is applied to the Rome transit network system. Chapter 12, written by Smith et al., describes a descent algorithm for bilevel optimization in multi-modal equilibrium transportation models for the optimization of traffic control parameters. Convergence towards equilibrium points is ensured, and an intuitive motivation for the convergence of the control parameters towards points satisfying necessary optimality conditions are provided. Chapter 13, written by Allal et al., describes a demand-responsive park & ride transport system. Its real-time aspects are analyzed, and simulations results are reported. Chapter 14, written by Berri, analyzes household car ownership in seven countries, characterized by different economic and cultural contexts, by means of demographic modeling. Differences in long term forecasting results between countries and zones are explained by two main factors: the history of car ownership development and population density. The Swedish Communications Research Board (KFB) supported the conference financially, as did Chalmers, for which we are greatful. We would like to thank the participants of the Meeting for making it enjoyable, and the referees for their duly work. MICHAEL PATRIKSSON, GÖTEBORG, DECEMBER 2000
Chapter 1 ORIGIN-BASED NETWORK ASSIGNMENT Hillel Bar-Gera
[email protected]
David Boyce
[email protected] Department of Civil and Materials Engineering University of Illinois at Chicago 842W Taylor St. (mc 246), Chicago, IL 60607, USA
Abstract
Most solution methods for the traffic assignment problem can be categorized as either link-based or route-based. Only a few attempts have followed the intermediate, origin-based approach. This paper describes the main concepts of a new, origin-based method for the static user equilibrium traffic assignment problem. Computational efficiency in time and memory makes this method suitable for large-scale networks of practical interest. Experimental results show that the new method is especially efficient in finding highly accurate solutions.
Keywords:
Origin-based traffic assignment, user equilibrium, network optimization
1.
Introduction
Given the demand for travel (vehicles/hour) between pairs of origins and destinations, the traffic assignment problem is to allocate those flows to specific routes of a given network of nodes and links according to a given behavioral hypothesis. A common hypothesis in transportation research is that users seek to minimize the cost associated with their chosen routes. These flow-dependent costs are assumed to be known perfectly in advance. Under these assumptions, known as Wardrop’s user equilibrium principle, for every pair, origin and destination a positive flow on route implies the cost of route is not greater than the cost of any other route from to The term cost is used here in the most general way, and can be interpreted as travel time, monetary cost, some 1
M. Patriksson and M. Labbé (eds.), Transportation Planning, 1–17. © 2002 Kluwer Academic Publishers. Printed in the Netherlands.
2
TRANSPORTATION PLANNING
combination of those, or any other measure of disutility of using the specific route. The solution of the Traffic Assignment Problem (TAP) is relatively challenging. The main difficulty is that link costs are typically increasing non-linear functions of link flows. Solving TAP for large-scale networks of practical interest requires computationally efficient solution methods. Many computational methods are available to approximate the equilibrium solution. All of these methods are iterative; i.e. they start by considering some initial assignment, calculate the costs using the flows of the considered assignment, then modify the assignment and update the costs. One way to categorize solution methods is by the level of aggregation in which they store previous solutions. The most aggregated approach is the linkbased approach of storing total link flows, aggregated over all origin-destination pairs. The main advantage of this approach is its relatively modest memory requirements. The most disaggregated approach is the route-based approach of storing all used routes and the flow on each. Route-based methods have been shown to achieve better solutions; the main disadvantage is their large memory requirements. We propose an intermediate approach of storing link flows by origin. This approach maintains the main advantages of the route-based approach while reducing its memory requirements substantially. The next section provides a formal statement of the traffic assignment problem, and introduces the notation used in this paper. Section 3 reviews previous work. A schematic description of an origin-based method is presented in section 4. More details about this method can be found in Bar-Gera (1999). Experimental results are presented in section 5. Section 6 discusses the main characteristics of the origin-based approach. Finally, conclusions and plans for future research are presented.
2.
Problem statement
Let the graph G = {N, A} represent a transportation network, where N is the set of nodes and A is the set of directed links (arcs) on that network. Let be the set of origins, and be the set of destinations. Let be the travel demand matrix, where denotes the travel demand (assumed fixed) from origin to destination in vehicles/hour. The total demand is defined as the sum of flows over all O-D pairs, that is: Traffic on the network is described by an originbased link flow array where is the flow on link of travelers originating at The total flow on link is the aggregation of origin-based link flows over all origins, and is the vector of total link flows. Let be the vector of link costs, where is the cost function of link In this paper we assume that link costs are separable, that is
Origin-based network assignment
3
strictly positive, strictly increasing and continuously differentiable (these assumptions may be relaxed). Let E be the link-node incidence matrix, where if i is the initiation node of link if i is the termination node of link and otherwise. Let be the expanded demand matrix, where if and if A feasible traffic assignment is an origin-based link flow array f, that maintains non-negativity, conservation of flow, and satisfies the demand. In other words, the set of feasible assignments is: The user equilibrium Traffic Assignment Problem (TAP) is to assign the travel demand onto specific routes in the network, assuming that users seek to minimize their own costs. Under this assumption at equilibrium the cost of any used route is not greater than the cost of any alternative route for the same O-D pair. When
is well defined, i.e. path-independent, (our assumptions of monotonic and separable cost functions are sufficient), TAP is equivalent to the following minimization problem:
The evaluation of solution methods requires consideration of convergence measures. There are several possible measures of convergence; the ones used in this paper are easier to define using route-based notation. Let be the set of simple routes from to and the set of all simple routes. Let be the cost of route and the flow on route Denote the minimum O-D cost by: The basic measure of the violation of Wardrop’s equilibrium conditions is the route excess cost defined as the difference between the route cost and the minimum O-D cost, that is: Clearly, at equilibrium the excess cost of all used routes must be zero. The main global (aggregate) measure of convergence used here is the average excess cost, weighted by route flow over all used routes of all O-D pairs, Average excess cost is equivalent to the difference between the objective function and the lower bound obtained from the solution to the linearized subproblem, divided by the total demand. This is a common measure that can be calculated using link-based, origin-based or route-based solutions. It is
4
TRANSPORTATION PLANNING
also common to consider the relative gap, which is the difference between the current solution objective function and the best lower bound obtained so far, divided by the absolute value of the best lower bound. Another possible measure of convergence is the maximum excess cost over all used routes of all O-D pairs, Maximum excess cost is a sensitive and effective measure for solution accuracy; however, it requires a detailed solution, origin-based or route-based, and cannot be calculated from a link-based solution.
3.
Review of solution methods for TAP
The most common solution method for TAP is the nonlinear optimization method of Frank and Wolfe (FW). In each iteration, a subproblem of minimizing the linearized objective function is solved by assigning all traffic to minimum cost routes defined on the current link flow solution of the main problem. The new solution is obtained by finding a convex combination of the current solution and the subproblem solution that minimizes the original objective function. The objective function can be evaluated using total link flows only. An aggregated link-based representation of the current solution is therefore sufficient for this method. As a result memory requirement of this method is relatively small, which is its main advantage. The main drawback of FW is its slow convergence rate. See Patriksson (1994) for a detailed discussion. Related link-based methods were proposed by Florian and Spiess (1983), Fukushima (1984), LeBlanc et al. (1985), and Lupi (1986). In all cases some combination of previous solutions and the subproblem solution is used as a search direction. The Restricted Simplicial Decomposition (RSD) method of Hearn et al. (1987) suggests performing a multi-dimensional search over the convex hull of all previous subproblem solutions. That is if are subproblem solutions from previous iterations, the main problem solution at iteration is obtained by solving the following multidimensional nonlinear problem:
The nonlinear simplicial decomposition of Larsson et al. (1998) is a similar method in the sense that solutions to the main problem are obtained by solving a similar multidimensional nonlinear problem, where are still subproblem solutions, only that the subproblems are nonlinear, rather than linear, approximations of the main problem. All of the above methods are link-based methods; that is, only total link flows aggregated over all O-D pairs must be stored between iterations. More recently, increased attention was devoted to route-based methods. These methods assume that all used routes, and the flow on each route, are known for the
Origin-based network assignment
5
current solution. Using that information, flows can be shifted from high cost routes to low cost routes in order to achieve equilibrium. The first method proposed to solve TAP, in fact, was a route-based method. In this method, for each O-D pair considered in a cyclic order, flows are shifted from the maximum cost used route to the minimum cost route until both routes have the same cost. This idea was suggested by Dafermos (1968, 1969) and implemented by Gibert (1968). Bothner and Lutter (1982) implemented a similar route-based method that is used in practice in Germany. When link cost derivatives are known, they can be used to approximate flow shifts from all routes to the minimum cost route of every O-D pair. The aggregation of flow shifts over all O-D pairs is used as a search direction, and the next solution is chosen as the minimum point of the objective function along that direction. Larsson and Patriksson (1992) refer to this approach as Disaggregated Simplicial Decomposition (DSD); they also provide encouraging experimental results. Jayakrishnan et al. (1994) proposed another route-based method, where shifts are based on Gradient Projection (GP). In general, route-based methods seem to achieve high accuracy levels. The detailed information provided by a route-based solution has some additional merits. It allows re-optimization with respect to changes in problem conditions like demand, cost parameters, network topology, road pricing, etc. Detailed route flow information is also important for certain analyses, like emission estimation. In general, route flow solutions for TAP are not unique; however, Rossi et al. (1989), Janson (1993), and others proposed maximum entropy as a criterion for the most likely route flow solution, subject to user equilibrium. The third category of solution methods is the origin-based approach. An origin-based formulation of the traffic assignment problem was first proposed by Beckmann et al. (1956). To the best of our knowledge, there have been few attempts to pursue this approach in developing computational methods. Bruynooghe, Gibert and Sakarovitch (1968) made an attempt to develop such a method; however, Gibert (1968) subsequently concluded that the presence of cycles makes origin-based methods quite complicated. In the late 70’s and early 80’s Gallager and Bertsekas developed destinationbased algorithms for routing in communication networks, a problem that is mathematically equivalent to the traffic assignment problem. (See Gallager, 1977; Bertsekas, 1979; Bertsekas et al., 1979; Bertsekas et al., 1984; Bertsekas, 1998, pp. 390–391.) The reader may find certain similarities between the concepts of the algorithm proposed here, which was developed independently by the authors, and the algorithms proposed by Gallager and Bertsekas.
6
4.
TRANSPORTATION PLANNING
An origin-based method for TAP
For every origin we consider a specific restricting subnetwork In this paper all restricting subnetworks are a-cyclic. For a given set of (acyclic) subnetworks we wish to consider only solutions that are restricted by that set. In other words we consider the following restricted feasible set:
The restricted traffic assignment problem is formulated as:
The general scheme of the algorithm is as follows:
1 Find an initial solution nothing assignment).
(trees of minimum cost routes, all or
2 Initialize an outer loop index:
inner loop index:
3 Set/Update restrictions 4 Find a feasible descent direction
5 Find the step size 6 Set 7 Repeat steps 4-6 with
update link flows and link costs. to restricted convergence.
8 Eliminate residual flows. 9 Repeat steps 3-8 with
to global convergence.
In order to choose the restricting subnetwork for a certain origin we first calculate the maximum cost over used routes from to each node using current link costs. When there are no used routes from to an extended maximum cost, as defined in the appendix, is used. The link is included in the new restricting subnetwork if and only if The resulting subnetwork is a-cyclic, since implies a topological order (precedence order) for that subnetwork, that is a function such that if link belongs to the a-cyclic network, then This method of restriction update also guarantees the feasibility of the previous solution. Once a set of restricting subnetworks is chosen, the restricted problem is solved iteratively. In each iteration, for every origin and every node, link costs
Origin-based network assignment
7
and cost derivatives are used in a quasi-Newton fashion to find flow adjustments that seek to equalize the cost of travel from that origin to that node through all approaches. The aggregation of those adjustments over all nodes and all origins yields a search direction. Using a line search, an optimal step size that minimizes the objective function along the search direction is found. Finally the solution is updated accordingly. A critical step in this algorithm is the elimination of residual flows (step 8). This step is similar to a regular iteration, except that only flow adjustments that cause flow on some link to be zero are considered. Those adjustments are chosen so that objective function value will decrease, thus avoiding disruption to overall convergence. The same adjustments may have been considered in previous regular iterations; however, the step size in regular iterations is typically less than 1.0. As a result, a positive (probably small) residual flow is likely to remain on some links during all iterations, even though the restricted equilibrium flow on these links is zero. These residual flows have a negligible impact on link costs, and on the value of the objective function. However, when updating restrictions, any flow from to (originating at ) prohibits the introduction of the link from to (for origin ), as it causes a cycle. Therefore, eliminating residual flows before the next restriction update is crucial for global convergence.
5.
Experimental results
Experimental comparisons between Frank-Wolfe and the proposed originbased method have been conducted using two networks, Sioux Falls (LeBlanc et al. 1975 1), and a sketch (aggregate) network for the Chicago region for the year 1990. The Frank-Wolfe method used the L-deque minimum cost routes algorithm of Pape (1974), considered by Pallottino and Scutella (1998) to be one of the best choices for transportation networks at the current state-of-theart. All experiments were conducted with double precision arithmetic on a Pentium II, 265MHz Dell server. Sioux Falls is a small network of 24 nodes, each representing an origin and a destination, 528 O-D pairs, and 76 links. The difficulty in finding equilibrium solutions for Sioux Falls is probably due to the high level of congestion on the network. At equilibrium, the flows on 59 out of 76 links exceed their capacities. (Capacity values are derived assuming a BPR interpretation of the link cost functions.) Figure 1.1 shows relative gap results for the Sioux Falls network; Figure 1.2 shows excess cost results for the Sioux Falls network; average route costs are also given for comparison. After 3 seconds of CPU time, 71 restriction updates, and 1003 line searches, the origin-based assignment method reached an objective function value of 42.313352871074300, relative gap of 1.54E-15, average excess cost of 3.09E-
8
TRANSPORTATION PLANNING
Origin-based network assignment
9
10
TRANSPORTATION PLANNING
16 hours, and maximum excess cost of 2.41E-14 hours. These results are likely affected by the machine precision of approximately 2.6E-16. In fact additional iterations exhibit instability, probably due to truncation errors. The purpose of solving the problem to such high accuracy is to examine the behavior of the method, which we found to be quite pleasing. In the same CPU time, the Frank-Wolfe method performed 964 iterations, and reached a relative gap of 2.23E-04, and average excess cost of 2.80E-05 hours. Even after 10,000 iterations, and 33.4 seconds of CPU time, the relative gap for the Frank-Wolfe method was 2.50E-05, and the average excess cost was as high as 4.00E-06 hours. The results indicate the clear advantage of the origin-based assignment method over the Frank-Wolfe method. The equilibrium origin-based solution used 770 routes for the 528 O-D pairs with positive flow, averaging 1.46 routes per O-D pair. Examples from the resulting solution are shown in Figure 1.3. The flows from origin 1 (Figure 1.3a) form a relatively simple network, with only two additional links; that is, a tree may be obtained from this network by eliminating two links. Figure 1.3b shows the flows from origin 12 for that solution, which form a relatively complicated network with seven additional links. One may observe eight different routes from origin 12 to destination 16, which is the maximum number of routes for one O-D. The Chicago sketch network is a medium size network of 317 zones, each representing an origin and a destination, 76,267 O-D pairs, 1,088 nodes, and 3,008 links. The Chicago network is less congested; at equilibrium only 502 out of 3,008 links have flows that exceed their capacities. Relative gap results are shown in Figures 1.4 and 1.5. Excess costs for that network are shown in Figures 1.6 and 1.7, and average route costs are also given for comparison. After 30 minutes of CPU time, 63 restriction updates, and 8,715 line searches, the originbased assignment method reached a relative gap of 1.08E-13, average excess cost of 1.31E-13, and maximum excess cost of 5.01E-10. In the same CPU time, the Frank-Wolfe method performed 2,300 iterations, and reached a relative gap of 1.70E-05, and average excess cost of 2.80E-05. After 5,000 iterations (66.5 minutes of CPU time) the relative gap for the Frank-Wolfe method was 8.00E-06, and the average excess cost was 1.10E-05. On this network, the performance of the two methods is similar for the first 20-30 seconds (25-40 Frank-Wolfe iterations). However additional CPU time allows the origin-based assignment method to improve solution accuracy at a reasonable rate, while convergence of the Frank-Wolfe method is quite slow. The equilibrium origin-based solution used 121, 189 routes for the 76,267 O-D pairs with positive flow, averaging 1.59 routes per O-D pair. The memory requirement for storing the origin-based solution (excluding input data) with the first set of restrictions is about 4.9MB, but as the algorithm converges, the memory requirement decreases to about 1.9MB at equilibrium. (In the current
Origin-based network assignment
11
12
TRANSPORTATION PLANNING
Origin-based network assignment
13
implementation, the minimum memory requirement for a network of that size is about 1.4MB, while the upper bound is about 26.0MB.) In comparison, the input data requires about 0.8MB which is used mainly to store the trip table in double precision accuracy. The Frank-Wolfe method may be implemented with an almost negligible additional amount of memory.
6.
Discussion
There are two main reasons to prefer origin-based algorithms over the stateof-practice Frank-Wolfe method for practical applications: detailed solution, and substantially lower CPU time when higher accuracy is required. For many applications the detail provided by an origin-based solution is practically equivalent to the detail of a route-based solution. See Bar-Gera and Boyce (1999) for an elaborated discussion. Such detail is not provided by link-based methods. As noted in section 3, such detail is needed for certain analyses, like emission estimation, which have important practical implications. Detailed solutions also allow re-optimization with respect to changes in the demand, cost parameters, network topology, road pricing etc. For example, an origin-based solution for a given demand, can be easily adapted to provide a feasible solution for a different demand. This feature makes origin-based algorithms highly suitable in cases where the traffic assignment problem is one component of a larger transportation modeling problem. Route-based methods also provide detailed solutions; however, origin-based methods are more suitable for practical large-scale applications because of their reasonable memory requirements. The theoretical upper bound on the memory requirements of an origin-based solution is on the order of the number of origins times the number of links. The minimum requirement, if no alternative routes are used, is one integer per origin per node. For practical networks memory requirements are likely to be closer to the minimum requirements than to the upper bound. According to the results, the origin-based method is faster than the FrankWolfe method when higher accuracy is desired. Accuracy requirements in practice depend on computer technology. The number of FW iterations that can be computed in a practical sense for large-scale networks has increased from 5-10 in 1980 to 20-40 presently. As computer speed and memory increase further, additional iterations will likely be performed, as more highly converged solutions are desired. At that time we suggest that origin-based algorithms will become the preferred method. From a theoretical point of view there are several reasons for the computational efficiency of origin-based algorithms. First, the restriction to a-cyclic origin-based networks allows the definition of topological order. Using the topological order, the computation time of the minimum, maximum, and av-
14
TRANSPORTATION PLANNING
erage cost from the origin to all destinations is linear in the number of links in the subnetwork. The computation time of the search direction per origin is also on the order of the number of links in the subnetwork of that origin. The topological order of an a-cyclic network can be found in a time which is a linear function of the total number of links. Another contribution to the efficiency is achieved by reducing optimization complexity, which may be measured by the number of independent variables (decision variables) in the solution. In a route-based algorithm, the number of independent variables is the number of alternative routes in the system, that is the difference between the total number of used routes and the number of O-D pairs. In an origin-based algorithm, the number of independent variables is the number of additional links in the subnetworks, defined by: In general the number of independent variables in an origin-based representation is expected to be substantially lower than the number of independent variables in an equivalent route-based representation. For example, our equilibrium solution for the Chicago sketch network, suggests that there are 44,922 alternative routes, while the same solution requires only 8,428 additional links in an origin-based representation.
7.
Conclusions
The origin-based approach provides a highly accurate, memory conserving, and computationally efficient solution method for the traffic assignment problem. The current implementation, even though not computationally optimal, produces encouraging results. In addition to coding improvements, the implementation includes several parameters that may be optimized to improve computational efficiency. The authors plan to conduct careful experimental comparisons of the origin-based method with other methods in the near future. Finally, the authors hope to apply this method to larger problems, especially the combined model for travel demand and traffic assignment, and examine the method’s efficiency in that context.
Appendix: extended maximum costs Restriction updates are based on the maximum cost from the origin to each node The maximum cost over used routes is defined only if there exists at least one used route from to Following Hagstrom (1997), we suggest an extended definition of maximum cost for all nodes that may be described as follows. For a given origin link is a used link if the origin-based link flow from is strictly positive, A used node is the termination node of a used link. An extended used route is a route that starts as a used route, and continues
REFERENCES
15
through unused links and unused nodes only. An extended maximum cost used route is an extended used route, for which the used part has the maximum cost among all alternative used routes. The extended maximum cost from the origin to used node i is defined naturally as the maximum cost over all used routes from to For unused nodes the extended maximum cost is defined as the minimum cost over all extended maximum cost used routes.
Acknowledgments We are grateful for the financial support of the National Science Foundation through the National Institute of Statistical Sciences, Research Triangle Park, NC. Comments and suggestions of Professors Jane Hagstrom and Robert Abrams are appreciated. Chicago network data were provided by the Chicago Area Transportation Study, Chicago, IL.
Notes 1. The trip matrix was divided by 10, to reproduce results in previous literature.
References [1] H. Bar-Gera. Origin-based Algorithms for Transportation Network Modeling. PhD thesis, Civil Engineering, University of Illinois at Chicago, 1999. [2] H. Bar-Gera, and D. Boyce. Route flow entropy maximization in originbased traffic assignment. Transportation and Traffic Theory, Proceedings of the 14th international symposium on transportation and traffic theory. Jerusalem, Israel, 20-23 July, 1999, A. Ceder, ed. Elsevier Science, Oxford, UK, 397–415. [3] M. Beckmann, C.B. McGuire, and C.B. Winston. Studies in the Economics of Transportation. Yale University Press, New Haven, CT, 1956. [4] D. P. Bertsekas. Algorithms for nonlinear multicommodity network flow problems. in Proceedings of the International Symposium on Systems Optimization and Analysis. A. Bensoussan and J. L. Lions, eds., SpringerVerlag, New-York, 210–224, 1979. [5] D. P. Bertsekas, E. M. Gafni, and K. S. Vastola. Validation of algorithms for optimal routing of flow in networks. in Proceedings of the 1979 IEEE conference on Decision and Control, San Diego, CA, January 10-12, 1979, 220–227, 1979. [6] D. P. Bertsekas, E. M. Gafni, and R. G. Gallager. Second derivative algorithms for minimum delay distributed routing in networks. IEEE Transactions on Communications, COM-32:911–919, 1984.
16
TRANSPORTATION PLANNING
[7] D. P. Bertsekas. Network Optimization - continuous and discrete models, Athena Scientific, Belmont, Massachusetts, USA, 1998. [8] P. Bothner and W. Lutter. Ein direktes verfahren zur verkehrsumlegung nach dem 1. prinzip von wardrop. Forschungsbereich: Verkehrssysteme Arbeitsbericht 1, Universitaet Bremen, 1982. [9] M. Bruynooghe, A. Gibert, and M. Sakarovitch. Une méthode d’affectation du trafic. In Proceedings of the 4th International Symposium on the Theory of Road Traffic Flow, Karlsruhe, 1968, W. Leutzbach and P. Baron, editors, Beiträge zur Theorie des Verkehrsflusses Strassenbau und Strassenverkehrstechnik, Heft 86, Herausgegeben von Bundesminister für Verkehr, Abteilung Strassenbau, Bonn, pp. 198–204, 1969.
[10] S.C. Dafermos. Traffic Assignment and Resource Allocation in Transportation Networks. PhD thesis, Johns Hopkins University, Baltimore, MD, 1968. [11] S.C. Dafermos and F.T. Sparrow. The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards, 73B:91–118, 1969. [12] M. Florian and H. Spiess. Transport networks in practice. In Proceedings of the Conference of the Operations Research Society of Italy, Napoli, pp. 29–52, 1983. [13] M. Fukushima. A modified Frank-Wolfe algorithm for solving the traffic assignment problem. Transportation Research, 18B:169–177, 1984. [14] R. G. Gallager. A minimum delay routing algorithm using distributed computation. IEEE Transactions on Communications, COM-25:73–85, 1977. [15] A. Gibert. A method for the traffic assignment problem. Report LBSTNT-95, Transportation Network Theory Unit, London Business School, London, 1968. [16] J.N. Hagstrom. Computing tolls and checking equilibrium for traffic flows. University of Illinois at Chicago, preprint, 1997. [17] D.W. Hearn, S. Lawphongpanich, and J.A. Venture. Restricted simplicial decomposition: computation and extensions. Math. Program. Study, 31:99–118, 1987. [18] B.N. Janson. Most likely origin-destination link uses from equilibrium assignment. Transportation Research, 27B:333–350, 1993. [19] R. Jayakrishnan, W.K. Tsai, J.N. Prashker, and S. Rajadhyaksha. A faster path-based algorithm for traffic assignment. Transportation Research Record, 1443:75–83, 1994.
REFERENCES
17
[20] T. Larsson and M. Patriksson. Simplicial decomposition with disaggregated representation for the traffic assignment problem. Transportation Science, 26:4–17, 1992. [21] T. Larsson, M. Patriksson, and C. Rydergren. Application of simplicial decomposition with nonlinear column generation to nonlinear network flows. In licentiate thesis by Clas Rydergren, Thesis No. 702, Linköping Institute of Technology, Linköping, Sweden, 1998. [22] L.J. LeBlanc, R.V. Helgason, and D.E. Boyce. Improved efficiency of the Frank-Wolfe algorithm for convex network programs. Transportation Science, 19:445–462, 1985. [23] L.J. LeBlanc, E.K. Morlok, and W.P. Pierskalla. An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Research, 9:309–318, 1975. [24] M. Lupi. Convergence of the Frank-Wolfe algorithm for solving the traffic assignment problem. Civil Engineering Systems, 3:7–15, 1986. [25] S. Pallottino and M.G. Scutella. Shortest path algorithms in transportation models: classical and innovative aspects. In P. Marcotte and S. Nguyen, editors, Equilibrium and Advanced Transportation Modelling. Kluwer Academic Publishers, Boston, 1998. [26] U. Pape. Implementation and efficiency of moore-algorithms for the shortest route problem. Mathematical Programming, 7:212–222, 1974. [27] M. Patriksson. The Traffic Assignment Problem, Models and Methods. VSP, Utrecht, Netherlands, 1994. [28] T. F. Rossi, S. McNeil, and C. Hendrickson. Entropy model for consistent impact fee assessment. Journal of Urban Planning and Development/ASCE, 115:51–63, 1989.
Chapter 2 ON TRAFFIC EQUILIBRIUM MODELS WITH A NONLINEAR TIME/MONEY RELATION Torbjörn Larsson
[email protected]
Per Olov Lindberg
[email protected] Department of Mathematics, Linköping University SE-581 83 Linköping, Sweden
Michael Patriksson
[email protected] Department of Mathematics, Chalmers University of Technology SE-412 96 Gothenburg, Sweden
Clas Rydergren
[email protected] Department of Mathematics, Linköping University SE-581 83 Linköping, Sweden
Abstract
We consider a traffic equilibrium problem in which each route has two attributes, time delay and monetary outlay, which are combined into a generalized time through a nonlinear relation. It is shown that this problem can be stated as a convex optimization model. Two simplicial decomposition type methods are proposed for its solution. The subproblem of these methods, which is a twoattribute shortest route problem, can be efficiently solved by the multi-labelling technique which has previously been applied to resource-constrained shortest path problems. Our numerical experiments show that both methods are feasible approaches to the equilibrium problem.
Keywords:
Traffic equilibrium, nonlinear value-of-time 19
M. Patriksson and M. Labbé (eds.), Transportation Planning, 19–31. © 2002 Kluwer Academic Publishers. Printed in the Netherlands.
20
1.
TRANSPORTATION PLANNING
Introduction
In models for traffic equilibria one usually assumes that travellers choose the routes from their origins to their destinations that are preferred according to a cost criterion (the Wardrop principle, e.g., [10, Section 2.1], or [11]). The routes typically have several attributes, such as time, monetary outlays, distance etc. Usually these attributes are combined linearly to a generalized cost. However, empirical studies, e.g., [7] and [6], indicate that travelers value travel time changes nonlinearly rather than linearly, in that short changes have lower value of time than longer ones. At first sight, this might seem puzzling, but it is in fact easy to envisage situations where this is the case. Consider, for example, a young commuter heading for his workplace. Arriving a quarter of an hour late to work is probably then more than three times worse than coming five minutes late. Conversely, having to wake up a quarter of an hour earlier, similarly, is experienced to be more than three times worse than waking up five minutes earlier. In the present paper, we will study a situation with two route attributes: time and money. In a subsequent paper, we will hopefully return to the case of more than two attributes. The two-attribute case has already been studied by Bernstein and Gabriel (B&G for short) in [4] and [2]. They assume that route choice is based on a (nonlinear) generalized cost. In particular they assume that the (generalized) cost for route r is
with and being monetary outlay and travel time, respectively, and the nonlinear value of time for route To compute equilibria of their model, B&G utilize a specialized code based on a Gauss-Newton type method for nonlinear complementarity problems. It is not a priori obvious why route choice should be based on (generalized) cost rather than on time. Thus, in the present paper we consider to instead base route choice on time rather than on cost, At first sight, the time-based cost (2) seems to be just a reformulation of the money-based one (1), with It turns out, however, that they are not equivalent. For the case with flow independent monetary outlays, the time based equilibrium problem can be stated as an equivalent optimization problem. This will give the benefit of usually faster computational methods as well as better control of convergence. The development of this equivalent optimization model and the techniques to solve it are the theme of this paper. The paper is structured as follows. In Section 2 we state the time-based traffic equilibrium problem. Section 3 is devoted to the simplicial decomposition
On Traffic Equilibrium Models with a Nonlinear Time/Money Relation
21
approaches to solve this problem; on the one hand a disaggregate version, where all route flows are stored, on the other hand an aggregate version, where only link flows are stored. In Section 4 we describe how to generate new routes to be used in the simplicial decomposition schemes, using a multi-label shortest path method [3]. Section 5, finally, is devoted to some computational testing on the example of B&G and on the classical Sioux Falls network.
2.
The time-based traffic equilibrium problem
We will first introduce some further notation. The set of commodities (i.e., the origin-destination pairs) is denoted by and denotes the traffic demand for commodity (More general, could denote a segment of travellers in a certain travel relation.) Let be the set of simple routes for commodity and let be the set of all routes. Similarly, let denote the routes that pass link with being the set of links in the network. Let denote the flow along route and let be the travel time at link flow on link Thus, the travel time for route will be Similarly, let be the monetary outlay for link which is assumed to be independent of the traffic flow. If the monetary outlay for route is assumed to be additive, then (We can allow for more complex structures for the monetary outlay for a route. The important thing is that they are monotone and can be computed recursively.) Travellers are assumed to base their route choice on some generalized times on the routes, and based on these times they always choose the minimal time route from origin to destination. The situation can be expressed by the well known equilibrium condition, the Wardrop principle (e.g., [10]),
where is the generalized time on route If travel time is the only measure of generalized time, we have and it is well known that the flows and that fulfill (3) can be obtained by solving the following convex optimization problem (see e.g., [10], Section 2.2).
22
TRANSPORTATION PLANNING
subject to
If we want to include a monetary cost component for each route, and to express a situation with a nonlinear relation between travel time and monetary cost, we can express the generalized time on route for given link flows according to
Since the time equivalent of money, probably is dependent on socioeconomic factors, it is natural to assume that it depends not on but on the commodity corresponding to The function is naturally assumed to be nonnegative and increasing. The Wardrop conditions for the time-based traffic equilibrium problem are expressed by (3) using the definition of according to (4). An equivalent optimization model for this problem can be formulated as
subject to
The only difference in comparison with problem (P) is the extra linear term in the objective. Thus, is a convex problem, since (P) is. Further, since has a compact feasible set it attains its minimum, and since the constraints are linear an Abadie constraint qualification is fulfilled, whence there are Lagrange
On Traffic Equilibrium Models with a Nonlinear Time/Money Relation
23
multipliers such that the Karush–Kuhn–Tucker (KKT) conditions are satisfied (see [1], Theorem 5.1.3 and Lemma 5.1.4). Letting be the multiplier for the demand constraint and substituting the expression for into the objective, we get for the KKT condition
with equality if
Thus
Hence, the KKT conditions state, for that if that is fulfills the Wardrop conditions. Conversely, assuming that fulfills the Wardrop condition and letting it follows that fulfills the KKT conditions, and hence is an optimal solution to If the link travel time functions are strictly increasing, then the solution to the time-based traffic equilibrium problem has unique link flows. This follows from the fact that the objective of is in this case strictly convex in the link flows. In summary we have shown the following. Proposition 1 (Optimization formulation) The time-based traffic equilibrium problem admits an equivalent optimization formulation.
3.
Solution approaches
In practice, the route set is too large to be handled explicitly. Instead, one has to generate profitable routes systematically and iteratively. We propose to solve the problem using either the disaggregate (DSD) or aggregate form (ASD) of the simplicial decomposition method (cf. [10, 8]). The DSD method, which alternates between a route generation phase and a master problem phase where the problem is solved using the routes generated so far, is analogous to the original DSD method for the standard traffic equilibrium problem proposed in [8]. Suppose we have generated a subset of the routes, where is the subset of the routes for commodity We then solve a restriction of replacing with This problem (the master problem) is denoted , and it gives the solution giving an upper bound to the optimal value of Next, we want to find out whether we need to include more routes. This is accomplished through the solution of a subproblem, a linearized version of The solution of this subproblem (the route generation problem) amounts
24
TRANSPORTATION PLANNING
to checking whether some non-generated route than zero, i.e., to check whether
where
has a reduced cost less
is the multiplier for demand constraint
Thus, we
have to solve
which is to find the route with minimal generalized time, and then we have to check whether this generalized time is lower than A solution procedure for finding the new routes is given in next section. Since there are only finitely many routes for each O/D–pair we have the following result. Proposition 2 (Convergence) The DSD method will terminate with an optimal solution after a finite number route generations. Similarly to classic traffic assignment problems, the shortest path subproblems in the route generation arises from a linearization of the objective of e.g., ([10], Section 4.1.2). If we linearize the objective, then the cost coefficients will be flow independent, and all traffic can be sent along the shortest paths. Due to the convexity of the objective function of the solution of the linearized problem yields a lower bound of the optimal value, as stated below. Proposition 3 (Lower bound) paths in the route generation for
be the set of generated shortest Then,
is a lower bound on the optimal value of The lower bound together with the upper bound from solving the master problem gives the possibility to terminate the algorithm when a prescribed error is achieved rather than when all routes with nonzero flows are generated. In large networks, the DSD strategy may be too memory consuming. Hence, there is need for more aggregate versions. In classical (aggregate) simplicial decomposition (ASD) methods for traffic assignment, one takes convex combinations of link flow patterns arrived at by assigning all demand in each commodity to the shortest path obtained from the route generation subproblems (e.g., [10]). Exactly the same can be done in the current situation.
On Traffic Equilibrium Models with a Nonlinear Time/Money Relation
25
To be specific, assume that the shortest route for commodity in the iteration is and that this route has monetary outlay Assigning all demand in each commodity to the shortest route, we get the link flow pattern vector where for each link we have
Further, let be the total time equivalent of the monetary outlays for this flow pattern. The aggregate master problem for the time based traffic assignment problem is then to minimize the objective of the original problem over convex combinations of generated link flow patterns up to the current iteration I, that is
subject to
This problem gives new link flows and hence travel times Given these travel times, we solve a new route generation subproblem. Assigning all flow to the generated routes, we get a new link flow pattern etc. The theoretical results for the ASD method are totally in parallel with those of the DSD method. The solution to whose feasible set corresponds to a restriction of gives an upper bound to the optimal value of Proposition 4 The ASD method will terminate after a finite number of route generations. Proof Follows from the fact that there are only a finite number of link flow patterns that can be generated, since they are composed of flows along a finite number of routes. The observation that the generated shortest paths solve a linearization of the true objective, is valid also for the aggregate master the only difference
26
TRANSPORTATION PLANNING
being that we linearize at link flows that are convex combinations of generated link flow patterns. In practice, the number of generated link flow patterns will become very large. Hence, if we have a limit on how many patterns we can store, we will have to drop patterns (possibly after aggregation), i.e., we will use restricted simplicial decomposition [5]. This will destroy the finite convergence, giving convergence in the limit.
4.
A route generation algorithm
The minimization problem to solve for finding new routes is a generalized shortest path problem, where the links have multiple attributes, in our case travel time and monetary outlay. Due to the nonlinear transformation of money to time, it cannot be solved using standard procedures for shortest paths. In particular it does not adhere to the optimality principle of dynamic programming. If the “shortest” path from an origin to a destination passes node that does not imply that the sub-path from the origin to node is the shortest path between the origin and node Our shortest path problem can however be solved using a multi-label shortest path method, known from the solution of resource constrained shortest path problems [3]. Each node gets labels (usually several) of the form where and are the accumulated travel time and monetary outlay to get to the node from the origin via predecessor node (or or more generally, label) For a given origin, one starts by giving the origin node the label (0, 0, –). For each labeled node, one labels all nodes that can be reached from it. If for instance node can be reached via a link with time delay and monetary outlay from node with label then node gets the label Thus, the labels will indicate the total time and total monetary outlay to get to the nodes along paths indicated by the predecessor indices. The embryonic version of multi-label shortest path methods just described, will in fact generate all paths in a network. Possibly, a node can get one label for each predecessor. Since the number of labels in practice can be very large, we need to use domination tests to keep down the number of labels. If in a given node there are two labels and with and then the label can be deleted, since any path continuing from that label will be no better than the corresponding path from Since both travel time delays and monetary outlays for the links are nonnegative, domination implies that no path corresponding to the labels will contain cycles. Hence, the labeling process is finite. When the process stops, each destination node has received a set of labels It is then easy to find the best label, i.e., the one minimizing and the best O/D path can
On Traffic Equilibrium Models with a Nonlinear Time/Money Relation
27
be traced using the predecessor indices. The multi-label shortest path method is summarized in the rudimentary pseudo code in Table 2.1.
5.
Numerical tests
We have tested the disaggregate as well as the aggregate version of the proposed simplicial decomposition method on two small test networks which are summarized in Table 2.2. Network 1 is taken from [2]; we have used the inverse of their time-to-money transformation,
to describe the nonlinear relation between monetary outlay and travel time, i.e. Moreover, since G&B in contrast to us use elastic demand, we have used their equilibrium demand as our demand. Network 2 is a modification of the classical Sioux Falls network, where we have used the tolled links of [9] and the same function G as for Network 1. Our experiments were not aiming at obtaining computational efficiency, but rather at verifying the validity of the algorithms. Hence, for both networks, and for both methods, we have solved the master problems to a quite small relative error before generating new routes. This accuracy bound is computed in a similar way as for the global accuracy. For the minimization in the master problem, we have used gradient projection in the DSD method and Newton’s method in the ASD method. We initialize the algorithm by assigning all travel demand to the time optimal routes.
28
TRANSPORTATION PLANNING
The disaggregate version terminates, for both test networks, in a few iterations, as shown in Tables 2.3 and 2.4. (Note that the relative gap, or error, in a given iteration is in fact not determined until the route generation of the next iteration.) The solution procedure generates 131 and 1175 routes for Network 1 and 2, respectively, and the number of routes with positive flow in the optimal solutions is 84 and 663 for Network 1 and 2, respectively. In the tests of the aggregate version we have used non-restricted simplicial decomposition, i.e., no traffic patterns were discarded. As expected, convergence is much slower for the aggregate version. Figures 2.1 and 2.2 display the iteration histories, giving iteration-wise upper and lower bounds of the objective. We achieve a gap of 0.1% at iterations 23 and 45 for the network 1 and 2, respectively. Gabriel and Bernstein give no computing times and do not mention how many routes they have generated. However, in order to compare their results to ours, we chose our money-to-time transform G as the inverse of the time-
On Traffic Equilibrium Models with a Nonlinear Time/Money Relation
29
to-money transform in [2]. To our initial surprise, the solutions did not coincide. A closer look shows that this is in fact quite natural. Consider the example in Figure 2.3. Using we get a money-based cost of and a generalized time of It is then easy to verify that the money
30
based equilibrium is
TRANSPORTATION PLANNING
and that the time based equilibrium is
Observation 1 (Non-equivalence of time- and money-based equilibrium problems) Evaluating routes in a money based way using generalized cost does not necessarily give the same equilibrium as evaluating routes in a time based way, using generalized time with In a later paper we will come back to how one can utilize the equivalent optimization formulation of the time based approach to solve money based problems and more general multi attribute traffic assignment problems.
References [1] M.S. Bazaraa, H.D. Sherali and C.M. Shetty. Nonlinear Programming: Theory and Algorithms. John Wiley & Sons, New York, NY, 1993. [2] D. Bernstein and S.A. Gabriel. Solving the nonadditive traffic equilibrium. In P.M. Pardalos, D.W. Hearn, and W. Hager, editors, Network Optimization, volume 450 of Lecture Notes in Economics and Mathematical Systems, pages 72–102. Springer–Verlag, 1997. [3] J. Desrosiers, Y. Dumas, M.M. Solomon, and R. Soumis. Time constrained routing and scheduling. In M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser, editors, Handbook in Operations Research and Management Science, Network Models. North–Holland, 1995. [4] S.A. Gabriel and D. Bernstein. The traffic equilibrium problem with nonadditive path costs. Transportation Science, 31:337–348, 1997. [5] D.W. Hearn, S. Lawphongpanich, and J.A. Ventura. Restricted simplicial decomposition: Computation and extensions. Mathematical Programming Study, 31:99–118, 1987.
REFERENCES
31
[6] D.A. Hensher and T.P. Truong. Valuation of travel savings. Journal of Transport Economics and Policy, pages 237–260, 1985. [7] L. Hultkranz and R. Mortazavi. The value of travel time changes in a random nonlinear utility model. CTS working paper 1997:16., Submitted. [8] T. Larsson and M. Patriksson. Simplicial decomposition with disaggregated representation for the traffic assignment problem. Transportation Science, 26:4–17, 1992. [9] T. Larsson, M. Patriksson, and A-B. Strömberg. Ergodic, primal convergence in dual subgradient schemes for convex programming. Mathematical Programming, 86:283–312, 1999. [10] M. Patriksson. The Traffic Assignment Problem – Models and Methods. VSP, Utrecht, 1994. [11] Y. Sheffi. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice–Hall, Englewood Cliffs, NJ, 1985.
Chapter 3 STOCHASTIC NETWORK EQUILIBRIUM UNDER STOCHASTIC DEMAND David Watling
[email protected] Institute for Transport Studies, University of Leeds, UK
Abstract
A generalisation of the conventional stochastic user equilibrium (SUE) model is developed in order to represent day-to-day variability in traffic flows due to stochastic variation in both a) the inter-zonal trip demand matrix, and b) the route choice proportions conditional on the demands. The equilibrated variables in this new problem are the link flow means and covariance matrix. A heuristic solution algorithm is proposed, based on the solution of a sequence of SUE subproblems. Numerical results are reported from the application of this technique to a realistic network, under the assumption of probit-based choice probabilities. In these tests, as the level of demand variability is increased (but the mean demand held fixed), the link flow variances predicted by the proposed model are seen to increase, but the effect on mean flows is relatively small. The increased variation in flows is, however, seen to have an inflationary effect on one of the prime indicators of network congestion, mean total travel cost.
Keywords:
Networks, route choice, equilibrium, uncertainty, stochastic demand
1.
Introduction
The established family of network equilibrium models for representing driver route choice over congested traffic networks consists of a variety of techniques, the most well-known being the deterministic user equilibrium (DUE) and stochastic user equilibrium (SUE) models, which have been formulated for both the ‘steady state’ [13] and ‘within-day dynamic’ [11] cases. A characteristic feature of all models in this family is their use of a deterministic representation for both: the key variables of predictive interest, namely link flows and travel times; and 33
M. Patriksson and M. Labbé (eds.), Transportation Planning, 33–51. © 2002 Kluwer Academic Publishers. Printed in the Netherlands.
34
TRANSPORTATION PLANNING
the primary input variables, namely the inter-zonal travel demand matrix and network characteristics (e.g. free-run speeds/times, capacitites). The essential difference between the ‘steady state’ and ‘dynamic’ models is that in the latter these input/output quantities are disaggregated into shorter time periods within the day. The more important distinction for the present paper is that between DUE and SUE (whether steady state or dynamic). In the SUE model, drivers are assumed to have perceptual differences in their evaluation of a given travel cost, these differences being most conveniently represented by a pre-specified perceptual probability distribution, distributed across the population of drivers. DUE, on the other hand, assumes a single, mean perception of travel cost. That is to say, in terms of the input/output quantities mentioned above, SUE is no more stochastic than DUE (a point also made in [6]). This latter comment on the inherent determinism of SUE is not merely a theoretical nicety. There is, of course, extensive evidence that the factors above may vary significantly from day-to-day (e.g., [9]; [5]; [14]; [17]; [8]), but the deterministic assumption has prevailed on the basis of their being no clear, tractable way of including it, and based on the belief that variability need not be considered in order to approximate mean conditions. There are, however, a number of drawbacks to such a pragmatic approach. Firstly, there are theoretical arguments to suggest that – due to the non-linearity of the system under consideration – neglecting variability will lead to a systematic bias in the estimate of mean travel times/costs. Moreover, it is not clear that the impact of such biases will be consistent across the network or with respect to different policy measures. Secondly, the models provide only mean output measures (traffic flow, network performance, etc.), whereas information on the variations in traffic flows and travel times would also be of value to the planner. Thirdly, these existing models are poorly suited to testing policies that are designed to respond to variability. The study of driver information systems has provided a primary example of such a policy; the major complications that have arisen in matching model predictions with empirical evidence of response could be said to be a difficulty in separating ‘subjective variation’ (individuals’ preferences and constraints) from the ‘uncertainty’ (the degree to which an individual fails to satisfy their own preferences/constraints due to predictive errors). With these comments in mind, the objectives of the present paper are: 1 To formulate a modified version of SUE that is able to represent stochastic variation in travel demand, and the effect of such variation on route choice. 2 To propose a solution algorithm for this modified model, and to present preliminary numerical results from its application to a realistic network.
Stochastic Network Equilibrium Under Stochastic Demand
35
In particular, it is noted that the objective is not to build an entirely new modelling paradigm, but to seek a minimal extension to SUE in order to include such variations. The approach is based on extending the network equilibrium model presented in [15] from the case of deterministic to stochastic demand. In fact, the approach may be further extended to include the effect of stochastic variations in network attributes such as capacities, provided their distribution is independent of traffic conditions. However, in the present paper, the focus will be on stochastic demand (rather than supply) variations, as it is the demand variations that are the most complex to represent within a consistent equilibrium framework. The paper begins by introducing some basic notation and definitions (section 2), and then goes on to make a critique of the existing SUE model in the context of daily variations (section 3). In section 4, a summary is given of the salient details of a recently proposed extension to SUE, that is able to model variable traffic flows but under deterministic demand. In section 5, this method is subsequently extended to the case of stochastic demand. In section 6, a heuristic solution algorithm is presented, and in section 7 preliminary simulation results are reported.
2.
Notation
We suppose the network consists of A links indexed and W inter-zonal (origin-destination) movements indexed The N possible routes that pass through a link at most once, across all such inter-zonal movements, is indexed by the set {1,2,..., N}, in such a way that the subset of routes relating to inter-zonal movement are indexed by the set
The demand rates (vehicles per hour) for each of the W inter-zonal movements are held in the column vector of dimension W, with elements 1,2,... , W). Define to be an N × W path-movement incidence matrix with elements (for and
Then is an N × N diagonal matrix, with diagonal entries from the vector such that each row relates to a route, and the diagonal entry for that row is the demand appropriate to that route. The column vector of dimension N denotes an assignment of flow to each of the possible routes, with the convex set of demand-feasible non-negative
36
TRANSPORTATION PLANNING
route flow rates denoted by
where denotes N-dimensional non-negative real space, and where here and throughout the paper, denotes the transpose of the matrix The corresponding convex set of demand feasible link flow rates is
where is an A × N link-path incidence matrix with elements 1 , 2 , . . . , A and
The cost of travelling along link at a given link flow rate vector is denoted These functions may also themselves be arranged in a column vector, These link performance functions imply corresponding route cost-flow performance functions
by
Suppose further that for each movement is a route choice model describing the probability of a randomly-selected driver on interzonal movement choosing each of the alternative routes when the perceived route costs (averaged across the driver population) are and that denotes these functions across all movements, arranged in a column vector of dimension N. For example, for each movement it may be assumed that is a random utility model:
where
follow some given joint probability distribution.
We may then state the following well-known definition [13]. Definition 1 The route flow rate vector (SUE) if and only if
is a stochastic user equilibrium
Alternatively, the link flow rate vector
is termed a SUE if and only if
Stochastic Network Equilibrium Under Stochastic Demand
37
Corresponding to the usual flow rate variables and as defined above) it will also prove useful to define respective absolute flow variables and with elements in the discrete (integer) units of “vehicles" or “drivers". These absolute flows relate to a particular period of the day, of duration hours. For example, Throughout the paper, the capitalised versions of and namely F, V, , , T and C will be used to denote vector random variables of the relevant flow and cost quantities. In terms of the absolute flows, the discrete demand-feasible route flows are given by
where denotes the N-dimensional space of non-negative integers. Similarly, the demand-feasible link flows are given by:
3.
Critique of SUE in the context of day-to-day variability
As noted in the introduction above, observations of traffic volumes and travel times indicate considerable day-to-day variability, and so it is not difficult to make a case that these quantities are most appropriately represented as stochastic variables. From a purely deductive philosophy, the fact that SUE neglects significant sources of variability (as DUE does) is perhaps sufficient criticism to warrant the investigation of more sophisticated modelling tools. This is true even if our only interest is in mean network performance, due to the non-linear nature of the interactions between traffic flow, travel times and travel choice, refuting any naive claim that SUE/DUE necessarily represent mean performance to which variations may subsequently be added. Taking a more pragmatic viewpoint, however, it is known from the long experience with DUE/SUE models that they have a good degree of explanatory power; that is to say, they “explain" a good deal of the performance of traffic networks. It is therefore relevant to ask in what way can they be built upon for the purpose of this paper, and in what circumstances can they said to characterise approximate mean performance. Answering this question is a deceptively difficult problem. An appealing pragmatic approach is to assume the SUE link flows represent the mean of independent (between links) Poisson variables, and one could then compute mean costs/times corresponding to these variable flows. One problem with this approach is that is does not represent the covariances between links that are likely to occur due to the network structure. Two obvious sources of covariance are: in the case of a fixed demand matrix, for two links that are part of alternative routes for a particular inter-zonal movement, the contributions
38
TRANSPORTATION PLANNING
to these link flows from that movement will be negatively correlated (since the route flows are negatively correlated), and for links that are part of the same route there will be a positive correlation; in the case of stochastic demand, the correlations above must be balanced against positive correlations between the components of link flow for all links used by a particular inter-zonal movement (when demand is high, all route flows are likely to be high). A second problem with this approach is that it pre-supposes SUE correctly predicts mean flows under such variable conditions. An argument often cited for this is that one can suppose that the long-run variable route flows (for each inter-zonal movement) are multinomially distributed, assuming drivers make choices independently, with choice probabilities based on some form of random utility model evaluated at SUE costs. It is then argued that as all inter-zonal demands become large, the distribution of the flow proportions will become increasingly narrow, and focused on the SUE flows; in the limit, then, as the flow probability distribution becomes focused on a single point, SUE can be viewed as an equilibrium condition on the flow probability distribution. There are a number of difficulties with this line of reasoning: 1 If drivers build up their predictions of travel times/costs from a finite number of past experiences (these experiences are themselves subject to random variation), then while the distribution of route flows conditional upon the past may be multinomial, the unconditional equilibrium distribution will in general be an over-dispersed multinomial, since the choice probabilities are then stochastic [7]. 2 Even if it is possible to assume that drivers’ experiences are sufficiently long that they are able to predict long-run expected costs, so that the choice probabilities are deterministic, then for non-linear link cost-flow performance relationships, SUE - in effectively substituting costs at expected flows for expected costs - contains an inherent systematic bias [2]. For convex cost-flow relationships, expected costs are systematically underestimated. 3 As the absolute number of travellers on all inter-zonal movements approaches infinity, then we expect SUE increasingly to approximate SUE mean flow rates, in spite of the misgivings above [4]. In typical urban, peak period, traffic assignment applications, the zoning system is likely to be sufficiently fine that many inter-zonal movements will have quite a “small" demand, and so the usefulness of the asymptotic result is not clear. In addition, it is important not to confuse the absolute demand with the typical demand input to a traffic assignment model, which is
Stochastic Network Equilibrium Under Stochastic Demand
39
the mean flow rate per hour. The absolute demand depends on both the demand rate and the length of the time period over which this rate is assumed to be valid. A large demand rate on its own is not sufficient, particularly when one considers the current trend in traffic assignment models, towards dynamic models that assign a number of multiple, short time periods. In response to some of the issues raised here, a radically new approach to traffic assignment modelling was proposed by Cascetta [2], and extended further by Davis [4] and in [1]. This approach models the dynamic, day-to-day evolution of travel choices as a discrete time stochastic process, explicitly representing variability in flows and travel times/costs and their effect on (future) travel choices. Equilibrium in this setting refers to a fixed point condition on the joint probability distribution of network flows. The flexibility of this approach makes it extremely appealing, yet it leaves a practical dilemma. Should we discard the many years of research on understanding and applying traditional network equilibrium approaches (offering an albeit limited but well-controlled modelling environment), in favour of a new approach (the outputs of which are significantly more complex)? Can no use be made of the understanding of traditional equilibrium solution methods? This is a difficult decision, particularly since we would probably be most comfortable selecting conventional equilibrium for some policy tests, and the new approach for others, though this leaves a problem of an inconsistent evaluation framework. With these issues in mind, the present author recently proposed an intermediate modelling framework, termed a Generalised Stochastic User Equilibrium of order and denoted [15]. This is effectively based on equilibrating the moments of a natural joint probability distribution of network flows, the model having as active equilibrated variables the moments of order and below. A GSUE(1) model therefore equilibrates means only, and turns out to be an SUE model (regardless of the demand levels, i.e. this is not only a large sample result), whilst a GSUE(2) model equilibrates the flow mean and covariance matrix. This approach, which will form the basis of the remainder of the paper, will shortly be introduced in detail. However, it is useful first to describe the philosophy adopted in the context of random utility theory. In the SUE model (presuming its aim is to estimate mean traffic flows), the cost of each alternative (route) is essentially set to:
The cost at mean traffic flows is a deterministic quantity given by the costflow performance relationships, and the perceptual differences are randomly
40
TRANSPORTATION PLANNING
distributed (and, in realistic models such as probit, correlated between alternatives). It turns out that the structure of the choices made in the GSUE(2) model could be described as being equivalent to assuming:
where the uncertainty is in general a random quantity (between days and between drivers) and is due to the actual variance in traffic conditions. At this level, the objective of the paper can be viewed as a technique for fitting alternative error structures for a random utility model, with mean flows subsequently predicted by SUE based on this modified error structure. This description of the approach needs, however, to be clarified in two ways: 1 If the true variance in costs were and drivers’ predictions are assumed to be formed from a large number say) of experiences, then neglecting any correlations between experiences/alternatives, the variance in the “Uncertainty" is and so as this variance tends to zero. This does not, however, imply that (5) approaches (4), since unlike “Perceptual difference", the “Uncertainty" does not have a zero mean; the variability in traffic flows affects not only the variance in actual costs, but also mean actual costs. 2 From the argument in 1., determining the appropriate correction factor is non-trivial, since in order to determine mean costs at variable flows, the whole flow probability distribution is required. But this leads to a circular argument, since in order to determine the random utility error structure, the (equilibrium) flow distribution is required, but the whole point of specifying the error structure is to determine the equilibrium flows. The approach will therefore be to deduce conditions that must simultaneously be satisfied by the error structure and the equilibrium flow allocation. This is first considered, in section 4, in the case of a fixed (deterministic) demand, and is then generalised in section 5 to the case of stochastic demand.
4.
Equilibrium conditions: fixed demand
The first task is to define equilibrium in a more general setting in which there is random variation in the route and link flows, which in turn induces random variability in the actual travel costs. This is quite a complex issue, and is dealt with in two stages. Firstly, equilibrium conditions are presented on the joint probability distribution of network flows. Secondly, an approximation to these conditions, based on first and second order moments only, is deduced. This
Stochastic Network Equilibrium Under Stochastic Demand
41
latter approximation will be the defining conditions for our generalised model. In this section we assume that demand is fixed (i.e. inelastic and deterministic). For a further elaboration of the proofs and analysis of all the results in this section, the reader is referred to [15]. Let denote the column vector which has elements given by the (unknown) probabilities thus has dimension equal to the cardinality of and is simply a representation of the joint probability distribution of the absolute link flow vector variable . This distribution is related to the route flow probability distribution (a column vector of probabilities o f dimension by where is a matrix with elements
Suppose that as in the SUE definition (2)/(3), a function is given, which relates the probabilities of a randomly selected driver choosing each of the alternative routes at given route costs Then define partitions of this function and the route flow vector according to the different inter-zonal movements, such that:
Now suppose that the route costs where is a vector of link costs, so that conditionally on , for each inter-zonal movement independently, each ofthe drivers independently chooses between the available routes with probabilities Then the distribution of movement route flows conditional on random link costs Y, is given by (independently for
The following consistency (equilibrium) condition on the distribution then be established.
may
Theorem 1 (Asymptotic equilibrium condition). Suppose that drivers form estimates of actual costs from a random sample of the link costs from their previous travel experiences, where is given,
42
TRANSPORTATION PLANNING
and is a sample of independent, identically distributed, demand-feasible link flow vectors. The given cost-flow performance functions are assumed to be bounded for Suppose further that, at given route costs the population of drivers chooses independently between the available routes with probabilities Then asymptotically, as the link flow probability distribution satisfies the equilibrium condition:
where
is a vector of dimension
with elements the probabilities
where
denotes that has a given probability distribution where denotes the expectation operator with respect to the distribution of and where the conditional distribution of is given by (8) based on the partition (7). Theorem 1 essentially hinges on the fact that as the number of experiences tends to infinity, the variance in the mean of these i.i.d. experiences will tend to zero, and in the limit implies that the distribution of the mean of the experiences is focused on the true long run expectation. Hence the corresponding choice probabilities will be deterministic, and the unconditional distribution of can be approximated by the conditional distribution (10), which by hypothesis is formed from a combination of multinomials (8). The derivation of the condition above is very much along the lines of conventional analyses of traffic networks, in the sense that we seek a consistency condition that should reasonably be satisfied, without any specific reference as to how a network may arrive at such a state. For example, in the SUE model (1) defined earlier, the hypothesis is that is in equilibrium if the route proportions given by the behavioural choice model at costs are consistent with flows of In addition, by allowing the number of experiences to become very large in Theorem 1, we are effectively assuming a “well-informed" driver population, again something that is consistent with conventional analyses. Having presented the underlying equilibrium conditions, a more tractable approximation may then be deduced. Theorem 2 (Approximation to Equilibrium Conditions). Consider a network with twice-dijferentiable link cost-flow functions Then an approximation to the mean and covariance matrix of an equilibrium probability distribution (9) is given by an A-vector and A × A matrix satisfying the fixed point
Stochastic Network Equilibrium Under Stochastic Demand
43
conditions:
where
is an A-vector with elements
where is the A × A Hessian matrix of 1 , 2 , . . . , A), where the scalar product of any two is denoted by
evaluated at matrices X and Y
and where is a function whose result is an N × N block diagonal matrix, with blocks the matrices of dimension
where is partitioned as in (7). A pair satisfying (11) is termed a Generalised Stochastic User Equilibrium of order 2, and is written GSUE(2). The essential steps in the proof are firstly to deduce a second order Taylor series approximation to the link cost-flow functions, whereby (12) may be deduced as an approximation to the expected costs in (10). The effect is that on the right hand side of (9), only appears through its mean and covariance matrix, and so these are the only ‘active’ elements of to equilibrate. Hence, on the left hand side, we also deduce the link flow rate mean and covariance matrix, which is related to the absolute link and absolute route flow mean and covariance matrix. This latter mean is diag (note while the covariance matrix is block diagonal, with blocks this latter being an expression for the covariance matrix of a multinomial variable. The particular advantage of conditions (11) over condition (9) is in the development of solution algorithms for large realistic networks. In such cases, the enormous dimension of makes it unappealing to deal with directly, whereas (11) may be solved by an efficient heuristic method. A discussion of this heuristic method will be postponed to section 6, where it is extended to the case of stochastic demand.
44
5.
TRANSPORTATION PLANNING
Equilibrium conditions: stochastic demand
Having set up a model in which driver choices and flows may be stochastic, it is a natural extension to allow the inter-zonal demands to be stochastic: Theorem 3 (Stochastic Demand Equilibrium Conditions). Suppose that the hypotheses of Theorem 2 hold, except that now demand is assumed to be stochastic. Let the given W-vector denote the potential demand (number of potential travellers) on each of the inter-zonal movements, and suppose that on any given day, each such potential traveller decides independently to travel with given constant movement-specific probabilities in the W-vector which has elements Conditional on the choice to travel, a route is subsequently chosen according to probabilities Then, relative to (11), the modified equilibrium conditions on are:
where where blocks:
and are as previously defined, and is a function whose result is a block diagonal matrix, with
and where the mean demand rate
is related to
by
A pair satisfying (14) is termed a Stochastic Demand Generalised Stochastic User Equilibrium of order 2, and is written SDGSUE(2). Proof The conditions may be derived from Theorem 2, by introducing a dummy “no travel" route joining each inter-zonal movement. Under the assumptions of Theorem 3, the potential travellers on each movement are multinomially distributed between the non-dummy routes with probabilities Hence, by the application of Theorem 2, we obtain equilibrium conditions of:
where substitution (16).
Expression (14) is then obtained from (17) by the
45
Stochastic Network Equilibrium Under Stochastic Demand
One point that is worth noting about (14) is what happens as In that case, with all other variables held fixed, tends to the zero matrix. Then, from (12), and the first condition in (14) reduces to an SUE condition on Now as for a given mean trip demand rate of and travel probability then by (16) the absolute number of potential travellers That is to say, asymptotically (as all absolute trip demands approach infinity), a SDGSUE(2) mean flow vector is an SUE. This is consistent with the findings of Davis [4] in the context of stochastic process models. Of course, in real networks many interzonal demand levels will be rather small, and so the practical applicability of this result is limited.
6.
Solution algorithm
One of the main advantages of the SDGSUE(2) formulation (14) is that it allows the direct computation of moments of the equilibrium probability distribution, without having to refer to the underlying distribution. Examining (14), it is notable that the first condition has the appearance of an SUE condition (3), and this observation is the motivation for the proposed heuristic solution algorithm. In particular, for given the first condition in (14) is indeed an SUE condition on based on modified link cost functions This leads to the obvious strategy of alternately solving an SUE sub-problem in for given and then updating according to the second SDGSUE(2) condition for the equilibrium route proportions output by the SUE sub-problem. The SUE sub-problem is solved by the method of successive averages (MSA), as described in many standard texts (e.g. [13]). Formally, the algorithm is as follows: Initialisation Set matrix.
to the A-vector of zeroes, and
to the A × A zero
Then, for Auxiliary solution Solve an SUE sub-problem in
conditional on
denoting the solution by and the SUE route proportions by Obtain the corresponding estimate of from:
The pair
is the iteration
auxiliary solution.
TRANSPORTATION PLANNING
46
Update Estimates Update the SDGSUE(2) estimates according to:
The algorithm is therefore based on two (an ‘inner’ and ‘outer’) MSA updating schemes. The inner iterations are used to solve an SUE sub-problem, conditional on the current estimates of the link flow covariance matrix. The outer iterations use the auxiliary solution from the SUE sub-problem to form an updated estimate of a satisfying the SDGSUE(2) conditions; at any given outer iteration, this estimate is the average of all auxiliary solutions computed to date. By initialising the covariance matrix to zero, the first outer iteration computes a conventional SUE solution (i.e. based on link cost functions This seems a sensible starting point given the asymptotic correspondence, noted in section 5, between SDGSUE(2) mean flows and SUE. In the ‘separable’ cost function case, if each is twice continuously differentiable, is strictly increasing and has a non-decreasing second derivative, then conditional on the modified link cost functions are continuous and monotonically increasing in This, together with some technical conditions on the joint probability distribution of perceptual errors, guarantees the existence of a unique solution to each SUE sub-problem, and the convergence of the MSA algorithm to this solution ([3]; [13]). However, the convergence of the outer iterations is not guaranteed, but if the outer iterations do converge, the resulting estimate will, by construction, be a SDGSUE(2) solution.
7. Numerical tests 7.1. Test networks The algorithm presented in section 6 was implemented in the C language on a personal computer, in which a user-specified number of inner and outer iterations are performed. Previous experience with the algorithm in the deterministic demand case had found it to be an efficient and reliable procedure, provided that a relatively large number of inner iterations were permitted. These are the iterations used to solve each SUE sub-problem. In tests on the network considered below, thirty outer and one hundred inner iterations was found to be a reasonable compromise between computation speed and reproducibility of the results for different random number seeds ([15]). A probit-based choice probability model was used in the tests reported here, implicitly defined by assuming that the link cost perceptual errors were independent between links, the error for each link following a Normal distribution with a mean of zero and a standard deviation where is
Stochastic Network Equilibrium Under Stochastic Demand
47
a link-independent dispersion parameter and is the free-flow travel cost on link A value of was assumed throughout. Actual travel time was assumed to be synonymous with actual travel cost. Separable, BPR-type link cost-flow performance functions were used in all cases, of the form:
where and are user-specified constants, and vehicles/hour is the capacity of link All cases were run for a short time period duration of hours, in order to emphasise the differences (relative to, say, convergence error). A choice of a larger value for would generally cause the differences between SUE and SDGSUE(2) flow rates reported below to decrease. The test network considered represents the Weetwood area of the city of Leeds, a commuting corridor consisting of some 70 zones, 440 links and 174 nodes. The inter-zonal demand matrix represents morning peak period trips, consisting of a total of some 39692 passenger car equivalents per hour. The link-specific BPR powers range from 1.6 to 12.2.
7.2.
Test results
Running the algorithm for 100 inner and 30 outer iterations on the test network required around 45 minutes of run-time on a 120MHz PC. Convergence, as monitored by various flow similarity measures between successive iterations, was achieved with little difficulty in all the tests performed. By construction, any such converged point is a SDGSUE(2) solution, establishing empirically that such solutions do indeed exist. The main results of the tests are summarised in Table 3.1. The definitions of the column headings are as follows: Probability of a randomly selected driver choosing to travel on any given day. Mean total travel time: Mean total travel time across the network
vehicle-hours/hour).
Adjusted SUE: An SUE model in which the final travel times are adjusted to approximate the effect of variability (see below). AAD(flows): Average absolute difference, on a link-by-link basis, between SDGSUE(2) mean flows and SUE flows. AAD(times): As AAD(flows), except for mean travel times. S: A measure of flow variation, simply the unweighted sum across all links of the SDGSUE(2) link flow standard deviations.
48
TRANSPORTATION PLANNING
The comparisons in Table 3.1 are made for different values of the travel probability (a common value across all inter-zonal movements), but with the matrix adjusted according to equation (16) so as to maintain a constant mean demand matrix across all tests. In this way, the smaller the value of the higher is the demand variability. The adjusted SUE model is a modified form of SUE in which the flow means and covariance matrix are estimated. The flow means are precisely SUE flows. The covariance matrix is computed by assuming that the SUE route proportions are multinomial probabilities:
where
is given by (15). The adjusted mean travel times are then given by based on (12). In fact, this is equivalent to performing a single iteration of the SDGSUE(2) solution algorithm, i.e. with no iterative feedback of the new expected costs. It is presented for comparative purposes, and is not intended to be a suggested model in its own right. For comparison, the total travel time under a conventional SUE model was estimated as 648.0. The SDGSUE(2) mean total travel time is therefore between 5% and 7% higher than the SUE prediction, the discrepancy increasing with increasing variability in demand. This inflationary effect on mean total travel time of allowing for flow variability is what one would expect under convex link performance relationships, as discussed in section 3. However, it should be clarified that the anticipated inflationary effect typically described in the literature (e.g. [2]) is with respect to a fixed flow probability distribution, whereas in the SDGSUE(2) model the flow probability distribution must effectively equilibrate. In contrast, a comparison of the results for the SUE and Adjusted SUE models is effectively a comparison with respect to a fixed flow probability distribution,
ACKNOWLEDGMENTS
49
and it is notable that the inflationary effect is considerably greater than that predicted by the SDGSUE(2) model. That is to say, in the SDGSUE(2) model drivers are able to compensate for some of the inflationary effect on mean travel times by changing to less “risky" routes. This seems reasonable, since it would be precisely these mean travel times that drivers would be expected to perceive. The Adjusted SUE model, on the other hand, will tend to over-estimate the effect of variability on mean conditions. This is considered to be an empirical justification for the SDGSUE(2) approach, relative to the Adjusted SUE model and, indeed, other approaches based on post hoc modifications of a conventional equilibrium model (see [16] for a review of these latter approaches). Turning attention, then, to a comparison of the SUE and SDGSUE(2) link flow and travel time predictions, table 3.1 indicates hardly any change in the AAD between the mean link flows of the two models as the demand variability is increased. In absolute terms, on a link-by-link basis, the differences in mean flows range from around -95 to +95 vehicles/hour, this range hardly changing with The main effect of is on the variance in link flows, as can be seen from the increase in with increasing variability. This in turn has an effect on the SDGSUE(2) mean travel times, with the discrepancy with SUE travel times (as measured by the AAD) increasing with an increase in demand variability.
8.
Conclusion
It has been demonstrated that stochastic, day-to-day variation in route choice and trip demand can be formulated within the context of an extended network equilibrium framework. The resulting model, which equilibrates link flow means and covariance matrix, is in this way a natural extension of conventional modelling techniques. The heuristic solution algorithm proposed has been shown to be computationally feasible for large realistic networks. Further research in this area can focus on a number of directions. Firstly, more elaborate models may be developed, taking account of factors such as finite driver learning processes, in which the multinomial route flow assumption breaks down, as well as within-day variations in traffic flows and travel choices. Secondly, more numerical simulations should be made; a particularly interesting area is the comparison with stochastic process models. Thirdly, attempts should be made to establish theoretical properties of these new models, such as conditions to guarantee existence and uniqueness of equilibrium and the convergence of solution algorithms. Fourthly, the practical use of higher order moments, such as variances and covariances, may be studied in the context of scheme evaluation; the present paper has focused on mean outputs, but how would knowledge of variances affect decision-making? Fifthly, applications of these techniques should be developed, which seem to have particular relevance to policies that respond to variability, such as driver information systems.
50
TRANSPORTATION PLANNING
Acknowledgments This research was carried out under the support of an Advanced Fellowship from the UK Engineering and Physical Sciences Research Council.
References [1] Cantarella G.E. and Cascetta E. (1995). Dynamic Processes and Equilibrium in Transportation Networks: Towards a Unifying Theory. Transpn Sci 29(4), 305-329. [2] Cascetta E. (1989). A stochastic process approach to the analysis of temporal dynamics in transportation networks. Transpn Res B 23B(1), 1-17. [3] Daganzo C.F. (1982). Unconstrained Extremal Formulation of Some Transportation Equilibrium Problems. Transpn Sci 16(3), 332-360. [4] Davis G.A. and Nihan N.L. (1993). Large population approximations of a general stochastic traffic assignment model. Operations Research 41(1), 169-178. [5] Hanson S. and Huff J. (1988). Repetition and day-to-day variability in individual travel patterns. In: Behavioural Modelling in Geography and Planning, ed. by R.C.Golledge and H.Timmermans, Croom Helm, Kent, U.K. [6] Hazelton M. (1998). Some remarks on stochastic user equilibrium. Transpn Res 32B(2), 101-108. [7] Hazelton M. and Watling D.P. (1999). Approximation methods for overdispersion and learning processes in markov models of route choice. In preparation. [8] Mohammadi R. (1997). Journey time variability in the London area. Traffic Engineering and Control 38(5), 250-257. [9] Montgomery F.O. and May A.D. (1987). Factors affecting travel times on urban radial routes. Traffic Engineering and Control, September 1987, 452-458. [10] Ortuzar J. and Willumsen L.G. (1994). Modelling Transport. Second edition. John Wiley and Sons, Chichester, U.K. [11] Ran B. and Boyce D.E. (1993). Dynamic Urban Transportation Network Models. Springer-Verlag, Berlin. [12] Rathi A.K. (1992). The use of common random numbers to reduce the variance in network simulation of traffic. Transpn Res 26B, 357-363. [13] Sheffi Y. (1985). Urban transportation networks. Prentice-Hall, New Jersey.
REFERENCES
51
[14] To D.K.B. (1990). What happens when it rains. M.Sc. thesis, Institute for Transport Studies, University of Leeds, U.K. [15] Watling D.P. (1999a). A Second Order Stochastic Network Equilibrium Model. First revision, submitted to Transpn Sci. [16] Watling D.P. (1999b). Traffic Assignment with Stochastic Flows and the Estimation of Travel Time Reliability. Paper presented at Second Workshop on Network Reliability, July 27th 1999, Newcastle, U.K. [17] Willumsen L. and Hounsell N.B. (1994). Simple models of highway reliability: supply effects. Paper presented at Seventh Int Conf on Travel Behaviour Research, Santiago, Chile, June 1994.
Chapter 4 STOCHASTIC ASSIGNMENT WITH GAMMIT PATH CHOICE MODELS Giulio Erberto Cantarella
[email protected] Dept of Comp. Sci., Math., Electr., Transport.- Univ. of Reggio Calabria - Italy tel: +39-0965-875227, fax: +39-0965-875297
Mario Giuseppe Binetti
[email protected] Dept. of Highways and Transportation - Politecnico di Bari - Italy tel: +39-080-5460485, fax: +39-080-5460329
Abstract
Traffic assignment models simulate transportation systems, where flows resulting from user choice behaviour are affected by transportation costs, and costs may be affected by flows due to congestion. Several path choice behaviour models can be specified through random utility theory. Probabilistic path choice models, where perceived path costs are modelled as random variables, lead to stochastic assignment. In this paper, reasonable modelling requirements are proposed to assure a realistic simulation ofpath choice behaviour through probabilistic choice models. Then, additive Gammit path choice models based on Gamma distribution are introduced and deeply analysed. These models satisfy all the proposed modelling requirements, and can be effectively embedded within existing models and algorithms for stochastic assignment.
Keywords:
Stochastic assignment, gammit choice model, gath choice, stochastic user equilibrium, stochastic network loading.
1.
Introduction
Traffic assignment simulate transportation systems, where flows resulting from user choice behaviour are affected by transportation costs, and costs may be affected by flows due to congestion. Three sub-models make up an assignment model: 53
M. Patriksson and M. Labbé (eds.), Transportation Planning, 53–67. © 2002 Kluwer Academic Publishers. Printed in the Netherlands.
54
TRANSPORTATION PLANNING
supply model which simulates (whether and) how user behaviour affects network performances, such as travel times, etc; demand model which simulates how network performances affects user behaviour; supply-demand interaction model which simulates their interaction. Transportation supply is usually simulated through a congested network model. In this case, demand-supply interaction is mostly simulated through equilibrium models. These models search for mutually consistent flows and costs, defining a state in which no user can reduce the (perceived) cost of his/her choice by unilaterally changing it (reviews and references in [13]; [12]; [6]). Recently, dynamic process models have been proposed, which generalise the equilibrium approach (see [5] for a general framework and a review). If the user behaviour do not affect network performances, transportation supply is simulated through a simpler non-congested network model, leading to network loading models, which also play a relevant role in the formulation and solution of assignment models for congested networks. Generally,the user choice behaviour, simulated by the demand model, refers to several choice dimensions, such as destination, mode, path, etc. In this paper, for simplicity sake, only path choice behaviour will be explicitly dealt with, assuming that other choice dimensions, like mode and destination, are not affected by (congested) network performances. Several path choice behaviour models can be specified through random utility theory. Probabilistic path choice models, where perceived path costs are modelled as random variables lead to stochastic user equilibrium (SUE) effectively formulated through fixed-point models ([8]; [4]). This paper explicitly deal with (multi-user) mono-modal equilibrium assignment with rigid demand (briefly reviewed in section 2 for unfamiliar readers). Extensions to multimodal assignment, and/or elastic demand, as well as pre-trip/en-route path choice behaviour (relevant for urban transit systems) are quite straightforward as discussed in [4]. Cantarella and Cascetta [5] discuss extensions to dynamic process assignment. This paper, after presenting notations and the necessary background in section 2, first provides a general framework to path choice behaviour modelling (subsections 3.1-3), embedding it within stochastic assignment theory. In particular, reasonable modelling requirements are proposed to assure a realistic simulation of path choice behaviour through probabilistic choice models, as well as link-based and additive path choice models. Then, Gammit path choice models, based on Gamma distribution, are analysed in subsection 3.4; the use of Gamma distribution has been suggested by other authors ([13]; [2]; [11]), but resulting choice models have never been analysed. Whilst additive Gammit
55
Stochastic assignment with gammit path choice models
model fulfils all the modelling requirements, this is never the case for other existing models. Gammit choice models can be embedded within existing models and algorithms for stochastic assignment and applied to real-size networks, as shown in section 4.
2.
Review of stochastic assignment
A transportation system is generally analysed by concentrating origins and destinations of journeys into centroids, and grouping users into user classes. Each user class, denoted by a single index such as is a set of users travelling between an origin-destination pair with a common set of relevant paths and common behavioural parameters. Throughout this paper, it is assumed that at least one path connects each O-D pair, that is each set is non-empty. Moreover, only elementary (say loop-free) paths are considered (for further comments on this issue see section 3.1), thus only a finite number of paths exists for each user class, that is each set is finite. It seems worth noting that a non-elementary path surely contain an elementary path, whilst an elementary path may not contain another elementary path.
2.1.
Basic notations and definitions
Transportation supply is usually simulated through a congested network model, which expresses how user behaviour affects network performances. Let be the link-path incidence matrix for user class with entries link a belongs to path and otherwise; be the path flow vector for user class
if
with entries
be the link flow vector, with entries be the link cost vector, with non negative entries by travel time); be the path cost vector for user class with entries negative,
(for example given
assumed non
The path flow propagation model defines the relation between path and link flows:
56
TRANSPORTATION PLANNING
Moreover, link flows depend on link costs through link cost functions, which can be specified through traffic engineering models:
The path cost model defines the relation between link and path costs:
The transportation demand model simulates how network performances affects user behaviour. As already stated in section 1, for simplicity’s sake, only path choice behaviour is explicitly dealt with. Let be the demand flow for users belonging to class b e the path choice probability vector class with entries
and
for user
The path choice model simulates user path choice behaviour through a relation between path flows and costs:
The demand flow conservation equation assures that the sum of path flows is equal to the demand flow for each user class:
2.2.
Path choice models from random utility theory
Most path choice models are specified through random utility theory (introduced by Domencich and McFadden [9]; for a comprehensive review see [1]). It is assumed that each user within class • examines all paths in the (non empty and finite) set •
associates to each path within set a perceived utility modelled through a random variable, due to several causes, such as aggregation errors, fluctuations of attributes, missing attributes, dispersion of user behaviour, user perception errors, etc;
• chooses the maximum utility path. According to the above assumptions the probability, that a user of class chooses path within set is given by the probability that path is the maximum perceived utility path. The perceived utility (p.u.), of path for a user of class can be expressed by the sum of its expected value
57
Stochastic assignment with gammit path choice models
the systematic utility (s.u.), plus a random residual (r.r.) Thus, each random residual has zero mean, and variance equal to the p.u. variance The above assumption yield:
Hence, the path choice probabilities depend on the expected values of perceived utilities, and of the distribution parameters as well. By using vectorial notations, let be the path perceived utility vector for user class
with entries
be the path systematic utility vector for user class
with entries
be the path random residual vector for user class
with entries
be the (symmetric positive semi-definite) path covariance matrix for user class relative to p.u. or r.r. vectors. Assuming that costs are measured in the same units of utility, systematic utility is usually assumed equal to the opposite of cost (plus other attributes not explicitly introduced for simplifying notations):
The relationship between the path choice probability vector and the vector of systematic utility is called the path choice map:
The path choice map, combined with the utilityfunction between systematic utility and cost allows specifying the path choice model (2.4). In particular, probabilistic path choice models are obtained when path covariance matrix is non singular, In this case any path may be used, and the resulting relation between path costs and choice probabilities is a function (otherwise it may be a point-to-set map), which also depends on parameters of p.u. or r.r. distribution. Probabilistic path choice models will be discussed in details in the next section 3.
2.3.
Models and algorithms for stochastic assignment
The application of probabilistic choice models leads to stochastic assignment. In particular, if link costs do not depend on link flows (non congested networks) the resulting stochastic assignment model can be described by
58
TRANSPORTATION PLANNING
the stochastic network loading (SNL) function obtained combining equations (2.1),(2.3),(2.4)and(2.5):
where is the feasible link flow set, non empty (if at least one path is available to each user), compact (since bounded and closed), and convex. If link costs depend on link flows (congested networks) stochastic assignment is usually based on the equilibrium approach, searching for consistency between flows and costs. Stochastic user equilibrium (SUE) can be effectively analysed through fixed-point models obtained combining the SNL function (2.8) with the link cost flow functions (2.2), such as the model proposed by Daganzo [8]:
Other fixed-point models are described in [4]. Existence of stochastic user equilibrium flow or cost pattern can be stated through the Brouwer theorem, mainly requiring that SNL function and link cost functions are continuous, since set is non-empty, compact and convex, and condition is always assured. Uniqueness of SUE flow or cost pattern mainly requires that the SNL function is non-increasing (or quasi strictly decreasing) monotone and link cost functions are strictly increasing (non-decreasing) monotone. If existence and uniqueness conditions hold, stochastic user equilibrium link flow pattern can be found through two algorithms which are simple, since their application only requires the computation of SNL and cost functions, and feasible, since they produce a sequence of feasible link flow vectors. The Flowaveraging algorithm (MSA-FA), whose convergence is assured if the Jacobian of link cost functions is symmetric, is described by the recursive equations below ([8]; and [4]):
The Cost-averaging algorithm (MSA-CA), whose convergence is assured if the Jacobian of SNL functions is symmetric, is described by the recursive equations
Stochastic assignment with gammit path choice models
59
below, cf. [4]:
The MSA-CA algorithm can be proved converging also if Jacobian of link cost functions is not symmetric, but its convergence is generally slower than the MSA-FA algorithm. Thus, two-stage algorithms should be preferred, where the starting solution, is obtained through MSA-FA scheme and final steps are performed through MSA-CA scheme. Multi-stages algorithms are also useful to prevent step becoming too small.
3.
Probabilistic path choice models
Different probabilistic path choice models can be specified according to different assumptions on the joint probability density function of perceived utilities or random residuals, as discussed in the rest of this section. In particular, requirements introduced in the following subsection are useful to analyse different specifications of the path choice models (some of them are also in [2]; [11]).
3.1.
Requirements for probabilistic path choice models
Mathematical requirements, presented below with reference to path choice behaviour, are useful to effectively model any choice behaviour. In particular, the path choice model (2.4), is specified by a function if perceived utility values and random residuals, as said before, are assumed distributed as continuous random variables with non singular covariance matrix, Continuity of the path choice function, assures that small changes of path costs induce small changes of choice probabilities. If it is also continuously differentiable it has a continuous Jacobian, This feature, assured by commonly used joint probability density functions, guarantees continuity of the resulting SNL function, thus it is useful to state existence of stochastic user equilibrium. Monotonicity of the path choice function, assures that an increase of the cost of a path induces a decrease of the corresponding choice probability. More generally, the path choice function, should be non-increasing monotone with respect to path costs. This feature guarantees monotonicity of the resulting SNL function, thus it is useful to state uniqueness of solutions of stochastic user equilibrium. Independence from linear transformations of utility assures that any change of the scale of the utility does not affect the model (as guaranteed by Normal or Gamma distribution).
60
TRANSPORTATION PLANNING
Beside the above presented mathematical requirements, modelling requirements, presented below, are useful to effectively simulate path choice behaviour. Similarity of perception of partially overlapping paths rules out counterintuitive results. Indeed two partially overlapping paths are likely not perceived as two totally separated paths. Introducing a positive co-variance between any two overlapping paths can simulate similarity. Independence from link segmentation (within the network model) assures that if a link is further divided into sub-links redefining link costs so that path costs are not affected, path p.u. or r.r. distribution is not affected too, and thus choice probabilities. This requirement makes reference to features of the distribution of the sum of random variables. Further considerations are reported in subsection 3.3. Negativity of perceived utility assures that no user perceives a positive utility to travel along any path. This feature can be assured by assuming lower bounded random distributions (for instance Log-Normal, or Gamma). According to this feature a non-elementary path is always a worse choice than the elementary path within it, thus supporting the assumption of considering elementary paths only (section 2). On the other hand, if this feature is not presented, a nonelementary path may be a better choice than the elementary path within it. Hence, non-elementary paths should be included within the path choice set (which is non longer finite), possibly leading to unrealistic situations (a part from some algorithmic drawbacks).
3.2.
Path versus link formulations of probabilistic path choice models
In path or direct formulations of probabilistic path choice models the distribution of path perceived utility or random residuals, introduced in subsection 2.2, is explicitly specified. The analysis of path choice behaviour should be carried out at the path level, but path p.u. or r.r. distribution can be specified by introducing link perceived utilities and specifying their distribution, using link or indirect formulations. Let be the link perceived utility vector, with entries equal to the opposite of link cost vector,
and expected value
be the link r.r. vector, with entries with null expected value, and variance equal to the variance of link perceived utility, be the (symmetric positive semi-definite) link (p.u. or r.r.) covariance matrix. Path perceived utilities and random residuals, introduced in section 2., are assumed given by the sum of the corresponding link perceived utilities and
Stochastic assignment with gammit path choice models
61
random residuals:
Hence, link p.u. or r.r. distribution specifies path perceived utility or random residuals distribution with path covariance matrix given by:
According to equation (3.3), even if link p.u.’s and r.r.’s are independently distributed, that is covariance matrix is diagonal, the perceived utilities, and random residuals, of any two overlapping paths have a positive covariance, given by the sum of variance of the perceived utilities, or random residuals, of common links. Thus, through link formulated choice models similarity of perception of paths partially overlapping can be easily simulated. The independence from link segmentation mainly requires the use of reproductive random variables. For instance, the sum of several independently distributed Normal random variables is still a Normal random variable, with mean given by the sum of the means and variance by the sum of the variances. This feature is also shown by independently distributed Gamma random variables with the same variance to mean ratio. In both case if links in a path are further segmented, provided that the mean path cost and the variance are not affected, the resulting path perceived utility distribution is not affected, and then the choice probabilities. Generally, the SNL function with any link-formulated choice model can be easily computed, if link perceived utilities are assumed independently distributed, through MonteCarlo techniques (introduced by Burrell [3]; see also [13]). In this case the result is an unbiased estimate of obtained by averaging several shortest path loading corresponding to different pseudo-realisations of with If all elementary paths are considered, explicit path enumeration can be avoided by using anyone of the many shortest path algorithms. (It is worth noting that effective shortest path algorithms require that link costs are non-negative, paths containing negative cost loops.)
3.3.
Additive probabilistic path choice models
A particular class of choice models are additive models, which are (continuous and continuous differentiable) probabilistic choice models where the p.u. or r.r. distribution does not depend on the path costs (neither set ). In other worlds the parameters of p.u. or r.r. distribution, such covariance matrix, do not vary with the path costs These models can be easily specified assuming, for instance, that parameters of p.u. or r.r. distribution do not depend on costs at all or depend on zero-flow costs. Choice probabilities resulting from additive
62
TRANSPORTATION PLANNING
choice models only depend on differences between path costs, rather than their absolute values. Some empirical results seem indicating that these assumptions on user choice behaviour are quite realistic (see [2]). Additive probabilistic path choice models, are specified by non increasing monotone functions with a symmetric (negative semi-definite) Jacobian (as shown by Cantarella [4], starting from results in [7]). Strictly positive additive models are specified by quasi strictly monotone functions ( [4]). Thus, these models lead to continuous and monotone SNL functions (with symmetric Jacobian) features useful to guarantee existence and uniqueness of stochastic user equilibrium (and convergence of MSA algorithm). Additive path-formulated choice models always assures independence from link segmentation, whilst additive link-formulated choice models have this feature only for reproductive random variables (for instance Normal or Gamma variables). From all results presented above, additive choice models seem appealing both from theoretical and practical points-of-view. However, additivity is only a sufficient condition to assure relevant features, whilst characteristics of non-additive choice models are still an open issue.
3.4.
The Gammit choice model
In this subsection, choice models based on Gamma distribution are introduced and deeply investigated. Nielsen [11], starting from an earlier suggestion by Sheffi [13], also considered Gamma distribution without analysing it in details (see also [2]). The Gammit model is obtained assuming that perceived disutilities are jointly distributed as a non negative "shifted" MultiVariate Gamma, with mean equal to the path costs and path covariance matrix Gammit path choice probabilities cannot be expressed in a closed form, and their computation requires MonteCarlo techniques. The Gammit model allows taking into account similar perception of paths partially overlapping through covariance between paths. Path-formulations of Gammit model may be undetermined, since the Covariance matrix alone does not completely define the joint probability density function of a MultiVariate Gamma random variable. On the other hand, the link formulation described below allows overcoming this drawback, and at the same time assures independence of link segmentation and rule out positive perceived utilities for any paths. Let be the (strictly positive) reference cost on link a, assumed not greater than the link cost, say The perceived disutility of link a, is assumed distributed (independently of the perceived disutility of any other link) as a non negative shifted Gamma variable with mean given by the link cost, variance by proportional to (strictly positive) reference
Stochastic assignment with gammit path choice models
63
link costs and shifting factor given by the difference between link cost and reference cost,
In other words, the link perceived disutility is the sum of a non-negative deterministic term possibly depending on link flows, and a non-negative stochastic term independent from link flows. The assumption on link reference costs yields that the corresponding reference cost on path is strictly positive and not greater than the path cost, Thus, the perceived disutility on path k is marginally distributed as a non negative shifted Gamma variable:
Path perceived disutility vector is distributed as a non negative shifted Multi Variate Gamma, with covariance matrix since the link covariance matrix is given by In this case independence from link segmentation is assured. In fact, let be the reference path cost vector, with (strictly positive) entries the variance for path is given by and the covariance between paths and is given by where is the costs of links shared by paths and The described specification leads to an additive choice model if the variance parameter and reference link costs do not vary with link costs (for instance are zero-flow costs), and the resulting additive Gammit path choice model fulfils all the requirements proposed in subsection 3.1. Aggregate calibration parameter is briefly addressed in section 4, but a detailed analysis of this issue is out of the scope of this paper.
4.
Numerical examples
The main aim of this section is showing that stochastic assignment with Gammit path choice model can be applied to a real size network, thus results of the application as such will only briefly discussed. In particular, the O-D matrix, obtained through calibration of demand models and/or estimation from counts, may be worth of further analysis, as well as the parameters within link cost functions. The graph simulates road facilities of the city of Salerno (Italy), with roughly 200,000 inhabitants, it contains 685 nodes, including 89 centroids, and 1147 links. Traffic counts are available for 65 links. The number of relevant O-D pairs is, in the morning peak hour, 3844 out of 7921 (89x89); whilst the total demand flow is 23,825 vehicles/h. Path choice behaviour has been modelled through a link-formulated additive Gammit model with zeroflow costs as reference costs. Separable link cost functions have been used.
64
TRANSPORTATION PLANNING
Stochastic assignment with gammit path choice models
65
The SNL function has been computed through MonteCarlo techniques, with 50 pseudo-random realisations of link random residuals, generated through analytical approximations, using the same draws for all the O-D pairs. Stochastic user equilibrium has been solved through the MSA-FA algorithm, with convergence error 0.10. The total number of shortest-path loading steps can be reduced through two-stage algorithms, if during the first stage the SNL is computed with only one pseudo-realisation of costs. Figure 4.1 shows the (relative absolute) maximum and the (relative absolute) average difference between computed and observed link flows against variance parameter Whilst the average difference seems only slightly affected by the value of this parameter, the maximum difference gets its minimum for This quite strange result may depend on O-D matrix estimate (and possibly the link cost functions calibration). The joint calibration of the variance parameter together with the update of O-D matrix will be addressed in future work.
Figure 4.2 shows a detailed comparison between observed and computed link flows, relative to the best fit variance parameter. Generally, observed link flows are well reproduced. Figure 4.3 shows a comparison between Gammit and Probit-based assignment. It can be easily recognised that the two models provide close values.
66
TRANSPORTATION PLANNING
different from the well-established Probit model. Anyhow, it is worth noting that the use of Probit model requires some care to avoid negative perceived costs, which may causes troubles to standard shortest path algorithms. Some issues seem worth of further research work. First of all the efficiency of stochastic network loading algorithms based on the proposed choice models strongly relies on draws from a Gamma random variable. Thus, more efficient algorithms not based on Monte Carlo methods could be looked for (following an approach similar to the numerical approximation proposed by Maher and Hughes [10] for Probit-based assignment). Furthermore, the calibration of the variance parameter, possibly jointly with the update of the O-D matrix, needs to be addressed. More generally, features of non-additive path choice models, such as Gammit (or Probit) models with flow dependent reference costs, are still an open issue.
Acknowledgments Authors wish to thank an anonymous referee and the editor who rose several relevant issues helpful to improve the paper.
References
REFERENCES
67
[1] Ben Akiva, M. and Lerman, S. R. (1987). Discrete Choice Analysis. MIT Press, Cambridge MA. [2] Bovy, P. H. L. and Stern, E. (1990). Route Choice: Wayfinding In Transport Networks. Kluwer Acad. Pub, Dordrecht, The Netherlands. [3]
Burrell, J. E. (1968). Multiple route assignment and its application to capacity restraint. In Leutzbach, W. and Baron, P., editors, Proceedings of 4th International Symposium on the Theory of Road Traffic Flow. Karlsruhe, Germany. [4] Cantarella, G. E. (1997). A General Fixed-Point Approach to MultiModde Multi-User Equilibrium Assignment with Elastic Demand. Transportation Science, 31:107–128. [5]
Cantarella, G. E. and Cascetta, E. (1995). Dynamic Processes and Equilibrium in Transportation Networks: Towards a Unifying Theory. Transportation Science, 9:305–329.
[6]
Cascetta, E. (1998). Teoria trasporto. UTET, Torino, Italy.
[7]
Daganzo, C. F. (1979). Multinomial Probit: The Theory and Its Application to Demand Forecasting. Academic Press, New York, NY.
[8]
Daganzo, C. F. (1983). Stochastic Network Equilibrium with Multiple Vehicle Types and Asymmetric, Indefinite Link Cost Jacobians. Transportation Science, 17:282–300.
metodi dell’ingegneria dei sistemi di
[9]
Domencich, T. A. and McFadden, D. (1975). Urban Travel Demand: Behavioral Analysis. North Holland, Amsterdam. [10] Maher, M. J. and Hughes, P. C. (1997). A Probit-Based Stochastic User Equilibrium Assignment Model. Transportation Research -B, 31B:341– 355. [11] Nielsen, O. A. (1997). On the distributions of the stochastic components in SUE traffic assignment models. In Proceedings of 25th European Transport Forum Annual Meeting,Seminar F, pages 77–93. [12] Patriksson, M. (1994). The Traffic Assignment Problem: Model and Methods. VSP, Utrecht, The Netherlands. [13] Sheffi, Y. (1985). Urban Transportation Networks. Prentice Hall, Englewood Cliffs, NJ.
Chapter 5 ESTIMATION OF TRAVEL TIME RELIABILITY USING STOCHASTIC USER EQUILIBRIUM ASSIGNMENT SENSITIVITY Chris Cassir
[email protected]
Michael G.H. Bell Transport Operation Research Group University of Newcastle-upon-Tyne Newcastle, UK
[email protected]
Abstract
1.
This paper presents a methodology for evaluating the reliability of transportation networks, which could be used to support the design of networks that are robust to everyday disturbances, in the sense that an acceptable level of network performance will normally be maintained. While tools already exist to determine the expected benefits of travel demand management or new infrastructure, tools have yet to be developed which take into account unlikely disbenefits arising from disturbances (like gridlock, to take a dramatic example). This paper focuses on the performance reliability of transportation networks in the face of normal variations .It is proposed to use a logit Stochastic User Equilibrium assignment model for obtaining reliability measures related to travel times. It is shown that logit SUE sensitivity expressions can be computed and applied in order to estimate travel time distributions. Computational results are also discussed.
Introduction
The efficient functioning of any society depends critically on networks of various kinds, such as water, electricity, gas, sewage, communication and of course transportation. The importance of the transportation network is perhaps best appreciated when it is severely disrupted, for example by an earthquake. 69
M. Patriksson and M. Labbé (eds.), Transportation Planning, 69–84. © 2002 Kluwer Academic Publishers. Printed in the Netherlands.
70
TRANSPORTATION PLANNING
The potential sources of disruption to transportation networks are numerous, ranging at one extreme from natural or man-made disasters (like earthquakes, floods, landslides, terrorist attacks, mining subsidence, bridge or tunnel collapses, and major accidents), which tend to occur rather infrequently, to at the other extreme events (like congestion, road maintenance, badly parked vehicles, and minor collisions), which occur on a daily basis. The scale, impact, frequency and predictability of such events will of course vary enormously. While little can be done about their scale, frequency or predictability, particularly where natural disasters are concerned, it should be possible to design transportation networks so as to minimise the disruption such events can cause. While many tools exist for studying the impact of new transport infrastructure or travel demand management measures on traffic flows (for example, the widely-used CONTRAM and SATURN programs), there are no tools for assessing the impact of such measures on the reliability of transportation networks. As an example, the reallocation of road space from private to public transport through the creation of a bus lane will on average provide benefits for public transport which may be assessed using existing tools. However, the bus lane may also increase the risk of queues of cars blocking upstream junctions (referred to as blocking back), which may exceptionally cause severe disruption to public transport services. To make a good judgement, the decision-maker should set unlikely disbenefits against likely benefits in a way that duly reflects priorities and risk adversity. Network reliability has two dimensions. The first relates to the connectivity reliability of a network. When links fail in unfavourable configurations it may no longer be possible to reach a given destination from a given origin, in which case the network becomes disconnected. However, even a connected network may fail to provide an adequate level of service. For example, random events may for a given network cause unacceptable variation in origin-to-destination travel times, making it difficult for travellers to arrive at their destinations on schedule. The second dimension of reliability is therefore the performance reliability of a network. Previous work on network reliability (Du and Nicholson, 1993; Iida and Wakayabashi, 1989) has focused principally on connectivity in degradable transportation networks, and the field of performance reliability in normal conditions appears to be under-researched. Assuming OD flows are normally distributed with known parameters, Asakura and Kashiwadani (1991) solved a static User Equilibrium (UE) assignment problem several times, with a demand sampled from these normal distributions, in order to estimate OD travel time distributions, from which the probability of reaching one’s destination within some acceptable time can be estimated, thereby providing some measures of network performance reliability.
Estimation of travel time reliability
71
The study in this paper attempts to achieve the same latter objective, namely estimating some travel time distributions in normal conditions, but it proposes to use sensitivity analysis of a logit Stochastic User Equilibrium (SUE) assignment model, instead of simulation. This approach would have the potential advantage of delivering reproducible results in reasonable computational time. The principles of the method are based on approximating linearly the relationship between equilibrium OD or route travel times and exogenous factors such as OD trips or link capacities, which in normal conditions are subject to fluctuations. The factors in this linear approximation can be obtained by deriving sensitivity expressions for the equilibrium assignment model. Tobin and Friesz (1988) obtained expressions for the sensitivity of deterministic user equilibrium (DUE) link flows to perturbations in origin-destination demands and link travel times, however because DUE route flows are not unique, they had to determine one route flow solution among the many in order to carry out the sensitivity analysis. SUE assignment presents the advantage of providing one unique route flow solution which is essential for sensitivity analysis, and the logit version of SUE offers the advantage of providing a tractable analytical solution. Taking Fisk (1980) route based formulation as the non-linear program corresponding to a logit SUE problem, Bell and Iida (1997) presented sensitivity expressions for the equilibrium route flows, in response to perturbations in origin-destination flows and link travel times. The route flow sensitivities can then be used to evaluate link flow, link travel time and route travel time sensitivities. However their method requires inverting matrices whose dimensions are determined by the number of routes defined in the network. Since this number can be quite large in large realistic networks, this may make computation cumbersome. A more economical approach would be to reduce the dimension of the system for sensitivity analysis by deriving the logit SUE link flow sensitivity expressions directly, and subsequently using those to calculate link travel time and route travel time sensitivities. It will be shown below that such an approach is possible with SUE, provided however that the route flows are explicitly defined in the base solution, around which sensitivity analysis is being carried out. That is a reason which makes route-based formulations for SUE particularly attractive in the context of sensitivity analysis. This paper will first present the general mathematical formulation of a route based logit SUE model. It will then be shown how sensitivity expressions for SUE link flows are derived , along with link ,route and minimum expected OD travel times sensitivities, and how those sensitivity expressions can be used to estimate variances of travel time distributions. Finally, results for a small network will be presented and discussed.
72
2.
TRANSPORTATION PLANNING
Logit SUE model
Given a vector of OD flows a SUE solution yields route flows and route travel times consistent with each other by virtue of the equilibrium principle, while the equilibrium assignment of flows to routes is governed by the logit route choice model as follows, for any route flow between an OD pair
with
the route choice proportion factor given by
where denotes the set of routes between OD pair is the logit dispersion parameter and a vector of link saturation flows.The relationship between route costs and route flows occurs because route travel times are the summation of link travel times and that the travel time on a particular link depends on the flow going through that link and on its saturation flow, via some monotonically increasing function. Using the linear relationship between link flows and route flows where A is the link-route incidence matrix (and denotes the transpose of A), we have: with The SUE solution can be interpreted as the mean value of a network equilibrium where users minimise their perceived travel times. Due to random errors in travel time perception, the model is stochastic and therefore the estimated flows and travel times are also random variables. However the mean values provided by the SUE are meant to provide a reasonable estimation of average network traffic conditions on a particular period of the day (like peak hour) as it allows for some non homogeneous driver behaviour in route choice (as opposed to DUE) while taking congestion effects into account. We shall hereafter refer to the ‘base solution’ as being the logit SUE solution obtained for a given vector of OD flows considered to be the average trip table, and the vector of average link saturation flows. From this base we can then look at the effects of random variations in both demand and saturation flows on route travel times and expected minimum OD travel times necessary for calculating reliability measures.
3.
Logit SUE sensitivity analysis
We start this section by denoting the number of OD pairs by by the number of links in the network, and the number of routes defined in the
73
Estimation of travel time reliability
network.The logit SUE solution for the link flows satisfy the following system of non-linear equations:
where represents the probability choice matrix, whose elements are the logit model continuous functions of route cost and are defined by: if route j belongs to OD pair otherwise. This system of non-linear equations can be rewritten in the following form:
Each elements of represent the differences between some given link flows and the link flows that would result from a logit assignment with costs depending on the given flows. At equilibrium these quantities should be equal to zero.
3.1.
Sensitivity of SUE link flows
Suppose, without loss of generality, that we are interested in variations of the trip table only. We can then drop as a variable and look at the following system of non-linear equations:
For a given fixed it is known that this fixed point problem has a unique solution if the Jacobian of link travel times is a positive-definite matrix. This is a sufficient condition for a unique SUE solution (see Sheffi ,1985) and is satisfied if the link cost functions are strictly increasing with link flows. Suppose the trip table is perturbed in an infinitesimal way , with an vector of unity, and an infinitesimal small positive number.We then want to find the new corresponding SUE solution, that will solve the perturbed system:
By differentiation, we obtain:
where
is the
matrix with elements
matrix with elements
and
is the
Taking one perturbation at a time, we have, for
74
with yields:
provided
TRANSPORTATION PLANNING
the
th column of
If we take the limit
exists, that is provided
is non-singular.
Lemma 1 is non-singular for all link travel times is a positive-definite matrix. Proof For all links
equation (3.1)
if the Jacobian of
we have:
W represents the set of OD pairs and represents some element the link-route incidence matrix for OD pair So for the derivatives of are given by:
of and
using
since for a route belonging to OD pair equation (3.2) can be written as:
In matrix notation
75
Estimation of travel time reliability
where is the Jacobian of the vector of route-choice proportion for OD pair with respect to route travel times. Now to prove that is non-singular and therefore invertible, we first note that being positive definite is also non-singular.Also being the choice probability Jacobian is also the Hessian of the expected minimum travel time for OD pair
Since this function is concave with respect to travel times it follows that is negative semi-definite, or equivalently – is positive semi-definite. We then notice that is also positive semi-definite, since it is a symmetric matrix with semi positive elements (each element results from a quadratic form with a positive semi-definite matrix). Therefore, as a sum of positive semi-definite matrices factored by a positive quantity is also positive semi-definite. If we then multiply from the right by we get:
The first term on the right is positive definite, and the second term is semipositive, since it is a symmetric matrix with semi positive elements, each resulting from a quadratic form with a positive semi-definite matrix. Adding a positive definite matrix with a positive semi-definite one gives a positive definite matrix, therefore is positive definite, which implies that it is also non-singular. being non-singular means that has to be non-singular. If we regroup all the vectors together in a matrix, we obtain the following matrix of sensitivity expressions of SUE link flows with respect to perturbations of the trip table:
Likewise, the sensitivity expressions of SUE link flows with respect to perturbations of link capacities are given by:
where
is the Jacobian of
with respect to
76
3.2.
TRANSPORTATION PLANNING
Sensitivity of route and expected minimum OD travel times
Sensitivity of route travel times, between each OD pair can then be easily computed via the Jacobian of link travel times and the route-link incidence matrix using the chain rule of differentiation:
Overall we can see that the main difficulty in computing these expressions, consists in calculating the inverse of the (number of links squared) matrix necessary for the SUE link flow sensitivities. This is much more manageable in general than having to do the same type of inversion operation for a route-based matrix. However, the route structure still needs to be retained for calculating as can be seen from the proof of the lemma. If we assume that there is no re-routing induced by the fluctuations of demand and saturation flow, then it is no longer appropriate to consider variations of flow due to re-routing. Therefore the SUE sensitivities and are no longer required. Instead we can look at distributions of route travel times around the equilibrium caused by the demand- and supply-side perturbations only (the route choice proportions remain fixed). The following gradients then reflect the route travel time sensitivities:
Another useful measure is the sensitivity of expected minimum OD travel time vector defined as follows according to the logit model, for Since the logit route-choice proportion, the sensitivities of are given by:
Estimation of travel time reliability
4.
77
Approximation of travel times variances
By making the following first order approximation of the relationship between equilibrium route/OD travel times and OD flows/capacity, around a base solution
and by assuming some independent normal random distributions for each elements of and around and we can obtain the following approximate variance and covariance expressions for route travel times and OD expected minimum travel times.
5.
Example
We were able to use the expressions derived in the previous sections for a fairly large network (8000 OD pairs, 2000 links) of York and obtained the estimates of route travel time variances in about 8 hours, which is a considerable improvement on the method of finite differences reported in Bell et al (1999). However, to illustrate the type of results obtained, the methodology was applied to a much smaller network, thereby allowing a better overview of the results to be presented in this paper.
5.1.
The network
The network considered here is a small part of an urban network in Leicester, England. It consists of 103 links (including micro-links at junctions), 9 origins and 9 destinations. A representation of the network is shown in Fig. 5.1. The topological data (including signal timings), along with a trip table for a peak period were made available for a Phd project on OD estimation based on SCOOT traffic counts. We did not use the link detector data here.
78
TRANSPORTATION PLANNING
Estimation of travel time reliability
5.2.
79
Computation of time variances and reliability measures with respect to OD flow fluctuations
We used our route-based SUE model, the Path Flow Estimator (PFE), on the Leicester network with the trip table available for the afternoon peak-hour to obtain a base solution, and applied the sensitivity expressions defined in section 2, with and without route response, in order to compute first-order estimates of variances for route travel times and expected minimum OD travel times, with respect to OD flow fluctuations only. For lack of information on OD flow fluctuations, we assumed normal distributions of OD flows centred around the trip table values and chose arbitrary standard deviations equal to However, since some of the OD flows were larger than 100 veh/hr, we put a limit of 30 veh/hr on the standard deviation. This was to avoid very large deviations, which given the first order approximation used in the method, could have lead to unrealistically large variances of travel times. Note that a deviation of 30 veh/hr is not strictly speaking small enough to warrant a valid use of the first order approximation for the relation between the equilibrium solution and the OD flows. However it was conjectured that for this moderately congested network, the second-order derivatives of the equilibrium flows would be sufficiently small so as to make the second order terms relatively negligible. This conjecture is based on the network structure (it is a relatively small network) and on the Kimber and Hollis (1979) link-cost function that is used in our model: the first and second-derivatives of this cost function yield very small values in the base case, and since these terms feature prominently in the second-order approximation terms for route travel times, it appears that, with a maximum deviation of 30 veh/hr for OD flows, an upper bound for the second order terms might be found to be about one minute, for all route and OD travel times, which would be an acceptable error for a crude approximation. A rigorous study about the acceptability of the first-order approximation, which depends on the network, the base demand and the link cost functions employed in the model, would however be necessary in the future. 5.2.1 OD expected minimum time variances. Table 5.1 shows the standard deviation, with and without SUE re-routing, of the expected minimum OD travel times, for the 20 most unreliable OD pairs. We can see that, for all OD pairs, the standard deviation is greater, and thus the reliability lower, when equilibrium route response is not taken into account. This suggests that the effects of drivers re-routing is to lessen to impacts of variations. We can see that all OD pairs connecting DES_B have a substantially higher variability in travel time compared to all other pairs. A quick look at the network shows why: to get to DES_B, it is impossible to avoid either link 215L or link 215K. These two
80
TRANSPORTATION PLANNING
links happen to be the only over-saturated links in the whole network in the base solution. (The same observation could be said for DES_A on the evidence of Fig. 5.1; however in reality link 215K is divided into 2 sub-links, and it is only the right-turn sub-link leading to DES_B that is actually over-saturated.). This evidence points to a correlation between congestion in the average equilibrium situation and high variations in travel times.
5.2.2 Route travel time variances and reliability. The normal distributions for the input OD flows mean that the output travel times are also normally distributed, because of the linear approximation of the relationship between OD flows and route travel times. We could then obtain a measure of reliability for routes by calculating the probability that a route travel time is less than some performance threshold. The travel time threshold for reliability, was arbitrarily taken at 110% of the mean route travel time.
Estimation of travel time reliability
81
Thus for each route the travel time reliability defined as the probability that the travel time will be less than 110% of the mean travel time was calculated as follows:
with 1.1 and where is the cumulative probability of the unit normal distribution . Table 5.2 shows the travel time deviations (with SUE re-routing) and reliability results obtained for the 20 most ‘unreliable’ routes, of which 10 are shown in Fig. 5.2. Again, we see that the over-saturated links 215L and 215K (highlighted) feature quite strongly in the most ‘unreliable’ routes. We also noted that links 212S and 222A, which appear in some of the routes, are operating close to capacity, with high delays, in the base case. All those links appear to account for the significant variations in travel time. Overall we can see that, given our definition of reliability, the most unreliable routes are those with short travel time and relatively high deviation due to the presence of congested links.
While the correlation between high variability and congestion appears to make sense, it still prompts a question about some limitations of the method; the most unreliable routes could indeed have been identified before the calculations
82
TRANSPORTATION PLANNING
Estimation of travel time reliability
83
of the variances just by finding out the routes containing congested links in the base solution.This limitation comes from the first order approximation, which is only valid in the vicinity of the base solution. Therefore it would be useful to account more accurately for the effects of larger variations, which tend to happen in reality anyway. However to model the impacts of these larger variations the non-linear effects in the relationship between input and output need to be included. The potential problems in this case would concern first the evaluation of the second-order approximation, and secondly the subsequent estimation of the output distributions.
6.
Conclusion
We have presented a method for deriving logit SUE sensitivity expressions which can be used in order to estimate travel time reliability measures. Experimentation on a small network showed an expected link between congestion and travel time variability, under normal variation of the demand. Future work shall be carried out in the following directions: a) calculation of error bounds to check the validity of the first order approximation in the relationship between exogenous input and the model output b) inclusion of second-order terms where appropriate c) combination of several variable exogenous factors (demand and supply) with appropriate random distribution in order to improve reliability assessment.
References Asakura, Y and Kashiwadani, M (1991). Road network reliability caused by daily fluctuation of traffic flow. In: Proceedings of the PTRC Summer Annual Meeting in Brighton, Seminar G, pp. 73–84. Asakura, Y and Kashiwadani, M (1992). Road network reliability measures based on statistic estimation of day-to-day fluctuation of link traffic. In: Proceedings of the World Conference on Transport Research, Lyon, France, June. Asakura, Y and Kashiwadani, M (1995). Traffic assignment in a road network with degraded links by natural disasters. Journal of the Eastern Asia for Transport Studies, Vol. 1, No. 3, pp. 1135–1152. Asakura, Y (1996). Reliability measures of an origin and destination pair in a deteriorated road network with variable flow. In: Proceedings of the Meeting of the EURO Working Group, Newcastle-upon-Tyne, UK, September.
84
TRANSPORTATION PLANNING
Bell, M G H, Cassir, C, Iida, Y and Lam, Y (1999). A sensitivity based approach to network reliability assesment. To appear in Proceedings of the International Symposium on Transportation and Traffic Theory. Jerusalem, Israel, July. Bell, M G H, Lam, W and Iida, Y (1996). A time-dependent multiclass route flow estimator. In: Proceedings of the International Symposium on Transportation and Traffic Theory, Lyon, France, July. Bell, M G H and Iida, Y (1997), Transportation Network Analysis, Wiley, England. Du, Z P and Nicholson, A J (1993). Degradable transportation systems performance, sensitivity and reliability analysis. Research Report, No.93-8, Department of Civil Engineering, University of Canterbury, Christchurch, New Zealand. Du, Z P and Nicholson, A J (1997). Degradable transportation systems: Sensitivity and reliability analysis. Transportation Research B, 31, No 3, 225–237. Fisk, C (1980). Some developments in equilibrium traffic assignment. Transportation Research, 14B, 243-255. Iida, Y and Wakayabashi, H (1989). An approximation method of terminal reliability of road network using partial minimal route and cut set. In: Proceedings of the World Conference, Vol. IV, Yokohama, Japan, pp. 367–380. Kimber, R M and Hollis, E M (1979). Traffic queues and delays at road junctions. TRRL Laboratory Report 909, Transport and Road Research laboratory, Crowthorne, England. Sheffi, Y (1985) Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Prentice-Hall, Englewoods Cliffs, NewJersey. Tobin, S J and Friesz T L (1988). Sensitivity analysis for equilibrium network flow. Transportation Science, 22, 242-250.
Chapter 6 A JOINT MODEL OF MODE/PARKING CHOICE WITH ELASTIC PARKING DEMAND Pierluigi Coppola
[email protected] Dipartimento d’Ingegneria dei Trasporti Università degli Studi di Napoli “Federico II” Via Claudio 21, 80125 NAPOLI (Italy)
1. Background and objectives In the last years it has been widely recognized by analysts that Parking Management policies have the great potential to divert Travel Demand from Private modes (car, Motorbikes,...) towards Public Transportation System (bus, metro,...) and, thus, to contribute to reduce congestion (and other traffic-related undesired impacts) in urban areas, especially in their Central Business District (CBD). In fact, the problem of increasing parking demand in CBD is approached in a different way: the possibility of finding a parking place at the end of the trip is no more considered a service debt to drivers, but a useful tool to influence their travel choices. In order to define optimal parking management policies a model simulating the performance of the Parking System and the behavioral responses of the travelers, is necessary. But which are the requirements for parking modeling ? Parking Management deals substantially with the global dimension of parking supply and with the location of parking places within the study area. The parking places, furthermore, have to be differentiated according to different parking typologies (free, charged, time-limited, illegal,...). Impacts of changes in parking supply pattern, on the other hand, can affect both Parking Demand System itself (e.g. occupation ratio of parking infrastructures, revenues from parking fares,...) and the global 85 M. Patriksson and M. Labbé (eds.), Transportation Planning, 85–104. © 2002 Kluwer Academic Publishers. Printed in the Netherlands.
86
TRANSPORTATION PLANNING
Travel Demand System (e.g. modal split, trip distribution and trip frequency within a certain area, tour timing within a day and land-use). Therefore, a model aiming at simulating parking choice has to be able to simulate some of these interactions. Moreover, there are two other modeling requirements that a parking model should have. Firstly, the model should be multi-user, since behavioral responses to changes in parking system could strongly vary with travelers’ characteristics (e.g. the desired parking duration, trip purpose,...): it is rather intuitive to understand that an increase of parking fares will affect much more the choice of travelers with long parking stays than those with short parking stays. Secondly, since parking demand flows are not transient such as the link-flows on a road network, but persistent in the parking infrastructure for the whole parking duration, to model the performance of the parking system we must consider the effects of accumulation and dissipation of occupancy over the day. Thus, the temporal dependency between the successive time periods over the day is an additional model requirement for parking modeling (Polak and Vythoulkas, 1993). The parking models found in literature mainly follow two approaches: a network and a non-network approach. In a network approach (Eldin et al., 1981, Gur and Beimborn, 1986, Bifulco, 1991), a standard privatemode-network is expanded by means of parking links (simulating the cost of parking infrastructure) connected to the centroids by pedestrian links (simulating the walking distance to the final destination) and to the original network by access-egress links (see Fig. 1). Following a network approach, parking choices are simulated within the assignment procedure.
A Joint Model of Mode/Parking Choice
87
In a non-network approach, on the other hand, parking choices are modeled through Random Utility Theory: at each parking alternative (i.e. a certain parking infrastructure) a value of Utility, sum of a deterministic term (i.e. the Systematic Utility) and a random residual, is associated. Different specifications are possible according to the specification of the systematic utility and to the hypotheses on the residual. Most of the specifications found in literature are Logit or Nested Logit (Van Der Goot, 1982, Hunt and Teply, 1993, Bifulco, 1996). Previous researches have been carried on in order to simulate explicitly the impacts of parking policies on mode choice. Bradley et al. (1993) and Miller (1993) propose to model jointly mode and parking choices following Random Utility theory, through a Nested Logit model specification. In these models, however, the (attribute) searching time for an empty parking space which should depend on parking occupation ratios (so in turn on parking demand) is calculated off-line on an average basis. In other words, there is a circular dependence between parking demand and parking generalized costs, which in the above models is not taken into account. The lack of feedback between parking supply performances and parking demand leads to a model system in which both parking demand and performances are derived from exogenous variable (fixed by the analyst) which are not the results of users’ choice process. In this paper a joint model of mode and parking choice with elastic parking demand is presented. The overall framework consists of the
88
TRANSPORTATION PLANNING
Nested Logit specification depicted in Fig. 2: users who have chosen to travel by car or motorbike, will next have to choose parking typology and location. Consistency between two choice dimensions (i.e. mode and parking) is achieved through the satisfaction variable (i.e. the Logsum variable) which is explicitly included as an attribute of the mode choice sub-model. In Section 2 a non-network parking choice sub-model, including the functions adopted to compute the generalized parking cost, is presented, while in Section 3 we report the results of a partial information estimation of the mode choice sub-model. In Section 4, finally, the results of the application of the model to Salerno (a mediumsize city of South of Italy) in order to simulate realistic parking policies, are shown.
Although the model focuses on the effects of Parking Management on modal split, the adopted approach can be easily extended to deal with other travel choices like destination and trip frequency.
2.
The parking choice sub-model
The parking choice sub-model aims at simulating interactions between Parking Supply and Parking Demand Systems. In the adopted parking choice sub-model, the existing parking places are grouped according to parking typology and according to their location. The elementary parking alternative is defined as the total parking supply of a given type in a given zone. Considered parking typologies are:
A Joint Model of Mode/Parking Choice
89
free parking; illegal parking; time limited parking (i.e. free parking allowed for a certain period then parking not allowed); charged parking (where a fare structure is applied); limited + charged parking (i.e. charged parking allowed only for a certain period).
Each parking elementary alternative is characterized by several attributes. The following parking attribute classification is proposed:
where indicates the users’ class and F the parking occupancy. According to the above classification, the attributes included in the model are the following.
Attributes of type C1 is time spent walking from the parking infrastructure to the final destination. Assuming a walking speed of 1 meter/second, it is given by the distance (in meters) from the parking places to the centroid of the destination zone. All the parking places of a given typology in a given zone have the same pedestrian distances. In doing so, the effective distribution of parking places of the same typology in a given zone is lost. This is, however, consistent with the discretization of the trips, whose “real” origin and destination are assumed to be the centroids of origin and destination zones.
Attributes of type is the monetary cost for users’ class i related to parking fare .
90
TRANSPORTATION PLANNING
where is desired parking duration (in hours) of users’ class is the fare for each parking hour after the first (in EURO per hour) and fix is the fare for the first parking hour (in EURO). Since parking monetary cost depends on parking duration, a segmentation of the demand according to the desired parking duration is required. Therefore, parking demand is segmented in four user-classes according to four time intervals of desired parking duration. An average parking duration is associated to each of them, as shown in Tab. 1.
is the perceived monetary cost for users’ class i of illegal staying or overstaying:
where Tmax (in hours) is the maximum permitted parking stay (for illegal parking Tmax = 0); fine is the amount of the fine for illegal staying or overstaying and risk is the probability of being fined for each illegal (staying or overstaying) hour.
A Joint Model of Mode/Parking Choice
91
According to the level of enforcement the proposed values for risk are those reported in Tab 2.
Attributes of type C3(F) is the time spent looking for an available parking space. It is, in general , a function of the capacity of the parking infrastructure, of the occupancy at the beginning of the simulation period and of the number of arrivals and departures during the simulation period. The adopted mathematical expression of the searching time function (Bifulco, 1991) gives rise to cost functions like the ones depicted in Fig. 3, where the capacity of the considered parking infrastructure is assumed to be 100 vehicles.
92
TRANSPORTATION PLANNING
The curves are parameterized with respect to the parking occupancy at the beginning of the simulation period. The independent variable represents the parking occupancy due to the parking loading mechanism within the simulation period and the dependent variable is the searching time.
Attributes of type none, since the specification of attributes contemporaneously depending on users’ class and parking occupancy could give rise to nonuniqueness and instability to the solution of parking choice equilibrium problems (see below). As shown above, the number of users that choose a certain parking infrastructure during the simulation period, depends on the searching time for an empty parking place. In our model, searching time is a function of parking infrastructure occupancy, which in turns depends on the number of users choosing that infrastructure. In other words there is a “circular dependence” between parking demand and searching time (i.e. parking cost), as shown in Fig. 4. This gives rise to a “fixed point”
A Joint Model of Mode/Parking Choice
93
problem similar to the fixed-point problem related to assignment to congested road network (see Cantarella, 1997) which here is solved using an MSA (Method of Successive Averages) algorithm (Sheffi, 1985). Moreover, it is possible to prove the existence and the uniqueness of the stated fixed-point problem because of the absence of the costs simultaneously depending on both users’ class and parking congestion.
The user’s choice set (i.e. the set of all the alternatives the user considers to be attractive for his own choice) consists of all the elementary parking alternatives of his/her destination zone and of those owing to “neighboring” zones. The parking demand directed to a certain zone can, thus, be satisfied by the parking supply of the destination zone and by the parking supply of “neighboring” ones. Two zones are assumed to be “neighboring” if, for instance, the (average) walking distance lying between them is not greater than 500 meters. The systematic utility functions of each parking alternative are assumed to be linear in of the above attributes. However, since the parking choice sub-model has not been calibrated, the coefficients used in the applications have been taken from the (calibrated) mode choice model. In practice we have proceed as follows. Starting from value of betas taken from literature (Bradley et al., 1993), we have used such values to compute the inclusive variables of parking choice (i.e. Logpark variable, see section 3), which are attributes
94
TRANSPORTATION PLANNING
of the mode choice sub-model. With these values of logsum we have calibrated the mode choice model. It has been assumed, then, that the values of searching time, walking time and monetary cost in parking choice are perceived by the user as equal respectively to in-vehicle time, walking time and monetary cost in mode choice. As consequence, according to Nested-Logit theory (see Mc Fadden, 1978), the values of for such attributes have been obtained by dividing the values of corresponding parameter in the mode choice model by the value of In doing so, the values obtained are not exactly the same of those according to which the inclusive variables have been calculated. Therefore, starting from these values new inclusive variables are calculated and accordingly a new calibration of the mode choice is carried out. This iteration procedure stops when consistency between inclusive variable and beta’s of parking attributes is achieved.
The trip purposes, here considered, are: Workplace Other constrained: purposes constrained in destination (i.e. those characterized by destination that cannot be daily chosen), such as Business, Study, and so on Other unconstrained: purposes that are not constrained in destination (i.e. those characterized by destination that can be easily changed), such as shopping, leisure, and so on. For different trip purposes the reported in Tab 3.
estimated as described above, are those
95
A Joint Model of Mode/Parking Choice
3. The mode choice sub-model The modal alternatives to be included in the model specification come out of the analysis of the data available for the calibration. In fact, as the estimation of the model is based on an RP (Revealed-preference) survey, any mode that either doesn’t exist or that is coarsely utilized within the study area (e.g. Metro and bicycle, in Salerno) must be left out of the model specification. As consequence, the modal alternatives considered are: Moto Car
Walk Bus
The systematic utilities of each mode are the following:
where: is the travel time by motorbike on the minimum path between origin zone and destination zone is the travel time by car on the minimum path between and
is the travel time to walk from
to
is the waiting time at the bus stop on the minimum hyperpath (see Guyen e Pallottino, 1988) connecting
to
96
TRANSPORTATION PLANNING
is the access-egress time to/from the bus stop on the minimum hyperpath connecting
to are the monetary costs to go from
to
respectively by car, motorbike and bus;
Age is a dummy variable which is equal to 1 if the user is not older than 30 years, 0 otherwise; is the inclusive variable of the parking choice alternatives (i.e. Logsum variable), computed as:
being
and
respectively the Systematic Utility of the generic
parking alternative and the choice set of users directed to zone (i.e. all the parking alternatives within the zone plus those within the “neighboring” ones, as already explained in section 2) Note that Alternative Specific Constant (ASC) have been introduced for “Auto”, “Moto” and “Walk” modes. The following rules are introduced in order to define which subset of the four potential alternatives is feasible for each user: Moto is available only if the pedestrian time on the same O/D pair does not exceed 5 minutes. Auto is available if the pedestrian time on the same O/D pair does not exceed 5 minutes and the user owns a car and a license driving. Walk mode is available only for trips not exceeding 30 minutes. Bus is available if the Access+Egress pedestrian time does not exceed 30 minutes, the waiting time does not exceed 30 minutes and the pedestrian time on the same O/D pair does not exceed 5 minutes.
The mode choice model has been calibrated through the “maximum likelihood” method. In Tab. 4 the and the corresponding values of T-ratio are reported for different trip purposes.
A Joint Model of Mode/Parking Choice
97
All the coefficient estimates have the expected sign and are significantly different from zero at the 5% level of confidence. As expected, the “Other constrained” value of time (VOT) is higher than other VOT’s since this purpose includes also “Business” trip (remark that “workplace” here is synonymous of “commuters”).
4. Simulation of realistic parking policies The model so far presented is part of a comprehensive modeling system developed within the EC project AIUTO. It has been used to evaluate the impacts of Parking Management on the modal split in the city of Salerno, one of the Italian AIUTO test-sites. In this section some
98
TRANSPORTATION PLANNING
realistic parking policies will be simulated. It is worth noting that Parking Management could also affect destination and activity-time choices, however these choice levels here are not covered. Moreover, only the morning peak period is simulated. Salerno is a medium-size city of the South of Italy that extends for about narrow between the mountains and the homonymous gulf. With a population of more than 150.000, Salerno suffers from heavy congestion problem due to high and “concentrated” travel demand. The travel demand is here segmented per parking average duration (i.e. 0.5, 2, 5, 9 hours), which directly affects parking choice, and per age (i.e. > or <= 30 years old), which directly affects mode choice. Considered travel purposes are: workplace, other purposes constrained in destination (e.g. Business) and other purposes not constrained in destination (e.g. Shopping). The (percentage) trip distribution across trip purposes over the morning peak period and over the whole day is reported in Tab. 6.
The study area is defined as the city center of Salerno plus the traffic zones adjacent to the center. Here most of the congestion is located. The traffic zones within such area have been grouped into two macro-zones: the so-called “red” zone, consisting of the zones of the city center, the “yellow” zone, consisting of the zones adjacent to the city center (see Fig. 5).
A Joint Model of Mode/Parking Choice
99
Different parking measures have been introduced for these two groups of zones with respect to a base-scenario derived from a survey of 1993. It is worth to remark that the perceived cost of illegal parking is here calculated as the product of fine and probability of being fined. Therefore, increasing fines could correspond to increase either the fine itself or the probability of being fined (e.g. by means of enforcement of parking restrictions). In the “red zone” the applied parking measures consist of: the free parking spaces are reduced to 100 spaces for each traffic zone transforming the rest in charged parking with the costs indicated in Tab. 7, corresponding to a fare of 0.75 EURO per hour in the base scenario and 1.5 EURO per hour after applying parking policies; the illegal parking is controlled with the fines indicated in Tab. 7, corresponding to a “high” level of enforcement (see Tab. 2) and a fine of 25 EURO in the base scenario, and to a “very high” level of enforcement and a fine of 50 EURO after applying of parking policies; the time limited parking becomes charged parking with the fares indicated in Tab. 7.
100
TRANSPORTATION PLANNING
In the “yellow zone”, the parking measures applied, consist of: the free parking spaces are reduced to 100 spaces for each traffic zone transforming the rest in time limited parking with the fines (in case of overstaying) indicated in Tab. 8; the illegal parking is controlled with the fines indicated in Tab. 8, corresponding to a “medium” level of enforcement (see Tab. 2) and a fine of 25 EURO in the base scenario, and to a “high” level of enforcement and fine of 50 EURO after applying of parking policies; to the already existing charged parking the fares applied are those indicated in Tab. 8, corresponding to a fare of 0.75 EURO per hour in the base scenario and 1.0 EURO per hour after applying parking policies; to the already existing time-limited parking the fines, in case of overstaying, are those indicated in Tab. 8.
The main impact of such parking measures is that of diverting car travel
A Joint Model of Mode/Parking Choice
101
demand to alternative modes, as it is shown in Tab. 9. where the (percentage) trip changes for each mode is reported.
Percentage trip changes, for the generic mode
are here calculated as:
being and the demand on mode m respectively after and before the introduction of parking measures. It can be noted that the reduction of the number of trips by car seems to be comparable for red and yellow zones, even tough fares and parking restriction in the red zones are stronger. This can be explained by the fact that the parking model takes into account that users can reach a given destination (e.g. in the red zone) also by parking in neighboring zones (e.g. in the yellow zone). This yields a first modeling consideration: a parking model which allows drivers directed to a certain zone to park in the neighboring zones, leads to a sort of homogenization of the impacts of parking policies across all the zones of the understudied area. In Tab. 10 the percentage reduction of trip-by-car for different trip purposes is reported: as expected the parking policy impact (both in red and yellow zone) is strongly different according to travel purpose. While trip purposes characterized by long average parking duration (i.e. workplace) are strongly discouraged by parking measures, medium stay purposes (i.e. other constrained) are much less affected and short term purposes (i.e. other unconstrained) are almost not discouraged at all by using car.
102
TRANSPORTATION PLANNING
This is explainable as follows. When parking measures are applied, in fact, users travelling for purposes implying long parking duration (e.g. workplace) have to pay much more than in the base-scenario, therefore, most of them find more convenient diverting towards other modes. On the other hand, the relatively low monetary cost increase for users travelling for purposes characterized by a short (or medium) parking duration is compensated (at least partially) by the reduction in searching time (reduction which is due to the fact that long duration stay trips have diverted). As consequence, those with low desired parking duration might find parking even more attractive (e.g. other unconstrained in the red zone, see table above) when, for instance, the reduction in searching time is perceived as higher than the increase in parking monetary cost. The increase of monetary parking costs can be compensated by decrease of searching time (depending on parking congestion) and vice versa, since parking model and the mode choice model are framed into an “elastic” modeling procedure. The parking demand (i.e. the number of users choosing the car mode) and the parking Level Of Service (LOS) are (at equilibrium) mutually consistent.
A Joint Model of Mode/Parking Choice
5.
103
Acknowledgements
The author would like to thank the Salerno research laboratory ELASIS for having given access to the database through which the calibration of the model has been possible.
6. References BIFULCO G.N., (1996) - Stochastic models for the simulation of parking choices: a non-network approach - Proceedings of the EUF-PTRC BIFULCO G.N., (1991) - A stochastic user equilibrium assignment model for the evaluation of parking policies - Proceedings of the PTRC Summer Annual Meeting BRADLEY M. -KROES E. and HINLOOPEN E., (1993) - A joint model of mode/parking type choice with supply constrained application Proceedings of the PTRC Summer Annual Meeting CANTARELLA G.E.,(1997) - A General Fixed-Point Approach to MultiMode Multi-User Equilibrium Assignment with Elastic Demand Transportation Science, vol.31 (2). ELDIN N.-EL REEDY T.J. and ISMAIL H.K., (1981) - A combined parking and traffic assignment model -Traff. Eng. and Contr., 22(10) pp. 524-530 GUYEN S. and PALLOTTINO S., (1988) – Equilibration Traffic Assignment for large scale transit Network – European Journal of Operational Research - pp. 176-186 GUR Y.J. and BEIMBORN E.A., (1986) - Analysis of parking in urban centres : equilibrium assignment approach - Transportation Research Record 957 - pp. 55-62 HUNT J.D. and TEPLY S., (1993) - A Nested Logit model of parking location choice - Transp. Res.-B, Vol. 27B, No.4 - pp. 253-265 McFADDEN D., (1978) – Modeling the choice of residential location – in Spatial Interaction Theory and Planning models by Karlqvist A. et al.,
104
TRANSPORTATION PLANNING
North Holland Publishing Company MILLER E.J., (1993) - Central area mode choice and parking demand Transportation Research Record 1413 - pp. 60-69 POLAK J. and VYTHOULKAS P. (1993) – An assessment of the state-ofthe-art in the modeling of parking behavior – Report n.752 of Transport Study Unit SHEFFI Y. (1985) – Urban transportation networks – Prentice-Hall ed. VAN DER GOOT D., (1982) - A model to describe the choice of parking place - Transp. Res., Vol. 16A, No.2 - pp. 109-115
Chapter 7 A NEW GENERAL EQUILIBRIUM MODEL Yanling Xiang
[email protected]
Michael J. Smith
[email protected] York Network Control Group Mathematics Department, York University York YO10 5DD, UK
Miles Logie
[email protected] MVA Limited MVA House, Victoria Way, Woking, Surrey GU21 1DD, UK
Abstract
In this paper we present a new general equilibrium model appropriate for multimodal networks. A solution of the model gives the equilibrium distribution of travellers and vehicles over a transportation network. The model is expressed in terms of inverse cost-flow functions; and delays are explicitly modelled. The paper outlines an equilibration algorithm and convergence results for a small network are provided. The equilibrium model has been designed in such a way that optimisation procedures may naturally be added to the equilibration algorithm.
Keywords:
Equilibrium, assignment, multicopy network, bottleneck delay, monotone cost functions
105 M. Patriksson and M. Labbé (eds.), Transportation Planning, 105–118.
© 2002 Kluwer Academic Publishers. Printed in the Netherlands.
106
1. 1.1.
TRANSPORTATION PLANNING
Introduction The General Equilibrium Model described in this paper
The General Equilibrium Model specified in this paper has been designed and a solution method has been implemented within software as part of a UK Government LINK project with partners MVA Limited, University College London and the University of York. The LINK project was supported by the Department of the Environment, Transport and the Regions (DETR), the Engineering and Physical Sciences Research Council (EPSRC), the Engineering and Sciences Research Council (ESRC) in the United Kingdom and MVA Limited. The model is general for a number of reasons. Firstly, it provides an integrated framework for consideration of both transport demand and supply. It does this in a form of a standard economic model, suggesting the potential for making the transport model an element of a wider economic model. Secondly, its form embraces the four stages of trip generation, distribution, modal split, and assignment of classical transport modelling. Thirdly, the model allows for complex network modelling features such as capacity constraints and interactions where flows on one link affect costs and flows on another. These interactions may extend across modes and need not be symmetrical. Finally, the model may consider costs calculated from deterministic and stochastic functions, and offers a very natural potential for extension to the dynamic case. The model and the context motivating its development have been described by Logie et al. [5]. In this paper we describe (i) some technical details of the model, and (ii) some initial convergence results generated by the model. It should be noted that “the equilibrium objective function" in (3.6) which is driven to zero at equilibrium is completely different to the usual “equilibrium objective function". This departure; which appears to be necessary so as to allow for interactions; means that the model is novel within transportation software although the theoretical ideas have been around for a while. The different equilibrium objective function also allows bilevel optimisation procedures to be readily implemented within the model and one way of doing this is outlined in Smith et al. [12]. Thus the “optimising" version of this model will itself make suggestions to the transportation planner and so assist with the achievement of targets.
1.2.
Issues for transport modelling
The generality of the model described here is of significance to many of the issues which current trends in transport policy, planning, and modelling are emphasising. These trends give rise to changing targets and increasingly so-
A New General Equilibrium Model
107
phisticated controls which provide the transport planner with a correspondingly difficult task. Policies in the UK, for instance, increasingly emphasise demand management, and local authorities face traffic reduction targets. This has been accompanied by research into the impact of highway capacity reductions ([2]) and into elasticities associated with demand suppression and induction (MVA [6], and previously SACTRA [8]). We may note that these considerations match the original work by Beckmann et al. [1], who allowed for demand elasticity and strict capacity limits. Thus a pure Beckmann equilibrium model is suitable at least to assess these issues. We may observe also that the demand for transport is derived from the need to conduct other activities; it is not an end in itself. Other research is aimed at modelling needs for activities. These needs (to go to work, shopping, collecting children from school, etc.) may also form an input to the General Equilibrium Model which, depending on the implied costs, can determine whether travel or alternatives, such as telecommunications, are required to meet the needs. Currently, computer models of transportation are used to assess strategies, leaving the planner to devise strategies for testing against new and changing targets. This is a difficult task and there is a corresponding need for an effective and proven mathematical optimisation methodology; implemented with helpful and easy-to-use software. The ability to allow bilevel optimisation, where the upper level is used to optimise a strategy, is therefore significant. This is most clearly seen in respect of traffic signal controls where signal timings for a network (particularly in the UK but also elsewhere in Europe) are often chosen to minimise delay for the observed traffic pattern, and neither consider nor seek to improve long-run effects. Yet it is easy to see that settings which are best for the present may cause problems in future as route and mode choices change to take advantage of these settings. It is therefore valuable to be able to optimise controls such as signal settings when assessing schemes and policies. Prices are also important controls of economic and transportation systems, and their varied application commands increasing attention as part of transport policies. Methods proposed for setting prices are often based on marginal cost prices which pay little regard to practical constraints. It is usually more appropriate to solve the problem, known as the second best problem, namely; what should prices be set at when some prices cannot be marginal cost prices? This arises because it is either practically or politically difficult to alter some prices (say, bus fares and road tolls) and not others (say, parking charges). Similarly, theoretical System-Optimal flow patterns only give the right prices if all links are charged; as soon as some links are not charged we have a second best problem. Therefore a more general optimisation procedure is required
108
TRANSPORTATION PLANNING
which may incorporate constraints reflecting the fact that certain links must not be subject to charge. These pricing issues further the value of integrating transportation assessment and optimisation models as the General Equilibrium Model framework allows.
2.
DREAM—The general equilibrium model
The model described here incorporates controls; including prices and greentimes; within a model with inelastic and elastic demand, and deterministic and stochastic route and mode-choice. Like Beckmann et al. [1] the model embodies explicit capacity constraints and like Payne and Thompson [7] explicit queueing delays. Here we describe the model without stochastic choice and with fixed controls; give an equilibration procedure, and some initial convergence results.
2.1.
Monotonicity
The model will be monotone in the flow, delay and cost variables for each fixed control vector This will allow a fairly wide range of interactions between flows on one link and costs on other links but will also mean that there is at least one algorithm which is bound to converge to equilibrium for any fixed signal control settings and prices.
2.2.
DREAM
The model is called DREAM (Demand Responsive equilibrium assignment model) and has the potential for optimisation facilities, including second-best pricing facilities, essentially built in. The need for optimisation has been a central feature of the design of the equilibrium procedures. We believe it is the first equilibrium model to have been constructed beginning with this point of view.
2.3.
The basic structure of DREAM
Smith [9] introduced an equilibrium as a point
such that
This formulation of equilibrium as a complementarity problem is fundamental to DREAM. DREAM also has an explicit representation of delays at link exits following Payne and Thompson [7]. The model, specified in a route space, has been developed from that described in Smith et al. [12], in Smith et al. [11], and in Xiang and Smith [14] which is in a link flow framework. Three descent algorithms for equilibration are
109
A New General Equilibrium Model
implemented: the Smith Algorithm (D) direction ([10]), the steepest descent direction, and the conjugate gradient direction; and various line searches are implemented including Armijo type and quadratic type. Many non-linear flow-delay functions may be used in DREAM. For example, the flow-delay function corresponding to the transition curve due to Kimber and Hollis [4] has been implemented. Figures 7.2 and 7.3 illustrate the performance of DREAM on a small network by using this curve. The convergence of DREAM to equilibrium is guaranteed for monotone non-decreasing flow-delay functions.
3. 3.1.
An outline of the DREAM model Notation
The notation adopted in DREAM is given below; there is a base network (a model of the actual road network) and a multicopy network ([3]). The idea of the multicopy network is explained below before the notation is shown. In a multicopy network, within each copy the commodity flowing on that copy must have a single specific destination node. If there are K commodities the multicopy network has K copies of the basic network. The simplest commodity comprises all travellers with the same destination. Then if there are K destinations there are K commodities. We may also consider different types of vehicle as different commodities. Here, for example, we may consider all heavy goods vehicles with a specific destination. In this case the copy of the basic network may have no links which correspond to link in the basic network – the heavy vehicles may be prohibited from certain road links. Thus the copies may in fact essentially be copies of subsets of the base network. In what follows all the copies are considered together as a single multicopy network. At an initial reading think of the as 1. Variables to be found. = flow along route
in the multicopy network;
= least cost of reaching the destination from node in the multicopy network and is to be zero if is that destination; and = bottleneck delay at exit of link in the base network. Fixed control variables. = proportion of time stage
is green;
= price to be paid to traverse route
in the multicopy network; and
= price to be paid to traverse link in the base network.
110
TRANSPORTATION PLANNING
Fixed given data. = free-flow cost of traversing route = saturation flow at exit of link (may be infinite); = passenger car unit equivalent of a unit of flow in that commodity whose network contains route and = passenger car unit equivalent of a unit of flow in that commodity whose network contains node Multicopy network structure data.
if node
is the upstream node of route
before
and 0
otherwise; if link belongs to route in the multicopy network and 0 otherwise; if link is in stage if links in stage 0 otherwise.
and 0 otherwise; and
have downstream node
in the base network and
Immediately derived variables. passenger car unit, or normalised, flow along link in the base network so that (it is this normalised flow which causes congestion); and the nominal capacity of link Demand and flow-delay functions. flow generated at node if the cost to destination vector is (with inelastic demand constant and for all if is a destination); and maximal possible average flow on link if the average bottleneck delay is and the nominal link capacity is
3.2.
Supply, Demand and User Equilibrium
Supply. The links in DREAM have performances which may be written: and
A New General Equilibrium Model
111
This says that the realistic capacity of a link is never exceeded and that if the outflow is less than the realistic capacity then the queueing delay is zero there is no holding back. Demand constraints. An appropriate (elastic or inelastic) demand constraint may be written similarly:
This implies that for any non-destination node the net inflow to node (allowing for the properly generated by the cost vector ) is never positive; or that (allowing for the there is no net outflow from the network at any non-destination node. If this condition holds then it is automatically true that the outflow at a destination equals the sum of the inflows at all the non-destination nodes for that commodity and that this sum is at least the sum of the relevant (The user-equilibrium condition below then implies that the inflow to the network at each equals User equilibrium. We shall use the following version of Wardrop’s user equilibrium condition ([13]): for each route the (least) cost to the destination from the upstream node (before is no more than the least cost to the destination via route and if it is less then no flow will enter route or
3.3.
The Equilibrium Problem
The problem here is the problem of finding an equilibrium within the demand and capacity constraints. The equilibrium conditions (3.1), (3.2) and (3.3) may be written as a non-linear complementarity problem (multiplying (3.2) and (3.3) through by the positive and as follows:
is normal at
to
for each
112
TRANSPORTATION PLANNING
is normal at
to
for each
is normal at to for each Let the vector with coordinate vector with coordinate be may be written:
be and let the Then the above conditions
is normal at where is the number of routes (a variable in DREAM) in the multicopy network, is the number of OD pairs in the multicopy network, and is the number of links in the base network.
3.4.
Optimisation Formulations of the Equilibrium Conditions
Rewrite (3.4) in the form:
where
and
Generally will be the co-ordinate of and will be the co-ordinate of We must augment the condition (3.5) with feasibility constraints on and These we will here assume to be:
and
(all and
where A is a matrix.
A New General Equilibrium Model
113
Consider the energy
where and If and for all then satisfies (3.5) and is an equilibrium provided is feasible. Thus, finding an equilibrium is now the same as finding a feasible minimum of at which certain upper bounds are not binding. (We are now solving this model in a way which avoids the need for the upper bounds. See Smith et al. (2000) and the objective function therein.)
4. 4.1.
Features of the general equilibrium model Gap function for optimisation
In this paper, the assignment problem is considered by letting the control variables be fixed. To be specific we suppose to be linear here. Then let (for fixed controls)
where are concerned with flow-delay functions used in DREAM as explained below, is the Jacobian matrix of equation (4.0), and is a constant vector.
4.2.
Flow-delay functions
Flow-delay functions currently available in DREAM are of the form:
Formula (4.2) is a function of the bottleneck delay at the exit of link and the (fixed) nominal capacity of link and are two parameters specified by users. Typically, and In these cases, flow-delay function (4.2) is a non-decreasing function of if is fixed. For fixed functions (4.2) may be written as
114
TRANSPORTATION PLANNING
where is a diagonal matrix with elements and is a vector consisting of elements is the total number of links in the network). As described earlier in the paper, congestion costs normally represented by a cost-flow function will in fact occur in DREAM as bottleneck delays which arise from equilibrating via thefunctions The may be thought of as the inverse of given cost-flow functions.
4.3.
The outer loop and inner loops
DREAM alternates between two phases: an outer loop and inner loops. In the outer loop, an active route set is generated or augmented by Dijkstra’s shortest path algorithm. The active route set is generated automatically and route enumeration is not needed. In the inner loops, a capacity-constrained user equilibrium assignment problem is solved as an optimisation problem within the route set generated so far.
4.4.
Assignment problem in the inner loops
From equations (4.0) and (4.3) it is clear that (the Jacobian matrix of is positive semi-definite when flow-delay function (4.2) is non-decreasing, and then is a monotone function. According to Smith [10], gap function (3.6) has for fixed always a descent direction while away from zero where
The gradient vector
of the gap function
in (3.6) is
Apart from the algorithm (D) direction (4.4), the steepest descent direction and the conjugate gradient direction can be easily obtained from the above gradient vector (4.5). The three directions are implemented along with three distinct line searches: the constant step length, the quadratic line search, and the Armijo-type line search.
4.5.
Active route set generation in the outer loop
DREAM uses Dijkstra’s algorithm to calculate shortest paths between one origin and all destinations, for the active route initialisation and also later when new cheapest routes are added to the active route set. When a new shortest path is found according to current link costs for an origin-destination pair the number of routes for the OD pair is increased by
A New General Equilibrium Model
115
one, and the total number of routes in the active set is then updated. The system will be re-equilibrated in the new (expanded) route set. When the active route set is updated, the gap function (3.6) will jump upwards to a (new) peak point.
4.6.
Upper bounds
The gap function used in DREAM is given in (3.6), where are lower bounds (always zero) on variables and are upper bounds on variables Route flow variables are naturally bounded above by demands. For link delays and least origin-destination pair costs, upper bounds must be specified initially by users as input parameters. When a variable is found to reach its upper bound during iterations, DREAM will automatically update the corresponding upper bound by increasing a certain amount. When this happens, the gap function jumps upwards; as happens when new routes are added into the route set.
116
5.
TRANSPORTATION PLANNING
Test Results
Figure 7.1 illustrates a single-modal example network with twenty-eight links and twelve nodes. Nodes 31 – 38 are signalised junctions (31 – 34 are also destinations), and nodes 39 – 42 are origins. There are four origindestination pairs with demand 1000 veh/hr each: 39 to 33, 40 to 34, 41 to 31, and 42 to 32. Signalised junctions 31 – 38 have a fixed cycle time of 120 seconds with two stages and for each of the junctions, the green-times of the two stages are all fixed at 60 and 60 seconds respectively. Link labels, saturation flows, free flow times, and the stage numbers for the Dring network are given in Table 7.1. Figure 7.2 illustrates the convergence of the (energy) gap function (3.6) to zero. The three peaks indicate where the active route set has been updated, that is, new cheapest routes have been added into the route set. Figure 7.3 illustrates the convergence of the total journey times for two flow-delay functions: and (the Kimber and Hollis formula).
Acknowledgments We thank UCL for their collaboration. Our results presented here are obtained within a UK LINK project, supported by DETR, EPSRC, and ESRC in the UK, and MVA Limited. We are very grateful for their financial support.
References [1] Beckmann, M., C. B. McGuire, and C. B. Winsten: 1956, Studies in the Economics of Transportation. Yale University Press. [2] Cairns, S., C. Hass-Klau, and P. Goodwin: 1998, Traffic Impact of Highway Capacity Reductions: Assessment of the Evidence. Landor Publishing.
[3] Charnes, A. and W. W. Cooper: 1961, ‘Multicopy Traffic Network Models’. In: Herman R. (ed.): Proceedings of the Symposium on the Theory of
REFERENCES
117
118
TRANSPORTATION PLANNING
Traffic Flow,. held at the General Motors Research Laboratories, Elsevier, Amsterdam. [4] Kimber, R. M. and E. M. Hollis: 1979, ‘Traffic Queues and Delays at Road Junctions’. Technical Report LR909, TRRL Laboratory, UK. [5] Logie, M., B. G. Heydecker, and M. J. Smith: 1998, ‘Generalised Equilibrium Modelling: An Integrated Framework for Transport Planning’. In: European Transport Forum. [6] MVA Limited: 1998, Traffic Impact of Highway Capacity Reductions: Report on Modelling. Landor Publishing. [7] Payne, H. J. and W. A. Thompson: 1975, ‘Traffic Assignment on Transportation Networks with Capacity Constraints and Queueing’. Paper presented at the 47th National ORSA/TIMS North American Meeting. [8] SACTRA: 1994, ‘Trunk Roads and the Generation of Traffic’. Technical report, Department of Transport, UK. [9] Smith, M. J.: 1979, ‘The Marginal Cost Taxation of a Transportation Network’. Transportation Research, B13, 237-242. [10] Smith, M. J.: 1984, ‘A Descent Method for Solving Monotone Variational Inequalities and Monotone Complementarity Problems’. Journal of Optimisation Theory and Applications 44, 485–496. [11] Smith, M. J., Y. Xiang, R. Yarrow, and M. O. Ghali: 1998, ‘Bilevel and other Modelling Approaches to Urban Traffic Management and Control’. In: Marcotte P. and Nguyen. S (eds.): Equilibrium and Advanced Transportation Modelling. pp. 283–325. [12] Smith, M. J., Battye, A., A. Clune, and Y. Xiang: 2000, ‘Cone Fields and the Cone Projection Method of Designing Signal Settings and Prices for Transportation Networks’. In: Proceedings of the 6th Meeting of the EURO Working Group on Transportation, Gothenburg.
[13] Wardrop, J. G.: 1952, ‘Some Theoretical Aspects of Road Traffic Research’. In: Proceedings, Institute of Civil Engineers II, 1, pp. 235–278. [14] Xiang, Y. and M. J. Smith: 1998, ‘A General Equilibrium Model, Solution Algorithms and Convergence Results’. Paper presented at the First International Transportation Symposium, Newcastle.
Chapter 8 FIRST ORDER MACROSCOPIC TRAFFIC FLOW MODELS FOR NETWORKS IN THE CONTEXT OF DYNAMIC ASSIGNMENT J.P. Lebacque
[email protected] CERMICS-ENPC, France
M.M. Khoshyaran TASC Consultant, USA
Abstract
1.
The purpose of the paper is to adapt the classical LWR (Lighthill-WhithamRichards) model, in its continuous version, to networks, in the context of dynamic assignment. This implies several specific adaptations of the basic model: introduction of partial flows, possibly inhomogeneous flows on links, and intersection modeling. The latter proves particularly difficult, and we discuss three different modeling approaches: extended versus pointwise intersection models, and flow maximization. We show that all three types of models are actually closely related, and compatible with the link flow models. The concepts of local traffic supply and demand prove to be essential, both for link and for intersection modeling. A brief comparison with experimental merge data gives some support to the phenomenological models introduced in the paper.
Introduction
Modeling traffic flow for dynamic assignment is a difficult task, because a compromise has to be struck between conflicting imperatives. The model should be realistic, accomodate partial flows, be suitable for large networks and at the same time be very simple in order to be compatible with intensive numerical computation. The general trend in traffic models for dynamic assignment has been one of increasing sophistication, starting with the simple exit function models [23], moving on to travel time function models [7], [25], point queue models [11] and finally macroscopic models ([20], [12], [6], [27], [2], [1]). 119
M. Patriksson and M. Labbé (eds.), Transportation Planning, 119–140. © 2002 Kluwer Academic Publishers. Printed in the Netherlands.
120
TRANSPORTATION PLANNING
These macroscopic models rely on the discretization of their basic equations, and on heuristics for the intersection description. It is therefore very difficult to obtain for instance optimality conditions for assignment problems with such macroscopic models. This has only been attempted in the simplest of cases [9]. The object of the proposed paper is, in the case of the simpler LWR (LighthillWhitham-Richards [21], [26]) model, to provide a general methodology for a rigorous description of networks in the context of dynamical assignment. Our choice of the LWR model is justified by: its simplicity, the availability of nontrivial analytical solutions, the absence of inconsistent features ([4]). The outline of the paper is the following. After recalling the basic LWR model and introducing the local traffic supply and demand concept, we describe boundary conditions and link models for partial flows, i.e. flows disagregated according to some attribute. We then proceed to intersection modeling, beginning with the so-called zone model in which the physical extension of the intersection is taken into account. By neglecting the dimension of the intersection, we can deduce pointwise intersection models. These can be shown to result also from some flow-maximization principle. We conclude with a brief comparison between model prediction and experimental data in the case of a simple merge.
2.
The basic model LWR model for a link The basic LWR model can be writen as:
or simpler as:
with
the flow, K the density, V the speed,
resp. speed-density relationships and denote position and time. The aspect of
and
the equilibrium flow-
As usually, is the following:
121
Macroscopic flow models
In the sequel we only consider the continuous version of the LWR model. The classical calculation of the analytical entropy solution of this equation is wellknown and need not be recalled here, the discretization of this equation relies on the Godunov scheme [8] (ch 3), [3], [15]. The following questions must be addressed in order to extend this basic model to networks and to assignment problems: define proper boundary conditions for links, modelize intersections with emphasis on their relationship with link boundary conditions, introduce partial densities and flows into the link and intersection models. Following [15], let us introduce now the equilibrium supply and demand functions, which are functions of the density and the position
(the symbols + and - representing right- and left-hand limits). The following illustration describes these functions.
Then we define the local supply and demand
and
which represent respectively the greatest possible inflow and outflow at point It can be shown that the entropy solution of the LWR model satisfies the natural condition:
122
TRANSPORTATION PLANNING
(the flow as the minimum between upstream demand and downstream supply). The formula (2.5) would be trivial, but for the circumstance that it is valid at all discontinuity points, whether related to density (shock-waves), or to the equilibrium flow-density function (boundary conditions, incidents, intersections). The importance of the local traffic supply and demand concept stems from this fact. Supply and demand are the basic tools required to describe discontinuities. Boundary conditions express themselves trivially in terms of local supply and demand. Let us consider a link such as the following:
the boundary data is clearly the downstream supply at extremity and the upstream demand at extremity These quantities, combined with the link traffic supply and demand, yield the link inflow and link outflow according to:
Thus: An intersection model should therefore provide adequate supply values to the upstream links of the intersection, and demand values to links downstream of the intersection.
3.
Partial flow models for links
For assignment models, the flow has to be disaggregated according to some assignment attribute d (destination, path, vehicle type, information availability). Let us denote the flow, density and speed of vehicles d (the partial flows, densities and speeds). Trivial equations for partial flows are:
which must be supplemented with a behavioral equation for
3.1.
A FIFO partial flow model
The simplest possible model of partial speeds is the FIFO model:
123
Macroscopic flow models
which will be privileged in dynamic assignment models. composition coefficients:
Introducing the
it follows that and the following advection equation results for the composition coefficients:
This equation means that the traffic composition remains constant along a trajectory. Notably, if is the travel time experienced by the user entering the link at time the following equations holds for compositions: which shows that, under the FIFO hypothesis, the present composition of the link exit flow is determined by the composition of the link inflow at some past instant. This is a very important fact because it implies strong constraints on intersection models. The reader is referred to [1] and [16] for the numerical computation of the variables T and which all satisfy advection equations.
3.2.
Local assignment models
The problem we consider here is that vehicles may have restricted access to lanes according to some assignment attribute d. Let I be the set of lanes, the set of lanes accessible to vehicles the maximum density of lanes the density of vehicles in lanes Then are the unknowns of the lane-assignment problem and are subject to the following constraints:
Implicitly The
if The constraints express the split of constraints express that the total density
into the in lane
cannot exceed the maximum density of this lane. The constitute the dynamic data (analogue to OD data in classical deterministic assignment on networks problems) and the and constitute the geometric data of the lane assignment problem. The unknowns can be determined by solving either:
124
TRANSPORTATION PLANNING
(Wardrop user optimum), or:
(Wardrop system optimum), subject to constraints (3.4) in both instances. The lane assignment resulting of (3.4), (3.5) is such that the speed of vehicles is maximal in lanes such that and identical in all those lanes. This fact can be easily checked by writing the Karush-Kuhn-Tucker (KKK) necessary optimality conditions for (3.4), (3.5), which are also sufficient in this case, and using the property of of being a decreasing function. The formulation (3.5) is actually an analogue of the Beckman transformation, which is hardly surprising: the problem is one of assignment between lanes. Specifically, (3.5) realizes locally (at each location and instant) a user (Wardrop) optimum in which the inverse of speed replaces path travel times or costs, and lanes replace paths. The model [5] appears as a special case of the model (3.4), (3.5), with two lanes two vehicle types and The lane assignment resulting of (3.4), (3.6) is such that the wave speed of vehicles is maximal in lanes such that and identical in all those lanes. By definition the global flow is maximized locally, which would correspond to an entropy-like solution in which transient dynamics in the traffic flow are neglected. To use once more the analogy between static deterministic assignment on networks and assignment between lanes, (3.6) could be viewed as yielding locally system optimal solutions to the lane assignment problem. Only field experiments would allow to choose between models (3.5) or (3.6), the difference between the two being essentially a difference in user behavior. Both models might well be correct, under different conditions. At this point, to the authors knowledge, no proper boundary conditions have been stated for the lane-assignment model.
3.3.
Supply-Demand models
These models are based on ideas sketched in [14] and [1], and developed in [15]. They generalize formulas (2.4), (2.5) and (2.6). The principle is to calculate partial supplies and demands for all superscripts and to determine the corresponding partial flows by comparing partial demands to partial flows. Partial demands are defined as:
which is the usual FIFO-like model (partial demands proportional to the compositions). The partial supply model really defines the user behavioral model.
125
Macroscopic flow models
Let us first define coefficients which determine the maximum density (i.e. of the lanes available to vehicles d. If we refer to the notations of the preceding subsection,
We propose the following two models for the partial supplies: Model 1: Model 2:
(linear model), (homogeneous section model).
Recall that is the total supply, and is the equilibrium supply function at location Model 1 is extremely simple but allows to exceed Model 2 does not have this drawback but still does not take partial flow overlapping into account as precisely as the lane-assignment models of the preceding section, since the data formed by the sets and the coefficients has been simplified and only coefficients are left. It would also be natural to define the partial flows as:
Nevertheless, since
is usually > 1 (because of the partial flow overlap-
ping), it is possible that partial flows calculated according to (3.8) satisfy:
thus implying a model inconsistency. In keeping with the idea of constructing entropy solutions, we propose to calculate the partial flows as solutions of the following program:
with
some concave increasing functions. For instance, with:
the KKT optimality conditions for (3.9) result in the following expression for the partial flows:
126
TRANSPORTATION PLANNING
and the total flow is then given by:
It should be noted that although (3.10) yields a relatively simple closed form for the partial flows, it does not constitute an entirely satisfactory model since the functions thus defined are not intrinsic. They depend on the local partial supplies and demands instead of the local geometric attributes such as the or the maximum flow. As such, model (3.10) is a purely ad hoc phenomenological model. The idea behind the choice (3.10) and the resulting expressions (3.11) is that: the partial flows
should be equal to their natural values, the quantities whenever possible, i.e. provided that the total flow does not exceed the total supply,
the partial flows natural values
should be as large as possible and proportional to their otherwise.
The supply-demand models of the present subsection provide natural boundary conditions: partial supplies and demands, which are fully compatible with network modeling. Another remark: all models of this section yield systems of conservation laws, the solutions of which have the usual properties (families of characteristics, Shockwaves ... ).
3.4.
Other models
A few other models exist in the literature. We may cite [22], which relies on a linear relaxation-type interaction between lanes. Another example is [10], although this last model constitutes a discretization of the LWR model only in a very loose sense.
4. 4.1.
Intersection modeling Exchange zones
Macroscopic modeling of intersections is difficult, since macroscopic models are based on the continuum hypothesis, i.e. the assumption that the traffic flow can be described by the macroscopic functions K, V. This assumption is only valid at a sufficiently large space and time scale, say 50 to 100 meters as far as the space scale is concerned, which exceeds the size of most intersections. The basic difficulty in modeling an intersection is that various movements may occupy the same physical location. Two answers are possible: consider overlapping cells (the SSMT solution, [13] and [6]) or consider exchange
127
Macroscopic flow models
zones [1], in which movements overlap, and the details of this interaction are accounted for by global zone behavioral functions. Basically, an exchange zone is similar to a cell or segment (as in the Godunov scheme), but has multiple entry points and exit points and the following dynamic variables: point
the number of vehicles having entered the zone through entry exiting it through exit point the number of vehicles having entered the zone
through entry point the number of vehicles about to exit the zone through exit point the total number of vehicles of the zone, all of which, if need be, can be disaggregated according to some assignment attribute The mixing of movement flows in the zone is described by global zone supply and demand equilibrium functions, defined as link equilibrium functions, with the difference that their argument is N instead of and for a zone These functions yield the global zone supply and demand:
The zone dynamical variables are calculated by simple conservation relationships, for which the following ingredients are necessary: zone inflows zone outflows assignment coefficients and inflow composition. The inflows are obtained by comparing the zone partial supplies and demands to the upstream link (or zone) demands and downstream supplies in the usual way. The only difficulty is to deduce the zone partial supplies and demands from the available zone variables, which constitute the behavioral component of the model. For the partial demands, we
128
TRANSPORTATION PLANNING
recommend the following FIFO-like model:
Other models are possible (see [17]). For partial supplies, several models are possible depending on driver behavior. Hereafter we give three examples, relying on so-called supply-split coefficients equal for example to the relative number of lanes available in the zone for traffic entering through entry point model 1:
(linear model),
model 2: model 3: ual storage capacity).
(homogeneous zone model), (partial supply proportional to resid-
For complex intersections, several zones may be required, for simpler ones, such as merges and diverges, a simple zone is sufficient. All these partial supply and demand models rely on global zone supply and demand, which recapture the global behavior of the zone. The dynamic equations of traffic in a zone are given by:
with the assignment coefficients of the zone. is the proportion of users entering the zone through entry point at time and exiting it through exit point The above formula also relies on the usual asumption on the composition of the exit flow, supposedly the same as that of the zone itself. The outflows are given by
and the inflows are given by :
a formula similar to (3.11), and based on the same idea. Specifically, the inflows should be as great as possible, considering the total inflow, should be less than the zone supply. The inflows should also be proportional to their “natural values”
Macroscopic flow models
4.2.
129
Pointwise models
Of course, to solve complex optimization problems related to dynamic assignment, these zone models are far too complicated and expensive in terms of computational requirements. A drastic simplification can be obtained by considering pointwise intersections. For instance in [2], pointwise merges and diverges were considered. In this section we adopt the following approach: we consider the intersection as a single zone, and study the limiting case in which the dimension of the zone is neglected. This way, part of the physical properties of the intersection, such as they are described by the zone equilibrium supply and demand functions and the supply and demand split coefficients, are carried over in a consistent way to the pointwise model. In order to calculate the zone supplies and demands say and in this case, as a function of upstream demands and downstream supplies the best approach is to calculate a stationary state of the zone, by considering the upstream supplies and downstream demands as constant. This means we consider the time-scale of the variation speed of upstream demand and downstream supply as infinitely large in regard to the variation speed of variables internal to the zone. Such an approach was applied successfully for the study of moving singularities in [19]. 4.2.1 Stationary solution of zone dynamics: the case of a merge. Let us consider the following merge:
and the simple linear supply split model giving the partial supplies: We shall consider only a stationary, i.e. a time-independent solution of the zone dynamics, for stationary data (downstream supply) and (upstream demands). We shall denote the maximum flow through the intersection, as resulting from the zone equilibrium functions. The main internal unknowns are the total number N and partial numbers of vehicles in the zone, but the main unknowns from the point of view of the intersection workings are the inflows and the total outflow The total zone supply and demand are given by:
130
the total zone inflow
TRANSPORTATION PLANNING
and the zone inflows
are given by:
and the total zone outflow is given by:
The equilibrium of the zone can be expressed by the following: and the partial numbers actually result from the partial inflows (at equilibrium): Therefore the only effective unknown is N. Now and are respectively concave decreasing and increasing functions of N, with Further, if N = 0, and and if (storage capacity of the zone). The existence of a solution results immediately. Supply Regime. This regime is characterized by is given and that concave and piecewise linear function of
The greatest possible value of regime is:
The equation yielding
being
and It follows that can be represented as an increasing which has the following aspect.
the validity domain of the supply
131
Macroscopic flow models
can be solved by a Newton-like algorithm in O(I), with I the number of zone entry points which is described in detail in [18]. The algorithm is straightforward by virtue of the piecewise linearity of Demand Regime. This regime is characterized by and resulting from (4.3) with is given and that concave and trivially piecewise linear function of
It follows that is an increasing
The unknown is now which is determined by the equation: which admits a solution iff:
This last condition constitutes the validity range of the demand regime. Let us summarize these results:. and
results from (4.6), if the supply regime (4.5) applies.
and results from the equation demand regime (4.7) applies.
if the
global supply and demand, and the various flows are given by (4.2), (4.3) and (4.4). 4.2.2 Stationary solution of zone dynamics: the case of a diverge. Let us consider the following zone, modelling a diverge
The data are the downstream supplies and the upstream demand the total capacity of the diverge is the assignment coefficients are and the basic unknowns are the total number of vehicles N and the partial numbers All dynamic quantities, including of course the data, are assumed here to be stationary. As usual, the partial zone demands are given by the FIFO-like model: where we introduce the zone composition coefficients
132
TRANSPORTATION PLANNING
These coefficients satisfy the constraints:
The inflow is given by and the outflows are given by Supposing now that the flow in the upstream link satisfies the FIFO rule, it follows that the zone inflow has composition thus yielding the following stationarity conditions:
The unknowns are N and the Supply Regime. It is characterized by:
and the data the
and
and the
Hence:
The outflows are proportional to the assignment coefficients which are generically independent from the downstream supplies This observation is the key to the resolution. Let us define:
Generically, or as shown in [18]. The case is obviously a limit case of the demand regime, and will not be considered anymore. Let us consider that which determines the outflows which yields the validity range of the supply regime:
The solution is given by:
Demand Regime. It is characterized by and the zone equilibrium conditions are and All these quantities can be deduced from the data. The equilibrium condition at each zone exit point is:
133
Macroscopic flow models
with unknowns
The above equilibrium condition implies that:
thus yielding the validity range of the demand regime. An argument similar to the one applied for the supply regime shows that:
This completes the analysis of the demand regime.
5.
Intersection models as solutions of optimization problems
Other models can be built according to a slightly different concept, which is the following. One way to express the nature of the entropy solution is to maximize flow, which then appears as the minimum of the upstream supply and downstream demand. This is the concept we extended to intersections by introducing partial supply and demand models in the intersection. Another way to recapture the concept of an entropy solution at intersections would be to maximize some concave increasing flow function, subject to supply and demand constraints. As usual, this means that transitory states, in the present case both inside and around the intersection are neglected. For instance in the case of a merge, with upstream demands and downstream supply as depicted hereafter,
we could find the flows
by considering the following problem:
with concave increasing functions describing the behavior of users at the intersection. The constraint could include the maximum throughflow of the merge, by replacing by if need be.
134
TRANSPORTATION PLANNING
Let be the KKT coefficient of the
with otherwise
constraint. It follows:
a decreasing function. If
then
results from the following equation:
The right-hand-side of that equation being a monotone increasing function in the numerical resolution is trivial. Now, let us consider the specific function
with split of the supply merge. If
The coefficients describe as usual the according to the linear model, i.e. the geometry of the then and
Otherwise, the equation yielding
becomes:
It follows:
is smaller than and thus equal to summarized by the single formula:
Both solutions can be
As already mentionned, an obvious drawback of these functions is that they are not intrinsic but depend on the data and of the problem. The above solution (5.1) is of course similar to (3.11), but also to (4.3) which were obtained by a very different approach. Let us note nevertheless that in formula (4.3) the downstream supply is replaced by the equilibrium zone supply which is the solution of (4.5), i.e.:
and therefore greater than for large supply values, and equal to for small supply values. The above model (5.1) is slightly different in this respect from the stationary zone model (4.3).
Macroscopic flow models
135
A similar optimization problem can be considered for the diverge problem
Let us denote as usual the downstream supplies, the upstream demand, the diverge outflows, and the assignment coefficients. We shall also denote the total diverge inflow. We would try to optimize some function:
subject to supply and demand constraints, with the concave increasing functions. The supply and demand constraints are trivial:
In order to complete the model we have to relate the total diverge inflow to the diverge outflows which is to say we have to complete the behavioral part of the model. The simplest possibility is to assume FIFO behavior of upstream vehicles. This would be the case if the upstream link has only one lane, or no preselection lanes. It follows:
and the constraints can be reduced to:
The resulting optimization problem admits the following solution, considering that the functions are increasing:
This model was already obtained with the stationary zone model of 4.2.2. It is also similar to the discretized diverge model of [3]. A non FIFO model can be obtained by assuming that the outflow constraints should be:
136
TRANSPORTATION PLANNING
expressing that the coefficients are demand composition coefficients. Such a behavioral model requires a non FIFO flow model for the upstream link, such as the lane assignment or the partial supply/demand models. The resulting constraints are and the (trivial) solution of the corresponding optimization problem is, (since the functions are increasing):
For the diverge models we have seen, the main behavioral elements are the demand split coefficients and models, the assignment coefficients and the type of upstream flow, FIFO or non FIFO. It should also be noted that the solutions (5.2) and (5.3) do not depend on any specific choice of the functions. The different macroscopic approaches to intersection modelling we have developed in the present paper appear to be consistent. The pointwise models of subsection 4.2 result from the zone models at the vanishingly small timespace scale limit, and yield formulas similar to the flow maximization models of the present subsection. For practical purposes, the simpler flow optimization approach should therefore be preferred in most cases. Another interesting point: the models developed in this section are completely consistent with the supply-demand link flow models.
6.
An experimental validation
In this section we shall interpret some experimental obtained and analyzed by Oltra and Jardin [24]. The several experimental sites these authors considered were all of following the merge type:
and the traffic conditions were oversaturated. The authors made experimental observations of the flows and and tried to calculate linear relationships between these flows through linear interpolation of the data. In order to validate the merge model developed in section 5, we assume a linear supply split model with coefficients chosen as the ratio between the number of lanes of the upstream link and the downstream link. Assuming one of the links to be oversaturated, the following inequalities result (see [18], an expanded version
137
REFERENCES
of the present paper, for details):
and, if both links
are oversaturated, the following identity results:
The deterministic scatter predicted by the model is the expression of a hidden variable: the demand upstream of the link that is not oversaturated. This prediction fits the data much better than the linear relationships considered by the authors. The following figure illustrates the data points as compared to the model predictions:
7.
Conclusion
We have shown that the LWR model can be extended to networks. There is no unique extension, even by sticking to entropy solutions: indeed, user behavior plays a major role both in link modeling (FIFO behavior should be assumed or not depending on infrastructure and traffic management) and in intersections, in which it determines how upstream demand and downstream supply interact. The discretization of the models described in this paper is trivial and in some cases available ([1]), but the investigation of analytical solutions is yet to be done even in the simplest cases. Further, little field evidence is available at this point as far as intersection modeling goes. There is some support for the split-demand and split-supply intersection models [24], as we have seen, nevertheless experimental validation should be an essential objective for future investigations.
References
138
TRANSPORTATION PLANNING
[1]
C. Buisson, J.P. Lebacque, J.B. Lesort, H. Mongeot “The STRADA model for dynamic assignment”. Proc. of the 1996 ITS Conference. Orlando, USA. 1996.
[2]
C.F. Daganzo, “The cell transmission model 2: network traffic simulation”. Transportation Research 29B. 2: 79-93. 1995.
[3]
C.F. Daganzo, “A finite difference aproximation of the kinematic wave model”. Transportation Research 29B. 261-276. 1995.
[4]
C.F. Daganzo, “Requiem for second order fluid approximations of traffic flow”. Transportation Research 29B. 277-286. 1995.
[5]
C.F. Daganzo, “A continuum theory of traffic dynamics for freeways with special lanes”. Transportation Research 31 B. 83-102. 1997.
[6]
E. Elloumi, H. Hadj Salem, M. Papageorgiou, “METACOR, a macroscopic modelling tool for urban corridors”. Proc. of the TRISTAN II Int. Conf.. V1, 135-149. Capri. 1994.
[7] T.L. Friesz, D. Bernstein, T.E. Smith, R.L. Tobin, B.W. Wie, “A variational inequality formulation of the dynamic network user equilibrium problem”. Operations Research 41, 179-191. 1993. [8]
E. Godlewski, P.A. Raviart, “Hyperbolic systems of conservation laws”. SMAI. Ellipses (Paris). 1991.
[9]
B.G. Heydecker, J.D. Addison, “Analysis of traffic models for dynamic equilibrium traffic assignment, in “Transportation networks: recent methodological advances” (M.G.H. Bell ed.). 35-50. Pergamon. 1997.
[10] M. Hilliges, “Ein phänomenologisches Modell des dynamischen Verkehrsflusses in schnellstraßennetzen”. PHD dissertation. Institut für theoretische Physik der Universität Stuttgart. Shaker Verlag. 1995. [11] M. Kuwahara, T. Akamatsu, “Decomposition of the reactive dynamic assignments with queues for a many to many origin-destination pattern.” Transportation Research B. B 31, 1-10. 1997 [12] R. Jayakrishnan, H.S. Mahmassani, T.Y. Hu, An evaluation tool for advanced traffic information and management in urban networks”. Transportation Research C, C2: 129-147. 1994. [13] J.P. Lebacque, “Semimacroscopic simulation of urban traffic”. Proc. of the Int. 84 Minneapolis Summer Conference. AMSE. V4, 273-291. 1984. [14] J.P. Lebacque, “L’échelle des modèles de trafic, du microscopique au macroscopique”. Annales des Ponts, 74. 48-68. 1995. [15] J.P. Lebacque, “The Godunov scheme and what it means for first order traffic flow models”. Proc. of the 1996 ISTTT(J.B. Lesort ed.). 647-677. 1996.
REFERENCES
139
[16] 1. J.P. Lebacque, “Instantaneous travel times for macroscopic traffic flow models”. CERMICS Report 59-96. 1996. 2. C. Buisson, J.P. Lebacque, J.B. Lesort, “Travel times computation for dynamic assignment modelling”, in “Transportation networks: recent methodological advances” (M.G.H. Bell ed.). 309-319. Pergamon. 1997. [17] J.P. Lebacque, “Rapport du Contrat LICIT-CERMICS 1997”. 1997. [18] J.P. Lebacque, M.M. Khoshyaran. “First order macroscopic traffic flow models for networks in the context of dynamic assignment.” CERMICS Report. To be Published. [19] J.P. Lebacque, J.B. Lesort, F. Giorgi, “Introducing buses into first order macroscopic traffic flow models”. Transportation Research Record 1644: 70-79. National Academy Press. 1998 [20] D.R. Leonard, P. Gower, N.B. Taylor, “CONTRAM, structure of the model”. TRRL Report RR 178. Crowthorne (U.K.). 1989. [21] M.H. Lighthill, G.B. Whitham, “On kinematic waves II: A theory of traffic flow on long crowded roads”. Proc. Royal Soc. (Lond.) A 229: 317-345. 1955. [22] P.G. Michalopoulos, D.E. Beskos, Y. Yamauchi. “Multilane traffic flow dynamics: some macroscopic considerations”. Transportation research 18B, 377-395. 1984. [23] D.K. Merchant, G.L. Nemhauser, 1. “A model and an algorithm for the dynamic traffic assignment problem”. 2. “Optimality conditions for a dynamic assignment model”. Transportation Science 12: 183-199 & 200-207. 1978 . [24] C. Oltra, P. Jardin. “Etude des écoulements de trafic sur les voies rapides pendant la congestion”. RTS 54. 3-14. 1997. C.Oltra, “Etude des écoulements de trafic sur les voies rapides pendant la congestion: approche macroscopique”. Rapport de DEA. ENPC - Université Paris XII. 1994. [25] B. Ran, D.E. Boyce, “Modeling dynamic transportation networks”. Second revised edition. Springer Verlag. 1996. [26] P.I. Richards, “Shock-waves on the highway”. Op. Res. 4: 42-51. 1956. [27] M. Van Aerde, “INTEGRATION: A model for simulating integrated traffic networks”. Transportation Systems Research Group. Queen’s University, Kingston, Ontario. 1994.
Chapter 9 AIMSUN2 SIMULATION OF A CONGESTED AUCKLAND FREEWAY
John T Hughes
[email protected] Regional Transportation Engineer Transit New Zealand, P. O. Box 1459 Auckland, New Zealand
Abstract
The Spanish AIMSUN2 microscopic traffic simulation package is being used to model a 9.7 km section of a congested urban freeway in Auckland, New Zealand. An outline of the model building process is presented along with selected findings. Flow profiles based on field data from a four-hour morning commuter traffic peak have been applied to the modelled network. Preliminary results show that modelled speed and flow relationships realistically reproduce those found in field data from the freeway. Exact reproduction of transient effects, such as timevarying lane utilisation ratios and queue lengths have not been fully achieved in the model. Further investigation into appropriate values for sensitive lane-change parameters are expected to improve this aspect of the model’s performance.
1. Introduction and objectives The objective of this paper is to present an outline of the model building process and selected findings