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.