ii

Declaration of Authorship

I hereby declare that I wrote this thesis on my own and without Affidavit:

the use of any other than the cited sources and tools. All passages which are literally or in general matter taken out of publications or other sources are marked as such, as well as that the thesis has not yet been handed in neither in this nor in equal form at any other official commission.

____________________________

Berlin, 7 April 2011 Ingo Kleinert

iii

iv

Zusammenfassung (German summary)

Das weltweite Straßenverkehrsaufkommen steigt beständig an bei annähernd gleich bleibenden Straßenverhältnissen und -kapazitäten. Die Vermeidung von Staus zur Gewährleistung einer möglichst geringen Reisezeit der Verkehrsteilnehmer erfordert eine durchdachte Verkehrsplanung. Vorschläge zur Erhebung von Mautgebühren sind in der Wissenschaft ein zentraler Lösungsansatz, welcher jüngst auch in mehreren Städten weltweit praktiziert werden. Jede Straße des gesamten Verkehrsnetzes differenziert zu besteuern ist aus technischen, ökonomischen und politischen Gründen noch nicht möglich. Dementsprechend untersuchen wir das mathematischne Optimierungsproblem, Mautgebühren für einen vorher festgelegten Teil der Straßen zu berechnen mit dem Ziel, die Gesamtfahrzeit aller Verkehrsteilnehmer zu verringern. Ferner wenden wir uns dem verwandten Problem zu, Mautgebühren zu berechnen, wenn nur eine Höchstanzahl an bemautbaren Straßenabschnitten zulässig ist. Zu beiden Problemen präsentieren wir Algorithmen und diskutieren deren Effizienz anhand realer Beispiele. Schließlich integrieren wir die erzielten Resultate in einem agenten-basierten Verkehrssimulator, um somit dessen Lösungen bei verringerter Laufzeit zu verbessern.

Abstract

The world-wide road traffic volume increases continuously while street capacities cannot be expanded accordingly. Coping with traffic congestion to reduce the overall travel time requires sophisticated traffic planning methods. Charge fees for the usage of network capacities is of special interest in scientific literature and, recently, has been implemented in practise. However, for technical, economical or political reasons, it is still not practicable to impose tolls on every edge of a given traffic network individually. Therefore, we study the mathematical optimization problem of computing tolls for a predefined subset of roads with the objective of reducing the total travel time. Furthermore, we discuss the related problem of computing tolls when only a finite number of taxable roads is accounted for. For both problems we present algorithms applicable on general large-scale traffic networks. We test their performance and solution quality systematically on real-world instances. Finally, the results are integrated into an agent-based transport simulator to achieve qualitatively better solutions and reduced convergence time of the simulation process.

Contents

1  Introduction  1

1.1  Related Work  4

1.2  Outline of the Thesis  4

2  Preliminaries  7

2.1  Graphs and Flows  7

2.2  Wardrop Transportation Model  10

2.3  The Price of Anarchy  18

3  Taxes on Subnetworks  25

3.1  Preliminaries  26

3.2  NP-Hardness of Computing Optimal Taxes on Subnetworks  27

4  Toll Computation Algorithms for General Networks  35

4.1  The Algorithms  35

4.2  Flow Computation with CMCF  39

4.3  Data sets  40

4.4  The Choice of the Set of Taxable Edges  43

4.5  Computational Results  43

4.6  Convergence Time  48

5  The Cardinality Constrained Toll Problem  53

5.1  NP-Hardness  53

5.2  Computational Study  59

6  Integration into a Multi-Agent Transport Simulator  67

6.1  Tolls in MATSim  68

6.2  Computational study  70

7  Conclusion  79

Bibliography   81

vii

1 Introduction

