Due on Canvas at 11:59 PM, Friday, May 4. Submit two files: a PDF containing your solutions to the
questions, and a ZIP file containing your code for the Python problems. Textbook problems must be
solved individually, Python problems can be solved individually or in groups of two. More details below on how to
submit the Python code.
Questions
Question 1: Equilibrium uniqueness, stability, and efficiency
Consider a network with one origin, one destination, two possible departure time intervals (1 and 2), and two paths (A and B). A total of 16 vehicles depart during time interval 1, and 4 depart during time interval 2. Let $t^\pi_\tau$ refer to the travel time on the $\pi$-th path when departing at the $\tau$-th time interval, with $h^\pi_\tau$ defined similarly for path flows. Suppose the travel times are related to the path flows as follows:
$$\begin{align*}
t^A_1 &= 0.5 h^A_1 + 5 h^A_2 + 6 \\
t^B_1 &= 0.5 h^B_1 + 3 h^B_2 + 10 \\
t^A_2 &= 0.3 h^A_1 + 0.6 h^A_2 + 0.8 \\
t^B_2 &= 0.2 h^B_1 + 0.4 h^B_2 + 2 \\
\end{align*}$$
and consider the following four path flow matrices:
$$ H_1 = \begin{bmatrix} 0 & 16 \\ 4 & 0 \end{bmatrix} \qquad H_2 = \begin{bmatrix} 12 & 4 \\ 2 & 2 \end{bmatrix} \qquad H_3 = \begin{bmatrix} 8 & 8 \\ 2 & 2 \end{bmatrix} \qquad H_4 = \begin{bmatrix} 16 & 0 \\ 0 & 4 \end{bmatrix} $$
Which of the above path flow matrices satisfy the principle of user equilibrium?
Which of the above path flow matrices represent efficient equilibria?
Perturb $H_3$ in the following way: adjust $h^A_2$ from 2 to 2.1 (so $h^B_2$ becomes 1.9), changing all of the travel times. Then, adjust $h^A_1$ and $h^B_1$ until $t^A_1 = t^B_1$ (restoring equilibrium for the first departure time). Then, adjust $h^A_2$ and $h^B_2$ until $t^A_2 = t^B_2$ (restoring equilibrium for the second departure time), and so on, alternating between the two departure times, until you reach a new equilibrium solution. Which equilibrium solution do you end up at? Is $H_3$ stable?
(Question adapted from Netter, M. (1972) Affectation de trafic et tarification au coût marginal social; critique de quelques idées admises. Transportation Research 6, 411-429.)
Question 2: Daganzo paradox
The image below shows a four-link network, with the parameters shown for each link. As the capacity of the bottom link varies, the equilibrium assignment will shift. Calculate and plot the total system travel time in the network as the capacity varies from 60 to 600 vph. You may find it useful to answer this question after completing the Python assignment below. After implementing time-dependent shortest path and the convex combinations method, you can edit the daganzo.txt file to solve for equilibrium with different capacity values on the bottom link, then calculate and display the total travel time using the network.calculateTSTT method. See daganzo.py for an example.
Python questions
In this assignment, you will implement the time-dependent version of Dijkstra's algorithm learned in class, and the convex combinations method.
When this is done, you will have a simple, but complete dynamic traffic assignment code that you can use for projects, research, and so forth.
Download and unzip these files to a convenient directory. You will be editing just one file in this assignment:
network.py. You are welcome to look at the other files too but they should not be edited.
The network.py file defines the Network class. This contains code for reading a network file, and implementing the dynamic traffic assignment algorithm introduced in Chapter 12 of the textbook. This includes implementations of the network loading algorithm from Chapter 10, which builds off of the link and node models you implemented in Homework 2 and Homework 3. You will find it worthwhile to browse through this file and node.py and see the methods used to implement these algorithms, even though it isn't necessary to understand every detail.
There are some other attributes and methods defined or used in the Node class; the most useful ones for this assignment are:
links -- a dictionary whose keys are a string ID for a link (e.g., '(i,j)') and
whose values are Link objects. In this assignment, travelTime and ID attributes have
been added to the Link class. travelTime is a list whose length is equal to the time horizon, and whose
values give the travel time on the link for each possible entry time. ID is a string identifier for a link.
nodes -- a list of Node objects
ODs -- a list of OD objects
forwardStar -- a list with one element per node; each element of this list is a list of IDs for
links leaving this node.
reverseStar -- the same as forwardStar, but for links entering this node.
pathFlows -- a dictionary whose keys are paths (expressed as tuples of link IDs), and whose values are
lists of path flows at each time step.
pathTravelTimes -- a dictionary whose keys are paths (expressed as tuples of link IDs), and whose values are
lists of path travel times for each possible departure time (one element per
time step).
To understand how these work, you may find it helpful to add some print statements to see what these lists and dictionaries look like and what information they contain. The daganzo.py file shows how a network can be read, which you can use as an example. Also see the instructions for Question 2 for more details on how the network topology is encoded in Node, Link, and Network objects.
As with earlier assignments, you can run grader.py to check your implementations against the test cases I will be using. You can browse these
in the tests folder if you want to see the input data and the correct output values. All numerical values must be within 1% of the reference
values to be marked correct.
Question 3: Convex combinations algorithm
In this question, you will implement the convex combinations algorithm. In network.py, find the updatePathFlows method. This
method takes two arguments -- the targetPathFlows dictionary (representing $H^*$), and the step size $\lambda$ -- and changes the current path flows
stored in the self.pathFlows dictionary (representing $H$). Both targetPathFlows and self.pathFlows are dictionaries whose
keys are a string listing the links in the path, and whose values are a list of numbers (one per time step), indicating the number of vehicles departing on that
path at that time step. You can refer to a specific value in the $H$ matrix with self.pathFlows[path][t], where path and t
are a particular path and departure time, and similarly with targetPathFlows.
Question 4: Time-dependent shortest path
In this question, you will implement a one-to-all time-dependent shortest path algorithm, for one origin and departure time, given as arguments to the TDSP
method in network.py. You can assume that link travel times satisfy the first-in, first-out principle.
This method should return two lists, each with one element per network node: one list containing the cost labels at termination, and the other containing the backlink labels. Unlike the textbook, the Python code should return the ID of the last link in the shortest path to each node, rather than the penultimate node in this path. This will require a trivial change to the algorithm given in the text.
The ID of a link can be accessed either using the ID attribute of a link, or from the forwardStar and reverseStar lists in the Network class. In the given implementation, Nodes are aware of the adjacent links through the upstreamLinks and downstreamLinks lists, which provide direct references to the Link objects; Link objects are aware of what the upstream and downstream node indices are through their head and tail attributes; and the Network object knows the network topology through the forwardStar and reverseStar lists of link IDs. Given a node index i or link ID ij, the corresponding object can be accessed through self.nodes[i] or self.links[ij], respectively.
Your implementation should use the INFINITY and NO_PATH macros defined in network.py for undefined cost and backlink labels, respectively. The autograder will not recognize other values.
Demonstration: the Daganzo paradox
If you have done everything correctly, run daganzo.py and you should be able to see an approximate equilibrium solution on the Daganzo paradox network. You can experiment around with the convergence criteria and network parameters (length of the top link, and capacity of the bottom link), printing the link cumulative counts and travel times to see how the equilibrium and paradox arise. You may find this helpful in answering Question 2.
Submission instructions
Your answers to the textbook questions should be placed in a single PDF file and uploaded to Canvas. Please verify that your file uploaded correctly, that the pages are in the right order, etc.
For the Python questions, submit a single ZIP file and upload to Canvas. Please follow these instructions:
Include a text file named README.txt which contains (at a minimum) the names of you and your partner (if any). Both partners do not need to submit this ZIP file. (But both partners should submit their PDF questions from the tetxbook separately.) You can add in additional comments or explanations about your implementation in this file, if necessary.
Everything in the original ZIP file should be in the ZIP file you submit (do not just submit the files you changed.)
Give your ZIP file the same name as the ZIP file you downloaded (in this case, hw4.zip).
When I unzip your file, I should get a folder called hw4/ with all of your files in it (it should not expand in place.)
To grade your code, I will execute the following commands. (If you have a Linux environment, you can test these steps yourself. Failure to follow the instructions above will not usually result in a grade penalty, but it makes my life less convenient.) If you feel that the autograder is not correctly judging your code, let me know and I will review manually.
unzip hw4.zip
diff -bur master/ hw4/ # master is the original version; this shows me your changes
cd hw4
cat README.txt
python3 grader.py
cd ..
rm -r hw4 hw4.zip
