CE 392C - Transportation Network Analysis

Fall 2023

Homework 3

Due on Canvas at 11:59 PM, Friday, October 15. 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 8: Exercises 1, 3, 4

Python questions

The Python questions on this assignment area all related to shortest paths: you are to implement two shortest path algorithms, and find an all-or-nothing assignment obtained by assigning all demand to the shortest paths available.

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 assignment.

There are two important implementation details to be aware of:

1. The networks used in this assignment follow the TNTP format, a standard format for traffic assignment networks. The network file indicates the "first through node." In many networks, centroids and centroid connectors should only be used when trips start and end (so that centroid connectors cannot serve as "shortcuts" around congestion). Nodes with IDs less than the first through node can only appear at the start or end of a path, never in the middle. Nodes with IDs greater than or equal to the first through node can appear anywhere in a path. In some networks (e.g., Sioux Falls), the centroids coincide with physical nodes, and there is no restriction on passing through them in the middle of trips. In these networks, the first through node is set to 1 to indicate that all nodes can be used as "through nodes." You can identify the first through node in the firstThroughNode attribute of the Network class. Your implementation must respect the first through node when finding paths.
2. In the text, shortest paths are indicated with a backnode label showing the previous node in the shortest path. In this assignment, you will indicate shortest paths with a backlink label showing the previous link in the shortest path, rather than the previous node. This change makes it easier to reconstruct the links in the path, which you need to do in Question 3.

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: Acyclic shortest path

You are to implement the acyclic shortest path algorithm described in Section 2.4.1 of the text, by filling out the acyclicShortestPath method. You do not have to find the topological order, and can assume it is provided in the order attribute of the network Nodes. You can also access the topological order of the network in the topologicalList attribute of the Network class -- this is a list of node IDs in topological order, so topologicalList[3] refers to the 3rd topological node, and so on. The origin has topological order 1. You also do not have to calculate link costs or travel times, assume that they are given in the cost attribute of the network Links.

Your function should return the backlink and cost labels in two dictionaries, with node IDs as the keys. When you initialize labels, use the constants defined in utils.py: NO_PATH_EXISTS when the backlink label is undefined, and INFINITY for costs when no path has been found yet. Please note the two implementation details mentioned above.

Question 2: General shortest path

You are to implement a shortest path algorithm that can work on networks with cycles, by filling out the shortestPath method. You can use any of the algorithms in Section 2.4 that work for cyclic networks. As in Question 1, use the given cost attributes for each Link, and return dictionaries of backlinks and costs.

Question 3: All-or-nothing assignment

Building on Question 2, you must now generate an all-or-nothing assignment (a "target" vector x^*) by assigning all trips in an OD matrix (all origins and all destinations) to the shortest paths available to them. Fill out the allOrNothing method to do just this. Treat the link costs as fixed, and do not recalculate them during this method.

You are (very) strongly encouraged to call the shortest path method you implemented in Question 2. Done properly, this method can be fairly short. Excluding initialization, my reference implementation only requires 7 lines of Python code. Also, while your code will not be graded based on efficiency, you should think about different ways to build an all-or-nothing assignment and how to do this quickly. (The 7-line version I wrote for the solutions is the simplest way to do an all-or-nothing assignment, but definitely not the fastest.)

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, hw3.zip).
4. When I unzip your file, I should get a folder called hw3/ with all of your files in it (it should not expand in place).

unzip hw3.zip
diff -bur master/ hw3/ # master is the original version; this shows me your changes
cd hw3
cat README.txt
python3 grader.py
cd ..
rm -r hw3 hw3.zip

Return to CE 392C.