CE 367R - Optimization Techniques for Transportation Engineering

Spring 2021

Homework 3: Shortest paths and maximum flow

Due on Canvas at 11:59 PM, Friday, February 10. Submit a ZIP file containing your code for the Python problems. More details below on how to submit the Python code.

The questions on this assignment involve basic network algorithms. Download and unzip these files to a convenient directory, or fork this repl.it. The only file you will be editing in this assignment is network.py, but you are free to look at the other files too for reference. You will continue working with the Network class used in the previous homework assignment. The main Python problem involves implementing a shortest path algorithm -- you can implement any of the algorithms learned in class. There is an optional, extra-credit second Python problem implementing one of the maximum flow algorithms from class. You are not required to solve this second problem for full credit. There are also two problems which can be solved either by hand or by using Python code you have written. The solutions to these problems can be neatly handwritten or typed, and submitted on Canvas as a separate PDF file from the .zip containing your Python code. You may work with (one) partner from the class to complete these questions. Make sure your README.TXT file contains the name of your partner. Only one partner needs to submit on Canvas.

Important note: Python starts counting lists at zero, not one. So if there are 5 nodes in the network (self.numNodes = 5), the nodes are numbered 0, 1, 2, 3, and 4. The range statement in Python makes it easy to work with this convention: for i in range(5) goes between 0 and 4, so you can use range(self.numNodes) and it will loop over all of the node IDs in the network.

Question 1: Shortest path

The main coding question on this assignment has you implement one of the one-to-all shortest path algorithms from class (your choice). In network.py, this is done in the shortestPath method, which takes one argument (the origin node). This method should return a tuple containing two lists: a list of backnodes (the path labels, indicating the previous node in the shortest path) and a list of cost labels indicating the cost on the shortest path to each node from origin.

The network.py file already sets up these lists for you, and shows how you should return them when your code is complete. To access the cost of the link between nodes i and j, use self.cost[i][j]. These values are already set up by the code which reads the test files, and you should not need to change them. You still need to use the adjacency matrix to determine whether such a link even exists in the first place, from your standpoint you should not assume anything about the values of self.cost[i][j] if there is no link from i to j. Finally, as the "default" values for the labels, use the built-in constants utils.NO_PATH_EXISTS and utils.INFINITY, rather than defining your own values.

You can view the test instances and networks by browsing in the tests directory. All of the tests are plain text files which can be opened by any decent text editor (Windows Notepad sometimes struggles with line breaks). The test file contains references to the network files themselves (adjacency matrix and link data), and to the correct answers. You may find these useful in debugging your code.

Question 2: Maximum flow (optional extra credit)

An optional coding question has you implement one of the maximum flow algorithms taught in class. You can receive full credit on this assignment without attempting this question, but there are some extra credit points available if you can successfully complete it.

Look at the maxFlow method of network.py. This method should return a tuple containing a numeric value (the total amount of flow shipped from the source to the sink) and the corresponding flow values. The flow values are represented using a 'matrix' (actually a list of lists) flow, where flow[i][j] is the amount of flow on the link (i,j). (If no such link exists, flow[i][j] should equal zero.). The provided file already sets up this matrix for you, and shows you what your code should return when done.

To access the capacity of the link between nodes i and j, use self.capacity[i][j]. These values are already set up when the test files are read, and you should not need to change them. You still need to use the adjacency matrix to determine whether such a link even exists in the first place, from your standpoint you should not assume anything about the values of self.capacity[i][j] if there is no link from i to j.

Fair warning: this problem is significantly harder than the other programming questions you've done so far. You may find it helpful to re-use your basic search code from the previous assignment, perhaps with some minor modifications.

Question 3: Shortest path application

The last of the test instances for Question 1 uses a network which is (loosely) based on the city of Sioux Falls, SD. This is a schematic of the network showing the links and nodes; the costs are given in the file tests/networks/SiouxFalls_linkdata.txt.

Sioux Falls network

What is the shortest path from node 1 to node 23, and what is its cost?

If you got full credit for Question 1, your code already has the answer to this. Can you display it in a way that lets you identify what the actual path is?

Question 4: Maximum flow application

You are manufacturing goods in one location, and must ship them by rail to another location for sale. The following network represents the options available to you, where the source and sink nodes correspond to the production and retail locations, and the other nodes represent cities with transfer points. All links represent rail lines, and the capacities represent the rate at which you can move your product along those rail lines, in tons per day. (This capacity largely reflects the frequency of trains along the route.)

Network for Question 4

What is the maximum rate at which you can deliver product from the manufacturing plant to the retailer (in tons per day), and how much product will be shipped on each rail link in order to do so?

(For this problem, you don't have to worry about how long it actually takes to ship the product. The flow values above will give the "steady-state" flow rates over the long term.)

Submission instructions

Your answers to Questions 3 and 4 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:

  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. 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 hw1/ 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.) 
unzip hw2.zip
diff -bur master/ hw2/ # master is the original; this shows me your changes
cd hw2
cat README.txt
python3 grader.py
cd ..
rm -r hw2 hw2.zip

Return to CE 367R.