CE 392C - Transportation Network Analysis

Fall 2023

Homework 4

Due on Canvas at 11:59 PM, Friday, October 20. Submit two files: a PDF containing your solutions to the textbook problems, and a ZIP file containing your code for the Python problems. More details below on how to submit the Python code.

Textbook questions

Make sure you are using version 0.89 of the text.

Chapter 6: Exercise 9d

Chapter 8: Exercises 21, 22, 24

Python questions

The Python questions on this assignment area fill in the remaining pieces for you to have your own traffic assignment code that will solve for equilibrium on any network, using the method of successive averages (MSA) or Frank-Wolfe.

Download and unzip these files to a convenient directory. The only file you need to edit is network.py, but you are encouraged to look through the other files in the project. This assignment also works with the Network class you used last time; you can also see my solutions to the questions from the previous assignments. Feel free to either replace them with your own implementations from earlier, or to use mine.

As with previous assignments, any numerical values will be marked correct if they are within 1% of the reference answers given in the test files.

Question 1: Relative gap calculation

The first step is to calculate the relative gap of a given solution, so you have a termination criterion available. Within the relativeGap method of Network, write code that will do this, given the current link flows and costs (the flow and cost attributes of Links).

Use the definition of relative gap given in Equation 6.7 of Section 6.1.3 in the text, and return this value at the end of the method. You will find it very helpful to call some of the methods implemented in earlier assignments.

Question 2: Average excess cost

In this question, implement average excess cost as an alternative way to check how close a solution is to equilibrium. Use the definition given in Equation 6.10 of Section 6.1.3. After answering Question 1, you should be able to answer this question without much difficulty. Put your code in the averageExcessCost method in network.py.

Question 3: Flow shifting

Convex combinations algorithms, like MSA and Frank-Wolfe, shift flows by taking a weighted average of the current link flows x, and a "target" vector of link flows x*. Write code to do this in the shiftFlows method. The current link flows are accessed in the flow attribute of the Links. The target link flows are in the targetFlows dictionary given as an argument to shiftFlows, which has link IDs for keys. The stepSize argument indicates the weight to place on the target flow solution. If stepSize = 1 the current flows are replaced by the target flows; if stepSize = 0 there is no change at all, and linearly interpolate between these extremes.

Your method should store the new link flows in the flow attributes of the Links (exactly where the old link flows were stored). After updating the flow, you should update the cost value on the link by calling its updateCost method (see arc.py).

Question 4: Frank-Wolfe step size

The last question involves finding the step size λ which minimizes the Beckmann function, the key step of the Frank-Wolfe algorithm. Write code to do this in the FrankWolfeStepSize method, which takes as its arguments the targetFlows dictionary, and the precision you need for finding the step size. The absolute difference between the exact solution, and the value returned by your method, should be no greater than this precision value.

Upon completing this assignment, you have access to a complete implementation of MSA and Frank-Wolfe in the userEquilibrium method of network.py. Look over this method and its documentation: you can specify how the step size is chosen, how many iterations will be run, how the gap is calculated, and what the convergence gap is. In your own code, you can read any network in TNTP format by calling the Network constructor with the network and OD matrix files as its arguments (see the __init__ method of Network), and then use the userEquilibrium method for traffic assignment. We'll play around with this more in Homework 5, but you may want to do some exploring now.

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. A small penalty may be deducted if they are not followed.

  1. 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 textbook separately.) You can add in additional comments or explanations about your implementation in this file, if necessary.
  2. Everything in the original ZIP file should be in the ZIP file you submit (do not just submit the files you changed.)
  3. Give your ZIP file the same name as the ZIP file you downloaded (in this case, hw4.zip).
  4. 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.) 
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

Return to CE 392C.