Homework #3 -- Shortest Path Algorithms / Skim Trees [Due: Friday, 15 April 2022] Problem 1. Network Characteristics [10 points] Depicted below is the corrected 2020 Miasma Beach network. Using the network map and the information in Task 1 Table 1, convert speeds and distances to travel times. Produce a network map depicting link distance, speed, and travel time annotated on each link. You may use TransCAD to complete the calculations and produce the final labeled network, but you must do this work for your individual network. Solution: 3. Major Arterials: 45 mph = 0.75 miles/min = 1.33 min per mile 4. Minor Arterials: 45 mph = 0.75 miles/min = 1.33 min per mile 5. Collector Street: 30 mph = 0.50 miles/min = 2.00 min per mile 6. Local Streets: 15 mph = 0.25 miles/min = 4.00 min per mile 9. Centroid Connect: 25 mph = 0.42 miles/min = 2.40 min per mile Problem 2. Performance Analysis (20 points) Depicted below is the 2000 Miasma Beach transportation network with observed 2000 traffic volumes (kvph by direction) for the AM peak hour (7-8 AM). Calculate performance characteristics for each link (VMT, VHT, speed) and summarize results by link facility type as well as by network-wide totals for VMT, VHT, and average speed. Use the BPR link performance function to estimate link travel times based on observed volumes (use default values for α and β): [ t = t0(1+α(vol/cap)β) ]. Use the tabular format provided ( xls ). Do not include centroid connectors. Computation of Level-of-Service (LOS) can be complex and varies by facility type. Typically, freeway sections utilize link traffic density while arterials utilize link average speed and average time spent following. To simplify analysis, use the density-based assessment for all link types. Table 3.12 Density Ranges for Freeway LOS ------------------------------------------- Level of Service Density Range (A-F) (veh/mi/lane) ------------------------------------------- A 0 - 11 B > 11 - 18 C > 18 - 26 D > 26 - 35 E > 35 - 45 F > 45 ------------------------------------------- Describe any 2000 network problems. Consider LOS and observed volume/capacity ratios as a possible congestion measure. Summarize 2000 observed VMT, VHT, and average speed (total and by facility type). Solution: [ results ] Analysis of observed flows suggest that only SR-1 is congested (severely). Problem 3. Minimum Paths (20 points) Apply Dijkstra's Algorithm by hand, as illustrated in class, for either part 3A or 3B:
Include tables and plots that should approximate presentation standards. Use either the table format or the graph format (see skim tree notes). Plot the minimum path tree for each case. Construct the interzonal travel time matrix (tij) corresponding to the Miasma or class networks, including computed O-D travel times (or distances), including those from class. Solution for Miasma Beach: Solution for Lecture Network:
Problem 2(c) Class Ex: Travel Time Skims --------------------------------------- From\to 1 2 3 4 5 --------------------------------------- 1 2.0 6 5 4 9 2 6 1.5 3 5 5 3 5 3 1.5 4 6 4 4 5 4 2.0 8 5 9 5 6 8 2.5 --------------------------------------- Shortest Path Worksheet: From Centroid 2 ------------------------------------------------------------------ Node Path Length Step -------- ------------------ Decision Path From To Cum + Link = Total ------------------------------------------------------------------ 1 2 12 0 1 1 1. Add #12 p(12)= 2 ------------------------------------------------------------------ 2 12 6 1 3 4 4. Add # 6 p( 6)=12 10 1 4 5 6. Add #10 p(10)=12 13 1 1 2 2. Add #13 p(13)=12 ------------------------------------------------------------------ 3 13 3 2 1 3 3. Add C#3 p( 3)=13 7 2 4 6 5. Del link 9 2 2 4 5. Add # 9 p( 9)=13 11 2 3 5 7. Add #11 p(11)=13 ------------------------------------------------------------------ 4 C#3 3 At Centroid ------------------------------------------------------------------ 5 6 5 4 1 5 8. Add C#5 p( 5)= 6 7 4 1 5 9. Add # 7 p( 7)= 6 ------------------------------------------------------------------ 6 9 4 4 1 5 10. Add C#4 p( 4)= 9 8 4 5 9 10. Del link 11 4 2 6 6. Del link ------------------------------------------------------------------ 7 10 11 5 2 7 7. Del link ------------------------------------------------------------------ 8 11 1 5 1 6 11. Add C#1 p( 1)=11 ------------------------------------------------------------------ 9 C#5 5 At Centroid ------------------------------------------------------------------ 10 7 8 5 2 7 12. Add #8 p( 8)= 7 ------------------------------------------------------------------ 11 C#4 5 At Centroid ------------------------------------------------------------------ 12 C#1 6 At Centroid -- Finished! ================================================================== 13 8 7 Step not needed... ------------------------------------------------------------------ Shortest Path Worksheet: From Centroid 3 ------------------------------------------------------------------ Node Path Length Step -------- ------------------ Decision Path From To Cum + Link = Total ------------------------------------------------------------------ 1 3 13 0 1 1 1. Add #13 p(13)= 3 ------------------------------------------------------------------ 2 13 7 1 4 5 7. Add # 7 p( 7)=13 9 1 2 3 3. Add # 9 p( 9)=13 11 1 3 4 5. Add #11 p(11)=13 12 1 1 2 2. Add #12 p(12)=13 ------------------------------------------------------------------ 3 12 2 2 1 3 4. Add C#2 p( 2)=12 6 2 3 5 8. Add # 6 p( 6)=12 10 2 4 6 10. Add #10 p(10)=12 ------------------------------------------------------------------ 4 9 4 3 1 4 6. Add C#4 p( 4)= 9 8 3 5 8 8. Del link 11 3 2 5 4. Del link ------------------------------------------------------------------ 5 C#2 3 At Centroid ------------------------------------------------------------------ 6 11 1 4 1 5 9. Add C#1 p( 1)=11 10 4 2 6 10. Alt Path to #10 ------------------------------------------------------------------ 7 C#4 4 At Centroid ------------------------------------------------------------------ 8 7 6 5 1 6 7. Del link 8 5 2 7 13. Add # 8 p( 8)= 7 ------------------------------------------------------------------ 9 6 5 5 1 6 11. Add C#5 p( 5)= 6 ------------------------------------------------------------------ 10 C#1 5 At Centroid ------------------------------------------------------------------ 11 10 6 No new nodes ------------------------------------------------------------------ 12 C#5 6 At Centroid -- Finished ================================================================== 13 8 7 Step not needed... ------------------------------------------------------------------ Shortest Path Worksheet: From Centroid 4 ------------------------------------------------------------------ Node Path Length Step -------- ------------------ Decision Path From To Cum + Link = Total ------------------------------------------------------------------ 1 4 9 0 1 1 1. Add # 9 p( 9)= 4 ------------------------------------------------------------------ 2 9 8 1 5 6 9. Add # 8 p( 8)= 9 11 1 2 3 2. Add #11 p(11)= 9 13 1 2 3 3. Add #13 p(13)= 9 ------------------------------------------------------------------ 3 11 1 3 1 4 4. Add C#1 p( 1)=11 10 3 2 5 7. Add #10 p(10)=11 13 3 3 6 3. Del link ------------------------------------------------------------------ 4 13 3 3 1 4 5. Add C#3 p( 3)=13 7 3 4 7 10. Add # 7 p( 7)=13 12 3 1 4 6. Add #12 p(12)=13 ------------------------------------------------------------------ 5 C#1 4 At Centroid ------------------------------------------------------------------ 6 C#3 4 At Centroid ------------------------------------------------------------------ 7 12 2 4 1 5 9. Add C#2 p( 2)=12 6 4 3 7 11. Add # 6 p( 6)=12 10 4 4 8 7. Del link ------------------------------------------------------------------ 8 10 12 5 4 9 8. Del link ------------------------------------------------------------------ 9 C#2 5 At Centroid ------------------------------------------------------------------ 10 8 7 6 2 8 10. Del link ------------------------------------------------------------------ 11 7 6 7 1 8 11. Del link ------------------------------------------------------------------ 12 6 5 7 1 8 12. Add C#5 p( 5)= 6 ------------------------------------------------------------------ 13 C#5 8 At Centroid -- Finished ------------------------------------------------------------------ Problem 4. Cost of Network Improvements (10 points) Based on the 2000 Transportation Study, the City of Miasma Beach expanded the transportation network. Using the cost estimates provided, compute the cost of the network improvements between 2000 (the network in Problem 2) and 2020 (the network in Problem 1). Use the same spreadsheet as in Problem 2. Please note that all costs are per lane-mile and that all links improvements and additions must include link costs and the associated intersection costs, plus any development penalties. Solutions: Last Updated: 25 April 2024 |