|
Multicriteria Equilibrium Traffic Assignment Basic Theory and Elementary Algorithms - Part I - T2: The Bicriteria Model
Click HERE for graphic. Abstract T2 is an equilibrium traffic assignment model that forecasts the bicriteria path choices and consequent total arc flows for a stochastically diverse set of trips. Developed around a linear generalized cost model, T2 generalizes classical traffic assignment by relaxing the value-of-time parameter from a constant to a random variable with an arbitrary probability density function. For the case where arc time and/or cost are flow-dependent, this paper formulates conditions and algorithms for stochastic bicriteria user-optimal equilibrium arc flows, which reflect every trip's exclusive use of a path that minimizes its particular perception of generalized cost. Contents 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Overview of the T2 Model . . . . . . . . . . . . . . . . 2 1.3 Path Choice Probability. . . . . . . . . . . . . . . . . 4 1.4 Path Finding Algorithm . . . . . . . . . . . . . . . . . 8 1.5 Traffic Equilibrium. . . . . . . . . . . . . . . . . . . 8 1.6 Contents of this Paper . . . . . . . . . . . . . . . . .12 2 T2 Min-Path Assignment. . . . . . . . . . . . . . . . . . . .13 2.1 The Ground Set x . . . . . . . . . . . . . . . . . . . .13 2.2 Total Generalized Trip Cost. . . . . . . . . . . . . . .14 2.3 T2 Min-Path Traffic Assignment . . . . . . . . . . . . .14 2.4 T2 Min-Path Assignment Algorithm . . . . . . . . . . . .15 2.4. 1 Algorithm Likely Paths . . . . . . . . . . . . . . . .17 2.4. 2 Algorithm T2-MPA . . . . . . . . . . . . . . . . . . .17 3 T2 Equilibrium Assignment . . . . . . . . . . . . . . . . . .19 3.1 T2 Wardrop's Principle (T2-WP) . . . . . . . . . . . . .19 3.2 T2 Equilibrium Traffic Assignment Theorem. . . . . . . .19 3.3 T2 Equilibrium Traffic Assignment Algorithm. . . . . . .21 3.4 Algorithm T2-ETA . . . . . . . . . . . . . . . . . . . .22 3.4. 1 Example 1: Sampled Iterations of T2-ETA . . . . .23 3.4. 2 Example 2: Algorithm T2-ETA . . . . . . . . . . .26 3.5 T1.5 Equilibrium Traffic Assignment. . . . . . . . . . .28 3.6 Algorithm T1.5-ETA . . . . . . . . . . . . . . . . . . .30 3.6 Example 3: Algorithm T1.5-ETA . . . . . . . . . . .32 4 Concluding Remarks. . . . . . . . . . . . . . . . . . . . . .35 4.1 Summary. . . . . . . . . . . . . . . . . . . . . . . . .35 4.2 Additional Research and Development. . . . . . . . . . .35 4.3 Acknowledgements . . . . . . . . . . . . . . . . . . . .37 References 39 iii List of Figures 1 Feasible Paths and gp,(O.43) . . . . . . . . . . . . . . . . 3 2 Efficient Frontier, Likely Path Probabilities . . . . . . . . 5 3 Probability of Using Path 4 . . . . . . . . . . . . . . . . . 6 4 Arc Time vs Arc Flow (BPR). . . . . . . . . . . . . . . . . . 9 5 Arc Attributes at Free-Flow Volumes . . . . . . . . . . . . . 9 6 Value-of-Time Probability Density: Ÿ1,9(). . . . . . . . . .10 7 A T2 Equilibrium Traffic Assignment . . . . . . . . . . . . .11 8 Data Types for All Algorithms . . . . . . . . . . . . . . . .15 9 Likely Paths Algorithm. . . . . . . . . . . . . . . . . . . .16 10 T2 Min-Path Assignment Algorithm. . . . . . . . . . . . . . .18 11 T2-ETA: Equilibrium Traffic Assignment Algorithm. . . . . . .23 12 Ex. 1: Sampled Iterations of Algorithm T2-ETA . . . . . . . .24 13 Two-Arc Equilibrium Example Input . . . . . . . . . . . . . .26 14 Ex. 2: Three Iterations of Algorithm T2-ETA . . . . . . . . .27 15 T1.5-ETA: Equilibrium Traffic Assignment Algorithm. . . . . .31 16 Ex. 3: Three Iterations of Algorithm T1.5-ETA . . . . . . . .33 1 Introduction This paper presents the basic theory and elementary algorithms for a bicriteria user-optimal equilibrium traffic assignment model that forecasts bicriteria path choices of a stochastically diverse set of trips. Called T2, the model generalizes classical traffic assignment by relaxing the value-of-time (VOT) parameter in the generalized cost function from a constant to a random variable, with an arbitrary probability density function (PDF). T2's application potential spans a wide domain of currently difficult problems in traffic, highway and transit planning-including simultaneous mode/route choice, congestion pricing [25] and parking policies. 1.1 Related Work T2's roots are in Quandt [241 and later Schneider [26]; however, this paper develops the model very differently than theirs. Its mathematical programming approach adds generality regarding the value-of time probability density function (PDF) and formulates and solves the bicriteria user-optimal traffic equilibrium problem. The work here extends considerably the short note by Dial [5], which, while on the same subject, addressed only path finding. Besides these ear her papers, this paper builds on the variational inequality work of Magnanti and Perakis [20], presented at the 1994 ORSA/TIMS conference in Boston. It is their work that inspired algorithms T2-ETA and T1.5-ETA. Dafermos [31 addresses T2's equilibrium problem; however, none of her results find use in this paper.1 The insightful work of Leurent [16] merits comment. It shows the French are far ahead of the Americans in using time-cost network models. Leurent's formulation is at once more and less general than T2's. He deals with (linear) elastic demand, while T2 assumes a fixed total trip matrix; however, Leurent only permits one criterion, i. e., time, to be flow dependent, while T2 permits both. Moreover, his Monte Carlo solution approach [27] brings sampling errors, greatly restricts the VOT PDF, and converges glacially compared to T2's algorithm [28]. ___________________________ 1 Although, ironically, this writer in 1079 introduced Stella to the bicriteria problem and helped her to obtain the funding for her paper. 1 Finally, Florian [9] proposes an heuristic that uses a "small set of trip classes" to represent points on the PDF. This approach is an inefficient dead end. Besides risking gross aliasing errors [16] for all but the most simplistic PDFS, it wastes memory. It maintains link flow variables for each "class," thereby shutting out sophisticated but memory-hungry algorithms that can speed convergence or incorporate dynamic assignment. Moreover, these class link flows saved at such high storage cost are not unique, and storing them is tantamount to saving garbage. 1.2 Overview of the T2 Model Combined traffic assignment and mode choice serves as a concrete example to introduce T2. Consider a trip from origin o to destina- tion d. We wish to estimate the mode choice for this trip. Assume for the moment it is possible to enumerate all feasible paths for this trip and to know the time and cost of each. Now plot each path at a point in a graph according to its time and cost. Figure 1 plots these time-cost points for fourteen feasible paths ignore the dashed line for now. The horizontal axis is path time; the vertical axis is path cost. Each path label suggests its so called "mode."2 Helicopter is the fastest and most expensive. Walking is the slowest and cheapest. Gondola is very expensive and very slow. This example begs three general questions: 1. path choice probability: what are the odds that a trip will choose each of these paths? 2. path finding algorithm: how can a computer find these paths without enumerating all zillion feasible paths? 3. traffic equilibrium: how do we model the fact that path times depend on path choices, and vice versa? We introduce these questions now and answer them later. ___________________________ 2 Technically speaking, a mode is a label for a class of paths. The word has no deeper semantics than that. The labels in Figure 1 might represent fourteen classes by a single instance of each. There are several more potential classes and a zillion more instances. 2 Click HERE for graphic. 3 1.3 Path Choice Probability Answering this first question requires knowing how the trip decides among its feasible paths. Assume that a trip chooses a path p that minimizes its perceived generalized cost gp(à), where: gp(ct) = cp + àtp; cp = out-of-pocket ("dollar") cost of path p; tp = time of path p; à E [0, ì) = value-of-time, a random variable. The probability of a trip choosing a certain path depends on that path's time and cost compared to all others'-together with the trip's particular VOT à. Referring again to Figure 1, the dashed line represents the objective function, which a trip with a VOT of $0.43/min aims to minimize. The slope of this line is negative à. The generalized cost gp(à) of path p is the line's intercept with the cost axis. Therefore, for a given à, the best path is the first point that this line touches as it translates from left to right. Figure 1 shows path 4, "car/tollroad", is a trip's best choice if à = 0.43. If the dashed line had a different slope, then path 4 might not be the best path. Refer now to Figure 2. Whatever the slope à the only paths with any chance of selection are 1 through 6 those shown delimiting line segments. Among all feasible paths, only these six have a generalized cost (GC) that could be the minimand of a linear function of à. The line segments that connect such path points, in decreasing sequence by path time, form the efficient frontier (EF). Points where the EF changes direction are called extreme points. As we shall see momentarily, in the case of a continuous VOT PDF, only paths forming extreme points represent rational path choices. In any case, every path off the EF is dominated by some other path with smaller time and cost. 4 Click HERE for graphic. 5 Click HERE for graphic. 6 Thus, Figure 2 reveals how to compute the probability of using a path. For example, consider path 4, the toll road in Figure 3(à), which details the neighborhood of path 4 in Figure 2. Assume that the line segment connecting path 5 and path 4 has a slope of -2.8, and the line segment connecting path 4 and path 3 has slope -1.2. Then, path 4 will minimize any GC whose VOT is between 1.2 and 2.8. Hence, the probability of selecting path 4 is the probability that the random variable à is between these values. For example, if the probability density of à for trips going from o to d is fod(), then as Figure 3 shows, the probability of using path 4 is 0.63. In general, because the generalized cost is a linear function of à, the probability of using a path off the EF is zero, while for a path p on the EF: Click HERE for graphic. Where ap is the slope of the line segment connecting p to its right neighbor on the EF, and bp is the slope of the segment connecting p to its left neighbor. Note that ap = 0 for the cheapest path, and bp = ì for the fastest path. Any path that might be used we call likely, all other paths we call unlikely. Technically, likely paths have a non zero probability of use; unlikely paths have a probability of zero. A likely path is always on the EF; however, being on the EF does not guarantee a path is likely. For a continuous PDF, a likely path is always an extreme point on the EF. Any path not having distinct bounding à's is an unlikely path-whether on the EF or not. In the case of a continuous PDF, for Prob[p) to be greater than zero, bp must be strictly greater than ap, The table inset in Figure 2 lists the probabilities for Figure 2's likely paths; all other, unlikely paths have probability zero. In the case of a discrete (non differentiable) PDF, other paths on the EF are equally likely, and entropy considerations [15] dictate that any path with a minimum GC merits an equal share of trips; we ignore this consideration for now.3 ___________________________ 3 The all-min-paths algorithm described) in 4 can be applied in T2. 7 1.4 Path Finding Algorithm By considering likely paths only, we reduce an otherwise daunting challenge to a practical chore: of all the paths connecting o to d, we need to find only those few that shape the EF. Presuming that a path's cost and time are the sums of the cost and time of the path's arcs, then the GC of a path is just the sum of the GC of its arcs. Consequently, finding these likely paths can be easy. Each likely path p on the EF minimizes gp(à) for some à. Let the GC of an arc e be the of its cost plus à times time: ge = ce + àte. If we label each arc with its ge, for a fixed à and find the minimum GC path, that min-GC path will be on the EF. Thus, to find the EF is equivalent to finding min-GC paths for an appropriate set of à's. Remarkably, the computational complexity of an algorithm that finds all likely paths, is the same as one that finds a single min-GC path. This latter algorithm is virtually a standard min-path routine its only complication is tie-breaking-to guarantee extreme- point paths on the EF. The former algorithm derives directly from [6]; Section 2 provides details. 1.5 Traffic Equilibrium A traffic assignment model accumulates trips for all o-d pairs on each arc comprising their connecting path. When all trips use a min-GC path, we call the result a user-optimal traffic assignment. When arc times are fixed, a single min-path (a.k.a., "all-or- nothing") assignment performs this calculation by assigning each trip to its min-GC path. However, arc times may change, depending on how many trips use the arc-which in turn depends on arc times. The solution to this circular problem has the name traffic equilibrium. All classical traffic assignment methods permit only a single, fixed VOT à: they presume the perceived GC of a path is to all trips identical. In contrast, T2 assumes different trips perceive the same path as having different GCs by virtue of different VOTs. It represents these differences in a by user-supplied probability distributions. T2's generalization of Wardrop's principle [30], states that each trip uses only paths that minimize their particular perceived GC. A simple example makes this clear. 8 Click HERE for graphic. Click HERE for graphic. Figures 4-7 show an example of T2 equilibrium in a nine-node grid network, a single o-d pair, and a simplistic three-spike VOT PDF. The network is in Figure 5. All arcs are two-way and of length (d) one mile. The eight peripheral arcs are free roads; the four interior arcs are toll roads costing $5.00. Figure 4 shows the time-flow (BPR) curves of the network's two arc types, toll arcs having higher practical capacity (k) and speed limit (s) than free arcs. 9 Click HERE for graphic. Figure 6 is the VOT PDF, consisting of three spikes, at $0.10, $1.00, and $2.00 per minute and corresponding volumes of 800, 2400, and 800 trips. All trips go from node 1 to node 9. Figure 7(a) shows the associated T2 equilibrium flow. It labels each arc with an integer representing the total number of trips on the arc and a decimal number indicating the arc traversal time. For example, arc (1,2) has 2000 trips and requires 34.00 mins. Figure 7(b) shows an example of the component of the total flow that represents trips with VOT of $0.10/min. The dashed lines indicate unused arcs. The labels on the arc show trips and generalized cost. Note that all used paths from node 1 to node 9 have the same generalized cost, which is less than that of all unused paths: trips with VOT $0.10/min are in equilibrium. As seen in Figures 7(c) and (d), the same is true for the trips with VOT $1.00 and $2.00. Figures 7(b)-(d) sum to those in 7(a). Note however that unlike the latter, these former flows are not unique: any reallocation of individual flows among their min-GC paths that summed to the same total in Figures 7(a) would also be in equilibrium for every individual VOT classes. For example, if in Figure 7(b) 413 trips shift from path 1-2-3-6-9 to path 1-4-7-8-9, while at the same time in Figure 7(c), 413 trips make the opposite shift; the result is another equilibrium flow. The total arc flows would be the same, but individual arc flows for VOTs $.01 and $1.00 would differ enormously. 10 Click HERE for graphic. 11 1.6 Contents of this Paper The next two sections of this paper provide theoretical justification and algorithmic detail for the claims and procedures introduced above. Section 2 covers T2 min-path traffic assignment, which incorporates VOT as a random variable. It develops a model and algorithm for loading trips with a stochastic value of time on a network whose the arc times and costs are fixed. Building on the concepts introduced in prior sections, Section 3 develops mathematical theory and algorithms for bicriteria equilibrium traffic assignment for trips with an arbitrary VOT PDF whose arc costs and/or times vary with flow. The final section of this paper briefly addresses a few proposed T2 R&D topics then ends the paper acknowledging people who helped produce it. 12 2 T2 Min-Path Assignment Given a set of paths connecting all origin-destination o-d node pairs and given a trip matrix, which specifies the number of trips between each o-d pair, a traffic assignment algorithm simply accumulates on each arc the trip volume of every path using that arc. The output of a traffic assignment algorithm is this vector x of accumulated arc flows, which we call a traffic assignment.4 Depending on the paths the trips use, the vector x has many possible values. 2.1 The Ground Set X We call the set of all possible traffic assignments for a fixed trip table the ground set X. Let Click HERE for graphic. T2 is analogous to the classical model; however, to introduce the random variable à, it augments the variables and constraints defin- ing the ground set X with the following: Click HERE for graphic. ___________________________ 4 This paper uses the term traffic assignment to denote not a process but a state: a vector of arc flows - a decision variable. 13 Click HERE for graphic. For T2 the ground set becomes X = {(xe(à)) ò 0³equations (2) through (5) satisfied}. 2.2 Total Generalized Trip Cost A very useful statistic describing a traffic assignment xîX is its total generated trip cost G(x\c,t), which is the sum products of each trip times the GC of the path it uses - assuming arc costs and times are fixed at c = (ce) and t = (te): Click HERE for graphic. 2.3 T2 Min-Path Traffic Assignment If arc cost and times are fixed at c and t, then a T2 min-path traffic assignment y is a flow that reflects each trip taking its particular min-GC path. This which would minimize the total generalized trip cost: y = arg min G(x\c,t). xîX Because c and t are fixed, the right-hand side of (6) is separable in à, and a T2 min-path traffic assignment certainly results from assigning all trips with the same o-d and à to a feasible min-GC path p* that for each trip's specific à, minimizes gp (à) = ä ce + à ä te (7) eîp eîp 14 Lemma 2.1 For any traffic assignment x î X, G(x\c,t) = ô ä(ce + àte)xe(à)dà (8) õà e Proof. Obvious Corollary 2.1 Flow y is a T2 min-path traffic assignment iff y = arg min ô ä(ce + àte)xe(à)dà (9) xîE õà e That is, loading min-GC paths minimizes (9). Therefore, loading min-paths is the sine qua non of any traffic assignment procedure. For T2 this means loading likely paths, as discussed in Section 1. 2.4 T2 Min-Path Assignment Algorithm We now present formal algorithms to this end. The following two subsections are informal descriptions, which summarize the formal definitions in Figures 8-10.5 type Net data describing network Node Set N nodes in network Arc Set E arcs (i,j) in network type Path data for min path p* (for VOT à) VOT à value of time used to find p* Cost c cost of min path: cp* Time t time of min path: tp* GC G GC of min path: gp* = cp* + àtp* type Trips Set data describing trip matrix Node o origin Node d destination Flow v number of trips from o to d Figure 8: Data Types for All Algorithms ___________________________ 5 In Figure 10, ignore for now references to variables u and uo and the function H(). They concern T2 equilibrium traffic assignment and are explained in Section 3. 15 Click HERE for graphic. 16 Compared to the classical model, a min-path assignment algorithm for T2 is more involved. Each o-d pair may have several distinct min-GC paths depending on the value of a. Each path must receive its fare share of trips, and the sum of the flow on each path must be the given vod. Algorithm T2-MPA executed for each o-d yields a T2 min-path traffic assignment. Algorithm Likely Paths finds the paths to lead. 2.4.1 Algorithm Likely Paths The following procedure finds all likely paths and determines the exclusive range of à for which each path is optimal. see Figure 9. 1. [cheapest path] Let ào = 0 and solve this min-GC path problem; this finds the cheapest path - path 1 in Figure 2. 2. [fastest path] Let ào = ì and solve this min-GC path problem; this finds the fastest path - path 6 in Figure 2. 3. [between paths] Let ào be the slope of the line connecting paths 3. [between paths] Let ào be the slope of the line connecting paths 1 and 6, and solve this min-GC path problem; this finds path 4. Now consider the two line segments connecting path 1 with 4, and path 4 with 6; their slopes find paths 5 and 3. Continue recursively until unable to find any more likely paths. 2.4.2 Algorithm T2-MPA To load the network with vod trips going from o to d and having a VOT density Ÿod(), do the following (See Figure 10 for details): 1. [likely paths] Find all likely paths from o to d. 2. [trip assignment] For each likely path p*: 2.1 [à-ranges] associate with each likely path p* its VOT range: ap* ó à HERE for graphic. 18 3. T2 Equilibrium Assignment Up to now, the technical discussion has addressed only the simple case, where the arc costs and times are fixed - not flow-dependent. This section moves on to flow-dependent arc costs and times. 3.1 T2 Wardrop's Principle (T2-WP) Wardrop's principle [30] extends readily to the stochastic-a case:6 In a bicriteria equilibrium traffic assignment, where the VOT is a random variable à, no trip (with its particular à) has another path with a smaller GC (gp (à) = cp = àtp) than the one which it is using. That is, a T2 equilibrium traffic assignment (T2-ETA) is the vector of total arc flows (xe(à)) reflecting a traffic assignment that puts every trip on a path having minimum generalized cost with respect to that trip's particular VOT à. This generalization of classical traffic equilibrium admits a large, infinite, number of categories of trips in simultaneous equilibrium. 3.2 T2 Equilibrium Traffic Assignment Theorem All of the above conditions reduce to a simple facts: T2-WP implies that a T2 equilibrium traffic assignment has the same total generalized cost as a T2 min-path traffic assignment with the arc costs and times fixed at the level implied by the equilibrium flow. We restate this fact as the T2-ETA Theorem. The flow x* ä X is a T2 equilibrium flow iff G[x*³c(x*)] = g[y³c(x*),t(x*)] (10) ___________________________ 6 Admittedly, the term principle as used here is pompous: Wardrop's Principle is merely a simplifying assumption incorporated as a model requirement. 19 where as from before, where fixed arc cost and time vectors are given, G(x\c,t) = ô ä(ce + àte)xe(à)dà õà e y î arg min G(x\c,t) xîE Proof. We first state and prove a lemma regarding equilibrium for trips of a single given ào: Lemma 3.1 Let X(à) = {feasible assignment of trips with VOT à} y(à) ä arg min G(x³c,t). xäX(ào) Now consider a single VOT ào and assume all the remaining x(à)'s are equilibrium flows for their respective à's. Then the partial traffic assignment x(ào) î X(ào) is in equilibrium iff. G[x(ào)³c(x*),t(x*)] = G[y(ào)³c(x*),t(x*)](11) Proof. Obvious: By definition, this is just the classical single fixed - a case; At equilibrium, every trip with the same o-d uses a path with the same, minimum GC. We now can prove the theorem. The only-if part follows trivially from Lemma 3.1 The if part follows from the fact that the left- hand side of (11) can never be smaller than its right-hand side: Assume (10) is true and (11) is false for one or more à's; that is, one or more of the sums on the right are less than their partner on the left. then the integral of the left-hand side of (11) has to be greater than the on the right-hand side: a contradiction. Corollary 3.1 The t2-ETA Theorem and Lemma 2.1 imply that the flow x* î X is a T2-ETA, i.e., al trips for all VOTs are simultaneously in equilibrium, iff Click HERE for graphic. 20 3.3 T2 Equilibrium Traffic Assignment Algorithm T2-ETA entails the simultaneous equilibration of a (perhaps infinite) number of trip classes. Fortunately, while every individual trip class must be in equilibrium, only the total flow xe(à) are not unique. This permits the construction of a space- efficient algorithm. Notation. For purposes of symmetry, we effectively rename x* as xo and y as x. More precisely, the T2-ETA algorithm generates a sequence of xo's approaching x* and in doing so, solves a series of T2 min-path problems - each solution being called x. Click HERE for graphic. 21 Click HERE for graphic. 22 Click HERE for graphic. 3.4.1 Example 1: Sampled Iterations of T2-ETA To give a since of Algorithm T2-ETA's behavior, Figure 12 shows the results of a sampling of four iterations of the algorithm applied to the example in figures 4 and 5 in Section 1. Notice that the error in Figure 12(d): Iteration 9 is about 4 percent of the precise equilibrium in Figure 7(a). For realistic cases tested, T2-ETA generally approximates the equilibrium flows and speeds of Figure 7 rather quickly; however, due to the infamous "tailing problem" of steepest-descent algorithms, to duplicate them precisely could require several more iterations. Fortunately, approximate equilibria suffice for most practical applications. 23 Click HERE for graphic. 24 The Calculation of ue. The calculation of the integral ue (12) in Figure 11 warrants comment. Recall that for each o-d pair, the likely paths induce a partitioning on the range of à, associating with each likely path p the exclusive range of à for which that p is a min-GC path. This partitioning permits the exact calculation the ue integral as the sum of discrete quantities. To see this, let Click HERE for graphic. When Algorithm T2-MPA assigns a path's flow to its arcs, it knows these values. This permits an alternative expression for ue that is easy to compute: Click HERE for graphic. This last summand is the product of a known origin-destination trip volume times the first moment of a from ap to bp. Computing u, therefore, is merely to accumulate "link loads" of this summand. This explains the reference to ue in the procedure loadPath() and shows how to avoid storing any xe(à). 25 Click HERE for graphic. 3.4.2. Example 2: Algorithm T2-ETA Figure 13 poses a example simple enough for manual calculation. The network has only two arcs: the upper arc is free and has a time equal to its flow; the lower arc has a fixed cost of 1 unit and has a time equal to twice its flow. Ten trips go from node 1 to node 2; their VOT PDF is triangular between 0 and 1. Figures 14(a-c)show three iterations of Algorithm T2-ETA applied to the input data in figures 13(a-b). Each Iteration is described with four figures: The left most figure shows the beginning state of the algorithm: xo, uo and t(xo) (c is constant). The next figure is the efficient frontier implied by the arc times and costs at the beginning state: the dot on the t-axis represents the upper arc and the dot on the c-axis the lower arc. The slope of the line connecting these two dots give ào, the threshold VOT at which trips shift from the upper arc to the lower. The third figure shows the PDF and the fraction of trips that the ascent direction assigns to the upper arc (the remainder goes to the lower arc.) The fourth figure is the ascent direction, its arc flows x and moments u. Note that, in this simple example with two arcs and a triangular PDF. Click HERE for graphic. 26 Click HERE for graphic. 27 Furthermore, since c = (0,1) and t = (xa, 2xb), the solution to Click HERE for graphic. The subtitle contains the relative disequilibrium of the iteration's beginning state and shows the optimal fraction /* for combining the beginning state for the next iteration. For example, the first iterations starts with all 10 trips on the upper arc. This implies arc times of 10 and 0 (with fixed costs of 0 and 1) for the upper and lower arc respectively, producing points (10, 0) and (0,1) on the EF. The line connecting these points yields a threshold à0 = 0.1, implying that the ascent direction has xa = 10à2 0 = 0.1 xb = 10 - xa = 9.9 total trips on the upper and lower arc respectively. Similarly, Click HERE for graphic. 3.5 T1.5 Equilibrium Traffic Assignment Because the proof of convergence of Algorithm T1-ETA is outside the scope of this paper, we offer for the skeptic an alternative algorithm for the simpler problem, where only arc times vary with total flow and arc costs are fixed and à > 0, whose convergence 28 is readily proved. Due to the major restriction on arc costs and minor constraint on a, it is not quite a bicriteria model; so, we call it T1.5 equilibrium traffic assignment - or T1.5-ETA. which is clearly the case: 29 Click HERE for graphic. That Q() is convex is also clear. Its Hessian is zero everywhere except on its main diagonal, which has t'e (xe) as element (e,e). Assuming t() is nondecreasing and twice differentiable for x ò 0, the Hessian is positive semidefinite, making Q() convex in X[2]. This completes the proof. 3.6 Algorithm T1.5-ETA Since Q() is convex, we can find its minimand using the well-know Frank-Wolfe (FW) algorithm [11] [17] [22]. However, let us use an indirect approach that makes use of Algorithm T2-ETA. As before, rename x* as x0, and y as x, but now redefine ue as: xe(à) ue = ô ______ dà õà à Then, in the manner of Lemma 3.2, we can prove that xo is a T1.5- ETA iff Click HERE for graphic. Changing the definitions of the functions L() and H() in Section 3.4 and Figure 11 to those in Figure 15, we can run this revised Algorithm T2-ETA to perform in effect the appropriate FW.7 Algorithm T1.5-ETA is an instance of what Perakis and Magnanti [19] [20] [21] call Generalized Frank-Wolfe (GFW), which solves variational inequalities directly, obviating a formula for the function being minimized. If the Jacobian of the GFW functional (i.e., Hessian of the FW objective) is symmetric, GFW is equivalent to FW. ___________________________ 7 For T1.5 (14) would read Click HERE for graphic. 30 Click HERE for graphic. 31 Click HERE for graphic. T1.5-ETA Convergence Theorem. Algorithm T1.5-ETA, in Figure 15, converges on an equilibrium traffic assignment (in perhaps an infinite number of iterations). Proof. Follows directly from Lemma 3.3 and the T1.5-ETA Theorem. Since Algorithm T1.5-ETA uses GFW and FW are equivalent, it behaves like FW. 3.6.1 Example 3: Algorithm T1.5-ETA Click HERE for graphic. Otherwise, the calculation and interpretation of Figure 16 mimic those of Figure 14. 32 Click HERE for graphic. 33 4 Concluding Remarks 4.1 Summary This paper covered the basic theory and elementary algorithms for a bicriteria user-optimal equilibrium traffic assignment model dubbed T2. It defined T2's behavioral assumptions, derived its mathematical formulation, and designed its solution procedures. Specifically, it extended Wardrop's Principle to include a stochastic value-of-time, produced a simple equation that reflected an equilibrium state, and presented four novel and space-efficient algorithms: - bicriteria parametric min-GC path builder, likelyPaths(), - bicriteria min-GC path assignment, T2MPA(), - two bicriteria equilibrium assignment procedures, T2ETA() and T1.5ETA(), the former being more robust than the latter but lacking the latter's proof of convergence. The first two of these algorithms work in concert with either of the last two to produce an estimate of total arc flow that accrues when each trips use its particular min-GC path 4.2 Additional Research and Development Algorithm T2-ETA Convergence Proof. While the convergence of Algorithm T1.5-ETA's was easy to prove, it is beyond this writer's ability to prove that T2-ETA converges. Accordingly, I trust that a later paper will prove it does-as all my tests would indicate. Algorithm Speedup. Intended principally for pedagogical purposes, the algorithms presented here are "elementary." More sophisticated algorithms appropriate for "productions code' would obscure this paper's aim-to show that T2 makes sense and has an accessible solution. Speedups for sophisticated implementation are the subject of a future paper. For example, to find a feasible descent direction, Algorithm T2-MPA enumerates likely paths, as opposed to using a tree-based approach; however, T2 can be implemented with a parametric tree building algorithm [23]. This improvement not withstanding, the descent direction will still consume more computer cycles than the simpler classical model; therefore, T2 implementation must try to obviate steepest descent's tailing problem. 35 Model Calibration. Observing some path choices and their associated probabilities makes estimating a VOT PDF for T2 easy. Algorithm LikelyPaths (Figure 9) finds the likely paths on the EF and the range of a associated with each. Likely paths are a function of the network only; they are independent of the distribution of à; thus, we can determine their ranges of a without knowledge of the PDF. These à-ranges matched with observed path probabilities yield a sample of points on the cumulative frequency distribution for à, which then serve to fit a curve estimating the PDF. Upper Bounds on Arc Flows. If T2's model and algorithm incorporated prespecified upper bounds on arc flows in the manner proposed by Hearn [13], it would further improve its unique suitability for analyzing congestion pricing and parking policy. Nonlinear Generalized Cost. Every interesting result in this paper depends on the generalized cost of a path being a linear function of its cost and time.8 When GC is nonlinear, the GC of a path is no longer the sum of its arcs' GCs, making min-path finding an interesting and worthy challenge. Stochastic Assignment. Stochastic assignment models [29] [41 [27] have adapted the classical model to produce traffic assignments in which some trips take paths that are not minimal. Presumably by admitting non optimal (i. e., human-like) behavior, stochastic assignments mirror reality better. Because T2 generalizes the classical traffic assignment model, it supports any of the above methods. For example, one algorithm to do a "stochastic" T2 is the following: 1. determine likely paths p along with their associated à-range [ap, bp) and trip count vp; 2. for each path, compute the mean of à over its arrange; 3. for each path p, use its mean à to perform your favorite stochastic assignment of vp around its GC-min-path. The result is a multipath loading of paths both on and off the EF. _____________________________________ 8 Clearly, real trip makers do not all use this function: T2 accurately models those that do and inaccurately those that do not. In any case, T2 is more accurate than the classical model, which assumes every trip has the same VOT. 36 Dynamic Assignment. A dynamic traffic assignment [18] traces paths in both time and space. The path finding algorithm estimates that generalized cost of an arc when the trip expects to use the arc [12]. Dynamic models better reflect the trip making decisions process, the congestion that results, and the ability of trips to adjust their departure and arrival time to advantage. As described, T2 is a static model. Nevertheless, for the same reasons that it readily supports any stochastic assignment, T2 can also adopt dynamic assignment as easily as any classical model does. Elastic Demand. T2 ignores the fact that the total trips vod between an o-d usually depend on the generalized cost of the trip, which in T2 is a random variable. Speaking theoretically, the inverse of this demand function maps vod (à) into god(à); and the expected value of this inverse provides the average generalized cost E[god³vod] among all trips from o to d. Hence, at equilibrium Click HERE for graphic. where y = arg minx G[x³c(x*),t(x*)]. These equations could be solved with a two-stage algorithm using T2-ETA. The resulting model and algorithm would be a simultaneous destination - model route choice equilibrium, generalizing the work of Evans [8]. Tn: Beyond Two Criteria. While time and cost are paramount, they do not comprise all path-choice criteria. Other influential determinants include, to name a few: schedule reliability, number of transfers and out vs in-vehicle time. T2 extension to handle more than two criteria - Tn, if you will - is the topic of a future report [7]. 4.3 Acknowledgements Individuals from several institutions contributed directly and indirectly to the production of this paper: Academia. I thank Tom Magnanti and Rob Freund of the Massachusetts Institute of Technology for their lucid math programming lectures; David Boyce of the University of illinois at chicago, who read several drafts this paper; Mike Florian and Patrice Marcotte of 37 the University of Montreal, whose counter example [10] prompted my finding and repairing a serious error in an earlier version; and particularly Georgia Perakis of MIT for introducing me to the generalized Frank-Wolfe algorithm and for her helpful suggestions. Volpe Center. I am very grateful for my excellent working environment and generous colleagues: the assistance Sarah Maccalous, the opinions of Mark Bucciarelli, the insights of Peter Mengert, and particularly the encouragement of Mike Jacobs. Department of Transportation. Finally thanks go to the U.S. DOT, who with the Environmental Protection Agency, sponsored this work as part of its Transportation Model Improvement Program (TMIP); and to its technical representative, Fred Ducca, without whose support this paper would not have been written. 38 References [1] Ahuja, R., Magnanti, T., Orlin, J. (1993) Network Flows. Prentice Hall. [2] Bazaraa, M. Sherali, H., Shett C. (1979) Nonlinear Programming: Theory and Algorithms. John Wiley & Sons. [3] Dafermos, S. (1981) "A Multicriteria Route-Choice Traffic Equilibrium Model." Paper prepared for Frontiers in Transportation Equilibrium and Supply Models Symposia, University of Montreal, Nov. 11-13, 1981. [4] Dial, R. (1971) "A Probabilistic Multipath Assignment Model that Obviates Path Enumeration," Transportation Research 5, pp 83-111. [5] Dial, R. (1979) "A Model and Algorithm for Multicriteria Route Mode Choice. Transportation Research, Part B. Methodological, December. [6] Dial, R. (1994) "Multiciteria Equilibrium Traffic Assignment: Theory and Algorithms." Technical Report prepared for the Federal Highway Administration. Volpe National Transportation Center, Cambridge, MA. (In progress.) [7] Dial, R. (1994) "Multicriteria Equilibrium Traffic Assignment; Basic Theory and Elementary Algorithms: Part 11: Tn: the Multicriteria Model." (In progress.) [8] Evans, S. (1976) "Derivation and Analysis of Some Models for Combining Trip Distribution and Assignment." Transportation Research 10, pp 37-57. [9] Florian, M (1994) Formal Comments at the 1914 Annual Meeting of the Transportation Research Board, Washington, D. C. [10] Florian, M., and Marcotte, P. (1994) Personal Correspondence. University of Montreal. [11] Frank, M. and Wolfe, P. (1956) "An Algorithm for Quadratic Programming." Naval Research Logistics Quarterly, Vol. 3 pp 95-110. 39 [12] Friesz, T., Bernstein, D., Smith, T., Tobin L., Wie, B. (1993) "A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem." Operations Research, Vol. 41, No. I pp 179-191 [13] Hearn, D. (1980) "Bounded Flow Equilibrium Problems by Penalty Methods." Proceedings of the IEEE International Conference on Circuit and Computers. Vol. 1, pp 162-166. [14] Jones, P. M. "Working Paper 20: New Approaches to Understanding Travel Behavior. The Human Activity Approach." University of Oxford, Transportation Studies Unit, 1977. [15] Kapur, J. and Kesavan, H. (1992) Entropy Optimization Principles with Applications. Academic Press. University of California Press, Berkely, CA. [16] Leurent, F. (1993) "Cost Versus Time Equilibrium over a Network." Presented at the 1994 Annual Conference of the Transportation Research Board. Washington D. C. [17] LeBlanc, L. (1973) Mathematical Programming Algorithms for Large Scale Network Equilibrium and Network Design Problems. Ph. D. thesis, Northwestern University. [18] LeBlanc, L., Ran B., and Boyce, D. (1992) "Dynamic Travel Choice Models for Urban Transportation Networks." To appear in Proceedings of the 1992 IEEE International Conference on Systems, Man and Cybernetic, 1992. [19] Magnanti, T., and Perakis, G. (1993) "A Unifying Geometric Solution Framework and Complexity Analysis for Variational Inequalities." Working Paper OR 276-93, Operations Research Center, MIT, Cambridge, MA. [20] Magnanti, T., and Perakis, G. (1993) "On the Convergence of Classical Variational Inequality Algorithms." Working Paper OR 282-93, Operations Research Center, MIT, Cambridge, MA. [21] Magnanti, T., and Perakis, G. (1994) "From Frank-Wolfe to Steepest Descent: A Descent Framework for Solving VIPs." Presentation at TIMS/ORSA Joint National Meeting, Boston, April 1994. 40 [22] Nguyen, S. (1974) "An Algorithm for the Traffic Assignment Problem." Transportation Science, 8, No. 3 pp 205-218. [23] Orlin, J. (1993) "2-Criteria and 3-Criteria Shortest Path Problem: a Proposal," Personal Correspondence. [24] Quandt, R. (1967) "A Probabilistic Abstract Mode Model." Studies in Travel Demand, VIII." Mathematica, Inc., Princeton, N.J. pp 127-149. [25] Roth G. Paying for Roads: the Economics of Traffic Congestion. Penguin Books, 1967. [26] Schneider, M. (1968) "Access and Land Development," Pro- ceedings of the conference on Urban Development Models, Dartmouth College. [27] Sheffi, Y. and CDaganzo, C. (1977) "On Stochastic Models of Traffic Assignment," Transportation Science 11, N.3, pp 253274. [28] Slavin, H. (1993) Personal Correspondence. Caliper Corporation. [29] Von Faulkenhausen, (1966) "Traffic Assignment by a Stochastic Model, Proceedings, 4th International Conference on Operational Science, pp 415-421. [30] Wardrop, J. (1952) "Some Theoretical Aspects of Road Traffic Research," Proc. Inst. of Civil Engineers, Part 2, pp 325-378. 41