After the invention of the first modern motor vehicle by Karl Benz in 1885, the number of automobiles has grown continuously and now, in 2011, has almost reached one billion, as it is documented on the right hand part of Figure 1.1. The traffic situation is far away from being satisfactory, especially in big cities. Traffic jams occur in every day’s rush-hour and special events as sport or music events normally cause heavy traffic which deteriorates quality of life. Noise disturbance and slow traffic throughput by increased total travel time have an impact on humans well-being. In American urban areas with more than a million residents, a person spent on average about 46 hours in a traffic jam in the year 2007 [50]. For this period the Texas Transportation Institute estimated the cost of traffic congestion in the USA up to 87.2 billion for wasted fuel and lost productivity. Traffic congestion significantly increases gas consumption and carbon dioxide emission which lead to significant environmental pollution. Over the last years, the traffic situation became even worse. In particular, the rising mega-cities with more than 10 million inhabitants in Asia, Middle and South America suffer from extremely heavy traffic. For instance, the traffic volume in China has increased by 15% in 2005 and the average travel speed of cars in central Beijing has decreased from 45 km/h in 1994 to 12 km/h in 2003 [28]. The traffic volume is expected to grow even faster in the next three decades up to 2 billion cars, the double of the actual number [55]. Thus, sound network planning and traffic control will become even more important. From the beginning of scientific studies in this field, selfish behaviour of traffic participants has been considered to be one of the main reasons for traffic inefficiency [14, 24]. Such non-cooperative attitude normally leads to a deteri-oration of the traffic situation. However, there is also the paradoxical situation that the traffic time decreases while the street network capacity improves. This traffic paradox was described by Braess [14] and indeed observed in several cities, among them New York in 1990, where the permanently congested 42nd street has been closed down for construction works which led to an overall traffic improvement. Likewise, in 1969 the city of Stuttgart had to close a newly

1

1 Introduction

Figure 1.1: On the left hand side, there is documented the number of passenger cars by region between 1980 and 2004 [46]. On the right, there is indicated the estimated growth of the world-wide number of motor vehicles between 1950 and 2030 [55]

built road due to a great increase of travel time.

Modelling selfish behaviour of network participants has been studied extensively in science ever since (see Beckmann et al. [10] and Sheffi [51]). The original concept by John Glenn Wardrop [60] simulates the interactions between the network users as a noncooperative nonatomic game and has been generalized in various directions. The network is given as a directed graph with continuous non-decreasing latency functions on the edges, which model the influence of congestion. In addition, a set of origin-destination pairs (commodities) is given, each of them equipped with a demand, which specifies the continuous amount of agents to be routed from the respective origin to the destination node. Every agent controls an infinitesimal small amount of flow and selfishly tries to route from his origin to the destination with the objective of minimizing the experienced latency, given by the latency functions of every edge. The equilibrium state where no agent can improve his travel time by switching to another path is called Wardrop equilibrium [21, 60]. In general, this solution is far away from optimum. Despite the classical Wardrop model has been known for a long time, the problem of quantifying the efficiency loss of selfishly motivated network users has been considered only recently. Koutsoupias and Papadimitriou [37] introduced the price of anarchy, which measures the worst-case ratio of the cost

2

of a flow in Wardrop equilibrium over the optimal flow. In general networks, the efficiency loss of selfish behaviour is unbounded. This conclusion remains true even for such simple networks which only consist of parallel edges with general latency functions [49]. For general networks equipped with special latency functions including affine linear functions and polynomials with nonnegative coefficients, however, the price of anarchy is well understood and bounded [18, 48, 49].

For over 80 years researcher have searched solutions to reduce the large efficiency loss. Pigou [45] and Beckmann et al. [10] proposed congestion pricing strategies which impose tolls on the edges of a traffic network such that they become less attractive. The traffic participants change their route accordingly and finally establish an equilibrium state with less total travel time. Under the assumption that all roads can be taxed individually and all traffic participants value time and tolls equally, there always exist a toll distribution that induces an optimal equilibrium. For example, Marginal cost pricing, where the imposed tolls are equal to the marginal costs of the optimal solution, always lead to a system optimal equilibrium [10].

