CE 392C - Transportation Network Analysis

Fall 2023

Homework 2

Due on Canvas at 11:59 PM, Friday, September 22. 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.91 of the text.

Chapter 5: Exercise 20

Chapter 6: Exercises 2, 6, 11, 13

Python questions

For the remainder of this course, you will be adding features to a Network class in Python. By the end of the semester, you can use this class to solve for traffic assignment on realistic networks. This assignment starts by familiarizing you with how transportation networks are stored and manipulated in the Network class, and ends with you implementing a method to calculate the topological order on an acyclic network.

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 (in particular link.py, node.py, od.py, and path.py).

The comments in the project files explain the methods and attributes of the Network class. A few highlights:

  • Links, nodes, and OD pairs are stored as dictionaries, whose keys are IDs for the link/node/OD pair, and whose values are Link/Node/OD objects containing the information for the individual link/node/OD pair with that ID.
  • Paths are stored as tuple of link IDs. (In Python, the order of a tuple is fixed, so the sequence of links in a path cannot change.) Additional path attributes include the flow on that specific path, the cost on that path, and a pointer to the corresponding Network class.
  • The network structure is represented both in the Link and Node classes. Each Link has the IDs of its upstream and downstream nodes in the tail and head attributes, respectively. Each Node stores the IDs of all of the links entering and leaving that node in the reverseStar and forwardStar lists, respectively.
  • The methods Network.readNetworkFile and Network.readDemandFile read in network data from the TNTP format. This is a standard format for the traffic assignment problem. You can download and try different networks from Transportation Network Test Problems, a repository maintained by Ben Stabler and Hillel Bar-Gera.

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

Question 1: Link counting

The first question is designed to familiarize you with the Network class and how it stores transportation networks. For an arbitrary network, you must write code identifying a node that has the least number of incoming links. Open network.py and find the findLeastEnteringLinks method. Replace the comments saying *** YOUR CODE HERE *** with your implementation. This function should return the ID of a single node.

Question 2: Adjacency matrix

This question involves more involved manipulations of the Network class, and asks you to form a node-node adjacency matrix representation of a given network. As described in Section 2.3 of the text, this is a square matrix. An entry in the i-th row and j-th column is equal to one if there is a link from node i to node j, and zero otherwise.

In network.py, find the method formAdjacencyMatrix. The adjacency matrix returned by this method is a dictionary-of-dictionaries, where the first key represents the tail node (row), and the second key represents the head node (column). So, for instance, adjacencyMatrix[i][j] equals one if there is a link from node i to node j, and zero otherwise. The dictionary keys are already set up in network.py, you just need to fill out all of the entries.

Question 3: Topological order

Acyclic networks can often be processed much faster than general networks. Many of the fastest algorithms for traffic assignment exploit this property, by dividing a general network into acyclic subnetworks, and re-integrating them later. The key to this efficiency is a topological order, described in Section 2.2 of the text.

Theorem 2.1 proves that an acyclic network must have a topological order. This proof is "by construction," meaning that the proof shows exactly how a topological order can be found on any acyclic network. The goal of this question is for you to implement this construction procedure, in the findTopologicalOrder method in network.py.

This method should create a new attribute order for each network Node, storing the topological order of that node. These values should be distinct for each node, and range from 1 to the number of nodes in the network. If the network has a cycle, no topological order exists (this is the other half of Theorem 2.1). If this is the case, your code should raise BadNetworkOperationException to signal that an illegal network operation was attempted.

Question 4: Network loading

The final question asks you to implement network loading, that is, translating path flows into link flows, link costs, and path costs according to the procedure in Section 4.1 of the text.

The paths in the network are stored in the values of the self.path dictionary. The path flow can be found in the flow attribute of a given path, and a tuple of the link IDs in that path are stored in its links attribute. Your code must calculate the corresponding link flows (storing them in the flow attribute of each Link), as well as the corresponding link costs and path costs (storing them in the cost attributes of each Link and Path.) If you look at the link.py and path.py files, you will find some methods that can simplify this problem.

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 tetxbook 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, hw2.zip).
  4. When I unzip your file, I should get a folder called hw2/ 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 hw2.zip
diff -bur master/ hw2/ # master is the original version; this shows me your changes
cd hw2
cat README.txt
python3 grader.py
cd ..
rm -r hw2 hw2.zip

Return to CE 392C.