CE 392C - Transportation Network Analysis

Fall 2023

Homework 5

Due on Canvas at 11:59 PM, Friday, November 3. Submit two files: a PDF containing your solutions to the textbook problems and the writeup corresponding to the Python 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 5: Exercise 16, 17

Chapter 6: Exercise 20a -- you only need to calcualte L and U labels.

Python questions

This Python assignment is different from the earlier ones. The assignment is more open ended, and focused on practical questions about how traffic assignment can be used for planning, and on algorithm performance.

There are three questions which should be answered in a report. As this is a graduate course, pay attention to professionalism and presentation quality in your report. Append this report to your solutions from the textbook problems, and submit one PDF with both.

Question 1: Algorithm performance

Download the Sioux Falls network and trips file from Transportation Network Test Problems. You should be able to solve for user equilibrium using your code from Homework 4 with the following Python commands:

from network import *
net = Network("SiouxFalls_net.tntp", "SiouxFalls_trips.tntp")
net.userEquilibrium("FW", 20, 1e-4, net.averageExcessCost)

See the documentation of userEquilibrium from the previous assignment to see what the arguments do. After running this code, the link flows and costs can be seen in the flow and cost attributes of net.link.

For the first question on the assignment, compare the performance of MSA and Frank-Wolfe on this network. What is the gap level achieved for different numbers of iterations? What is the gap level achieved for different amounts of computational time? Experiment with different choices of step size for MSA (e.g., constant step size, different sequences) and different parameters in FW (e.g., different precision for solving for the step size, or using Newton's method instead of bisection). Describe your experiments, results, and conclusions, using tables and/or figures to illustrate your findings. What seems to be fastest?

Question 2: Effects of a network change

In this question, you will evaluate the impact of building a new highway in Sioux Falls. Here is a schematic of the Sioux Falls network, based on a diagram created by Hai Yang and Meng Qiang from the Hong Kong University of Science and Technology. The numbers indicate the order of the links in the network file. The red line indicates where the new highway is to be built.

Assume that this highway will double the capacity of each of the highlighted links (in both directions), and reduce the free-flow time by half. Your task is to forecast the effects of bulding this highway. Use equilibrium traffic assignment, and make sure you solve to a small enough gap that the link flows are stable. What will be the change in total system travel time? What links will see increased flow, and what links will see decreased flow? What links will see higher travel times, and what links will see lower travel times? Is there anybody who will have a higher travel time afterwards? Who are the "winners" and "losers" if this highway were to be built?

Document your analysis and conclusions, using tables and/or figures to illustrate your findings.

Question 3: Speeding up traffic assignment

The last question asks you to make changes to your code so that the run time for traffic assignment is reduced. You can make whatever changes you like to any parts of the code in any files. Your tests should involve networks of different size from the Transportation Networks Test Problems site. Document your changes, and their effects on the performance of the algorithm.

You will receive full credit for this problem as long as you clearly describe your experiments and their effectiveness, regardless of the amount of time you are able to save. However, there is an opportunity for extra credit. I will select a (fairly large) network and run each submission on this network on my machine. The individual or group whose code reaches a relative gap of 1e-6 fastest (as measured by wall clock time) will receive 10 bonus points on this assignment. The runner up will receive 5 bonus points.

Be sure to write your code so that I can run it using the three lines of code given at the start of Question 1 (replacing "Sioux Falls" with the network of my choice). I will independently verify that the flows returned by your code are feasible and correspond to a sufficiently small relative gap.

Submission instructions

Your answers to the textbook questions, and report from the Python 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 Question 3, submit a single ZIP file with your code and upload to Canvas, following the instructions for that question.