Transport Systems: Network Analysis

Problem 1: Shortest Path Assignment (20 points).
Part A (5 points). Given node-link adjacency matrix E from below answer the following:
State the number of nodes: ___
State the number of links: ___
AND draw the network
𝐸 =
[

−1 −1 0 0 0 0 0 0 0 0
1 0 0 −1 0 0 0 0 0 0
0 1 1 0 −1 −1 0 0 0 0
0 0 0 0 0 0 −1 1 1 0
0 0 0 0 0 1 1 −1 0 0
0 0 0 0 0 0 0 0 0 1
0 0 −1 1 1 0 0 0 −1 −1]

Part B (5 points). Assuming centroid A is connected via a connector to node 1, centroid B to
node 2, Centroid C from node 5, and Centroid D from node 6 (in other words A and B are
origins, C and D are destination) state the set of all acyclic paths in the network for each
origin-destination node pair.
Part C (10 points). Given the link cost vector 𝑐 = [4,5,2,5,2,1,3,2,2,2] (links and nodes in
the same order as stated with matrix E in Part A) and assuming all centroid connectors have
a cost of 0, use Dijkstra’s algorithm to solve the SP problem for this network. Show all
iterations.
Give the origin-destination minimum travel cost matrix:
C D
A ____ ____
B ____ ____
1. State the shortest path from A to C:
2. State the shortest path from B to C:
3. In what order did the nodes have their labels set (when solving Dijkstra’s) from origin A?
Problem 2: Algorithm Design (12 pts)
Let 𝐺 = (𝑁, 𝐴) be a directed graph with travel time 𝑙(𝑖,𝑗) for every link (𝑖,𝑗) ∈ 𝐴. Consider
the following algorithm:
Initialization:
Let 𝐿 = [𝑙𝑖𝑗] be a matrix where 𝑙𝑖𝑗 = 𝑙(𝑖,𝑗) if (𝑖,𝑗) ∈ 𝐴 and 𝑙𝑖𝑗 = ∞ otherwise.
Let 𝑃 = [𝑝𝑖𝑗]be a matrix where 𝑝𝑖𝑗 = 0 if 𝑙𝑖𝑗 = ∞ and 𝑝𝑖𝑗 = 𝑖 otherwise.
Algorithm
Input: 𝐺, 𝐿, 𝑃
1 for 𝑘 = 1. . |𝑁|
2 for 𝑖 = 1. . |𝑁|, 𝑖 ≠ 𝑘
3 if 𝑙𝑖𝑘 + 𝑙𝑘𝑖 < 0
4 return “there is a negative cycle”
5 if 𝑙𝑖𝑘 ≠ ∞ then
6 for 𝑗 = 1. . |𝑁|, 𝑗 ≠ 𝑖
7 𝑐 = 𝑙𝑖𝑘
8 if 𝑐 + 𝑙𝑘𝑗 < 𝑙𝑖𝑗
9 𝑙𝑖𝑗 ← 𝑐 + 𝑙𝑘𝑗
10 𝑝𝑖𝑗 ← 𝑝𝑘𝑗
11 end if
12 end for
13 end if
14 end for
15 end for
Output: 𝐿, 𝑃
Questions:
1-What does the algorithm do?
2-In the end, what does 𝑙𝑖𝑗 represent?
3- In the end, what does 𝑝𝑖𝑗 represent?
Problem 3: Convexity (16 points).
Definitions:
𝐴 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑓 ∶ 𝑿 → ℝ𝒏
𝑖𝑠 𝑐𝑜𝑛𝑣𝑒𝑥 𝑖𝑓, 𝑓𝑜𝑟 𝑒𝑣𝑒𝑟𝑦 𝑥1, 𝑥2 ∈ 𝑿 𝑎𝑛𝑑 𝑒𝑣𝑒𝑟𝑦 𝜆 ∈ [0,1]:
𝑓((1 − 𝜆)𝑥1 + 𝜆𝑥2) ≤ (1 − 𝜆)𝑓(𝑥1
) + 𝜆𝑓(𝑥2
)
𝐴 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑓 ∶ 𝑿 → ℝ𝒏
𝑖𝑠 𝑠𝑡𝑟𝑖𝑐𝑡𝑙𝑦 𝑐𝑜𝑛𝑣𝑒𝑥 𝑖𝑓, 𝑓𝑜𝑟 𝑒𝑣𝑒𝑟𝑦 𝑥1 ≠ 𝑥2 ∈ 𝑿 𝑎𝑛𝑑
𝑒𝑣𝑒𝑟𝑦 𝜆 ∈ (0,1):
𝑓((1 − 𝜆)𝑥1 + 𝜆𝑥2) < (1 − 𝜆)𝑓(𝑥1
) + 𝜆𝑓(𝑥2
)
Part A (8 points).
Using the definition of function convexity above, determine if the functions below are convex
or not on the domain specified.
1. 𝑓1
(𝑥) =
𝑥
3+2
𝑥
2+1
for 𝑥 ∈ ℝ
2. 𝑓2
(𝑥) = 3𝑥
2 − |𝑥 − 8| for 𝑥 ∈ [1,5]
Part B (8 points).
Using the definition of strict function convexity above, determine if the functions below are
strictly convex or not on the domain specified.
3. 𝑓3
(𝑥) = 11 + (𝑥 − 3) + 3𝑥
2
for 𝑥 ∈ ℝ
4. 𝑓4
(𝑥) = max{𝑥
3
, 0} for 𝑥 ∈ ℝ
HINT: Proof by contradiction can be used if the functions are not convex or strictly convex.
Problem 4: Optimality Conditions (16 points).
Part A (6 points).
Write the set of optimality conditions and state the optimal solution for the following
mathematical program:
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓(𝑥1, 𝑥2
) = 3𝑥1
2 − 5𝑥1+𝑥2
2 − 8𝑥2
s.t. 𝑥1, 𝑥2 ≥ 0
Part B (10 points).
Re-write the set of optimality conditions if the following constraint is added to the above
problem: 𝑥1 + 𝑥2 = 2. Does the optimal solution change? And if so, what is the new solution?
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓(𝑥1, 𝑥2
) = 3𝑥1
2 − 5𝑥1+𝑥2
2 − 8𝑥2
s.t. 𝑥1 + 𝑥2 = 2
𝑥1, 𝑥2 ≥ 0
Problem 5: One Dimensional Optimization (16 pts)
Find the minimum of f(x) = 2x
2
-10x +7 over the interval [0,5] to determine the optimal value
of x. Stop when the final interval is within 5% of the initial interval (do no extra work). Solve
using both Golden Section and Bisection. Compare the number of iterations required for
each. Which required more iterations and why? Show all work.
Problem 6: Traffic Assignment basics and User Equilibrium (20 pts)
Consider the network below with the following link travel time functions (𝑥𝑎 is the flow on
link 𝑎 and 𝑡𝑎
(𝑥𝑎
) is the travel time of link 𝑎):
𝑡1
(𝑥1
) = 4𝑥1 + 5
𝑡2
(𝑥2
) = 𝑥2 + 10
𝑡3
(𝑥3
) = 𝑥3 + 10
𝑡4
(𝑥4
) = 4𝑥4 + 5
𝑡5
(𝑥5
) = 2𝑥5
𝑡6
(𝑥6
) = 𝑥6 + 10
𝑡7
(𝑥7
) = 𝑥7 + 10
There are two origin-destination pairs (1,5) and (2,6) with demands (𝑟 is the origin node, 𝑠 is
the destination node and 𝑄𝑟𝑠 is the travel demand from 𝑟 to 𝑠):
𝑄15 = 30
𝑄26 = 60
Clearly write out the full system of equations required to algebraically solve for UE, and
determine the user equilibrium traffic flow on each link of the network.