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:
Distances are converted using speeds by facility type from Table 1 of the Miasma Beach
problem statement. Resulting travel times (in minutes) and distance (in miles) are displayed
in the figure below.
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 ]
The attached file summarizes the calculated performance
for the observed flows. The spreadsheet used the free flow speeds (in minutes/mile) and link
length with observed volumes, base capacities, to estimate congested travel times corresponding
to observed link travel times. Vehicle-miles traveled (VMT) and vehicle-hours traveled (VHT)
are computed by link and by facility type.
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:
- Find two minimum path trees for a single centroid (1-6) from the Miasma Beach network, using travel times from Problem 1 for one skim tree and distance for the second. Compare the two skim trees (since link speeds vary, so may the resulting skims). Show all work. You should verify your results with TransCAD.
- Find two minimum path time trees for centroids 2, 3, or 4 from
the in-class network.
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:
Time skim tables and trees for all 8 centroids;
Dist skim tables and trees for all 8 centroids;
Solution for Lecture Network:
Intrazonal travel times are computed as one half the travel time to the closest TAZ.
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:
Attached is a summary of cost calculations for
improvements to the 2000 Miasma Beach network to the 2020 Miasma Beach network.
All links are herein tabulated by direction. Intersection costs are only added for
one direction. The cost of the more expensive change is used (for example, the new
links on upper 3nd and 4th streets use the intersection cost for a Major Arterial
at Miasma Blvd but the corresponding cost for a local street at Mountain Blvd).
Total link and intersection cost is added and any penalties applied. The total cost
of upgrades and additions is $4,490,000.00 to produce the 2010 network.
Last Updated: 25 April 2024