System-Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion

SYSTEM-OPTIMAL ROUTING OF TRAFFIC FLOWS WITH USER CONSTRAINTS IN NETWORKS WITH CONGESTION Abstract. The design of route guidance systems faces a well-known dilemma. The approach that theoretically yields the system-optimal traffic pattern may discriminate against some users in favor of others. Proposed alternate models, however, do not directly address the system perspective and may result in inferior performance. We propose a novel model and corresponding algorithms to resolve this dilemma. We present computational results on real-world instances and compare the new approach with the well-established traffic assignment model. The essence of this study is that system-optimal routing of traffic flow with explicit integration of user constraints leads to a better performance than the user equilibrium, while simultaneously guaranteeing superior fairness compared to the pure system optimum. 1. Introduction Route guidance and information systems are designed to assist drivers in making route decisions. Such devices can provide information (e.g., about conditions drivers are likely to experience) or give recommendations (e.g., “leave the highway at the next exit and turn right”). We will concentrate on in-vehicle route guidance devices that provide recommendations to drivers. Drivers enter their destinations at the beginning of the trip, and the system computes routes based on digital maps, upto-date traffic data and current vehicle positions determined with the help of the Global Positioning System (Henry, Charbonnier, and Farges 1991). These devices normally use visual and acoustic indicators to aid drivers in following the proposed route. Currently, many cars are already equipped with simple versions of these devices, and with prices going down many more are likely to have one in the not-so-distant future. For that reason, it is widely hoped that route guidance systems can help to alleviate congestion caused by the still increasing amount of road traffic. Even small improvements can have a significant impact given that the “congestion bill” in the U.S. alone was $67.5 billion in the year 2000, consisting of 3.6 billion hours of delay plus 5.7 billion gallons of gas (Texas Transportation Institute 2002). Several kinds of in-car navigation systems have been proposed. The simplest devices perform static guidance; i.e., they work with information that is infrequently updated. Most of the in-car guidance consoles deployed today are of this type. Their main goal is to provide information to drivers who do not know the area well. From an algorithmic point of view, they are straightforward: they only compute shortest paths (or approximations thereof) to the destinations with respect to 1 2 travel time, geographic distance, or other appropriate measures. Computational challenges for these approaches arise “solely” from the huge size of the underlying road networks. More sophisticated route guidance systems make use of information on current conditions in the traffic network. That knowledge is the basis of reactive guidance systems (Papageorgiou 1990; Ben-Akiva, de Palma, and Kaysi 1996). In other words, the recommendation provided to drivers at any given time is based on a snapshot of the traffic at that time. One of the advantages of reactive guidance is that it can respond quickly to demand changes or incidents because no predictions are used. The most advanced approach, called anticipatory guidance, predicts future demands and traffic conditions and gives recommendations accordingly (Chen and Underwood 1991; Kaysi 1992). The issue is how future conditions should be predicted. When market penetration is low, guidance systems can basically ignore their own effect. On the other extreme, when most users are guided and they comply with the guidance, reality is likely to be as predicted. The problematic cases are in between the two extremes. These route guidance systems must predict how users will behave (e.g., follow the recommendation or not) to guide traffic in a way that is consistent with the predictions (Bottom 2000). Otherwise, guidance can fail to achieve the desired objective because recommendations were given making assumptions about the future that may not materialize. According to Bottom (2000), there is no consensus in the community on which of the latter two approaches should be used in practice. For the present paper, we adopt reactive guidance because it is conceptually simpler. Regardless of the source of network data, route guidance devices still have to compute concrete routes to be proposed to users. Several systems compute shortest paths, the k shortest paths for some properly chosen parameter k, or pareto-optimal paths (when multiple criteria are considered simultaneously). Some systems perform these computations online while others include them in a preprocessing step. For example, DynaMIT (2002), a simulation-based real-time system to provide travel information, computes shortest paths beforehand with respect to several static impedance functions. Among other measures, it considers free-flow travel times, peak-period travel times, geographic lengths, and the number of signalized intersections. Another possibility is to assign users to the paths of smallest individual impedance under the current conditions, giving rise to what is commonly known as a user equilibrium (or user-optimal solution). Alternatively, one can opt to minimize the total impedance in the system, a solution known as the system optimum. Current route guidance systems implement both user and system optimality, although the bias has always been towards user-optimal traffic patterns (e.g., Mah­ massani, Hu, Peeta, and Ziliaskopoulos 1994; Ben-Akiva, Bierlaire, Bottom, Koutsopoulos, and Mishalani 1997; Dynasmart 2002). Although system optimality is included in such systems for computing good upper bounds on traffic efficiency, it is not accepted as a realistic option for actual guidance. Indeed, it is well-known that under system-optimal patterns some users may end up traveling longer to allow the system to achieve global efficiency. Of course, it is not likely that many users accept recommendations that are too inefficient with respect to their personal optimal choices. We measure the detriment for users as the ratio of the impedance of the recommended path to that of the shortest possible path the user could have taken. This concept, called unfairness, will play a central role in this paper. For system-optimal solutions, DynaMIT assumes, as we will, that there is a single user-class, 100% market penetration and full user compliance. We remark that its feasible path selection method is similar to what we shall propose. For that reason, the system optimum that DynaMIT computes actually is a “constrained system optimum,” the key concept of this paper. 1.1. Drawbacks of current route guidance systems. None of the current guidance systems takes directly into account the efficiency of the solution they propose (with the exception of systemoptimal solutions, which are not implementable because of their unfairness). Thus, the need for 3 integrated algorithms that actually pay attention to the system-wide performance has been rec­ ognized (Henry, Charbonnier, and Farges 1991; Beccaria and Bolelli 1992; Kaysi, Ben-Akiva, and de Palma 1995). As mentioned earlier, the most popular approach is to route drivers according to a user equilib­ rium. In that way, drivers are routed along their respective lowest-impedance paths so there are no paths they would prefer to the ones they are given. The resulting flow pattern was originally introduced by Wardrop (1952) in order to model natural driver behavior, and it has been studied extensively in the literature. In fact, transportation engineers have used it to predict network uti­ lization for planning purposes. Magnanti (1984), Sheffi (1985), Patriksson (1994), and Florian and Hearn (1995) provide a comprehensive treatment of mathematical formulations and algorithms for computing the static user equilibrium. While a user equilibrium should satisfy the drivers, it does not necessarily minimize the total impedance (or latency) in the system, which is defined as the sum of all individual travel times. Roughgarden and Tardos (2002) provide examples that show that the total travel time in equilib­ rium can be arbitrarily large compared to that of the system optimum, although it is never more than the travel time incurred by optimally routing twice as much traffic. Another unfavorable property of the user equilibrium is its non-monotonicity with respect to the network’s capacity. This is illustrated by the Braess paradox, where adding a new road to a network with fixed demands actually increases the total travel time of the updated user equilib­ rium (Braess 1968; Sheffi 1985; Hagstrom and Abrams 2001). Merchant and Nemhauser (1978) recognized that the assumptions of the traffic assignment prob­ lem are unrealistic and proposed to consider a dynamic model. Since then, there has been significant effort towards the dynamic analysis of traffic networks (e.g., Ben-Akiva 1985; Friesz 1985). Unlike static traffic assignment, where models and solution methods are well established, the dynamic traffic assignment problem has been studied from several different perspectives with no single gen­ erally accepted model or methodology. We refer the reader to the article by Mahmassani and Peeta (1995), which provides a discussion of the inherent difficulties and corresponding solution attempts. 1.2. A different approach. From a global perspective, e.g., the traffic authority’s point of view, it is certainly desirable to explicitly minimize the total travel time (i.e., to compute a system optimum). In particular, the existing road network could then carry more traffic (Lafortune, Sengupta, Kaufman, and Smith 1991; Ferris and Ruszczyński 1997). Yet, users’ needs have to be taken into account: directly implemented, this policy could route some drivers on unacceptably long paths in order to use shorter paths for many other drivers. In fact, the length of a route in the system optimum can be higher than in user equilibrium, even in the pathological case of a single origindestination pair (Roughgarden 2002). This is critical because routes can only be recommended to drivers. It is reasonable to assume that only very few of them would be willing to sacrifice their own short routes for the benefit of the “community”. On the other hand, user acceptance of a route guidance system is important if it is supposed to help in reducing traffic congestion. Therefore, Beccaria and Bolelli (1992) have suggested to “find the route guidance strategy which minimizes some global and community criteria with individual needs as constraints.” We adopt a system optimum approach but honor the individual needs by imposing additional constraints to ensure that drivers are assigned to “acceptable” paths only. More precisely, we introduce the concept of the normal length of a path, which can be either its traversal time in the uncongested network, its traversal time in user equilibrium, its geographic distance, or any other appropriate measure. The only condition imposed on the normal length of a path is that it may not depend on the actual flow on the path. Equipped with this definition, we look for a constrained system optimum in which no path carrying positive flow between a certain origin-destination (OD) pair is allowed to exceed the normal length of a shortest path between the same OD pair by more 4 than a tolerable factor. By doing so, we achieve our primary goal of finding solutions that are fair and efficient at the same time. The novelty of our work consists in defining a constrained system optimum with the “right” set of allowable paths. We demonstrate that this model leads to a significantly better utilization of a traffic network than the standard traffic assignment (user equilibrium) and still guarantees fairness similar to that in the user equilibrium. To the best of the authors’ knowledge, no other work introduces a constrained system optimum approach that guarantees fairness comparable to that of the ordinary traffic assignment. While this paper studies the method from a computational perspective, Schulz and Stier Moses (2003) analyzed this idea theoretically and provided estimates of the efficiency gain when using constrained system optima instead of user equilibria. In a forthcoming paper, Schulz and Stier Moses (2004) extend this study and present theoretical results on the fairness of constrained system optima. After specifying the problem and the proposed model in Section 2, we present an algorithm for its solution in Section 3. It is based on a method called Partan, which is a revised version of the FrankWolfe algorithm. In Section 4, we give computational results obtained with our implementations. Many of the real-world instances that we used were kindly provided by DaimlerChrysler AG, Berlin. Additional instances were retrieved from an online library called Transportation Network Test Problems (Bar-Gera 2002). 2. The Model We consider a model of reactive route guidance that allows us to work with static flows. While not considering dynamic flows may preclude the direct application to real-world situations, our approach can provide traffic planners with bounds on the total travel time that are more accurate (compared to the ordinary system optimum). Moreover, Sheffi (1985) points out that there are times when traffic exhibits steady-state behavior; e.g., during rush hours. If nothing else, this research is a first step in explicitly incorporating system-wide effects into route guidance systems. We assume that all drivers use the route guidance system and that they actually follow the rec­ ommended routes. Admittedly, this assumption is relatively strong, but this should be considered a first step. Future research will explore the design of consistent route guidance systems that optimize efficiency without comprising user acceptance. One way to model a non-perfect market penetration is by considering two classes of users. Some users have access to route guidance devices and follow the recommendations, while the remaining users act selfishly. In this extension, a central question is that of creating a traffic pattern for the guided users that is fair and minimizes the total travel time (for all users, including those without guidance). Along this direction, Roughgarden (2001) studied how to compute an optimal strategy in a network consisting of a set of parallel links. 2.1. Preliminaries. We represent the road network by a directed multigraph G = (V, A) with two attributes on each arc a � A: the normal length ϕa � 0 serves as an a priori estimate for its traversal time in the solution we seek; the link delay function �a : R�0 � R�0 maps xa , the volume of traffic on arc a, to its actual traversal time �a (xa ). Normal lengths can be chosen to be any metric for the arcs that is fixed in advance. However, their proper choice will allow us to produce solutions with desirable features; we refer to Section 4 for details. Link delay functions �a measure the impedance of arcs for different congestion levels. We require them to be nondecreasing and differentiable, and �a (xa )xa to be convex. These requirements are naturally met by common link delay functions used to reflect congestion effects (Branston 1976; Sheffi 1985; Cohen 1991). Figure 1 illustrates their typical shape: after they reach the practical capacity ca (Patriksson 1994), they grow very fast. In our computations, we use the function put 5 �a (xa ) PSfrag replacements xa 0 Figure 1. Typical link delay functions. Here, xa is the flow on arc a, and �a (xa ) is the associated travel time. forward by the U.S. Bureau of Public Roads: �a (xa ) := �a0 � 1+� �x a ca � � , where �a0 > 0 is the travel time in the uncongested network (also called free-flow travel time), and � � 0 and τ � 0 are tuning parameters. We model vehicles with the same origin and destination as one commodity; K is the set of all commodities. For each commodity k � K, (sk , tk ) � V × V denotes the associated origindestination (OD) pair. The demand rate dk > 0 for k � K represents the amount of flow to be routed for commodity k (vehicles per time unit). We denote the set of paths connecting OD� pair k by Pk := {P : P is a directed path from sk to tk }, and the complete set of paths� by P := k�K Pk . For a given flow x and a path P � P, its actual traversal time is � (x) := P a�P �a (xa ), while � ϕP (x) := a�P ϕa is its normal length. We assess the quality of a particular traffic assignment using two criteria. Its (un)fairness is of direct importance to users, while the total travel time in the system matters to the traffic authority. Let us discuss unfairness first. 2.2. Measures of unfairness. Without any centralized control, one would expect that different users traveling between the same OD pair experience similar travel times. In fact, if this were not the case, users would have an incentive to switch routes. In a seminal contribution, Wardrop (1952) stated the following principle that formalizes this notion: The journey times on all the routes actually used are equal, and less than those which would be experienced by a single vehicle on any unused route. A traffic pattern satisfying this principle is commonly called a user equilibrium (Dafermos and Sparrow 1969). It is “fair” in the sense that users between the same OD pair encounter the same delay. However, it is well known that a user equilibrium does in general not minimize the total travel time in the system. Our goal is to select more efficient traffic patterns without loosing the fairness property. To make this more precise, let us introduce several notions of unfairness of a solution. For a given flow, we define the unfairness of a particular traveler as follows: Loaded unfairness: ratio of her experienced travel time to the experienced travel time of the fastest traveler for the same OD pair, where “experienced travel time” means travel time measured in terms of the current congestion level. Normal unfairness: ratio of the length of her path to the length of the shortest path for the same OD pair, both measured with respect to normal arc lengths. User equilibrium (UE) unfairness: ratio of her experienced travel time to the travel time for the same OD pair in a user equilibrium (which is the same for all users of that OD pair). 6 Free-flow unfairness: ratio of her experienced travel time to the length of the fastest path for the same OD pair w.r.t. free-flow travel times. The respective notion of unfairness for a particular flow is the maximum over all OD pairs of the maximum unfairness of a traveler between that OD pair. More formally, for a given flow x and an equilibrium flow f , Loaded Normal UE Free-flow unfairness(x) unfairness(x) unfairness(x) unfairness(x) := := := := max{�P1 (x)/�P2 (x) : P1 , P2 � Pk , xP1 , xP2 > 0, k � K}; max{ϕP1 /ϕP2 : P1 , P2 � Pk , xP1 > 0, k � K}; max{�P1 (x)/�P2 (f ) : P1 , P2 � Pk , xP1 > 0, fP2 > 0, k � K}; max{�P1 (x)/�P2 (0) : P1 , P2 � Pk , xP1 > 0, k � K}. The notions of loaded and normal unfairness are similar. Both compare, using different metrics, the travel times of users to the shortest travel times they could have had. The UE unfairness, introduced by Roughgarden (2002) in the single-commodity context, indicates how the travel times of the solution relate to those in user equilibrium. In practice though, drivers typically do not know the travel times in equilibrium; it is arguably more important to them how their travel times compare to the actual travel times of others. The free-flow unfairness measures the degradation of performance that users experience due to the prevalence of congestion effects. Note that the normal unfairness and the loaded unfairness are always greater than or equal to 1, while the UE unfairness and the free-flow unfairness can be any nonnegative number. 2.3. Problem formulation. As it is difficult to directly control the loaded unfairness, we will instead impose an upper bound on the normal unfairness and show that by doing so the other notions of unfairness will be small as well. In particular, we consider solutions for which the normal length of any used path between OD pair k is not much greater than that of a shortest s k -tk -path (with respect to normal lengths), for all k � K. More specifally, we fix a tolerance factor � � 1 and restrict the normal unfairness to be smaller than �. In other words, a path P � P k is feasible if ϕP � Lk . Here, Lk := minP �Pk ϕP is the normal length of a shortest path between sk and tk . If we let Pk� denote �the set� of all feasible paths for OD pair k, we can define the entire set of feasible � paths as P := k�K Pk . Because route guidance systems eventually have to propose paths to the drivers, our formulation is path-based: there is a decision variable xP for each path P � P � . In fact, it is virtually impossible to model the restriction to feasible paths with the help of a formulation based on arc variables only. Moreover, even if one were (somehow) given an arc flow that has a decomposition into feasible paths, it is NP-hard to compute such a decomposition (Correa, Schulz, and Stier Moses 2003, Corollary 4). In contrast, user equilibria and ordinary system optima can be computed using arc-based formulations; any flow decomposition results in path flows with the desired property. The constrained system optimum that we propose to use in route guidance systems is an optimal solution to the following min-cost multicommodity flow problem with separable convex objective function and path constraints: CSO : min C(x) := � �a (xa )xa a�A s.t. � xP = d k k � K, xP = x a a � A, xP � 0 P � P �. P �Pk� � P �P � :a�P 7 Note that the flow variables are not required to be integral since they describe abstract flow rates. If paths were not restricted to be feasible (i.e., in P � ), an optimal solution to this formulation would coincide with an ordinary system optimum. We denote by CSO� an optimal solution to the problem with tolerance factor �. Figure 2 demonstrates the effect of path constraints on the system optimum. One commodity is routed through the road network between two clearly marked nodes. In the picture on the left, we display the (unconstrained) system optimum. The flow is distributed widely over the network in order to avoid high arc flows, which would incur high arc travel times. In the picture on the right, the same amount of flow is routed, but this time with the restriction that the normal length of any used path is at most 10% longer than that of the shortest path (i.e., � = 1.1). In this example, the normal length has been chosen to be the geographic distance. Line thickness reflects arc capacity (light gray) and arc usage (black), respectively. Figure 2. System optimum without and with restrictions on the normal length of paths, resp. Before we discuss the computational complexity of problem CSO and algorithms to find a constrained system optimum, let us emphasize that this model is different from previous traffic assignment formulations with side constraints. The most commonly considered type of side constraints are explicit bounds on arc capacities. In fact, capacity constraints on individual arcs have been used since the work of Charnes and Cooper (1961) to improve the modeling of congestion effects (see also Hearn 1980); some traffic control policies give rise to arc flow capacity constraints as well (Yang and Yagar 1994); arc capacities can also be used to derive tolls for the reduction of flows on overloaded links, we refer to Bernstein and Smith (1994) for references. Moreover, several authors have discussed the algorithmic consequences of modeling arc capacities explicitly (Daganzo 1977a; Daganzo 1977b; Hearn 1980; Hearn and Ribera 1980; Hearn and Ribera 1981; Larsson and Patriksson 1994; Larsson and Patriksson 1995). Larsson and Patriksson (1999) have summarized and extended this work to general convex side constraints on the vector of arc flows. Nonetheless, such constraints cannot be used to render certain paths infeasible, as we have argued earlier. Still, path-based multicommodity flow models similar to ours with explicit constraints on the set of allowable paths are frequently used in other application areas. A recent example is the work by Holmberg and Yuan (2003), who study routing problems in telecommunication networks and solve the resulting models by column generation. However, nobody has tried to capture aspects of system optimality and user fairness in a network with congestion effects, as we do. 3. Algorithms and Complexity To solve problem CSO, we use a variant of the convex combination algorithm of Frank and Wolfe (1956). As it is well-known that the standard Frank-Wolfe algorithm sometimes shows poor 8 convergence (see, e.g., Sheffi 1985; Patriksson 1994; Florian and Hearn 1995), we consider an improved version called Partan that was proposed by LeBlanc, Helgason, and Boyce (1985) and further studied by Florian, Guélat, and Spiess (1987) and Arezki and Van Vliet (1990), among others. As we cannot explicitly work with all variables xP associated with paths P � P � , because there may be exponentially many, we only generate them when needed. For that reason, our algo­ rithm can be considered to be a column generation method. The application of column generation to the computation of system optima and user equilibria was first studied by Gibert (1968) and Leventhal, Nemhauser, and Trotter (1973). For the sake of completeness, let us briefly describe the Frank-Wolfe method. 1 Given a current solution, the algorithm solves in every iteration a linearized version of CSO to determine a feasible descent direction. As the linearization permits the decomposition of the problem by commodities, it is enough to call a subroutine for finding a shortest path in Pk� for each commodity k � K. In the subsequent line search, the original nonlinear problem is solved restricted to the line defined by the feasible direction of descent. The algorithm terminates when a certain precision is achieved. To determine when this is the case, the convexity of the objective function is used to derive a lower bound on the value of an optimal solution. It is well known that this algorithm always converges to a global minimum (for convex programs). Partan is based on the same idea, but it performs a more intelligent line search. It determines the descent direction using the results of two consecutive iterations, thereby diminishing the zigzagging effect. The substep of computing a shortest path in Pk� is exactly the so-called constrained shortest path problem; see Section 3.1 below. The only difference between the algorithm we just described and the version of Frank-Wolfe (or Partan) employed for computing user equilibria or system optima is the use of constrained shortest paths instead of regular shortest paths in the solution of the linear subproblems. Note that other methods like partial linearization algorithms or simplicial decomposition can also be adapted to our problem. Since we want to make the point that constrained system optima are useful, it was not necessary to implement potentially more efficient algorithms as we can solve rel­ atively large instances within acceptable time limits by using Partan. As others concluded before, for our purpose “. . . the [Frank-Wolfe] algorithm is considered sufficiently good for practical use” (Patriksson 1994). Nevertheless, if one wants to deploy these ideas in a real-time setting, more care­ ful and efficient implementations are needed. We refer the reader to the books by Sheffi (1985) and Patriksson (1994) as well as the chapter by Florian and Hearn (1995) for comprehensive discussions of these algorithms as well as many others. 3.1. The constrained shortest path problem. Let us sketch how the computation of con­ strained shortest paths—the pricing component of our column generation approach—is carried out. In this subproblem, every arc a � A has two parameters, a traversal time � a and a length ϕa . Given an origin-destination pair (s, t), the objective is to compute a quickest path from s to t whose length does not exceed a given bound L. That is, one wants to solve the following problem: min{�P : P is a path from s to t such that ϕP L}, � where �P := a�P �a and ϕP := a�P ϕa . This problem is NP-hard (Garey and Johnson 1979). For solving this problem, Aneja and Nair (1978) proposed to use Lagrangean relaxation; Ribeiro and Minoux (1986) added a branch-and-bound scheme. Aneja, Aggarwal, and Nair (1983) extended Dijkstra’s algorithm to the case of two objective functions, and Climaco and Martins (1982) used path ranking. Because of its superior computational efficiency, we implemented the label correcting algorithm of Aneja et al. (1983). The algorithm fans out from the start node s and labels each reached node v � V with labels of the form (d� (v), dτ(v)). For each path from s to v that has been detected so � . 9 far, d� (v) represents its traversal time and dτ (v) its distance. During the course of the algorithm, several labels may have to be stored for each node v, namely the pareto-optimal labels of all paths that have reached it. This labeling algorithm can be interpreted as a special kind of branch-andbound with a search strategy similar to breadth-first search. Starting from a certain label of v, one obtains lower bounds for the remaining paths from v to t by separately computing ordinary shortest path distances from v to t with respect to travel times �a and lengths ϕa , respectively. If one of these bounds is too large, the label can be dismissed. 3.2. Computational complexity. For the sake of completeness, let us also quickly discuss the computational complexity of problem CSO. Note that it includes as a specical case the situation in which all link performance functions are constant; i.e., �a (xa ) = �a for all a � A. Moreover, the set of feasible paths is only given implicitly. Hence, the input dimension is |A| + |K|. In fact, CSO is already NP-hard for |K| = 1, as this case amounts to solving a constrained shortest path problem. 4. Computational Study The computational study is divided into three parts. First, we discuss which normal length should be used in practice. Next, we analyze efficiency vs. fairness of solutions for instances that arise from real-world networks. Finally, we briefly report on the performance of the algorithm itself. The seven instances we used in this study come from two different sources. Four of them represent different parts of the actual road network of the city of Berlin, Germany, and were provided by DaimlerChrysler AG. Their demand rates stem from origin-destination polls conducted in Berlin. The other three come from the Transportation Network Test Problems website (Bar-Gera 2002). Table 1 shows the specifics of each instance. Instances are listed in increasing order of the product of the number of arcs and the number of commodities. This measure of complexity has been used in the literature (e.g., Holmberg and Yuan 2003), and it indeed corresponds to the ordering with respect to solution times. Instances range from rather small ones, which were included because they are standard in the literature, to fairly large ones. Table 1. Problem instances used in the computational study Instance Name Short Name Sioux Falls SF Friedrichshain F W Winnipeg N Neukölln Mitte, Prenzlauerberg & Friedrichshain MPF Chicago Sketch CS Berlin B Source TNTP DC TNTP DC |V | 24 224 1,067 1,890 |A| 76 523 2,975 4,040 |K| |A| · |K| 528 40K 506 265K 4,344 13M 3,166 13M DC 975 2,184 9,801 933 2,950 83,113 TNTP DC 12,100 19,570 49,689 21M 245M 972M The algorithm described in Section 3 was implemented in C++ using the GCC compiler un­ der Linux; the computing platform was a Pentium IV based computer running at 2.4 GHz with 1 GB RAM. 4.1. Choice of normal length. We initially considered three possible ways to define the normal length of an arc: geographic distances, free-flow travel times, and travel times when the network is in user equilibrium. Recall that normal lengths can only be static; for instance, it is not possible to consider travel times under the current solution with the methodology described in this paper. The advantage of keeping the model simple is a fast algorithm that still produces solutions with small total travel time and low unfairness. It is important to remark that users do not need to know the 10 normal lengths; they are just an artifact of our algorithm to select solutions that are approximately fair. Geographic distances and free-flow travel times are highly correlated; therefore, one cannot expect significant differences between solutions resulting from choosing either one as the normal length. For free-flow travel times, Schulz and Stier Moses (2003) showed, and our runs confirm, that the total travel time of user equilibria is smaller than that of constrained system optima when the factor � is too small. Consequently, to obtain an improvement in the total travel time, bigger factors must be considered. However, this gives rise to relatively high unfairness, which is undesired. As an example, consider instance Neukölln. The graph on the left in Figure 3 shows 1 0.95 4000 0.9 probability value 3800 3600 3400 3200 0.8 0.75 3000 2800 0.65 UE1 1.2 1.4 1.6 1.8 2SO factor 0.6 1 1.2 1.8 1.6 1.4 loaded unfairness Factor UE 1.05 1.1 1.2 1.3 1.4 1.5 2 SO 0.8 Factor UE 1.05 1.1 1.2 1.3 1.4 1.5 2 SO 0.85 0.7 2600 1 probability 4400 4200 0.6 0.4 0.2 2 0 0.6 0.7 1 0.9 0.8 UE unfairness 1.1 1.2 Figure 3. Objective values and unfairness distributions for instance Neukölln and normal lengths equal to free-flow travel times the value of the objective function for different tolerance factors �, for the user equilibrium (UE), and for the system optimum (SO). Factors smaller than 1.4 are not helpful because the total travel time of the corresponding solutions is greater than the total travel time in user equilibrium. The other two graphs in Figure 3 depict the distribution of unfairness across users for varying tolerance factors; for instance, for factor � = 1.5, 80% of all users will experience a loaded unfairness of less than 1.1. This value increases to 1.2 if one considers 90% of all users. For factors greater than 1.5, the distributions are quite similar to that of the system optimum. In the graph on the right, note that for small tolerance factors most users end up traveling longer than they would in user equilibrium. This happens because there are not enough alternative paths between any one OD pair, which explains the poor quality of the solutions under this choice of normal length. We therefore propose to make use of the travel times in user equilibrium when defining normal arc lengths, which results in high-quality solutions. Indeed, for any factor �, the user equilibrium itself is a feasible solution to the constrained system optimum problem. Therefore, for all � � 0, C(CSO� ) C(UE ), which guarantees that the optimal solution to problem CSO is never worse than the user equilibrium in terms of the total travel time in the system. The advantage of this normal length definition is that it is flow-dependent; it provides a better indication which paths should be selected. Let us repeat that users do not need to know the user equilibrium; it is just an ingredient for the computation of the constrained system optimum. Figure 4 displays graphs similar to the ones in Figure 3 for this choice of normal length. Most notably, total travel times are distinctively smaller than in equilibrium, while the fraction of users traveling longer than in equilibrium is substantially smaller. We therefore limit our analysis in the sequel to this version of normal length; that is, we assume user equilibrium travel times are used to define normal lengths. 1 0.95 4000 0.9 3800 0.85 3600 3400 3200 3000 0.65 UE1 1.2 1.4 1.6 1.8 2SO factor Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.75 2800 0.6 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.8 0.8 0.7 2600 1 probability 4400 4200 probability value 11 1 1.2 1.8 1.6 1.4 loaded unfairness 0.6 0.4 0.2 2 0 0.6 0.7 1 0.9 0.8 UE unfairness 1.1 1.2 Figure 4. Objective values and unfairness distributions for instance Neukölln and normal lengths equal to travel times in user equilibrium 4.2. Quality of constrained system optima. Tables 2 and 3 exhibit the output of the algorithm for the instances presented in Table 1 and varying tolerance factors. Every row represents one run for the factor reported in the first column. The column objective value is the total travel time of the solution; the column number of paths contains the number of paths with positive flow, which is an indication of the complexity of the solution. In addition, the tables include the 99th percentiles of the different unfairness distributions, the number of iterations (one iteration consists of solving the linearized problem and performing the line search; see Section 3), and the time (in seconds) needed to reach the target optimality gap of 0.5%. For example, the third row for instance Friedrichshain portrays the attributes of the constrained system optimum with tolerance factor � = 1.02. The total travel time is 621, and the users between the 506 different OD pairs are assigned to 1, 290 different paths. The actual travel time for 99% of all users is not more than 65.7% than that of the fastest route between their OD pair. Compared to the user equilibrium, their individual travel time are at most 11.7% higher. Note that the corresponding quantities for the system optimum (10th row) are 106.3% and 25%, respectively. Before we interpret the computational results, let us call attention to an apparent anomaly in the rows of Tables 2 and 3 that correspond to user equilibria. In theory, the normal unfairness, the loaded unfairness, and the UE unfairness should be equal to 1; however, in practice they are obviously not. The reason is that each user equilibrium is computed as the optimal solution of an ap­ propriately defined convex optimization problem as per Beckmann, McGuire, and Winsten (1956). As the algorithm terminates as soon as the value of the current solution is within 0.5% of that of an optimal solution, the solution reported here is merely an approximate user equilibrium. In some sense, the normal unfairness, the loaded unfairness, and the UE unfairness give information about its actual deviation from a user equilibrium. Incidentally, in the derivation of the normal arc lengths, we computed the user equilibrium with higher precision, namely a target optimality gap of 0.01% instead of 0.5%. This explains why the 99th percentiles of normal unfairness, loaded unfairness, and UE unfairness of the user equilibrium are not necessarily equal to one another. Clearly, the larger the tolerance factor � the closer is the objective function value of an associated constrained system optimum to that of the unconstrained system optimum, and the higher is its unfairness. On the other hand, smaller tolerance factors lead to “fairer” solutions but also result in larger gaps of the total travel time compared to the unconstrained system optimum. However, we will argue that a carefully chosen tolerance factor strikes a good balance between these two conflicting effects. For the sake of argument, let us consider instance Neukölln with � = 1.02. The gap between the total travel time of CSO1.02 and that of the system optimum is about a third of the gap between the user equilibrium and the system optimum. In fact, the travel time of the system optimum is 2, 653 compared to 2, 903 in user equilibrium and 2, 732 for CSO 1.02 . Moreover, the travel time of 99% of all users in CSO1.02 is at most 30.4% higher than that of any 12 Table 2. Characteristics of constrained system optima with different tolerance fac­ tors, Part I 99th unfairness percentile number of runtime factor objective number (sec.) of paths normal loaded UE free-flow iterations value Sioux Falls 31 0 5.098 1.040 1.031 UE 989 1.001 7448 27 0 4.908 1.282 1.187 749 1.001 1.01 7263 38 0 4.901 1.258 1.184 754 1.001 1.02 7256 0 34 4.789 1.265 1.195 7251 758 1.001 1.03 0 4.749 32 1.290 1.210 1.05 7239 812 1.035 0 4.712 56 1.283 1.178 893 1.060 1.10 7216 46 0 4.573 1.295 1.168 984 1.078 1.20 7207 0 4.598 64 1129 1.092 1.296 1.170 1.30 7201 4.599 78 0 SO 7199 1326 1.092 1.295 1.169 Friedrichshain UE 682 1713 1.011 4.382 27 0 1.036 1.062 4.163 45 1 1.01 628 1283 1.008 1.657 1.087 30 1 1.02 621 1290 1.017 1.652 1.117 4.132 1 1.03 613 1515 1.029 1.711 1.094 4.124 42 43 1 1.05 612 1594 1.046 4.130 1.733 1.092 1.10 594 1598 1.096 1.929 1.109 3.565 40 1 1 74 1.20 591 2080 1.170 2.060 1.177 3.932 1.30 591 2251 1.213 2.058 1.229 3.948 59 1 1 SO 591 2631 1.213 2.063 1.250 3.947 63 Winnipeg UE 857 14633 1.029 1.050 1.047 1.503 16 7 8 1.01 844 10224 1.009 1.119 1.027 1.429 15 1.402 16 8 1.02 842 11901 1.017 1.123 1.019 1.03 842 13123 1.027 1.142 1.027 1.389 18 8 1.409 23 10 842 15374 1.043 1.164 1.044 1.05 1.10 841 17846 1.068 1.192 1.054 1.411 30 12 33 13 1.203 1.058 1.429 1.20 18619 1.075 841 12 1.458 30 1.210 1.068 1.30 841 18755 1.078 1.449 33 14 SO 1.211 1.066 19331 1.076 841 Neukölln UE 3.806 21 17 1.063 1.053 2903 6744 1.025 15 7 3.182 4380 1.008 1.332 1.084 2794 1.01 8 3.054 17 1.02 1.304 1.072 2732 4700 1.015 18 8 1.03 2721 1.420 1.070 3.079 5665 1.028 10 2.987 22 1.450 1.099 1.05 2690 6427 1.045 1.10 2.944 47 17 1.493 1.125 2672 8755 1.091 54 17 2.292 10018 1.168 1.527 1.179 1.20 2653 15 1.30 2.327 48 1.539 1.193 2653 7983 1.183 SO 2653 58 48 1.555 1.197 2.335 8631 1.187 13 Table 3. Characteristics of constrained system optima with different tolerance fac­ tors, Part II 99th unfairness percentile number of runtime factor objective number (sec.) of paths normal loaded UE free-flow iterations value Mitte, Prenzlauerberg & Friedrichshain 9 16 2.236 1.040 1.032 UE 28091 1.015 1845 30 25 2.086 1.304 1.051 32476 1.008 1771 1.01 30 25 1.993 1.291 1.045 34618 1.017 1762 1.02 27 24 2.008 1.303 1.045 35392 1.026 1755 1.03 22 26 1.808 1.358 1.060 39320 1.046 1733 1.05 14 29 1.881 1.451 1.083 48968 1.086 1727 1.10 17 37 1.918 1.478 1.122 56687 1.122 1726 1.20 15 35 1.910 1.477 1.124 56304 1.123 1726 1.30 24 40 1.921 1.471 1.126 64431 1.127 1726 SO Chicago Sketch UE 46 9 1.592 1.039 1.046 18383 194564 1.017 27 4 1.543 1.101 1.052 18123 119696 1.007 1.01 46 8 1.509 1.123 1.047 18047 155800 1.016 1.02 57 11 1.492 1.148 1.044 18016 192152 1.025 1.03 69 14 1.499 1.193 1.055 17993 242188 1.043 1.05 89 19 1.504 1.211 1.074 17971 289999 1.072 1.10 118 25 1.496 1.227 1.090 17970 334364 1.081 1.20 118 24 1.498 1.224 1.092 17976 344830 1.085 1.30 117 25 1.496 1.238 1.093 17981 331146 1.087 SO Berlin UE 1584 15 2.400 1.057 1.058 16223 150922 1.038 904 9 3.191 1.135 1.906 98271 1.008 16254 1.01 1274 14 2.181 1.214 1.112 15806 142944 1.018 1.02 1626 19 2.058 1.247 1.066 15671 171452 1.028 1.03 2247 29 2.003 1.270 1.060 15632 216328 1.045 1.05 2689 39 2.000 1.333 1.083 15587 257707 1.084 1.10 3614 49 2.016 1.372 1.120 15572 295138 1.126 1.20 4184 52 2.022 1.398 1.128 15565 307050 1.137 1.30 5512 56 2.066 1.438 1.135 15544 322687 1.148 SO other traveler (between the same OD pair), compared to 55.5% in the system optimum. In other words, the reduction of unfairness amounts roughly to 45%. The numbers are similar for most of the other instances. Figures 5 and 6 depict the complete unfairness distributions for all instances. Let us again pick Neukölln to highlight typical effects. In CSO1.02 , the travel time of just 4.5% of all users is more than 10% than that of the fastest paths of their OD pairs. In contrast, this number is 15.3% for the ordinary system optimum; i.e., one sixth of all drivers experience delays that are significantly above and beyond that of their fellow drivers. Moreover, most users (around 80%) spend less time on the road than they would in equilibrium. Actually, for factor 1.02, only 0.3% of the users travel 10% more than in equilibrium. Compare this number to the 4.6% that travel at least 10% longer under the system optimum. 14 Sioux Falls 1 0.95 0.8 0.85 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.8 0.75 0.7 0.65 0.6 probability probability 0.9 1 1.2 1 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.6 0.4 0.8 probability 1 0 0.6 2 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.4 0.2 0.2 1.8 1.6 1.4 loaded unfairness 0.6 0.7 1 0.9 0.8 UE unfairness 1.1 0 1.2 1 1.5 2 4.5 2.5 3 3.5 4 free-flow unfairness 5 Friedrichshain 1 0.95 0.8 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.8 0.75 0.7 0.65 0.6 probability probability 0.9 0.85 1 1.2 1.4 1.6 1 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.6 0.4 0.8 probability 1 0.2 1.8 0 0.6 2 0.6 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.4 0.2 0.7 0.8 0.9 1 1.1 0 1.2 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.2 2.4 free-flow unfairness UE unfairness loaded unfairness Winnipeg 1 0.95 0.8 0.85 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.8 0.75 0.7 0.65 0.6 probability probability 0.9 1 1.2 1.4 1.6 1 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.6 0.4 0.8 probability 1 0.2 1.8 0 0.6 2 0.6 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.4 0.2 0.7 0.8 0.9 1 1.1 0 1.2 1 1.2 1.4 1.6 1.8 2 free-flow unfairness UE unfairness loaded unfairness Neukölln 1 0.95 0.8 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.8 0.75 0.7 0.65 0.6 probability probability 0.9 0.85 1 1.2 1.4 1.6 1.8 loaded unfairness 1 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.6 0.4 0.8 probability 1 0 0.6 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.4 0.2 0.2 2 0.6 0.7 1 0.8 0.9 UE unfairness 1.1 1.2 0 1 1.2 2.2 2 1.4 1.6 1.8 free-flow unfairness 2.4 Figure 5. Unfairness distributions for various tolerance factors, Part I To facilitate a comparison of the characteristics of constrained system optima with different tolerance factors, Figures 7–13 plot various percentiles of the different notions of unfairness. The 15 ‘Mitte, Prenzlauerberg & Friedrichshain’ 1 0.95 0.8 0.85 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.8 0.75 0.7 0.65 0.6 probability probability 0.9 1 1.2 1 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.6 0.4 0.8 probability 1 0 0.6 2 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.4 0.2 0.2 1.8 1.6 1.4 loaded unfairness 0.6 0.7 1 0.9 0.8 UE unfairness 1.1 0 1.2 1 1.2 2.2 2 1.4 1.6 1.8 free-flow unfairness 2.4 Chicago Sketch 1 0.95 0.8 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.8 0.75 0.7 0.65 0.6 probability probability 0.9 0.85 1 1.2 1.4 1.6 1 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.6 0.4 0.8 probability 1 0.2 1.8 0 0.6 2 0.6 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.4 0.2 0.7 0.8 0.9 1 1.1 0 1.2 1 1.2 1.4 1.6 1.8 2 2.2 2.4 1.4 1.6 1.8 2 2.2 free-flow unfairness 2.4 free-flow unfairness UE unfairness loaded unfairness Berlin 1 0.95 0.8 0.85 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.8 0.75 0.7 0.65 0.6 probability probability 0.9 1 1.2 1.4 1.6 loaded unfairness 1 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.6 0.4 0.8 probability 1 0.2 1.8 2 0 0.6 0.6 Factor UE 1.01 1.02 1.03 1.05 1.1 SO 0.4 0.2 0.7 0.8 0.9 1 UE unfairness 1.1 1.2 0 1 1.2 Figure 6. Unfairness distributions for various tolerance factors, Part II two diagrams on top of each figure represent the 95th and 99th percentile, respectively, of the four notions of unfairness. The four remaining graphs correspond to each unfairness definition and show the 95th, 97.5th and 99th percentiles, respectively. Let us draw attention to some typical effects, and we will once again use instance Neukölln when we need to mention concrete numbers. We first compare the travel times of users in any of the computed route guidance solutions to the length of their shortest paths in the uncongested network (free-flow unfairness). It is remarkable that for virtually all tolerance factors in our study, the increase of travel time due to congestion effects is significantly smaller than the corresponding increase in the (approximate) user equilibrium. For instance, for Neukölln and the 99th percentile, the free-flow unfairness for all constrained system optima is about 3 or lower, while the free-flow unfairness of the user equilibrium is 3.8. The significance of this observation is only reinforced by the fact that at equilibrium all users between the same OD pair experience the same delay, while this is not necessarily the case in a constrained system optimum. The second important observation 16 Sioux Falls 4.5 loaded UE 3.5 free-flow 3 2.5 2 1.5 UE 1 1.2 1.1 factor UE 4 free-flow 3.5 3 2.5 2 1 1.3 SO 1.1 normal unfairness loaded 4.5 1.5 1.09 percentile 99th 1.08 97.5th 1.07 95th 1.06 1.05 1.04 1.03 UE 1 1.2 1.1 factor 1.3 SO 1.3 percentile 99th 1.25 loaded unfairness 1 unfairness normal 5 99th percentile unfairness 4 95th percentile unfairness 5.5 unfairness normal 1.02 97.5th 95th 1.2 1.15 1.1 1.05 1.01 UE 1 1.2 1.1 factor 1.22 UE unfairness 1 1.3 SO 1.2 percentile 99th 1.18 97.5th 1.16 95th 1.14 1.12 1.1 1.08 1.06 1.2 1.1 factor 1.3 SO percentile 99th 5 97.5th 4.8 95th 4.6 4.4 4.2 4 1.04 3.8 1.02 1 UE 1 5.2 free-flow unfairness 1 UE 1 1.1 1.2 factor 1.3SO 3.6 UE 1 1.1 1.2 1.3SO factor Figure 7. Unfairness over the different factors and percentiles for instance Sioux Falls 17 Friedrichshain 4 loaded UE 3 free-flow 2.5 2 1.5 UE 1 1.2 1.1 factor free-flow 3 2.5 2 1.15 1.1 1.05 UE 1 1.2 1.1 factor percentile 99th 97.5th 95th 1.8 1.6 1.4 1 1.3SO 1.3 1.2 1.15 1.1 1.05 1.2 1.1 factor 1.3 SO percentile 99th 4.2 97.5th 95th UE 1 4.4 percentile 99th 1.25 1 1.3SO 1.2 free-flow unfairness 1 1.2 1.1 factor 2 97.5th 95th UE 1 2.2 percentile 99th 1.2 normal unfairness UE 3.5 1 1.3 SO 1.25 UE unfairness loaded 1.5 loaded unfairness 1 unfairness normal 4 99th percentile unfairness 3.5 95th percentile unfairness 4.5 unfairness normal 97.5th 95th 4 3.8 3.6 3.4 3.2 UE 1 1.1 1.2 factor 1.3SO 3 UE 1 1.1 1.2 1.3SO factor Figure 8. Unfairness over the different factors and percentiles for instance Friedrichshain 18 Winnipeg 1.35 loaded UE 1.25 free-flow 1.2 1.15 1.1 99th percentile unfairness 1.3 95th percentile unfairness 1.55 unfairness normal UE 1 1.1 1.2 factor 1.35 1.3 1.25 1.2 1.15 UE 1 1.2 1.1 factor 1.3 SO 1.2 percentile 99th 97.5th 1.18 97.5th 95th 1.16 95th 1.05 1.04 1.03 loaded unfairness normal unfairness UE free-flow 1.22 percentile 99th 1.06 1.02 1.14 1.12 1.1 1.08 1.06 1.01 1.04 UE 1 1.2 1.1 factor 1.02 1.3 SO 1.07 1.04 1.03 1.02 free-flow unfairness 95th 1.2 1.1 factor 1.3 SO percentile 99th 1.5 97.5th 1.05 UE 1 1.55 percentile 99th 1.06 UE unfairness loaded 1.4 1 1.3SO 1.07 97.5th 95th 1.45 1.4 1.35 1.3 1.25 1.01 1 1.45 1.05 1.08 1 unfairness normal 1.1 1.05 1 1.5 UE 1 1.1 1.2 factor 1.3SO 1.2 UE 1 1.1 1.2 1.3SO factor Figure 9. Unfairness over the different factors and percentiles for instance Winnipeg 19 ‘Mitte, Prenzlauerberg & Friedrichshain’ 1.9 loaded 1.7 UE 1.6 free-flow 1.5 1.4 1.3 1.2 1.1 1.2 factor 1.12 normal unfairness UE free-flow 1.8 1.6 1.4 1 1.3SO 1.1 1.3 SO 1.5 percentile 99th 97.5th 1.4 97.5th 95th 1.35 95th 1.06 1.04 1.3 1.25 1.2 1.15 1.1 1.02 1.05 UE 1 1.2 1.1 factor 1 1.3 SO 1.14 1.08 1.06 1.04 1.3SO percentile 99th 97.5th 2.1 free-flow unfairness 95th 1.1 1.2 factor 2.2 97.5th 1.1 UE 1 2.3 percentile 99th 1.12 95th 2 1.9 1.8 1.7 1.02 1 1.2 1.1 factor 1.45 1.08 1 UE 1 percentile 99th loaded unfairness UE 1 1.14 UE unfairness loaded 2 1.2 1.1 1 unfairness normal 2.2 99th percentile unfairness 1.8 95th percentile unfairness 2.4 unfairness normal 1.6 UE 1 1.1 1.2 factor 1.3SO 1.5 UE 1 1.1 1.2 factor 1.3 SO Figure 10. Unfairness over the different factors and percentiles for instance ‘Mitte, Prenzlauerberg & Friedrichshain’ 20 Neukölln 2.4 loaded UE 2 free-flow 1.8 1.6 1.4 1.1 1.2 factor UE 3 free-flow 2.5 2 1 1.3SO 1.18 percentile 99th 1.16 97.5th 1.14 95th 1.12 1.1 1.08 1.06 UE 1 1.2 1.1 factor 1.3 SO 1.6 percentile 99th 1.5 loaded unfairness UE 1 1.2 normal unfairness loaded 1.5 1.2 1 unfairness normal 3.5 99th percentile unfairness 2.2 95th percentile unfairness 4 unfairness normal 1.04 97.5th 95th 1.4 1.3 1.2 1.1 1.02 1 UE 1 1.2 1.1 factor 1.2 UE 1 1.2 1.1 factor 1.3 SO 4 1.18 percentile 99th 3.8 percentile 99th 1.16 97.5th 3.6 97.5th 1.14 95th 3.4 95th 1.12 1.1 1.08 1.06 free-flow unfairness UE unfairness 1 1.3 SO 3.2 3 2.8 2.6 2.4 1.04 2.2 1.02 2 1 UE 1 1.1 1.2 factor 1.3SO 1.8 UE 1 1.1 1.2 factor 1.3SO Figure 11. Unfairness over the different factors and percentiles for instance Neukölln 21 Chicago Sketch 1.4 loaded 1.3 UE free-flow 1.25 1.2 1.15 1.1 UE 1 1.2 1.1 factor UE 1.4 free-flow 1.3 1.2 1 1.3 SO 1.09 97.5th 95th 1.06 1.05 1.04 1.03 1.2 1.1 factor 1.3 SO percentile 99th 97.5th 1.2 loaded unfairness 1.07 UE 1 1.25 percentile 99th 1.08 normal unfairness loaded 1.1 1.05 1 unfairness normal 1.5 99th percentile unfairness 1.35 95th percentile unfairness 1.6 unfairness normal 1.02 95th 1.15 1.1 1.05 1.01 UE 1 1.2 1.1 factor 1.1 UE unfairness 95th 1.07 1.06 1.05 1.04 1.03 1.2 1.1 factor 1.3 SO percentile 99th 1.55 97.5th 1.08 UE 1 1.6 percentile 99th 1.09 97.5th 95th 1.5 1.45 1.4 1.35 1.02 1.01 1 1.3 SO free-flow unfairness 1 UE 1 1.1 1.2 factor 1.3SO 1.3 UE 1 1.1 1.2 1.3SO factor Figure 12. Unfairness over the different factors and percentiles for instance Chicago Sketch 22 Berlin 1.8 loaded 1.6 UE free-flow 1.5 1.4 1.3 1.2 99th percentile unfairness 1.7 95th percentile unfairness 3.5 unfairness normal unfairness normal loaded 3 UE free-flow 2.5 2 1.5 1.1 UE 1 1.2 1.1 factor 1.16 95th 1.1 1.08 1.06 97.5th 95th 1.3 1.25 1.2 1.15 1.05 1.2 1.1 factor 1 1.3SO 1.9 percentile 99th 1.8 97.5th 1.7 95th 1.6 1.5 1.4 1.3 factor 97.5th 95th 2.4 2.2 2 1.6 1.3SO percentile 99th 2.6 1.1 1.2 1.3SO 2.8 1.8 1.1 1.2 1.1 factor 3 1.2 UE 1 UE 1 3.2 free-flow unfairness UE 1 2 UE unfairness percentile 99th 1.1 1.02 1 1.3 SO 1.35 1.04 1 1.2 1.1 factor 1.4 97.5th 1.12 UE 1 1.45 percentile 99th 1.14 normal unfairness 1 1.3SO loaded unfairness 1 1.4 UE 1 1.1 1.2 1.3SO factor Figure 13. Unfairness over the different factors and percentiles for instance Berlin 23 to be made is the strong correlation between the loaded unfairness and the normal unfairness, which is illustrated by the two diagrams in the middle of each figure. Bounding the normal unfairness (a static measure) results in bounded loaded unfairness (a dynamic measure), which explains why our approach is successful. Factor UE 1.01 1.02 1.03 1.14 C(x)/C(SO ) rag replacements 1.12 PSfrag replacements 1.1 1.08 1.06 1.04 1 Factor SO 1.01 1.02 1.03 2 1.9 1.8 1.7 1.6 1.5 1.4 1.3 1.02 loaded unfairness 2.1 loaded unfairness 1.16 1.2 SF F W N C (x)/C(SO ) MPF CS B 1.1 SF F W N MPF CS B Figure 14. Efficiency and loaded unfairness of constrained system optima across all instances. The plot on the left shows the efficiency (the cost of the solution over the cost of the system optimum) of select constrained system optima vs. that of the associated user equilibria; the plot on the right compares the loaded unfairness of the same solutions with that of the corresponding system optima. Figures 14 and 15 provide conclusive evidence of the benefits of the solutions we propose; con­ strained system optima with appropriately chosen tolerance factors bring together the favorable attributes of user equilibria and system optima. In Figure 14, we display constrained system op­ tima with tolerance factors close to 1.02 and compare them with the user equilibrium and the unconstrained system optimum, both in terms of efficiency and fairness. Figure 15 illustrates the tradeoff between efficiency and fairness achieved by constrained system optima. The graph shows, for each of the instances we studied, system optima (on the left), user equilibria (at the bottom) and the intermediate solutions represented by constrained system optima (in the center). The cir­ cled data-points correspond to CSO1.02 , for the various instances. In summary, constrained system optima with user equilibrium travel times as normal lengths provide a handle to effectively control the tradeoff between fairness and efficiency. 4.3. Performance of the algorithm. Let us briefly discuss our findings with respect to the running time needed by the algorithm described in Section 3. Figure 16 shows a detailed study of the effects of varying the tolerance factor and the target optimality gap. We only present the results for instances Chicago Sketch and Berlin because they are the largest and hence arguably the most difficult ones. For each selected instance, the figure contains a graph describing the objective function value, another one illustrating the number of iterations, and finally one displaying the computation time (in seconds). Most notably, the time needed by our algorithm to compute a constrained system optimum is typically not larger than that for computing an unconstrained system optimum, and it is only some­ what larger than that for getting a user equilibrium. In fact, the problem of finding a constrained system optimum becomes computationally more costly with increasing values of the tolerance fac­ tor �. The reason is that the number of allowable paths increases. However, the constrained shortest 24 PSfrag replacements 2.2 Instance SF F W N MPF CS B loaded unfairness 2 1.8 SO � 1.6 CSO 1.4 � 1.2 � � � �� 1 1 UE 1.02 1.04 1.06 1.08 1.1 1.12 1.14 1.16 C(x)/C(SO ) Figure 15. Tradeoff between efficiency and unfairness. For all instances, we plot the tradeoff curve between the efficiency (the cost of the solution over the cost of the system optimum) vs. the loaded unfairness. The left area of the graph corresponds to system optima (SO), the lower area corresponds to user equilibria (UE), and the circled data-points (denoted with ‘�’) correspond to constrained system optima with � = 1.02 (CSO1.02 ). path subproblems become easier because the normal lengths are less binding. In this trade-off sit­ uation, the total work and the number of iterations increase, but the work per iteration decreases. Generally, most of the time is spent on computing constrained shortest paths (which implies that improved algorithms for this subproblem would yield greatly improved overall performance). From our experience, instances with a few thousand nodes, arcs and commodities can be solved on an average PC within minutes. Bigger instances like Berlin take longer but can also be solved without difficulty. Very large instances (e.g., networks with twice as many nodes and arcs as Berlin and with over one million OD pairs) could not be handled mostly due to memory problems resulting from the path-based formulation. With respect to Partan, we found that the running time is reduced by 30% on average for our target optimality gap of 0.5% when compared to the original version of the Frank-Wolfe method. The reduction is even bigger if just the most difficult instances are considered. 5. Summary and Conclusion When designing a route guidance system, it is desirable to explicitly aim at reducing the total (and therefore the average) travel time by putting it into the objective function of the underlying optimization problem. Yet, without further constraints, this would include the possibility that some vehicles are assigned to fairly long paths in order to make the shorter paths available to other drivers. Obviously, this phenomenon would render such a system unacceptable for several drivers, jeopardizing the desired effect of improved system performance. We propose to capture this aspect of human behavior by imposing constraints on paths to elimi­ nate lengthy detours. While it may be ideal to explicitly enforce that travel times of recommended routes between the same origin-destination pair do not deviate significantly from each other, our computational results justify the use of a computationally simpler model, in which the deviation is not measured with respect to the actual flow but with respect to a “normal length”. Another plus of the latter tactic is that drivers with different origin-destination pairs can be treated equally. 25 Chicago Sketch Berlin 18700 18600 18500 16400 gap 0.5 1.0 16300 1.0 2.0 16200 2.0 4.0 18300 16000 15900 18200 15800 18100 15700 18000 17900 4.0 16100 value 18400 value 16500 gap 0.5 15600 UE 1 1.2 1.1 15500 1.3 SO UE 1 60 gap 0.5 10 1.0 2.0 40 4.0 iterations iterations 2.0 15 gap 0.5 50 1.0 20 4.0 30 20 5 10 UE 1 1.2 1.1 0 1.3 SO UE 1 120 2.0 80 seconds 2000 20 1000 1.2 factor 1.3 SO 2.0 4.0 3000 40 1.1 1.0 4000 4.0 60 gap 0.5 5000 1.0 UE 1 1.3 SO 6000 gap 0.5 100 0 1.2 1.1 factor factor seconds 1.3 SO factor 25 0 1.2 1.1 factor 0 UE 1 1.1 1.2 1.3 SO factor Figure 16. Specifics of the algorithm for various optimality gaps and tolerance factors for instances Chicago Sketch and Berlin 26 Our computational study suggests that the travel time in user equilibrium is an excellent choice for defining the normal length. In fact, it turns out that this approach offers significant advantages over both the traditionally considered user equilibrium and the system optimum. On the one hand, it guarantees superior fairness for the individual user compared to the system optimum, in which individual travel times between the same origin-destination pair may deviate substantially from each other. On the other hand, the total travel time of a constrained system optimum is still close to that in the (uncon­ strained) system optimum and thus much better than in user equilibrium. This shows that optimal route guidance with fairness guarantees is in principle feasible. Apart from the proof of concept, we consider our algorithm practical for problems with several thousand nodes, arcs, and commodities. Future work should incorporate the dynamic aspect of traffic and the behavior of unguided users. Acknowledgments The authors are grateful to Dr. Stefan Gnutzmann (DaimlerChrysler AG, Berlin), who excited our work on route guidance, and to Dr. Stefan Gnutzmann and Valeska Naumann (DaimlerChrysler AG, Berlin) for several stimulating discussions and support. The second author acknowledges support by grant 03-MOM4B1 “Models and Algorithms for Dynamic Route Guidance in Traffic Networks” of the German Ministry for Science and Education (BMBF). The last two authors gratefully acknowledge support by a General Motors Innovation Grant and the High Performance Computation for Engineered Systems (HPCES) program of the SingaporeMIT Alliance (SMA).