Over the last years, congestion pricing has been implemented in several cities all over the world including Norway’s three major cities Bergen, Oslo, Trondheim [39], as well as London [58], Santiago de Chile [54], Stockholm [25] and Singapore [52, 44]. Until now, in all of these applications only designated areas are considered for tolls. Charging individual fees for all network roads still is far away from practical application so that classical marginal cost pricing is not feasible at all.

It is therefore the aim of the present work to study the mathematical optimization problem of computing tolls for a predefined subset of roads with the objective of reducing the total travel time. In addition, we discuss the related problem of computing tolls given a cardinality constraint on the number of taxable roads. For both problems algorithms are presented that are applicable on general largescale traffic networks. In over 2500 computations we test their performance and solution quality on several real-world instances including various districts of Berlin, the capital of Germany, and a reduced road network of Switzerland. Finally, we integrate the results into an agent-based dynamic transport simu-lator. It turns out that, compared to the standard solutions, qualitatively better solutions and reduced convergence time of the simulation process are achieved.

3

1 Introduction

1.1 Related Work

Already in 1920 Pigou [45] observed that traffic participants should pay a fee equal to the difference of marginal social and marginal private cost (marginal cost pricing) to induce a system optimal traffic distribution. Later on, many scientists studied the theoretical background of marginal cost pricing, among them Knight [35], Beckmann et al. [10] and Smith [53]. Bergendorff et al. [11] and Larsson and Patricksson [40] showed that the set of tolls which induces a system optimal user equilibrium can be characterized by a non-empty polyhedron defined in terms of a system of linear inequalities. Hearn and Ramana [32] introduced toll optimization problems where the objective is to minimize a tolldependent function over the polyhedron of feasible tolls which induce an optimal flow. Subsequently, several efficient algorithms for computing such secondary toll optimization problems were worked out, among them toll computation algorithms which minimize the total revenue collected from the network users, see Dial [22, 23] and Bai et al. [4]. Furthermore, Bai and Rubin [6] and Bai et al. [5] proposed algorithms for the NP-hard minimum toll booth problem where the objective is to minimize the number of taxed edges. The toll computation problem in which only a subset of roads is taxable was studied by Yang and Lam [61] for queuing networks and Verhoef [59] gave an analytical study for small networks. Hoefer et al. [33] presented a polynomial time algorithm to find optimal taxes for parallel edges networks with affine linear latencies. In addition, they proved the NP-hardness of this problem even for two-commodity instances with affine linear latency functions. Harks et al. [31] presented an analytical study for single-commodity parallel edges networks and devised a polynomial algorithm for instances where the total travel time is a piecewise convex function of the demand d. This condition is satisfied by practically relevant functions such as M/M/1 functions and latency functions similar to the Bureau of Public Roads functions [16].

1.2 Outline of the Thesis

Since the application of optimal congestion pricing still is not possible, we study in this thesis the problem of calculating tolls on a predefined subset of edges of a network such that the resulting equilibrium state is optimal with respect to

4

total travel time. The outline of the thesis is as follows. Chapter 2 provides the notation that we need throughout this thesis. We define basic terms used in graph theory and introduce the mathematical net-work model by John Wardrop [60] which describes the selfish behaviour of traffic participants in routing network instances. We present simple examples and introduce the price of anarchy to quantify the efficiency loss of the selfish user equilibrium.

