ASSIGNMENT INFORMATION, TRAFFIC PLANNING

Transport optimization

Michael Patriksson

21st March 2001

Introduction

The assignment in the theme of traffic planning in the course aims to provide some insights into the properties of traffic equilibria. MATLAB is the intended instrument in the investigation; some small networks are available for these tests on the course web page.

This document includes (a) preparatory questions, which are good to answer before the assignment is done but are not to be handed in; and (b) the assignment questions, including bonus questions.

Summary questions and numerical examples

Some of the numerical questions can be good to do to get a feel for the network model. Answers are available. The notation follows that of my book.

1. (Summary) Describe how an equilibrium arises in a real network.

2. (Summary) When does a Wardrop equilibrium exist?

3. (Summary) When is an equilibrium link or route flow unique?

4. (Summary/Calculations) For the following instance of [TAP], give the link–route incidence matrix Δ, the node–link incidence matrix A, and give the polyhedral sets of feasible link and route flows explicitly. Calculate the equilibrium route and link flows according to the Wardrop equilibrium principle. The network has 2 nodes and 2 links; a total of 5 vehicles travel between node 1 and node 2.

Link Travel cost
1: (1, 2) t_{1}(f_{1}) = 2 + f_{1}
2: (1, 2) t_{2}(f_{2}) = 1 + 2f_{2}

(This question will be answered in the lecture on traffic assignment.)

5. (Summary/Calculations) For the following instance of [TAP], give the link–route incidence matrix Δ, the node–link incidence matrix A, and give the polyhedral sets of feasible link and route flows explicitly. Calculate the equilibrium route and link flows according to the Wardrop equilibrium principle.

The network has 3 nodes and 4 links; a total of 4 vehicles travel between node 1 and node 3.

Link Travel cost
1: (1, 2) t_{1}(f_{1}) = 2 + f_{1}^{2}
2: (1, 2) t_{2}(f_{2}) = 3 + f_{2}
3: (2, 3) t_{3}(f_{3}) = 1 + 2f_{3}^{2}
4: (2, 3) t_{4}(f_{4}) = 2 + 4f_{4}

6. (Summary/Calculations) For the following instance of [TAP], give the link–route incidence matrix Δ, the node–link incidence matrix A, and give the polyhedral sets of feasible link and route flows explicitly. Calculate the equilibrium route and link flows according to the Wardrop equilibrium principle.

The network has 5 nodes and 5 links; a total of 2 vehicles travel between node 1 and node 5, and 3 vehicles travel between node 2 and node 5.

Link Travel cost
1: (1, 3) t_{1}(f_{1}) = 1
2: (2, 3) t_{2}(f_{2}) = 2
3: (3, 4) t_{3}(f_{3}) = 2 + f_{3}
4: (3, 4) t_{4}(f_{4}) = 1 + 2f_{4}
5: (4, 5) t_{5}(f_{5}) = 1

7. (Summary/Calculations) For the following instance of [TAP], give the link–route incidence matrix Δ, the node–link incidence matrix A, and give the polyhedral sets of feasible link and route flows explicitly. Calculate the equilibrium route and link flows according to the Wardrop equilibrium principle.

The network has 4 nodes and 4 links; a total of 6 vehicles travel between node 1 and node 4.

Link Travel cost
1: (1, 2) t_{1}(f_{1}) = 50 + f_{1}
2: (1, 3) t_{2}(f_{2}) = 10f_{2}
3: (2, 4) t_{3}(f_{3}) = 10f_{3}
4: (3, 4) t_{4}(f_{4}) = 50 + f_{4}

Suppose that a link, (3, 2), is added, with the travel cost t_{5}(f_{5}) = 10 + f_{5}. Calculate the link and route flows for the new problem. Also calculate the equilibrium route costs in both cases, and discuss the difference in terms of the Braess paradox.

[Source: Sheffi (1985)]

(This question may be answered in the lecture on traffic assignment.)

8. (Summary) How can one construct an equilibrium model whose solution is system optimal?

Assignment

Write a summary of your answers to the following questions, together with motivations, analyses and conclusions.

The exercise utilizes some small scale instances of the problem [TAP]. They can be found as ascii files on the web page

http://www.md.chalmers.se/~mipat/Transp_kurs.html.

Choose one of the networks.

1. (Optimality and the Wardrop conditions) Apply the Karush–Kuhn–Tucker optimality conditions on the node–link and link–route formulations of [TAP] och show that they are equivalent to the Wardrop principle of user equilibrium.

2. (Equilibrium solution) Input the problem symbolically so that fmincon or quadprog (for quadratic problems) in the Matlab Optimization Toolbox can take care of it, and so that you can easily switch between instances if one should not work out well. Use the node–link representation. Guide: You need to construct the node–link incidence matrix A. Using matrix notation, input the problem in terms of two types of variables: f (as long as the number of links, |A|), and a vector of the commodity flows f_{pq}, one for each OD pair (p, q), each of which being as long as the number of links. The two groups of linear constraints need to be input as one big set of equations. Look at the demos (type optdemo in MATLAB) for a guide to the input format. Also note that you need to calculate and input the derivatives up to order two of the objective function in terms of the variables f and f_{pq}, that is, the gradient and the Hessian. The simplest way to deal with all of this is to effectively eliminate the variables f, as they are defined as the sum of the f_{pq} variables. So, in effect, we can work only in the f_{pq} variables. Give the equilibrium solution, f^{∗}. For some OD pair of your choice, verify by the use of the proper calculations that the Wardrop conditions are satisfied. How many routes are used? (Utilize f_{pq}^{∗}.) Does it seem like the commodity flows f_{pq}^{∗} are unique? Why/why not?

3. (System optimum) Solve the system optimal problem! (Guide: Which is the only modification that you need to make?) Compare the solutions (flows, objective value in the system optimal problem). Check the same OD pair as in the above exercise, and verify that the marginal costs are the same. Also compare the real travel costs.

4. (Braess’ paradox) Make some improvement of the network, for example a lower cost parameter for some link, or the introduction of a new link. Solve the user equilibrium problem for the new problem. Check if this is a case of Braess’ paradox.

5. (Influence of congestion) Let the elements in the demand vector increase proportionally by something like a factor between 0.5 and 2.0. Do exercise 2. for some choices in the interval and observe the main changes in the solutions. Questions: How does the number of used routes change? How does the travel cost change? (Calculate reasonable aggregated measures.)

6. (Bonus question, I: Properties of [TAP]) List as many properties of the model [TAP] that can be utilized in making it efficiently solvable, as you can. Explain why each of the properties that you list is important.

7. (Bonus question, II: Flow decomposition) If you have at hand an equilibrium solution f^{∗} (or any feasible link flow for that matter), how does one generate a consistent route flow solution?

Good luck!