After having introduced the basic model, we formulate the problem of calculating optimal tolls on a subset of network edges in Chapter 3. We demonstrate the non-uniqueness of optimal tolls and present the NP-hardness proof for the problem of finding optimal tolls given a predefined subset of taxable edges by Hoefer et al [33], which uses a reduction from the PARTITION problem. Given the complexity of finding optimal taxes for a subset of edges even on simple networks with only parallel edges, in Chapter 4 we concentrate on the design of algorithms for general networks. Four algorithms are presented that iteratively change the imposed tolls with the aim of decreasing the total travel time. The basic idea is to increase the toll on those edges where the Wardrop equilibrium flow exceeds the system optimal flow and to decrease it, otherwise. Three of the four algorithms follow a gradient-descent approach whereas the fourth algorithm is inspired by a combinatorial approach. We analyse the quality and the convergence behaviour of all presented algorithms via an extensive computational study on real-world large-scale network instances which include several districts of Berlin and a reduced road network of Switzerland. The results for almost every instance show, that imposing tolls on only a very small number of edges already reduces the total travel time significantly. In Chapter 5 we discuss the related mathematical problem of actually selecting a good subset of taxable edges. Our toll computation problem is subject to a cardinality constraint on the number of taxable edges, for which we show NPhardness. Then, we present and evaluate several edge selection heuristics in a computational study based on our toll computing algorithms. It turns out, that our gradient descent-based combined algorithms perform very well on almost every test instance. They converge fast and significantly reduce the total travel time already for small cardinality constraints

Finally, in Chapter 6 we integrate the computed tolls into a dynamic agentbased transport simulator called MATSim to achieve qualitatively better solu-

5

1 Introduction

tions and reduced convergence time of the simulation process. Bearing in mind the completely different approaches of the macroscopic static Wardrop model and the dynamic agent-based MATSim model, we cannot expect an improvement for all cases. However, for some test instances we were able to improve the simulation process and its solution quality significantly.

6

2 Preliminaries

This chapter provides the notation that is needed throughout this thesis. First, we define basic terms used in graph theory. Next, the mathematical network model by John Wardrop [60] is introduced which describes the selfish behaviour of traffic participants in routing network instances. We present simple examples and introduce the price of anarchy to quantify the efficiency loss of the selfish user equilibrium.

2.1 Graphs and Flows

In this work we will only deal with directed graphs. A digraph G = (V, E) consists of a finite set of nodes or vertices V , and E ⊆ V × V , a set of edges. Every edge e i = (v j , v k ) ∈ E has a starting node v j ∈ V and final node v k ∈ V , as illustrated in Figure 2.1. Directed edges are generally called arcs or links. Any digraph G represents, for instance, a road network, where the nodes refer to cities, road intersections or points of interests, whereas the edges can be imagined to be roads or highway lanes. In our approach parallel links are allowed, which connect the same pair of nodes by equally directed links (see Figure 2.1). Imagine a highway with several lanes, where every lane is represented by one edge. If there do not exist such parallel links and no loop e i = (v i , v i ), we call the graph simple.

Furthermore, it is convenient to introduce the notions δ ⁺ (u) := {(v, u) ∈ E} to be the set of all incoming, and δ ⁻ (u) := {(u, v) ∈ E} to be the set of all outgoing links, respectively.

A walk p in graph G is an ordered sequence of nodes v 1 , . . . , v k and edges (v i , v i+1 ) ∈ E for all i ∈ {1, . . . , k}. As we are only interested in short walks, we omit walks which revisit a given node v i ∈ V . A walk p, for which all nodes are distinct, is called a simple (v 1 , v k )-path with starting node v 1 and final node v k . In transportation models the start node usually is denoted by u ∈ V or s ∈ V and the end node, or target node, is denoted by v ∈ V or t ∈ V . A set of all (s, t)- pathsin a digraph is commonly denoted by P s,t . A network flow is a function

7

2 Preliminaries

f : P → R + 0 . f assigns to every path P ∈ P a non-negative real value f (P ), or simply f P , meaning the amount of flow routed via path P . The total flow P e f P and f (E ) = assigned to edge e ∈ E is defined as f e = e∈E f e for a

set of edges E ⊆ E. Every path flow uniquely defines the flow on all edges. Theorem 2.1 shows, that conversely every edge flow defines a path flow, so that we can consider both arc flow and path flow formulations to be equivalent.

Theorem 2.1 (Flow Decomposition Theorem). Every link-based flow f on a net-work G = (V, E) can be decomposed into a path and a cycle flow with at most |E| cycles with non-zero flow and |V | + |E| non-zero paths and cycles altogether.

Proof. See [3].

Additionally, we are given a demand vector d = (d v ) v∈V ∈ R ^{|V |} which specifies for every node v ∈ V the amount of flow which starts in v. If d v < 0, then v absorbs flow and is, therefore, a sink node. d v > 0 and d v = 0 means that v is a source and intermediate node, respectively. The flow f is feasible if the demand of every node v ∈ V is satisfied by f , i.e.

For a feasible flow the equation v∈V d V = 0 is satisfied. If there are exactly one

source s ∈ V and one sink node t ∈ V in the network G, we call f a s-t-flow. Let us switch to the treatment of traffic networks, in which an edge can cause costs, the origin of which could be

8

• the time needed to pass the street,

• the fuel consumption,

• air pollution and

• the erosion of street lanes.

To model such fixed costs, we introduce arc costs c e ∈ R +

Then, the cost of a static flow f is defined as C(f ) = One important flow problem is to find a minimum cost flow f ^∗ for given de-mand values d v , v ∈ V , i.e.

The minimum cost flow problem 2.2 can be solved efficiently by linear programming [3]. Further information about graph theory and its wide variety of interesting applications is found in textbooks [3], [8] and [12].

9

2 Preliminaries

2.2 Wardrop Transportation Model

In the previous chapter the basic terms of graph and network theory have been introduced. Now, we explain the mathematical network model put forward by John Wardrop [60] which describes the selfish behaviour of traffic participants in routing network instances. We present simple examples and introduce the price of anarchy to quantify the efficiency loss of the selfish user equilibrium. In most cases, minimizing costs (money and time) is the objective of well posed strategies. Naturally, a road user wants to arrive at his destination without loosing much time. To achieve this objective, everybody acts selfishly without taking into consideration the other network participants. If there occurs no congestion caused by the users, i.e. the edge latencies do not depend on the actual amount of flow, the optimal solution are shortest paths. All drivers with the same departure and destination would use the same (shortest) path. This is not a realistic scenario because congestion often occurs in reality.

2.2.1 The Network

In the traffic network model invented by John Glen Wardrop [60], a network instance G = (V, E) is given by V , the set of nodes (vertices) and E, the set of edges (links). Furthermore, there are k source-destination pairs called commod-

ities (s 1 , t 1 ), . . . , (s k , t k ) ∈ V × V, s i = t i ∀i ∈ {1, . . . , k} with finite and positive traffic demands d = (d i ) i∈{1,...,k} . As above, these demand values measure the amount of flow which has to be routed from source s i to the destination t i . P i is the set of all paths from s i to t i in G. A flow f is called feasible with respect to d, if for all commodities i ∈ {1, . . . , k} a total of d i units of flow are routed from s ⁱ to t i :

2.2.2 Link Performance Functions

In the previous chapter we only have considered flows with fixed costs. But this is not a realistic model for transportation networks. To model congestion, we assign a link performance functions to every edge e ∈ E instead of assigning fixed costs.

10

Definition 2.2 (link performance function). A link performance function

e : R + 0 −→ R +

0

is a function which assigns a non-negative real cost value to a given nonnegative flow f e on edge e ∈ E.

Definition 2.3 (Total latency). The total latency (total cost) of a network flow f is defined as

For routing traffic in road networks it is quite natural to define them as nondecreasing and continuous, which means that the travel time on a road will not decrease with higher traffic volume. Most of the common link performance functions depend both on the free-flow travel time, the time needed to travel the edge with zero flow, and on the link capacity. For a detailed overview of proposed link performance functions, we refer to [15]. In this work we mainly restrict to networks with standard link performance functions.

0 ←→ R ⁺ Definition 2.4 (standard function). A function : R + 0 is called standard if it is

• non-decreasing,

• differentiable and

• semi-convex, that means x · (x) is convex.

A convenient and in road networks widely used link performance function, which is standard, was proposed by engineers of the Bureau of Public Roads (BPR) [16]. It is the monomial function

with the following parameters

• α being the free flow travel time, i.e. the time needed to traverse the edge under no congestion, for instance at night,

11