Home

Development of A Path Flow Estimator for Inferring Steady

1. LPFE ESRI Spreadsheets Shapefiles H LPFE raw outputs text files y Table Creator Map File Creator Spread ArcViewShapeFile Spread aS p Figure 5 11 Visual PFE TD Software Components The three software components are ArcViewShapeFile OCX ESRI MapObjects FarPoint Spread 5 3 1 LPFE The LPFE program operates via the DOS command prompt If an estimation run is successfully the output files generated by the LPFE are in text files If an estimation run encounters errors due to incompatible parameter setting the LPFE program will quit and error messages will be issued by Visual PFE TD CHAPTER 5 VISUAL PFE TD 72 5 3 2 The ArcViewShapefile Read Write OCX An OCX is an object oriented software component conforming to Microsoft s ActiveX architecture The OCX was created to easily read or write Arcview Shapefiles for data conversion purposes The Shapefile format is a geographic data format published by ESRI The ArcViewShapefile Read Write OCX was created by Ross Pickard in Wellington New Zealand and is a shareware made available for download from ESRI web site Visual PFE TD uses the DLL version of the ArcViewShapeFile to convert the text files generated by LPFE to Shapefiles The converted shapefiles can be displayed with the Visual PFE TD map component and common GIS software Table 5 1 shows the conversion between th
2. st F 20 40 60 80 100 120 140 160 180 RMSE of the historical OD veh hr b freeway links 27 amp historical O D 100 CHAPTER 6 CASE STUDIES 101 For RMSE_OD the red line in Figure 6 34 marks the position where the RMSE OD of the historical O D flows equals the RMSE OD of the estimated O D flows Thus a point below the red line means that the estimated O D table is closer to the true O D table than the target one As we can see for both sets almost all the points lie below the red line meaning that LPFE does improve the accuracy of the input O D trip tables Furthermore when the RMSE ODs of the historical O D increase the RMSE ODs of the estimated O D do not change very much the RMSE ODs of the estimated O D is less than 60vel hr in all cases This seems to suggest that even a very coarse O D table is still useful to improve estimation quality so long as it contains the structural pattern of the O D demands to be estimated The RMSE Links tend to slightly increase when the RMSE _ODs of the historical O D trip table increase especially for the input set of freeway links Again this might be due to that our algorithm always check link constraints before O D constrains However compared to the magnitude of average link flows on freeway links 6104veh hr the RMSE Links the greatest one is 351velVhr are still acceptable 6 5 2 Measurement errors of link flows To study the influence of link measurement er
3. sS 5 Maximum Allowed Bad Iterations 1 To 1 000 h ooo 6 Zigzagqging Criterion 1E 16 To 1 0 000001 7 Maximum Allowed Zigzaging 1000 Iterations 1 To 1000 Cancel Help OK Ney Figure 5 2 Algorithm Input Window CHAPTER 5 VISUAL PFE TD 64 Parameter Input Parameters Setting Input Network File STilpfe_ex net Network Format DANET2 Type c FORT Type Output File Name Ipfe_ex_t Retain Iteration History ves a Time Dependent Record Link Detail ves v Enumerate All Paths No Yes z Record Path Detail Yes gt Allow Residual Queue No Record Path Topology No gt Create an Estimation Scenerio No Speed Flow Function BPR Function Consider Measured Link Times No Dispersion Parameter 01 Consider Target O D Demands No z Cost Scalar Ves Consider Link Observation Errors No z Algorithm Type MSA Consider Target O D Errors No OK Cancel Help Figure 5 3 Parameter Input Window Once successfully estimated Visual PFE TD can present the outputs to the users with four types of windows forms Network Maps OD and Path Tables Link Flow Scatter plots e Estimation Reports 5 2 2 Network Maps The Network Windows form is divided into the map and the legend areas Figure 5 4 A layer can be made active by moving mouse cursor over and clicking at the corresponding title of the map legend Labels colors and charts based on attributes can be applied to features of the active layer Drawin
4. PFE requires three input files pfe pfx and pfp as listed below to perform the estimation e pfe file describes network topology i e connectivity contains link characteristics and observed link volumes e pfx file describes the skeleton structure of O D trip table to be estimated as well as target O D volumes if available and e pfp file defines a certain set of routes that the user may particularly want to include into the estimation Common network data listed below are utilized to prepare these PFE input files Node related information e Node s ID e X coordinate of node e Y coordinate of node Link related information e Starting node of link e Ending node e Functional class of link Remark the highest maximum functional class defined by the user must be reserved for centroid connectors This is required for path building purpose Link capacity Free flow speed Link length Two parameters of BPR link cost function a and B respectively B link volume link capacity travel time free flow travel time x 1 0 a e Observed link volume e Measurement error of traffic count e g percentage error 5 O D related information e ID of origin node e ID of destination node 51 e Target O D flow if available e Confidence of target value if target O D flows are available User specified path information e List of paths e Number of nodes defining path e A sequence of
5. To install Visual PFE the computer needs to have the Microsoft NET framework Many of the Microsoft Windows programs are developed on the NET framework Therefore for a computer running Microsoft Windows it is likely that the NET framework is already installed If the users can not be sure if the computer has the NET framework or not an installation program dotnetfx exe is included in the Visual PFE TD installation CD Running the program will install the NET framework on the target computer After installing the NET framework users can proceed to run the Setup exe program and follow the setup instruction to complete the installation Graphical User Interfaces Visual PFE TD is developed with Microsoft Visual Basic NET It implements Microsoft s Multiple Document Interface MDI software architecture within which multiple windows forms can be created and viewed within the main window The main window is referred to as the MDI parent form and each sub window opened within the MDI parent is called a MDI child form With Visual PFE a MDI child form can take on the form of a map a table a graphic plot or a text document The program functions are controlled using Graphical User Interfaces GUI Multiple Document Interface When multiple result windows are opened in Visual PFE TD the titles of the MDI child windows are formatted in a way that results of the same network and time period can be identified Figure 1 shows suc
6. 4 i 100 nit p pea 95 90 85 80 0 20 40 60 80 100 120 140 160 180 RMSE of the historical OD veh hr b freeway links 27 amp historical O D Figure 6 32 TDCs for scenarios with different historical O D flow errors 98 CHAPTER 6 CASE STUDIES 180 160 140 120 100 80 60 40 a RMSE of the estimated OD veh hr 20 ba Pag rs A La 0 50 100 150 200 RMSE of the historical OD veh hr a all measured links 267 amp historical O D 180 160 140 120 100 80 60 n j an F 20 sst a RMSE of the estimated OD veh hr 0 50 100 150 200 RMSE of the historical OD veh hr b freeway links 27 amp historical O D Figure 6 33 RMSE_ODs for scenarios with different historical O D flow errors CHAPTER 6 CASE STUDIES 90 80 70 60 50 40 30 20 10 RMSE of the estimated link flows veh hr 400 350 300 250 200 150 100 50 RMSE of the estimated link flows veh hr Figure 6 34 RMSE _ Links for scenarios with different historical O D flow errors t i kd 21s E 4 20 40 60 80 100 120 140 160 180 RMSE of the historical OD veh hr a all measured links 267 amp historical O D too
7. ce cceeceeeseeeseeceeceeeeeeeeeeaeeeaeens 71 Figure 5 12 Shapefiles and Network Map Layers 0 eseeseeseeeseeeeseeceaeceeeeeeeeeeaeeenaeens 73 Figure 5 13 Shapefiles and the Scatter Plot Layers ssesseeesesseeseseresesersresrrseessresseseresee 73 Figure 6 1 Evaluation framework iced scutes caiecieniatnuniauelai eens 76 Figure 6 2 Yang and Meng s network 2 se c0c ie test ees cees cette oee cig facaiee detainee taae teeta 78 Fisure6 3 O D trip tables ensien SEa a eked 78 Figure 6 4 Scenarios with different n 0 001 bn 10 z 0 001 zn 10 we 79 Figure 6 5 Scenarios with different n 1000 bn 10 z 0 001 zn 10 eee 80 Figure 6 6 Scenarios with different bn n 1000 0 001 z 0 001 zn 10 80 Figure 6 7 Scenarios with different z amp zn n 1000 0 001 bn 10 81 Figure 6 8 Basic types of network topology ec ceeceeeeeescecsseceeeeeeeeesaeeceaecneeseeeeeaeessaeens 82 Fig re G79 A tree NetWork carcs iis otsi Gs oh Gate gana Sa a Gee ae ceeds eaei ets 83 Figure 6 10 True O D trip table icucniteved avin ie eet atone ead 83 Figure 6 11 Estimated O D flow profile for the tree network 0 ee cee eeeeeeeeeeeeeneeeeeeees 84 Figure 6 12 Estimated link flow profile for the tree network 0 ee eee ceeeeeeeereeeneeees 84 Pigure 6 13 Alinear network sis swe Se E E eee bee te KE 85 Figure 6 14 True O Dtrip table ie eee a eae atic 85 Figure 6 15 Estimated O D flow profi
8. tf K lt lel set K lel CHAPTER 3 LPFE FORMULATION AND ALGORITHM 29 Step 1 6 For each O D pair for which the target O D information exists Compute Ing ng 1 Prs If lt 9 set Vis Vis e Update f and Vif K lt lel set K lel Step2 Convergence test If lt stop otherwise return to Step1 Apparently IBA sequentially checks and fixes the violations of the Kuhn Tucker conditions 3 56 to 3 66 while maintaining the relationship dictated by the logit path choice model Equation 3 55 Proposition 3 1 Jf E LPFE SUB has a non empty feasible set algorithm IBA converges to its optimal solution Proof First note that the Lagrangian associated with E LPFE SUB is Lf u A A v gt v fe fing Inf D Af C u Aof lo Yo X0 A kaa Aof Io o Xo 27 F Aof Jo F No qo v z Aof Jo a Qo Go v Let f be a vector satisfying the first of the Kuhn Tucker conditions 3 55 then we replace f in L u A A v v with f which now is a function of Lagrangian multipliers According to Saddle point theorem the Lagrangian is minimized with respect to primal variables f maximized with respect to dual variables multipliers thus we have LE u A7 vt vT SLE u A A ee To show the convergence of the algorithm we take derivatives of the Lagrangian with respect to 4H OL f u A A7 v v Ou pine E Aup Ao A
9. 5 Af lt 0 3 60 A7 Ko Io 50 Aof 0 3 61 o Jo Mo Mof gt 0 3 62 v qo Jo no Mof 0 3 63 Go Jo Po Mof lt 0 3 64 Vv Go Jo Po Mof 0 3 65 w20 At 20 4 2 0 v4 2 0 v 20 3 66 H A A v V are multipliers associated with corresponding constraints and are path travel times containing measured link travel times i e eS OTe Go acAy acA y 3 67 Similarly path costs used in the logit choice model take the following form ae EP DY toet DY MOE DEA Se acA y acAo acAo 3 68 The model extensions developed so far can be easily extended to the time dependent case For the sake of complexness the formulation of the extended TD LPFE is given below L E TD LPFE a a 1 t P lyt min Jo rh ov dw S Taxi Fle Infi 1 0 5 vh Davi acA y acAo 3 69 subject to Equation 3 38 and CHAPTER 3 LPFE FORMULATION AND ALGORITHM 27 Aoft lt 3 Io 73 3 70 Aoft gt 3 I 85 3 71 Mof lt g6 Jo no 3 72 Mof gt Jo 5 3 73 Again the model E TD LPFE will be solved once for each time interval and the residual queue Vf is updated based on the queue from the last period v4 For the first time interval t 1 itis assumed that v 0 We close this section by mentioning that the total demand of an O D entry is not fully observable even with recent surveillance techniques Quite often only a subset of vehicles has the
10. Bond Bvt ort So bal C Using the relationship 3 55 we obtain CHAPTER 3 LPFE FORMULATION AND ALGORITHM 30 OLE u A AT vt v Ou Ay C For any link a Au if a areas k lt Ca the constraint is inactive so Ha should remain equal to 0 Otherwise the derivative of Lf u A A7 v v with respect to Ma is positive Thus to maximize L f 4 4 A v v Ha should increase From 3 55 we know that the increase of Ha will reduce the corresponding path flows and hence the value Dae Onde Apparently to increase L f u 4 A v v as much as possible we should increase Ha such that bas Dae Da Oak Ca but not beyond It is easy to verify that the adjustment made in Step1 2 of the IBA algorithm exactly achieves this The similar argument can be applied to other constraints As the algorithm always increases L f u A A7 v v it converges provided there exists a feasible solution This completes the proof However in practice there are situations where E LPFE SUB does not have a feasible solution thus algorithm IBA would not converge According to Bell Bell et al 1997 the major ones are 1 Traffic counts of one or more links belonging to Ao are not consistent with capacities of one or more links belong to Au 2 Traffic counts of some links belong to Ao are mutually inconsistent 3 Existing path set does not cover one or more counted links Such situations arise as a result of either errors
11. Field 1 Integer Number of nodes n Block 2 n rows Field 1 Integer ID of the first link going out from node i row i in Block 2 Field 2 Integer ID of the last link going out from node i Block 3 1 row Field 1 Integer Number of links m Block 4 m rows Field 1 Integer ID of the starting node of link i row i in Block 4 Field 2 Integer ID of the ending node of link i Field 3 float Capacity vehicle per hour Field 4 float Length mile Field 5 float Free flow speed mile per hour LPFE does not use data in Block 2 so users can put any integers there to fill the places APPENDIX I 2 Block 1 Block 2 Block 3 Block 4 Figure I 1 An example of the file project 1 Table I 2 A description of the file project 2 Range Fields Type Description Block 1 1 row Field 1 Integer Number of origins Block 2 n rows Field 1 Integer ID of the origin node i for row I in Block 2 Field2 Integer ID of the first O D pair associated with origin i Block 3 1 row Field 1 Integer Number of OD pairs Block 4 m rows Field 1 Integer ID of destination node for O D pair i row i in Block 4 the origin of this O D pair i can be derived from Field 2 in Block 2 Field 2 float Demand for O D pair i APPENDIX I 3 Block 1 Block 2 Block 3 Destination node 3 is at 25th row in Block 4 It is associated with origin 2 w Oo co 0 0 OO Co CO CO CO OF Oo Oo CO 0 O02 CO CO Figure I 2 An ex
12. veh 7 T i T T T 700d eN ANIE E ETENEE A SEEEN PATE ET 500d 400d a A E P E O EE Fu E AE E E A anced one 2000 Cumulative departure flow DOO asics sean R AE E sacha cdaen E E Sas cecea inn Tang naam Cuet gees tae Lae 1 i 1 i 1 i 1 i 1 i 1 i 1 06 00 06 16 06 33 06 50 07 06 07 23 07 40 07 56 08 13 Departure time Hour Minute Figure 6 44 A time dependent demand pattern As before we first solve a time dependent logit traffic assignment model TD_BSUE c f Section 3 1 2 to produce time dependent traffic counts According to the observation made in Section 6 4 2 we only employ traffic counts on the freeway links and consider a historical O D matrix which is generated by applying an up to 20 random perturbation over the true O D matrix Link RMSE at different time intervals are plotted in Figure 6 45 Clearly it is easier for TD LPFE to reproduce the observed link traffic counts when the demand level is low The number of used paths is small in uncongested cases as in the first few time intervals and thus they are easy to be identified by a column generation procedure When roads get congested however more paths were used and so the difficulty of satisfying all the constraints increases i e it is easier to get a path set from column generation which differs than the true one Of course algorithmic parameters can be finely tuned to achieve a better match of link traffic counts as described
13. 1993 Ashok and Ben Akiva 1993 1996 2000 reported encouraging results in several case studies and filed tests and indicated that their method turned out to be robust When attempting to implement Ashok Ben Akiva approaches for comparison purpose however Sherali et al 2001 discovered that the matrix needed to be inverted in updating the Kalman gain matrix is always singular As Sherali et al 2001 pointed out the failure might be a result of violating some Kalman filter assumptions in the application This observation called for special attention in checking data requirements and verifying standing assumptions when implementing Kalman filters in practice Sherali and Park 2001 proposed a dynamic path flow estimator which describes the relationship between dynamic O D flow and link flows as follows Pe Dp DPR oe X oh Va A k K s t h adler as r s k t 2 12 Sag eK et k 2 13 where f is associated with the path flow departs along path k during time interval t while ar 1 if link a is occupied during time interval h due to path flow f Bhs and 0 otherwise Sherali et al s dynamic PFE is formulated as a constrained least squares CLS problem which seeks to determine a set of time dependent shortest path flows that reproduce the observed link counts as closely as possible Specifically Sherali et al s CLS estimation model reads Z T min 2 gt D Sa ele u gt S cH n n 2 14 subject to H gt 0 V
14. E LPFE which reads E LPFE SUB in f c Lie nf 1 min f a 9 74 subject to 3 30 3 49 3 50 3 52 and 3 53 Note that we use instead of because some link travel times are measured values There exist a number of descent direction algorithms for solving a nonlinear program like E LPFE SUB e g the Frank Wolfe algorithm However the complex constraint structure involved in E LPFE SUB makes it unappealing to use those classical procedures The iterative balancing algorithm IBA offers a promising alternative by directly exploiting the Kuhn Tucker conditions Equations 3 55 to 3 66 The major steps of the algorithm are summarized below ALGORITHM IBA Step 0 Initialization Set u 0 4 0 4 0 v 0 v 0 K 00 Step 1 Iteratively check constraints and update path flows Step 1 1 Calculate path flow f according to Equation 3 55 Set x Af q Mf Step 1 2 Foreachlink 4 Au compute Inta nCa If e gt 0 get Ha Ma te Update f X and q Jif K lt lel set K lel Step 1 3 Foreach link 4 Ao compute Ma InXa 1 ya If gt 9 set Aa AG e Update f and 4 if K lt lel set K lel Step 1 4 For each link 4 Ao compute e Infa nx4 1 a If 6 lt 9 set Aa Aa Update f X and 9 if K lt lel set K lel Step 1 5 For each O D pair for which the target O D information exists e Ing ng 1 Mn Compute If e gt 0 set Vis Vis te Update f X and
15. Ipre_ex_t1_od db 12KB DBF File E Ipfe_ex_tt_od shp 2KB SHP File f eee eee rf lpfe_ex_t1_od shx 1KB SHX File El Ipfe_ex_t1_od_bounds dbf 1 KB DBF File esi Ipfe_ex_t1_od_bounds shp 1KB SHP File I lnfe od bounds shx B Hi Fil j ex_t1_scatterplot dbf 73KB DBF File Ipfe E Ipfe_ex_t1_scatterplot shp 3KB SHP File esi Ipfe_ex_t1_scatterplot shx 1KB SHX File E Ipfe_ex_t1_scatterplot_axis dbf 1KB DEF File Ipfe_ex_t1_scatterplot_axis shp 1KB SHP File E Ipfe_ex_t1_scatterplot_axis shx 1 KB SHx File F E Ipfe_ex_t1_scatterplot_marker dbf 1KB DBF File ies Ipfe_ex_t1_scatterplot_marker shp 1KB SHP File E Ipfe_ex_t1_scatterplot_marker shx 1KB SHXFile lt j l Figure 5 12 Shapefiles and Network Map Layers Figure 5 13 shows a side by side view of the list of shapefiles and legend of the Scatter Plot layers E Ipfe_ex_t1_od_bounds shp 1KB SHP File lipfe e B SHX File a Ipfe_ex_t1_scatterplot dbl DEF File ipfe ex_t1_scatterplot shp SHP File E Ipfe_ex_t1_scatterplot shx SHX File w Ipfe_ex_ti_scatterplot_axis dbf DEF File E Ipfe_ex_t1_scatterplot_axis shp SHP File SHX File Ipfe_ex_t1_scatterplot_marker dbf DBF File esi Ipfe_ex_t1_scatterplot_marker shp SHP File ipfe ex_t1_scatterplot_marker shx SHX File Figure 5 13 Shapefiles and the Scatter Plot Layers CHAPTER 5 VISUAL PFE TD 74 5 3 3 ESRI MapObjects MapObjects is a set of mapping software components that let
16. Th 12 9 140 16 9 80 Figure 6 17 Ring network Figure 6 18 True O D trip table O D estimation profile plot for time interval 1 RMSE 29 5448 100 00 percent total demand is captured EERS line 50 100 150 200 250 300 350 True O D flow Histogram plot for estimated O D 2 1 o 1 2 3 4 5 6 Deviation from True O D flows Figure 6 19 Estimated O D profile for the ring network CHAPTER 6 CASE STUDIES 88 Estimated link flow profile plot for time interval 1 Number of measured links 16 RMSE 0 0004 1400 1200 m 800 Estimated True link flow 600 200 400 600 1000 1200 140 800 True link flow Figure 6 20 Estimated link flow profile for the ring network Similar observations can be made for the ring network as the linear network which is somewhat expected because a ring network is a special type of linear network Both the link flow profile and the total amount of demand are predicted accurately while estimated O D flows does not perfectly match true O D flows with RMSE_OD 29 5448 This is again due to the fact that the path flow solution in a ring network is usually not unique 6 3 4 The case with a derived general network The derived network we use for testing is shown in Figure 6 21 There are 30 nodes eight origins and five destinations 33 links and 40 O D pairs in the network The true O D flows are provided in Figure 6 22 The estimated O D flow profile and link flow profi
17. amp Marquis G 1993 Dynamic estimators of origin destination matrices using traffic counts Transportation Science 27 363 373 Chang G L amp Tao X 1996 Estimation of dynamic O D distribution for urban network In Proceedings of 13th International Symposium on the Theory of Traffic Flow and Transportation pp 1 20 Chang G L amp Wu J 1994 Recursive estimation of time varying origin destination flows from traffic counts in freeway corridors Transportation Research 28B 141 160 Cremer M amp Keller H 1981 Dynamic identification of O D flow from traffic counts at complex intersections In proceedings of 8th International Symposium on Transportation and Traffic Theory Cremer M amp Keller H 1984 A systems dynamics approach to the estimation of entry and exit O D flows In proceedings of 9th International Symposium on Transportation and Traffic Theory Cremer M amp Keller H 1987 A new class of dynamic methods for the identification of origin destination flows Transportation Research 21B 117 132 Daganzo C F amp Sheffi Y 1977 On stochastic models of traffic assignment Transportation Science 11 253 274 Dial R B 1971 A probabilisitc multipath assignment model that obviates path enumeration Transportation Research 5 83 111 Fisk C S 1980 Some developments in equilibrium traffic assignment Transportation Res
18. amp Visus 1D Fie Edt View Table Estmate Dagom Windows Heip pee M MIE EA R E EE Scatter Piot SC MPFEM xample ES Tipton 1I FF LPFE_EX_T2_SCATTERPLO F LPFE_EX_T2SCATTERPLO Pad UPFE_DCTI_SCATTERPLO I UPFE_EX_19_00_ 0UNDS 7 UPFE_EX_T3_00 M F LPFE_EX_13_00 a F LPFE EX TI NETWORK Ww Figure 9 Create Shapefiles Window for Previously Estimated Outputs Scatter Plol_SC V PFE xarnpleVSIUpte_ FF LPFE_EX_T2_SCATTERPLO LPFE_EX 12 SCATTERPLO yw E LPFE_EX_T2 SCATTERPLO P UPFE_EX_12_01 F F LPFE_ X12 00 a R LPFEEX_TZ NETWORK M de Create Shapefiles and Tables The input network CALPFE Example EST ipfe_ex net Select from the following time intervals Time Intervals Create and show Tl Network I Scatter Plot F OD Table I Report 15 LPFE_EX_T1_SCATTERPLO F LPFE_OX THSCATTERPLO x LPFE_DX_TI_SCATTERPLO LPFE_EX11_00_BOUNDS P LPFE_EX_11_0L F LPFE_OX T1100 F LPFE EX TI NETWORK A Network Map Window The outputs of a LPFE estimation are converted to ESRI Shapefiles for visualization A map window is shown in Figure 10 The title of a map window corresponds to the file name and path of the LPFE estimation output for one particular time period For example the map window in Figure 10 corresponds to the estimation result of time period 1 based on the input network file called Ipfe_ex which is stored in the folder of C LPFE Example E
19. e ex EA te resur My Recent Documents 3 Desktop My Documents My Computer My Network File name 9GRD_Excel0D Places Save as type Excel files xls y Figure 28 Save OD Table as Excel File 32 Example 5 Visualize Paths The estimates of path flows between origins and destinations are also generated by PFE as a text file 1 e the pthsum csv file Similar to the OD tables the Visual PFE program can convert the path text file and formats it as a spreadsheet How to Open a Path Table 1 Make the corresponding network map the active window 2 Go to the menu item Tables Open Path Table The path will open accordingly Figure 29 ORIGIN DESTIN PATH_ID PATH_COST PATH_FLOW LINK_ID 4 5406784282 33 8352695815 5 0137019450 77 4 5969356316 16 1151400089 3 6312836916 60 372969305 4 0263277513 53 4945036560 4 0825849548 25 4784852252 4 6787445923 76 6271966005 5 5407941692 10 30261 50666 5 0143434232 11 3675820269 5 0706006267 5 4141781104 2 5853935222 130 3720190841 2 0710428454 206 1217935543 3 05905851 730 43 8008811303 3 5855092632 39 6974147003 3 5400398575 72 6775415587 2 1200770651 69 6270626458 3 02568918070 114 9052175645 i 2 a 4 5 6 7 E w ojal s wn o Figure 29 Path Table How to Display Paths 3 Make sure that both the network map and the path table windows are opened 4 Make the path table the active window Click at a cell in the path table to make
20. e f pit nf lt 9 f Fit inf This is apparently satisfied since f is an optimal solution of E LPFE SUB which should achieve the minimum objective function value End of proof Thus the optimal solution to E LPFE can be obtained by iteratively solving E LPFE SUB and moving along the resulted descent direction We proceed to present a descent direction algorithm in which the Golden section line search is used to find a suitable step size ALGORITHM DDAG Step 0 Initialization Set iteration index i 0 x OVaeA t t 0 Va A Call Algorithm RIBA to obtain f Step 1 Find the descent direction Update link travel times based on fi then call Algorithm RIBA to obtain a new path flow pattern denoted as g Set search direction d gi f Step 2 Find step size Step 2 1 Initialization Set 1 0 0 b G V5 1 2 a 1 G u 1 0 Compute Za 2 fi ad zp 2 fi bd Step 2 2 If Za lt zp l a a b b Ga 1 G u else u b b a a Gb 1 G l Compute Za Zp Step 2 3 If u I gt b a return Step2 2 otherwise if Za lt Zb a a else a b goto Step3 Step3 Move along search direction Set fi fi adi jf f fk stop otherwise set i i 1 return to Step1 In Algorithm DDAG we terminate the procedure when the two consecutive iterates are sufficiently close gt Stands for Descent Direction Algorithm with Golden section line search
21. e Toolbar Button Label Features E Activate the Label Setup Window to label features on the active layer of a map or a scatter plot Toolbar Button Class Map a Activate the Class Map Setup Window to classify the features on the active layer of a map or a scatter plot using different colors and symbol sizes Toolbar Button Bar Chart o Activate the Bar Chart Setup Window to create bar charts for the features on the active layer of a map or a scatter plot based on the selected values of the feature s attributes Toolbar Button Clear Postings E Clear all postings e g label classes and bar charts added to the features of a map or a scatter plot Toolbar Button Table Zoom In El Zoom in a table window Toolbar Button Table Zoom Out gl Zoom out a table window Toolbar Button OD Color E Activate the OD Color Setup Window to adjust the colors of the OD table cells according to the values of the cells Toolbar Button Display Desire Lines E Relate a cell in an OD table to the corresponding desire lines in the network If the active cell of the OD table stays on an internal cell when the button is clicked the focus will be move to the network window and the desire line corresponding to the OD pair will be highlighted If a cell in the row sum or the column sum is the active cell one to all or all to one desire lines will be highlighted If the active cell of the OD table stays on the table total all of the desire lines will be highl
22. measured link flows are reproduced by estimated flows Finally to simplify the analysis all tested scenarios assume that link travel times are independent of link flows 6 2 Algorithmic Settings The performance of LPFE may be substantially affected by several algorithmic parameters Thus it is natural to ask what are the optimal parameters leading to the CHAPTER 6 CASE STUDIES 78 best performance To answer this question we explore the relationship between the parameters and the LPFE performance using numerical experiments The major parameters in consideration include maximum iteration number n n restricts the maximum number of iterations for DDAG the algorithm solving the E LPFE SUB problem accuracy e defines the stopping criterion for both DDAG the algorithm solving the e LPFE SUB problem and CGA the column generation algorithm For narrative convenience we shall denote the convergence indicator of the 7 th iteration of DDAG as k hereafter Either algorithm will terminate if ki lt maximum bad iterations bn bn represents the maximum number of iterations in which ki gt kii zigzagging criterion Z and maximum zigzagging iterations zn z defines the criterion to count an iteration as a zigzagging iteration and zn restricts the ki ki t maximum number of zigzagging iterations for DDAG If ka sa the iteration will be treated as a zigzagging iteration A small network t
23. the model can be expressed in path flows only as shown below puny DE eee eS Dee D r S k r S k 3 8 subject to Equation 3 4 3 2 and yD roak Ca Va E A pobre oe 3 9 where Cy is the travel time on path k We can further simplify the model using matrix notation as follows BSUE min f c F t nf I 3 10 subject to Af lt C 3 11 Mf q 3 12 gt 0 3 13 where a b afb A and M are mxn and xn matrices respectively with m n and l are numbers of links paths and O D pairs respectively Ignoring the nonnegative constraints the optimality conditions of Bell s logit model can be written as CHAPTER 3 LPFE FORMULATION AND ALGORITHM 18 inf e Ap M o 0 0 3 14 C Af gt 0 gis CSARS 3 16 H20 3 17 q Mi 3 18 Note that 4 and are vectors of Lagrangian multipliers associated with constraints 3 11 and 3 12 respectively Conditions 3 14 and 3 17 provides the logit path choice model as of 3 5 However the path cost 7 in 3 5 now has the following form nis Dae Mad n 3 19 where Ha is the Lagrangian multiplier interpreted as the equilibrium queuing delay on link a 3 1 2 The time dependent case Although the introduction of capacity constraints rules out link flows beyond capacities it also reduces the feasible solution set that under some situations a feasible set may be empty particularly in congested networks An alternative is to model queues
24. traffic counts to be available An extended Kalman filtering procedure is used to solve the nonlinear dynamic system but no guarantee is made to satisfy the necessary constraints on the estimated variables The travel time computation procedure in the Chang and Wu model seems to be too simplistic to be realistic for congested freeway corridors Also the assumption that travel time between any O D pair will not span more than two intervals is very restrictive Wu and Chang 1996 further revised their earlier model to include constraints established through screenlines A scrrenline is a hypothetical cut that divides the network into two parts The basic idea of the modified model comes from the assumption that most vehicles from origin 7 arriving at the screenline during interval t should embark during some intervals knowable from travel time estimation Consequently the fundamental measurement equation relates the screenline flows to O D flows and time lag factors Since one can choose as many screenlines as possible for a given urban network sufficient constraints can be obtained for a more reliable estimation Later Chang and Tao 1996 extended the concept of screenline to cordon line for more general networks The measurement equation used in this model is similar to that in Chang amp Wu 1994 but the dynamic assignment parameter is assumed to be known A Kalman filter is again used to estimate the state during each time interval and as t
25. 26 Path Table Wind W meest a a a a N a a NS 27 Display Paths sinn a a R A a aN 27 Report Window inserer iiin E A E EAE T ET 28 Creating and Editing Text Piles iacssnscadacvcgus iisisti etetett ntes ear iE sees erates 29 Scenario Comparison Window nosediens 29 BoE Tare ORAA a A N EEE E A E 30 Technical SpeCiicat Omi ceskesss cust tic n a a a O A O a aS 31 E d S E E E E T E EE 32 The ArcViewShapefile Read Write OCX sseesesesessseeesseeessessresseesseessseeesseesseesseessee 32 The Shapefiles of the Network Map and Scatter Plot Windows ssesseeceeeeeeeeeeeeene 33 ESRI MapObjects cniinn n E E E E E 34 GT POLI SPEC AU a a A E ESS 35 List of Figures Figure 1 Multiple Document Interface 1j 25 2 soca desseieetder a istdessseetad ai eueeesstees adie 6 Figure 2 Main Waid Wy pear hee tear ie ects aa hte ce ase t ea te ba asec i es feels cet aaa 7 Figure 3 Toolbar Buttons nonien aA Aa ake E et a gad Dead 9 Figure 4 Algorithm Input Window seessesseseseseessesesseseresresseserssressessresrensesstesresseeseeseeesee 11 Figure 5 Parameter Input WindoW sessessesesesseseeseesseserssresseserssressesstertensesseesressreseeseresee 12 Figure 6 DOS Command WindoW esessesseseeeseeeesersstserssressesersstessersrsstensessreseeseeseseeesee 13 Figure 7 Create Shapefiles and Tables WindoW eesesessesseseeessssesseesresrersessresreesresseseesee 14 Figure 8 Main Window with Output Windows ssessseseseseesessesesssressessresrersessrr
26. 2KB SUM File gt Ipfe_ex_t zne 3KB ZNE File iS Ipfe_ex_ti_di dbf 116KB DBF File C LPFE Example ESTMpfe_ex_t1 DAR E lpfe_ex_t1_dl shp 40KB SHP File I LPFE_EX_TI_OL ilipfe ex t1 dl shx 4KB SHX File 2 5 IpFe_ex_t1_network dbf 265KB DBF File 17 LPFE_EX_T1_NETWORK ea Ipfe_ex_t1_network shp 77KB SHP File as esi Ipfe_ex_t1_network shx 8KB SHX File K ee eee S Ipre_ex_t1_od db 12KB DBF File E Ipfe_ex_t1_od shy 2KB SHP File Bere ere rome 5 Ipfe_ex_t1_od shp A Ipfe_ex_t1_od shx 1KB SHX File s TH S Ipfe_ex_t1_od_bounds dbf 1KB DBF File E Ipfe_ex_t1_od_bounds shp 1KB6 SHP File BROS eae ex od bounds shx KB Hx Fi S Ipfe_ex_t1_scatterplot dbf 73KB DBF File Ipfe_ex_t1_scatterplot shp 3KB SHP File EEC E Ipfe_ex_t1_scatterplot shx 1KB SHX File EEOC E lpfe_ex_t1_scatterplot_axis dbf 1KB DBF File tps esi Ipfe_ex_t1_scatterplot_axis shp 1KB SHP File E Ipfe_ex_t1_scatterplot_axis shx 1KB SHX File oe 5 lpfe_ex_t1_scatterplot_marker dbf 1KB DBF File EEE A E Ipfe_ex_t1_scatterplot_marker shp 1KB SHP File e Ipfe_ex_t1_scatterplot_marker shx 1KB SHX File lt Figure 24 Shapefiles and Network Map Layers 33 Figure 24 shows a side by side view of the list of shapefiles and legend of the Scatter Plot layers Se Ws bound ES exti ri a ipfe ex_t1_scatterplot shp Scatter Plot_SC LPFE Example ESTUpfe_ex_11 e Ipfe_ex_t1_scatterplot shx F LPFE_EX_T1_SCATTERPLOT S Ipfe_ex_ti_scatter
27. 4 Travel times on links belong to A are measured thus not computed from link performance functions CHAPTER 3 LPFE FORMULATION AND ALGORITHM 34 3 3 3 Column generation So far a path set hence the path link incidence matrix A is assumed to be predetermined Ideally all existing paths should be enumerated before hand This is of course computationally prohibitive even for a network of modest size In fact a great portion of available paths would remain unused in a complex congested network Different strategies have been suggested to set up a proper path set of which the most famous one is due to Dial 1971 who proposed to reduce the original network into an acyclic one containing only efficient links As we have noticed however a predetermined path set may introduce inconsistent constraints Thus it is desirable to generate paths iteratively only when they becomes needed based on the diagnostic information obtained from previous iterations This is known as column generation because the columns of path link incidence matrix A are generated as the iterations progresses A shortest path algorithm is commonly used to generate new paths However the calculation of shortest paths is not necessarily based on travel times In logit path flow estimators for example the paths that might help remove inconsistency of constraints should be given high priority This can be achieved by arbitrarily decreasing increasing link travel times s
28. 5 To reduce the view of the OD table again simply press down the toolbar button Table Zoom Out al The OD table view will be reduced again The default color scheme for the OD table cells is gray for cells 0 and red for cells gt 0 Users can adjust the colors of the cells using the OD Color Window How to Adjust the Colors of the OD Cells 6 Make the OD table the active window 7 Go to the menu item Table OD Table Color or click at the toolbar button OD Color E The OD Table Color Window will open Figure 23 26 ODTableColor 0 D_ C Visual PFE_exx 3_Exercise_3 IRVN pfe The maximum flow of the table is 4573 6812598021 Value 0 0 lt flow lt 1143 42031 495052 1143 42031 495082 lt flow lt 2286 84062990105 2286 84062990105 lt flow lt 3430 26094485158 26298 6672438521 lt flow lt 4573 6812598021 s Le toe Figure 23 OD Table Color Feature 8 Onthe OD Color Window the values of OD flows are broken down into four classes Double click at each color block to set up the color 9 Click at the Apply button The cell colors of the OD table will be adjusted accordingly Figure 24 tw O D_ C PFE_Workbook 3_Exercise_3 9GRD pfe SEE 19 35 03 7 i E 419 99 WESE 370 00 0 00 0 00 0 00 0 00 0 00 330 00 530 00 300 00 1160 00 Figure 24 The Adjusted OD Table Color 27 How to Display Desire Lines via the OD Table The desire line layer is typical
29. A S T Ul i Ww xi yo 52 56 60 64 70 19 22 25 29 80 85142 147 203 844 52 57 115 172 176 182 122 126 130 134 138 143 844 10 13 16 19 22 25 29 80 85143 844 52 57 115 172 176 182 122 126 130 134 138 142 147 203 844 10 14 60 65122 126 130 134 138 143 844 52 56 60 65122 126 130 134 138 142 147 203 844 10 13 17 65122 126 130 134 138 142 147 203 844 10 14 60 65122 126 130 134 138 142 147 203 844 44 52 56 60 64 70 19 22 25846 4 10 13 16 19 22 25846 4 10 13 16 20 68 74 22 25846 44 48 52 56 60 64 68 74 22 25846 4 7 10 14 60 64 68 74 22 25846 45 103 161 218 223 281 339 397 455 513 570 574 579 637 695 752 848 45103 161 219 277 335 393 450 455 513 570 574 579 637 694 699 s48 gt gt pz olw oo MN amp wi Mm LS BL ied ML id ed 2 el Me MD el BL ed a 1 2 3 4 5 6 7 8 1 2 3 4 5 1 2 Figure 5 6 Path Table Window 5 2 4 Link Flow Scatter Plots One of the most common and important diagnostic graphs for the OD estimation problem is the observed versus estimated scatter plot of network link flows see Figure 5 7 The scatter plot is implemented in Visual PFE TD as a collection of map layers The scatter plot point layer uses the observed value of a link as the X coordinate and the estimated value as the Y coordinate A link layer is used to represent the two axes and other boundary lines delineating the levels of accuracy of the estimation CHAPTER 5 VISUAL PFE TD 68 Scatter Plot_SC LPFE Example EST lpfe_ex_t1
30. O D flows Five upper bounds namely 10 20 30 40 and 50 are considered for these perturbations for each of which we generate five random O D tables The RMSE ODs of the hypothetical historical O D trip tables of all the scenarios are given in Table 6 1 while MOEs are shown in Figures 6 32 6 33 and 6 34 It can be seen from the figures that TDC is insensitive to the change of RMSE ODs Note that TDCs of all the scenarios fall into a narrow interval from 95 to 105 Table 6 1 RMSE_ODs for hypothetical historical O D flow trip tables uniform error for the link set of all measured links for link set of freeway links veh hr veh hr 15 33 40 51 19 66 31 79 10 42 26 37 85 26 94 34 99 23 41 28 46 47 88 62 81 32 69 39 68 20 82 43 62 98 80 25 44 21 83 85 32 51 127 84 87 39 41 49 112 53 30 111 35 92 90 90 88 93 52 114 17 73 62 121 93 147 85 58 59 147 66 40 61 82 53 68 97 86 115 14 96 46 98 61 113 11 63 44 77 27 58 90 50 140 35 146 29 152 67 103 94 139 43 153 42 CHAPTER 6 CASE STUDIES TDC 100 40 100 30 100 20 100 10 T 3 S 100 00 Q 99 90 n 99 80 rar 99 70 i 99 60 hd 99 50 0 20 40 60 80 100 120 140 160 180 RMSE of the historical OD veh hr a all measured links 267 amp historical O D 105 r na
31. O D table In this section we rerun the 25 scenarios set up in Section 6 5 1 but address the O D flow errors explicitly in LPFE The MOEs of the estimation results are shown in Figures 6 38 6 39 and 6 40 For comparison the results when input errors are not explicitly considered are also plotted in those figures 100 40 A 100 20 s 3 A A A A gt 100 00 ta iP a A a SA g 99 80 i ra a A e Ae A 99 60 z a 100 99 40 i F A Estimated OD not consider OD flow error A Estimated OD consider OD flow error 99 20 0 20 40 60 80 100 120 140 160 180 RMSE of the historical OD veh hr a all measured links 267 amp historical OD CHAPTER 6 CASE STUDIES 105 TDC 105 100 95 90 85 80 RMSE of the estimated OD veh hr 3 t e 24 AA A A A AA a A AA A A A Aa A A A A A Al 100 Estimated OD not consider OD flow error A Estimated OD consider OD flow error 0 20 40 60 80 100 120 140 160 180 RMSE of the historical OD veh hr b freeway links 27 amp historical OD Figure 6 38 TDCs for scenarios with different settings on the consideration of O D flow errors 180 T Historical OD 160 Estimated OD not consider OD flow error 140 gt A Estimated OD cons
32. O D trip table itself was subject to significant errors RMSE OD 110 41vel hr Yet it does provide important information regarding to the spatial structure of O D demands which greatly improves estimation results 6 5 The effects of Measurement Errors In reality both link flow and O D flow measurements are subject to errors which are usually not known exactly beforehand For example link traffic counts measured by detection devices might contain errors caused by calibration inaccuracy failure of the device and so on Further a historical O D trip table based on a travel diary survey done several years ago might be well out of date Hence the robustness of LPFE in presence of input errors is an important issue to address We test the influence of measurement errors of O D flows and link flows in subsection 6 5 1 and 6 5 2 respectively All the tests use Dallas Fort Worth network described in section 6 4 6 5 1 Measurement errors of O D flows Two different link flow sets i e all links and freeway links are used to study the CHAPTER 6 CASE STUDIES 97 influence of measurement errors of historical O D flows For clarity link measurement errors are not considered here For each link set we set up 25 scenarios each associated with a hypothetical historical O D trip table with various levels of measurement errors These O D trip tables are generated by randomly applying a perturbation to which is bounded from above the true
33. Po oe 0 gt No gt 0 90 gt 0 00 1 0 0 ne 0 0 o Finally note that in the original LPFE travel times on measured links contain no queuing delay because the capacity constraints of these links are not considered in estimation problems This causes miscalculation of path costs and in turn the problem of path flow estimation To address this issue not only traffic counts but also queuing delay needs to be measured The observed link travel times free flow travel time plus observed delay should be considered as constant over the estimation process Although measuring queuing delay directly is far more difficult than measuring traffic counts it is possible as Bell noted to calculate the queuing delay by use of an appropriate delay formula Now we are ready to present the extended LPFE in its complete form E LPFE min MEE iaXq L Inf I x f z s 3 54 subject to Equations 3 30 3 49 3 50 3 52 and 3 53 where fa denotes the observed travel time on link a which consist of a travel time component without delay and a delay component The Kuhn Tucker conditions of this extended formulation are I hnf C F Aus LL Ao A Ao A7 Ao v Ao V 0 0 3 55 Cu Auf 0 3 56 u Cu Auf 0 3 57 The Webster s formula was used for that purpose in Bell et al 1997 CHAPTER 3 LPFE FORMULATION AND ALGORITHM 26 Zo lo F Yo a Aof gt 0 3 58 A Ro Io Yo Aof 0 3 59 Zo Io
34. Visual PFE TD will attempt to create another LPFE input file i e the par file after users click at OK If the file is successfully created the LPFE program will be launched and a DOS command window will appear Figure 6 No user intervention is required when the program is executing If the LPFE run is not successful users will receive an error message prompting them to fix the LPFE network data or change the parameter values For details about the LPFE network data and the parameters please see LPFE User Manual cx C Documents and Settings MSL My DocumentsWisual Studio Projects LPFE GUI bin L_PFE_G Oo x A Software of Traffic Lab at UC Davis Author Yu Nie Building algorithm object Maximum allowed iterations should range between 1 and 1660000 The default value 100 is retained Accuracy should range between 1e 16 and 1 The default value 661 is retained Minimum allowed stepsize should larger than 1e 00 The default value 6 6061 is retained Line search accuracy should range between 1e 6 and 1 The default value 6 661 is retained Maximum allowed line search iterations should range between 1 and 1660 The default value 10 is retained Maximum allowed bad iterations should range between 1 and 1660 The default value 5 is retained Zigzagging criterion should range between 1e 16 and 1 The default value 6 61 is retained Maximum allowed bad iterations should range between 1 and 1000 The default value 5 is re
35. Window Figure 34 amp Report_C Wisual PFE_exx 3_Exercise_3 IRVN pfe SEE Number of link observations 182 Number of target O D flows D Number of paths generated 2164 Total Demand Estimate 46350 5663 RMSE of link flows estimates 59 7582 RMSE of O D flow estimates NZA Number of unobserved O D pairs 0 TDS_max 85255 3327 TDS_min 44502 5755 Total Demand Scale 40752 7572 Figure 34 Report Window How to Open a Report Window 1 Make the network map the active window 2 Go to the menu item Diagnostic Statistics A Report Window is actually a rich text box that can serve as a text editor User can use the Report Window to edit or create PFE input network data How to View and Edit Text Files To edit an existing text file go to the menu item File Open and select one of the PFE input text files e g 9GRD pfe The file will be opened with a report window Figure 35 37 amp C PFE_Workbook 3_Exercise_3 9GRD pfe SEE g 13 1 143 676615 59 922371 4 5 2 143 656615 59 922371 6 7 3 143 678615 59 902371 8 8 4 143 638615 59 902371 9 9 5 143 656615 59 862371 006 143 638615 59 8682371 10 10 11 143 638615 59 922371 11 13 12 143 658615 59 902371 14 14 13 143 678615 59 882371 14 121 280 00 1 00 2 00 0 15 4 00 124 0000000000 0 00 131 290 00 1 00 1 50 0 15 4 00 137 0000000000 0 00 181 280 00 1 00 3 00 0 15 4 00 109 0000000000 0 00 271 280 00 1 00 1 00 0 15 4 00 7 0000000000 0 00 28 1 600 00 1 00 1 00 0 1
36. accessing another class library TNM for some of constants and types defined in TNM may also be used To solve the steady state LPFE we first define and create a corresponding algorithm object TNM_LODE Note that four parameters are required to construct a TNM_LODE See the class description for the meaning of these parameters Lines 6 8 specify optional parameters such as the type of link performance function line 6 Default values would be used if no value is provided here Then the Build function is called to read files from disk files and allocate memory to handle data This Build function requires various input files depending on the problem type and the network file format the details of the input files will be discussed in Appendix A Once the algorithm is built successfully the Solve function is called to find the optimal solution followed by three report functions which together prepare a solution report comprising of several ASCII files Finally the algorithm object is deleted in order to release memory The code shown in Figure 4 2 can actually be employed to solve almost all problems discussed in Chapter 3 provided line 5 is modified to fit in an appropriate object Table 1 shows a guideline for the selection of objects Clearly the object oriented design provides a neat programming interface because all complexities have been encapsulated within objects This feature is particularly useful when developing user
37. be asks to check the numbers on the form For details about the parameters please see LPFE User Manual Clicking at the Next button will launch the Parameter Input Window Algorithm Input SEE Algorithm Input Selectthe input network c LPFE Example ESTlpte_exnet 1 Maximum Allowed Iterations 1 To 1 000 000 foo 2 Accuracy 1E 16 To 1 bo 80rti OCO OCOC 3 Minimum Allowed Stepsize 1E 9 To 1 ooon 4 Desirable Line Search Accuracy 1E 9 To 1 ooo t itsi s S 5 Maximum Allowed Bad Iterations 1 To 1 000 1000 6 zigzagging Criterion 1E 16 To 1 0 000001 7 Maximum Allowed Zigzaging 1000 Iterations 1 To 1000 Cancel Help OK l Figure 4 Algorithm Input Window 11 Parameter Input Parameters Setting Input Network File CALPFE Example EST lpte_e Nebel Ele DANET2 Type C FORT Type Output File Name Ipfe_ex_t Retain Iteration History ves Time Dependent Record Link Detail ves Enumerate All Paths No Record Path Detail ves Allow Residual Queue No Record Path Topology No Create an Estimation Scenerio No Speed Flow Function BPR Function Consider Measured Link Times No Dispersion Parameter 01 Consider Target O D Demands No Cost Scalar Yes Consider Link Observation Errors No Algorithm Type Consider Target O D Errors No OK Cancel Help Figure 5 Parameter Input Window 12 After parameters on the Parameter Input Window are properly entered
38. cell colors of the OD table will be adjusted accordingly HE ODTableColor DER 0 D_ C LPFE Example EST lpfe_ex_t1 The maximum flow of the table is 42 3 Value 0 0 lt flow lt 10 575 10 575 lt flow lt 21 15 21 15 lt flow lt 31 725 Ey 243 225 lt flow lt 42 3 w e Figure 17 OD Color Window 25 Reduced OD Table View Once the cell colors are adjusted the OD table can be reduced to facilitate visualization of flow patterns of the entire table Figure 18 The function is useful when comparing two OD tables of the same network i O D_SC LPFE Example EST lpfe_ex_t1 Figure 18 Reduced OD Table View To reduce the OD table view make the OD table the active window and click at the Table Zoom Out button The view can be return back to normal by clicking at the Table Zoom In button Link OD Table to Map A unique function of the OD table is the dynamic linkage between the OD table and the location of the corresponding desire lines on the map To use this function when the network Map and the OD Table windows are both opened click at a cell in the OD table to make it the active cell then press down the Display Desire Line button The corresponding desire line s will be highlighted in the Map Window If the active cell of the OD table stays on an internal cell when the button is clicked the focus will be move to the network map window and the desire line corr
39. clear the labels press the Clear Postings button E The function applies to all three types of postings Remarks After a class map is cleared the legend is reset To place another posting you need to remember tot set the active layer again How to Create a Bar Chart Map 11 Make the layer active by clicking at the name of the layer in the legend then press the tool button Chart Map The Bar Chart Window will appear Figure 19 22 Bar Chart C LPFE Example EST ipfe_ex_t3 Ipfe_ex_t3_od ZNID OMID DX DY Figure 19 Bar Chart Feature 12 Once the form appears clicking at an attribute from the attribute list box to will select and highlight the attribute Clicking at an attribute twice will de select the attribute Multiple attributes can be selected at the same time 13 Select the height and width from the two pull down boxes 14 Click at the Create Bar Chart button The program will create the bar chart accordingly Figure 20 23 C PFE_Workbook 3_Exercise_3 9GRD pfe M SGRD_OD_BOUNDS M 9GRD_DESIRELINES wv M 3GRD_OD a MV SGRD_NETWORK Figure 20 Bar Chart Window How to Clear a Class Map 15 To clear the labels press the Clear Postings button E The function applies to all three types of postings Remarks After a class map is cleared the legend is reset To place another posting you need to remember tot set the active layer again Bar charts are best suited for visua
40. derived network As expected for a more complex network the link flow profile and the total amount of demand are still been accurately estimated with RMSE Link 0 TDC 100 Due to the multiplicity of path flow solutions deviations are observed between the estimated O D flows and true O D flows with RMSE OD 19 4774 In summary for the basic network types we discussed above LPFE can offer satisfying link flow estimates and accurately capture the total demands provided all link flows are measured The true O D flows can not be reproduced exactly if there is more than one path solution as for the linear ring and derived networks Obviously link traffic counts alone cannot guarantee estimation results of good quality in most cases Additional information such as partial O D information is needed in general and this will be discussed in the next section 6 4 The Impact of Additional Inputs Starting from this section we begin to work on a real network the network of Dallas and Fort Worth in Texas The Dallas Fort Worth network Figure 6 25 consists of 211 nodes 13 of which are origins and 13 of which are destinations 481 links 26 of which are centroid connectors and 140 O D pairs A two hour static O D trip table was CHAPTER 6 CASE STUDIES 91 obtained When the static O D estimation is performed the hourly static O D flows are treated as the true O D flows The static O D trip table will further be decomposed to cons
41. flows veh hr Figure 6 43 RMSE _Links for scenarios with different settings on the consideration of link flow errors Similar observations can be made as in the last subsection that the O D estimation results are worse off when link measurement errors are explicitly taken into account This is because again the algorithm always search the corners of a feasible region thus is likely to miss the true values lying in its interior 6 7 The time dependent case The time dependent LPFE models queuing by considering residual queues Other than that TD LPFE is essentially the same as the static LPFE In this section we set up a time dependent estimation scenario using the Dallas Fort Worth network The two hour O D demands used for static testing are now divided into 24 time intervals each is 5 minute long To illustrate the accumulation and dissipation of queues these demands are assumed to be loaded onto network following a unimodal pattern as depicted in Figure 6 44 CHAPTER 6 CASE STUDIES 110 Demand profile for O D pair 183 gt 186 39000 T T T T T T T 800d 6000 5000 a EEE AA E S TESE ice Soha Gang Cane Same LT T te Sh ass S CR EET TITE PEIEE ECA N S Umaga 3000 Departure flow rate vph 1000 fi fi L fi 1 L 1 f 1 1 i fi 06 00 06 16 06 33 06 50 07 06 07 23 07 40 07 56 08 13 Departure time Hour Minute Cumulative Demand profile for O D pair 183 gt 186
42. for O D estimation 1 Network files just same as those required in Assignment Note that O D file is also needed to provide the structure of O D matrix Particularly O D demands specified O D files project 2 in FORT and project odp in DANET2 will be regarded as true values 2 Time dependent O D file project dmd It is optional in O D Estimation and used to provide true values of time dependent O D demands 3 Algorithm parameter file project alg same as those required in Assignment 4 Observation files consisting of project obs project mlt project tar project ler APPENDIX I 10 project ter 1 project obs provides link traffic counts This file is REQUIRED for any O D estimation problem See Figure I 9 for an example and Table I 8 for explanation 2 project mlt provides measured link travel times This file is optional If ignored travel times on measured links may be computed from specified link performance function The organization of this file is similar to project obs thus not repeated the only difference is the traffic counts in obs is replaced by measured travel times in mlt 3 project tar provides either historical O D demands or observed O D data This file is optional See Figure I 10 for an example and Table I 9 for a description 4 project ler specifies the error bounds for link traffic observations This file is optional See Table 10 for a description 5 project ter specifies the error bounds f
43. in Section 6 2 Such adjustment is not included in this CHAPTER 6 CASE STUDIES 111 experiment As reported in Figure 6 46 estimated O D matrices at all time intervals shows significant improvements over the target matrices A smaller RMSE implies that these estimated matrices are closer to the true matrices statistically compared to target matrices Unlike the pattern of link RMSE such improvements barely fluctuate across time Further a good portion of the total demand was captured in the estimation process more than 92 in most cases and the value of TDC keeps relatively stable at different time intervals Finally Figure 6 47 shows the change of queue length with time on two selected links As seen the queue appears as temporal demands exceed road capacities in this example starting from time interval 9 These queues are passed to and processed in subsequent time intervals and so we observed the gradual accumulation of queues on the links When demand level drops back the residual queues gradually shrink and at last completely disappear Moreover the evolution of queues on link 307 is reproduced quite accurately by TD LPFE as shown in Figure 6 47 However on link 428 the mismatch between the estimated and true queue evolution pattern is significant This is not surprising since link traffic counts are not perfectly reproduced from the estimation Link RMSE at different time intervals 100 RMSE
44. in traffic counting the inconsistence between steady state assumption and dynamic traffic behavior or an inappropriate path set Algorithm IBA offers a natural way to identify the infeasibility of constraints Note that the multipliers associated with the problematic constrains would be tending to infinity To fix the incorrectness of the path set is relatively easy it can be done by generating more paths or deleting those inappropriate However other causes of infeasibility are much difficult to address Since in reality one may never obtain an input which is fully consistent it is important to have the algorithm tolerate minor constraint inconsistencies Another issue that Algorithm IBA does not address is the violation of slackness conditions like 3 57 Since the constraints are examined sequentially it is CHAPTER 3 LPFE FORMULATION AND ALGORITHM 31 possible that an active constraint becomes inactive when checking other constraints which produces the violation of slackness conditions while the constraint is inactive the corresponding multipliers remain positive We present a revised iterative balancing algorithm RIBA to resolve these problems ALGORITHM RIBA Step 0 Initialization Set 4 0 4 0 47 0 v 0 v 0 K q Step1 Set Ko K Iteratively check constraints and update path flows Step 1 1 Calculate path flow f according to Equation 3 55 Set X Af q Step 1 2 Foreachlink a A compute e Inx
45. it the active cell There are four options to display paths a Toolbar Button Single Path E When the button is clicked the path corresponding to the active row of the Path Table will be highlighted Figure 30 33 fer Paths_SC PFE_Workbook 3_Exercise_3 9GRD pfe ORIGIN DESTIN PATHID PATH_COST PATH_FLOW LINK_ID 45406784282 33 8352695815 5 0137019450 7 4 5969356316 16 1151400089 3 6312836916 60 372969305 4 0263277513 53 4945036560 4 0825849548 25 4784852252 4 6787445923 76 6271966005 5 5407941692 10 30261 50666 5 0143434232 11 3675820269 5 0706006267 5 4141781104 2 5853935222 130 3720190841 2 NFINAPRARA 2NR 1217935543 neon oono nnne e e s w n w n wi n noa ww Nl w N a C PFE_Workbook 3_Exercise_3 9GRD pfe FM 9GRD_0D_BOUNDS a M SGRD_DESIRELINES w M 96RD_0D o 9GRD_NETWORK Figure 30 Display of Single Path b Toolbar Button One to All Paths E When the button is clicked all the paths originating from the origin of the active row of the Path Table will be highlighted Figure 31 34 C PFE_Workbook 3_Exercise_3 9GRD pfe I 9GRD_OD_BOUNDS oa M SGRD_DESIRELINES M 9GRD_OD o M 9GRD_NETWORK Figure 31Display of All Paths c Toolbar Button All to One Paths When the button is clicked all the paths ending at the destination of the active row of the Path Table will be highlighted Figure 32 C PFE_Workbook 3_Exercise_3 9GRD p
46. jv LPFE_EX_T1_SCATTERPLO a jv LPFE_EX_T1_SCATTERPLO hd V LPFE_EX_T1_SCATTERPLO m Figure 5 7 Scatter Plot Window The scatter plot layer can be linked to the network map to identify the link location of a particular scatter plot point 5 2 5 Report Document The LPFE generates a summary report for every successful estimation The estimation report can be viewed via the report document windows form Figure 5 8 The document windows is also a text editor with all the regular text editing functions such as cut copy and paste CHAPTER 5 VISUAL PFE TD 69 Report_ C LPFE Example EST pfe_ex_t1 DEAR sont ses iene nme ener esncionen ences ans ties se estan ns nseionen enssisesne esienial eb nnna AA Selected Parameters Maximum allowed iter 100 Required accuracy 0 001000 Minimum allowed step 0 000100 Allowed line search iter 10 Termination reason Required accuracy achieved Total iteration 10 Accuracy indicator 0 000003 Number of line search 0 Objective value 21411 717056 CPU time consumed 43 65 Figure 5 8 Report Window 5 2 6 Network Editing After examining the results of a LPFE estimation users can change attributes e g the observed flows of a network link and export the data back to the original LPFE data format for another estimation with improved results 5 2 7 Scenario Comparison If multiple estimation runs have been done for a network all of the previous results can be op
47. pfe 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 a O00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 330 00 530 00 300 00 1160 00 C PFE_Workbook 3_Exercise_3 9GRD pfe AN M 9GRD_DESIRELINES Figure 26 Desire Lines from Row Sum or Column Sum x V 9GRD_OD a Z SGRD_NETWORK x 14 If the active cell of the OD table stays on the table total all of the desire lines will be highlighted Figure 27 30 fer O D_SC PFE_Workbook 3_Exercise_3 9GRD pfe 0 00 330 00 530 00 300 00 9GRD_OD_BOUNDS a 9GRD_DESIRELINES fad M 9GRD_OD z V 9GRD_NETWORK vw Figure 27 Desire Lines from Table Total How to Clear the Desire Lines 15 To clear the magenta highlight from the map when the network map window is the active window press the Clear Track Lines button El The button also applies to the magenta highlights on links and paths The OD Table Window in Visual PFE is managed using the software component Spread The table itself is a spreadsheet and can be saved as a Microsoft Excel file 31 How to Save an OD Table as Excel File 16 Make the OD Table window the active window 17 Go to the menu item File Save as Excel 18 The Save File As dialog box will open for users to enter a desired file name for the Excel File Figure 28 fer O D_SC PFE_Workbook 3_Exercise_3 9GRD pfe Save the OD Table Save in e 3_Exercise_3 gt
48. proper equipment for the identification purpose Consequently what is actually available for estimation models is not the O D flow itself but the so called O D split fraction i e proportions of traffic departing from an origin heading towards a certain destination Thus constraints 3 53 and 3 52 should be replaced by what describes such proportional relationship among O D entries Obviously such relationship can be expressed in a linear equation e g Sf 0 However these constraints may pose numerical difficulties in applying algorithms like the iterative balancing algorithm because its right hand side is zero remember lnO has no definition We leave this to further research 3 3 Solution Algorithms We only present algorithms for solving E LPFE and E TD LPFE in this section But the presented algorithm can solve logit assignment problems with minor modifications since the two problems have similar structure above all they are all based on the logit path choice model We will first deal with a sub problem of E LPFE E LPFE SUB which assumes that all paths have been determined and all link travel times are fixed flow independent Then we will relax these assumptions by introducing a column generation procedure and a decent direction Finally we tackle the time dependent case CHAPTER 3 LPFE FORMULATION AND ALGORITHM 28 3 3 1 Solve E LPFE SUB When all used paths and link travel times are known we obtain a sub problem of
49. table structure file optional 43 e Path specific file optional The three input files must be in the dBase data format dbf The first input file is mandatory while the other two files are optional If the structure of trip table i e the second file is not provided it will be determined through topology of the network That is all feasible connected pairs of origin and destination will be included Similarly if there is no specific path to be included the path list in the third PFE network file pfp will be empty How to Prepare the Input dBase Data 1 Use a spreadsheet Excel to open the network topology file 9GRD dbf the trip table structure table 9GRDOD dbf and the user specified paths 9GRD_Path dbf files in the folder PFE_workbook 2_Exercise_2 Examine the structure of the input data tables Figure 40 EJ Microsoft Excel 9GRD dbf DAR Type a question for help o AEE A a AX LNGTH BETA OBS_FLW 143 678615 59 922371 143 658615 59 922371 2 00 4 00 1 00 143 678615 59 922371 143 678615 59 902371 1 50 4 00 1 00 143 678615 59 922371 143 658615 59 902371 3 00 4 00 1 00 143 656615 59 922371 143 638615 59 922371 1 00 4 00 1 00 143 658615 59 922371 143 658615 59 902371 1 00 4 00 1 00 143 678615 59 902371 143 658615 59 902371 2 00 4 00 1 00 143 678615 59 902371 143 678615 59 882371 1 00 4 00 1 00 143 638615 59 902371 143 638615 59 882371 1 00 4 00 1 00 143 658615 59 882371 1
50. that in logit assignment models path flows are so chosen that conservative conditions hold for each O D pair whereas in LPFE the selected path flows have to reproduce observed link flows 3 2 1 The static case Note that in reality only a subset of link flows can be measured The observed and unobserved link set are denoted as Ao and Au respectively with A Au Am Traffic counts are only available on links in Am For any link a A the free flow link travel time and the link capacity are assumed to be known Corresponding to the partition of link set the vector of link capacities C can be divided into Co and Cu Further path link incident matrix A can be divided into A and Au The logit path flow estimator is formulated as a mathematical program as follows LPFE in f c Lif nf 1 min f c as 3 28 subject to CHAPTER 3 LPFE FORMULATION AND ALGORITHM 21 Aof Xo 3 29 where Xo is a vector of observed link flows The KKT conditions of LPFE are L inf e Ay pH AoA 0 0 3 31 Cy Af gt 0 Ban u Cu Auf 0 3 33 H20 3 34 Ake oe 3 35 Again the multipliers associated with capacity constraints H can be interpreted as the equilibrium queuing delay Moreover the optimality condition 3 31 yields to the logit path choice Model 3 5 However 7 is defined differently using multipliers TS rs rs rs Tk ta ak j Ha Og k gt Aao a k a Au ao 3 36 3 2 2 The time depe
51. to the text file Cut Cut selected texts and place the content on the system clipboard Copy Copy selected texts and place the content on the system clipboard Paste Paste the texts contained on the system clipboard Select All Select all texts in the text file O0o000 0 e View Control the navigation functions of a map window o Zoom In Zoom in o Zoom Out Zoom out o Pan o Full Scale e Table Control functions related to the table window o Open Path Table Open the path table pertaining to a PFE estimation o Open OD Table Open the path table pertaining to a PFE estimation o OD Table Color Adjust the individual colors of an OD table e Estimate Open the LPFE time dependent estimation GUI e Diagnose Control functions designed to diagnose results of PFE estimation o Statistics Open the summary statistics of a PFE estimation with a text document window o Graphs Open a scatter plot observed vs estimated link flow window of a PFE estimation o Create Shapefiles Create shapefiles from previously estimated LPFE results e g est o Compares Open multiple MDI child forms pertaining to results of multiple PFE estimation runs from different input sets e Windows Organize opened MDI child windows o Cascade Cascade MDI child forms o Tile Tile MDI child forms e Help Provide users with help to Visual PFE o Visual PFE TD Help Open the Visual PFE Windows HTML help file o About Visual PFE TD Open th
52. vector capConLink a vector of pointers of TNM_SLINK defined in TNM objects associated with constraint 4 3 vector conDest a vector of pointers of TNM_SDEST defined in TNM objects associated with constraint 4 2 or 4 5 Constructor void TNM_MPEN theta default constructor Return none double theta the dispersion parameter 0 Attributes double GetTheta Get the dispersion parameter 0 CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 48 Return 0 Operations double updateFlowPattern link shift Update path and link flows based on the change of a multiplier made when checking a constraint associated with a link shifted flows ENUM link a pointer of a TNM_SLINK a static link class defined in TNM object double shift the change of the multiplier at the current iteration double UpdateFlowPattern od shift Update path and link flows based on the change of a multiplier made when checking a constraint associated with an OD pair Return shifted flows ENUM oda pointer of a TNM_SDESTV a static O D class defined in TNM object double shift the change of the multiplier at the current iteration double GetODIEMuChange od Compute the required change of a multiplier associated with a constraint of O D measurement Return the change of the multiplier ENUM oda pointer of a TNM_SDEST object int SetTheta theta Set the dispersion parameter 9 Return 0 if succeeds non zero value otherwi
53. 00 600 00 RMSE of the measured link flows veh hr Figure 6 37 RMSE_Links for scenarios with different link flow errors Figure 6 35 shows that TDC is not very sensitive to measurement errors of link flows For all scenarios the TDCs range between 95 to 105 Figures 6 36 and 6 37 show that both RMSE OD and RMSE Link increase as measurement errors in link counts increase However the RMSEs of estimated O D flows in all scenarios are still lower than that of the historical O D table illustrating the robustness of LPFE in the presence of significant link measurement errors In summary LPFE seems to be more sensitive to the link flow errors When the CHAPTER 6 CASE STUDIES 104 input of link flows contain significant errors LPFE may still capture the total demand well but often fails to estimate O D flows accurately Thus it is important to minimize link measurement errors in real applications Fortunately in practice it is much easier to obtain reasonably accurate link flow data than to obtain accurate historical O D data 6 6 Considering Measurement Errors in LPFE As shown in Chapter 2 LPFE is able to explicitly consider measurement errors of inputs by replacing the equality constraints with two sets of inequality constraints which enlarges the feasible region such that it contains the true solution This section will test whether or not this strategy helps provide a better solution 6 6 1 Considering errors of the base
54. 000 0 18750 0 06250 0 25000 0 25000 0 18750 0 06250 2 75000 2 75000 2 06250 0 68750 Figure I 7 An example of the file project dmd APPENDIX I 9 3 Algorithm parameter file project alg This input is optional If ignored default values will be used Changing parameters in this file may significantly affect the computation results To obtain a better converged solution sometimes users may find the estimated link flows do not perfectly match observed values or estimated O D flows do not match target O D flows In these case the solution is considered as not well converged a general resolution is to increase maximum allowed iterations but in general no more 1 000 reduce accuracy increase maximum allowed bad iterations increase maximum allowed zigzagging iterations or reducing zigzagging criterion Note that the running time may grow up quickly as the above adjustments are made for large networks Figure I 8 shows an example of the project alg file Maximum allowed iterations 1 1000000 100 Accuracy 1e 016 1 0 001 Minimum allowed stepsize gt 1le 009 0 0001 Desirable Line search accuracy le 009 1 0 001 Maximum allowed line search per iteration 1 1000 10 Maximum allowed bad iterations 1 1000 5 Zigzagging criterion le 016 1 0 01 Maximum allowed zigzagging iterations 1 1000 5 Figure I 8 An example of the file project alg I 2 Input files
55. 172 176 182 122 126 130 134 138 142 147 203 844 226 229 14 06 0 49 0 28 841 14 60 65122 126 130 134 138 143 844 226 229 14 06 0 64 0 32 841 56 60 65122 126 130 134 138 142 147 203 844 226 229 14 06 0 92 0 32 841 13 17 65122126 130 134 138 142 147 203 844 226 229 14 06 0 83 0 33 841 14 60 65122 126 130 134 138 142 147 203 844 226 231 6 56 1 05 0 22 841 56 60 64 70 19 22 25846 226 231 6 56 1 53 0 18 841 13 16 19 22 25846 226 231 6 56 1 42 0 23 841 13 16 20 68 74 22 25846 226 231 6 56 0 98 0 23 841 56 60 64 68 74 22 25846 226 231 6 56 1 27 0 24 841 10 14 60 64 68 74 22 25846 233 6 56 0 26 0 34 841 45 103 161 218 223 281 339 397 455 513 570 574 579 637 695 752 848 233 6 56 0 66 0 39 841 45103 161 219 277 335 393 450 455 513 570 574 579 637 694 699 848 gt gt 1 2 3 4 5 6 7 8 3 N OF M 0 Ol amp w N N N N _ _ N _ N N N N Figure 19 Path Table Window To open a path table when the corresponding network map is the active window go to the menu item Tables Open Path Table Display Paths If users want to see the location of a particular path or paths the Display Path toolbar buttons can be used To use this function when the network map and the path table windows are both opened click at a cell in the path table to make it the active cell There are four options to display paths e Toolbar Button Single Path When the button is clicked the path corresponding to the ac
56. 43 638615 59 882371 i 1 00 i 4 00 1 00 143 638615 59 922371 143 638615 59 902371 2 00 4 00 77 00 143 658615 59 902371 143 638615 59 902371 1 50 4 00 303 00 143 658615 59 902371 143 658615 59 882371 1 00 4 00 400 00 143 658615 59 902371 143 638615 59 882371 2 00 4 00 85 00 143 678615 59 882371 143 658615 59 882371 1 00 4 00 295 00 A 1 1 al 2 2 3 3 4 5 alaaa ONNN gt 44 EJ Microsoft Excel 9GRDOD dbf Type a question for help X Figure 40 Input dBase Data Remark Here it is assumed that the target O D volumes are unknown so put 1 00 minus one as the target value Only the structure of O D trip table to be estimated as shown in Table 1 is known EJ Microsoft Excel 9GRD_Path dbf iba File Edit View Insert Format Tools Data Window Help Adobe PDF Type a question for help f X ae r EME MA E S REE E Fad 9 S50 508 Number of nodes defining path AEL M 4 gt M 9GRD_Path Figure 41 Input Path Data Remark Here it is assumed that there are two paths that the user may particularly want to include into the estimation The first path traverses nodes 1 2 11 4 while the second path traverses nodes 1 3 13 5 6 see Figure 41 and Figure 42 45 Path 2 Figure 42 Paths in 9GRD Network How to Create a PFE Network 2 Close the files and the spreadsheet once you are done reviewing them Open Visual PFE go to the menu item Netwo
57. 5 4 00 467 0000000000 0 00 38 1500 00 1 00 2 00 0 15 4 00 212 0000000000 0 00 391 400 00 1 00 1 00 0 15 4 00 295 0000000000 0 00 461 300 00 1 00 1 00 0 15 4 00 50 0000000000 0 00 56 1 220 00 1 00 1 00 0 15 4 00 165 0000000000 0 00 7 4 1 300 00 1 00 2 00 0 15 4 00 77 0000000000 0 00 8 4 1500 00 1 00 1 50 0 15 4 00 303 0000000000 0 00 861 700 00 1 00 1 00 0 15 4 00 400 0000000000 0 00 8 6 1 250 00 1 00 2 00 0 15 4 00 85 0000000000 0 00 96 1350 00 1 00 1 00 0 15 4 00 295 0000000000 0 00 Figure 35 File Open Text 3 Go to the menu item Edit and try all of the common text editing functions Undo Cut Copy Paste and Select All 4 When you are done with editing go to the menu item File Save Text Figure 36 38 C PFE_Workbook 3_Exercise_3 9GRD pfe g 13 1 143 678615 59 922371 4 52 143 658615 59 922371 Save in 3 Erxercise_3 Result E 9GRD pfe My Recent E HYNG pfe Documents is IRWN pfe 121 280 00 E 13 1290 00 181280 00 Desktop 27 1 280 00 281 600 00 2 38 1500 00 391 400 00 46 1300 00 56 1220 00 7 41300 00 My Computer 8 4 1500 00 85 1700 00 86 1250 00 951350 00 MyNetwork File name Places Save as type PFE Network files pfe 7 My Documents Figure 36 File Save Text Remarks An input PFE network consists of three files pfe pfp and pfx Editing the network data as text files requires a thorough understanding of the data structure of all three files The
58. 9 A ea ee ea sa T 10 79 A SUM 164 80 173 87 133 04 138 23 185 35 280 00 207 33 188 78 288 50 142 57 198 82 127 11 155 31 162 73 166 62 200 2 Figure 5 5 OD Table Window For each cell in the OD table the locations of the origin and destination and the magnitude of the OD flow can be graphically presented over the network map by initiating a dynamic linkage between the OD table and the desire line layer That is by highlighting a particular cell in the OD table the desire line of that OD pair can be plotted over the network map with a band that varies by the magnitude of the OD flow see Figure 5 5 The path table is also implemented as a spreadsheet Figure 5 6 A dynamic linkage exists between a path table and the corresponding network layer The location of a path can be identified and highlighted over the network map by selecting a path in the Path table and initiating the dynamic linkage to the map CHAPTER 5 VISUAL PFE TD 67 fi Paths _SC LPFE Example EST pfe_ex_t1 Origin Dest Demand PathID Flow Cost LinkSet 226 229 14 06 1 07 0 34 841 226 229 14 06 038 0 3 841 226 229 14 06 091 0 26 841 226 229 14 06 0 66 0 35 841 226 229 14 06 0 49 0 28 841 226 229 14 06 0 64 0 32 841 226 229 14 06 0 92 0 32 841 226 229 14 06 0 83 0 33 841 231 6 56 1 05 0 22 841 231 6 56 1 53 0 18 841 231 6 56 1 42 0 23 841 231 6 56 098 0 23 841 231 6 56 1 27 0 24 841 233 6 56 0 26 0 34 841 233 6 56 0 66 0 39 841 K LI M N O P Q
59. CALIFORNIA PATH PROGRAM INSTITUTE OF TRANSPORTATION STUDIES UNIVERSITY OF CALIFORNIA BERKELEY Development of A Path Flow Estimator for Inferring Steady State and Time Dependent Origin Destination Trip Matrices Michael Zhang Yu Nie Wei Shen Ming S Lee Sarawut Jansuwan Piya Chootinan Surachet Pravinvongvuth Anthony Chen Will W Recker California PATH Research Report UCB ITS PRR 2008 10 This work was performed as part of the California PATH Program of the University of California in cooperation with the State of California Business Transportation and Housing Agency Department of Transportation and the United States Department of Transportation Federal Highway Administration The contents of this report reflect the views of the authors who are responsible for the facts and the accuracy of the data presented herein The contents do not necessarily reflect the official views or policies of the State of California This report does not constitute a standard specification or regulation Final Report for Task Order 5502 June 2008 ISSN 1055 1425 CALIFORNIA PARTNERS FOR ADVANCED TRANSIT AND HIGHWAYS Development of A Path Flow Estimator for Inferring Steady State and Time Dependent Origin Destination Trip Matrices Michael Zhang Yu Nie and Wei Shen Department of Civil amp Environmental Engineering University of California Davis Ming S Lee Sarawut Jansuwan Piya Chootinan Surachet Pravinvongvuth and Anthony Che
60. Copy e Paste e Select All 3 View e Zoom In e Zoom Out Figure 22 Windows Help 30 Technical Specification Visual PFE TD integrates the LPFE program with three other software components The architecture of the system is shown in Figure 23 Display and query Data MapObjects Management Visual PFE TD VB NET application LPFE ESRI Spreadsheets I Shapefiles H LPFE raw outputs text files x Table Creator Map File Creator Spread ArcViewShapeFile Spread aS p Figure 23 Visual PFE TD Software Components The three software components are e ArcViewShapeFile OCX e ESRI MapObjects e FarPoint Spread 31 LPFE The LPFE program operates via the DOS command prompt If an estimation run is successfully the output files generated by the LPFE are in text files If an estimation run encounters errors due to incompatible parameter setting the LPFE program will quit and error messages will be issued by Visual PFE TD The ArcViewShapefile Read Write OCX An OCX is an object oriented software component conforming to Microsoft s ActiveX architecture The OCX was created to easily read or write Arcview Shapefiles for data conversion purposes The Shapefile format is a geographic data format published by ESRI The ArcViewShapefile Read Write OCX was created by Ross Pickard in Wellington New Zealand and is a shareware made ava
61. ETNM_MPEN Constructor void TNM_LPFE theta default constructor in which costCoef is set to 1 0 Return none double theta the dispersion parameter 0 CLASS LPFE_RQ PARENT CLASS TNM_LPFE Constructor void LPFE_RQ theta default constructor in which costCoef is set to 1 0 Return none double theta the dispersion parameter 0 CLASS LPFE_RQ MSA PARENT CLASS LPFE_RQ Constructor void LPFE_RQ_ MSA theta default constructor in which costCoef is set to 1 0 CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 51 Return none double theta the dispersion parameter 0 CLASS LPFE_RQ_IBA PARENT CLASS LPFE_RQ Constructor void MPEN_DC_MC theta default constructor in which costCoef is set to 1 0 Return none double theta the dispersion parameter 0 CLASS TNM_LTAP PARENT CLASS MPEN_DC Constructor void TNM_LTAP theta default constructor in which costCoef is set to 1 0 Return none double theta the dispersion parameter 0 CLASS LTAP_RQ PARENT CLASS TNM_LTAP Constructor void LTAP_RQ default constructor in which costCoef is set to 1 0 Return none double theta the dispersion parameter 0 CLASS LTAP_RQ MSA PARENT CLASS LTAP_RQ Constructor CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 52 voidLTAP_RQ MSA theta default constructor in which costCoef is set to 1 0 Return none double theta the dispersion parameter 0 CLASS LTAP_RQ IBA PARENT CLASS LTA
62. EXCUTIVE SUMMARY This final report documents the research effort for extending and implementing the time dependent Logit Path Flow Estimator TD LPFE and its software product Visual PFE TD TD LPFE estimates time dependent O D trip matrices from traffic counts and historical O D matrices and Visual PFE TD provides a user friendly input output interface to visualize analyze and present the estimated trip tables and related statistics from TD LPFE In this research we have 1 extended the LPFE to include measurement errors and historical O D information 2 developed efficient object oriented C codes for the TD LPFE algorithm 3 investigated the effects of algorithm parameters measurement errors prior O D information and network topology on the performance of LPFE and TD LPFE 4 developed a user friendly graphical user interface for LPFE and TD LPFE 5 prepared a user manual and workbook for the developed software tool The developed software tool can easily estimate O D trip tables of large networks in a reasonable amount of time in the order of minutes and with Visual PFE TD the data preparation and results analysis times can also be significantly reduced The tool is most useful for planners and traffic engineers who deal with large networks with a coarse time resolution greater than 15 minutes because of the way TD LPFE models traffic flow it assumes trips complete within one time interval This is also the main reason making TD LP
63. FE computationally so efficient The outputs from this tool may not be appropriate for high resolution simulation studies that require a time resolution less than 15 minutes One can however combine this tool with O D estimation tools that often come with the high fidelity simulation software such as the O D estimator in Paramics to yield O D trip tables with a higher time resolution Our experience indicates that with a seed O D provided by TD LPFE Paramics s O D estimator can obtain a good O D trip table s in a much shorter time than with a seed O D obtained from a planning model The above limitation of TD LPFE can only be removed through the incorporation of a finer traffic flow model that tracks the growth and decay of vehicular queues in a more realistic manner But this would require a full blown dynamic network loading model that destroys the simple modeling structure of LPFE which could considerably increase the computational complexity of the estimation problem Nevertheless such an approach is worth investigating because it can provide higher resolution trip matrices e g O D trip tables in every minute that can directly be used in micro simulation studies Where to make traffic measurements and how many locations to make them are also important topics that need to be addressed in future O D estimation research Our investigation indicates that if chosen properly a small set of measurements can produce as good O D demand esti
64. FEWJCT 5280 5280 FWJCT 10560 5280 3 FWJCT 15840 5280 FWICT 21120 528 5 FWJCT 26400 528 6 FWJCT 31680 528 FWJCT 36960 528 8 FWJCT 42240 528 9 0 1 3 FWICT 47520 528 FWJCT 52800 528 FWJICT 5280 10560 FWIJCT 10560 10560 FWIJCT 15840 10560 O O O gt GOG DO DO 2 4 7 2 Figure I 5 An example of the file project nod APPENDIX I 7 Table I 6 The description of the file project odp Range P Type Description The file contains N 1 row Field 1 Text Prompt identical blocks Field 2 Integer ID of origin Node each describes O D Field 3 Integer Number of O D pairs associated pairs associated with this origin with an origin Multiple rows Field 1 Integer ID of destination node Field 2 Integer Number of time intervals Field 3 Float Demand for this O D pair Origin 101 14 104 6 5 0000 106 6 6 0000 108 6 5 0000 110 6 6 0000 12 6 3 0000 14 6 1 0000 16 6 6 0000 18 6 6 0000 120 6 9 0000 122 6 10 0000 124 6 9 0000 126 6 5 0000 128 6 1 0000 130 6 1 0000 Origin 103 14 02 6 0000 L06 6 19 0000 108 6 15 0000 10 6 19 0000 12 6 11 0000 14 6 3 0000 Figure I 6 An example of the file project odp APPENDIX I 2 Time dependent demand files project dmd Figure I 7 provides an example while Table I 7 explains how to read it Block 1 There are multiple ___ Range Fields Type _ Description identical blocks after the fir
65. Field 1 Integer Number of O D pairs c Field 2 Integer Number of time intervals There are multiple Row 1 Field 1 Integer Origin node ID identical blocks after Field 2 Integer Destination node ID the first block each Row2 Multiple Float Each field i corresponds to the target corresponds to an fields observed O D flow at the time interval i O D pair They can be put in more than one rows 210 6 Block 1 101 104 3 75 11 25 15 15 41 85 S96 Pee escoreae 101 106 diwth O D pair 4 5 13 5 18 18 13 5 ag Whom 10A 101 108 3 75 11 25 15 15 11 25 3 75 101 110 4 5 13 5 18 18 13 5 4 5 101 112 2 25 6 75 9 9 6 75 2 25 101 114 0 75 2 25 3 3 2 25 0 75 101 116 4 5 13 5 18 18 13 5 4 5 Figure I 10 An example of the file project tar Table I 10 A description of the file project ler r Type Description SI Block 1 1 row Field 1 Text Type of link error bound Field 1 Text either HOMO or HETE Block 2 1 row Field 1 Float Homogeneous Error bound HOMO stands for homogeneous error bound that is all links have a same error bound HETE stands for heterogeneous meaning that each link has different error bound The current version does not support HETE error bound Appendix II Visual PFE TD Time Dependent Visual PFE TD 1 0 User Manual June 2006 Visual PFE and Visual PFE TD are authored at the Utah State University Copyright application for Visual PFE and Visual PFE TD is currently in proces
66. GRD_ NETWORK layer will make the layer invisible Checking the legend of the 9GRD_DESIRELINES will make the desire lines visible Once you see how this work return the map to the original setting make desire lines invisible and the network links visible Figure 8 10 C PFE_Workbook 3_Exercise_3 9GRD pfe M 9GRD_OD_BOUNDS a M SGRD_DESIRELINES d M 9GRD_OD o SGRD_NETWORK C PFE_Workbook 3_Exercise_3 9GRD pfe 9GRD_OD_BOUNDS a V 9GRD_DESIRELINES rad M 9GRD_OD a SGRD_NETWORK al Figure 8 Invisible Visible Layer 11 How to Increase the Legend Width 4 Sometimes you may have a map layer with a long file name that does not fit in the initial legend width You can increase the width of the legend by clicking at the border bar between the legend and the map the mouse cursor will turn into a east west double arrow Moving the border bar while holding the mouse button will move the border bar to the desired direction Figure 9 C PFE_Workbook 3_Exercise_3 9GRD pfe I SGRD_OD_8C o SGRD_DESIR yw SGRD_OD D W 9GRD_NETW nw C PFE_Workbook 3_Exercise_3 9GRD pfe M SGRD_OD_BOUNDS E M SGRD_DESIRELINES Ww 3GRD_00 a SGRD_NETWORK w Figure 9 Increase of Legend Width 12 How to Navigate through the Network Map Zoom In Zoom Out Pan Full Scale and Identify Features 5 Click at the toolbar button Zoom In e Click at a point on the map where you want
67. InC If e gt 0 set Ha Ha Ge otherwise if H gt O set Ha Hate Update f and if x lt lel set K lel Step 1 3 Foreachlink a Ao compute hna nxa 1 7a If e gt 0 set AZ AZ ae otherwise if AZ gt 0O set AG Ai e Update f and q if x lt lel set x lel Step 1 4 Foreachlink a Ao compute Inx n a l a If e lt 0 set AZ AZ ae otherwise if Az gt 0 set AG Az e Update f and q if K lt lel set x lel Step 1 5 For each O D pair rs for which the target O D information exists Compute e Ing ng 1 ms If e gt O set vi vi ae otherwise if vi gt 0 set vi Vi te Update f and q If x lt lel set K lel Step 1 6 For each O D pair rs for which the target O D information exists Compute hng ng 1 Prs If e lt 0 set V Vj ae otherwise if Vy gt 0 set Vii Vy e Update f and q If x lt lel set K lel Step 2 Convergence test Step 2 1 If K a lt stop otherwise go to Step2 2 1 0 Mf CHAPTER 3 LPFE FORMULATION AND ALGORITHM 32 Step 2 2 If I x Ko Kolx set a return to Step Note that is the step size while is a positive scalar smaller than 1 is set as 1 at the beginning then reduced by applying whenever the two consecutive iterations do not lead to sufficient decrease of K the convergence indicator Further when the violatio
68. MSE_Links for different sets of measurements much smaller number of counting locations than what would be available CHAPTER 6 CASE STUDIES 94 Three out of the five scenarios i e scenarios with input set of all measured links freeway links and centroid connectors amp freeway links replicate the link flows quite well with RMSE Link no greater than 10veh h However the RMSE ODs for all the scenarios are rather high compared to the average O D flows 152velvhr This is again due to the existence of multiple path solutions corresponding to an observed link flow pattern Moreover the scenario of efficient links which originally designed to capture spatial structure of the demand to some extent perform the worst instead of the best in terms of RMSE ODs To summarize the scenario with input set of all measured links and the scenario with input set of centroid connectors amp freeway links seem to outperform the other three when all the MOEs are taken into account 6 4 2 The effects of historical O D flows 50 In this section we introduce historical observed O D data into inputs to improve the quality of estimates The historical O D trip table is generated by randomly introducing a perturbation with bounds 50 50 to each O D pair RMSE_OD between this historical O D trip table and the true O D trip table is 110 41 veb hr For comparison purpose the same O D trip table is used in combination with all the five link se
69. O D estimation process thus the estimated flow pattern is not necessarily consistent with the network state that yielded the observed travel times Compared with existing dynamic O D estimation methods Bell s time dependent LPFE TDLPFE seems much more tractable because it transforms the dynamic problem into static problems TDLPFE is not a true dynamic model in the sense that all trips are assumed to complete within each time interval However the transition of queues across time periods makes it capable of capturing the queuing phenomenon one of the most important characteristics of dynamic traffic The research approach described in the following chapters thus use LPFE to develop a software tool for deriving both steady state and time dependent O D trip tables to support various applications CHAPTER 3 LPFE FORMULATION AND ALGORITHM 15 Chapter 3 LPFE Formulation and Algorithm The O D estimation problem is closely interrelated with the traffic assignment problem since outputs of one problem serve as inputs to the other Thus we shall first review the corresponding traffic assignment model before turning to logit path flow estimator 3 1 Logit Traffic Assignment Model Static traffic assignment models based on Wardrop s principles 1952 can be classified into deterministic and stochastic ones The latter recognizes that travellers are unlikely to have perfect information about network conditions and stipulates that travele
70. ORITHM 37 Note that RIBATD and RIBA are very similar ignoring the time index f in RIBATD except in Step0 and Step 2 In Step0 the queue in the current time period is initialized according to the queue left over from the last time interval If the residual queue exceeds the capacity the initial value of v should be such set that s in Step 2 is always positive Proposition 3 3 Assuming that link travel times are fixed and the matrix A is given for each time interval t algorithm RIBATD converges to the optimal solution of E TD LPFE provided a feasible solution exists Proof the arguments used in the proof of Proposition 3 1 can be applied here in general We only need to show that the adjustment made in Step 2 of RIBATD ensures the increase of the Lagrangian First note that Int In Ca va va is an over adjustment because it would make the adjusted link flow X a Ca va vi However since v4 is increased accordingly the constraint is inactive after the adjustment The desirable update thus should be ui ui n Cy vi ve 3 76 where v4 denotes the queue length after the adjustment However it is not easy to t directly determine 44 since u4 and v4 are mutually dependent The difficulty can be overcome by making use of the concaveness of the log function Note that the following inequality holds va va In Ca v4 vi lt In Ca v4 v an Ca v vi Thus
71. P_RQ Constructor void LTAP_RQ MSA theta default constructor in which costCoef is set to 1 0 Return none double theta the dispersion parameter 0 CLASS LOGWRAP_RMP PARENT CLASS TNM_IA Data Members bool isRQ consider residual queue in the formulation or not bool isAsn consider assignment or O D estimation bool isMsLinkTime consider measured link travel times or not Constructor void LOGWRAP_RMP ntt at t default constructor Return none ENUM mt the type of sub problem ENUM at the type of solution algorithm only applies to the time dependent case double t dispersion parameter Attributes bool GetAsn Check the type of its subproblemtrue if the sub problem is an assignment model bool GetRQ Check the type of its subproblemtrue if the CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 53 sub problem considers residual queues bool IsMsLinkTime Check whether or not measured link times are considered Return a boolean value CLASS TNM_LOGWRAP PARENT CLASS TNM_IA Data Members bool pathEnum whether or not enumerate all paths int initPath the number of shortest paths required to generate for each O D pair in initialization int genPath the number of shortest paths required to generate in each iteration int pathNum the total number of paths generated so far Constructor void TNM_LOGWRAP nt at t ep default constructor Return none ENUM mt the type of s
72. RD_SCATTERPLOT_AXIE Number of paths generated 19 wv f T Total Demand Estimate 1160 0000 RMSE of link flows estimates 0 0030 a ere RMSE of O D flow estimates NA Number of unobserved O D pairs a 1160 0000 1160 0000 0 0000 gp 18 75 Obppsved 95025 K PFE_Workbook 3_Exercise_3 9GRD pfe Cory O D_SK PFE_Workbook 3_Exercise_3 9GRD pfe 9GRD_OD_BOUNDS a I S9GRD_DESIRELINES Ww W 9GRD_OD a 0 00 7 SGRD_NETWORK J T 0 00 w g i 0 00 330 00 530 00 300 001160 00 Figure 5 The Scatter Plot and the Estimation Report By now you have completed the estimation process for the given 9GRD network All of the output components are generated and displayed in corresponding windows After reviewing the notes about PFE parameters you will learn functions of each individual output window in the next examples What are the Static PFE Estimation Parameters In order to perform the estimation using the static PFE five input parameters are required 1 2 Network name of the main PFE network file pfe including full path of the directory simply browse for location of the file Dispersion parameter cost sensitivity in the logit SUE model It indicates how sensitive the road users are to the travel cost A small value of dispersion parameter e g between 0 01 and 1 00 is usually recommended to prevent the numerical problem of the algorithm It is however important to calibrate this parameter to properly reflec
73. S 50 c ccecccccsesesssesseeeseseseseeseeesesesesees 94 6 5 The effects of Measurement Errors i cecciteseseces nvaseisece i eterienencenetinesineeeuiea 96 6 5 1 Measurement errors Of O D flOWS wo cee cee ceeccesceecceecceesccececcceseesseceseeeeesees 96 6 5 2 Measurement errors Of link fIOWS eee eeceecccecceecceecccecececceecccseccescceseeeeeeees 101 6 6 Considering Measurement Errors in LPFE 0 eeecceeeseceeeeececeeeeeeseeeeeneeeeaes 104 6 6 1 Considering errors of the base O D table occ ccceeseseseeseseceseseeeeeeeeeees 104 6 6 2 Considering errors of link measurements ee eeeeeeseseseseeecececeseeeeeeeeeeeees 107 6 7 Th time dependent CASE cies neen Regen a e EE EE EEE i 109 Chapter 7 COMCHUISIONS sivsssedsvcadascccdesseecvesceccdvess tesebeidactevdsisddevesssvaccespatcedeecs deuedsigetesasasens 113 7 1 Major Findings Regarding the Performance of LPFE uw eee eeeeeeeeeeeeeee 113 1 2 F t re W OLK iinis esate aesae asiaa area 114 Bibliography a5 sic ns iad oacclnn evi bak pach vain reias eea ire Sa EE EEEn OH e ereis eere iias 116 Appendix I File formats Appendix II Visual PFE TD 1 0 User Manual Appendix III Visual PFE 1 0 A Quick Start Tutorial LIST OF TABLES Table 4 1 A guideline for the selection of algorithm Objects eescecseeeceereeeeteeeeeeees 59 Table 5 1 LPFE Output Text Files to Shapefiles 0 0 0 cee ceescecsenceceeceeceeececeeeeecseeeeesaeees 12 Table 5 2 LPFE Output F
74. ST For more details see Technical Specification C LPFE Example ES T lpfe_ex_t1 M LPFE_EX_T1_OD_BOUNDS C LPFE_EX_T1_DL PLE x TIo I Iv E H fad CCCP E E Figure 10 Network Map Window A network map consists of four ESRI Shapefiles each presented as a map layer e Network links All of the link attributes are stored in this layer including the observed and estimated link flows e Origins and destinations The production and attraction of the origins and destinations are stored in this point layer e Desire lines A desire line represents the flow between a pair of OD The desire lines layer is hidden by default Users can choose to display or hide them e Map boundary points Two boundary points are included in the network map to create sufficient margins around the network such that all features of the network can be displayed within the map window 16 The Network Windows form is divided into the map and the legend areas The names of the layers are displayed in the legend area Note that a layer name is made up by prefixing the name of the estimation result e g Ipfe_ex_tl with one of the words Network OD DL and OD_BOUNDS See Technical Specification for details Basic functions of the map window are adjusted through the map legend Setting the active layer A layer can be made active by moving mouse cursor over and clicking at the corresponding title in the map legend The legend of the active layer has a
75. TDANET2 Output File Name EXAMPLE est danet Retain iteration history 1 Record link detail Record path detail Record path topology 1 Speed flow function BPRLK dispersion parameter 0 1 cost scalar 1 algorithme type IBA Time dependent 1 Enumerate all paths 0 Allow residual queue 1 Create an estimation scenario 1 Consider target O D demands 1 Consider link observation errors 1 Consider target O D errors 1 Figure 4 3 A example Ipfe par file CHAPTER 5 VISUAL PFE TD 61 Chapter 5 Visual PFE TD A GIS Based Decision Support System for Time Dependent Origin Destination Trip Table Estimation 5 1 What is Visual PFE TD Visual PFE TD is a special edition of Visual PFE an integrated software suite that combines the Path Flow Estimator PFE with other software components to facilitate the estimation visualization and refinement of Origin Destination OD trip tables with user friendly Graphical User Interfaces GUI We have already discussed the detailed algorithmic implementations of the Logit Path Flow Estimator LPFE and its console interface in Chapter 4 which operates under the DOS command prompt with no GUIs and no graphical presentation of the output data To expand the capability of LPFE this special edition of Visual PFE is created to integrate LPFE with components of Visual PFE With Visual PFE TD users can Run LPFE with GUIs Conver
76. _ODs for different link sets with and without historical O D data 95 Figure 6 31 RMSE _Links for different link sets with and without historical O D data 95 Figure 6 32 TDCs for scenarios with different historical O D flow errors s es 98 Figure 6 33 RMSE _ODs for scenarios with different historical O D flow errors 99 Figure 6 34 RMSE Links for scenarios with different historical O D flow errors 100 Figure 6 35 TDCs for scenarios with different link flow errors 0 0 0 eee eeteeeeeeeeees 102 Figure 6 36 RMSE _ODs for scenarios with different link flow errors eee 103 Figure 6 37 RMSE_Links for scenarios with different link flow errors eeeeeeeee 103 Figure 6 38 TDCs for scenarios with different settings eee eeseeeeeceeeeeereeeeaeenteeeees 105 Figure 6 39 RMSE _ODs for scenarios with different settings cee eeeeeeseesteceeeeeees 106 Figure 6 40 RMSE _ Links for scenarios with different settings 0 0 0 0 cesses esseeeteeeees 107 Figure 6 41 TDCs for scenarios with different settings eee eeecseeceeeeereeenneeneeeees 108 Figure 6 42 RMSE _ODs for scenarios with different settings cee eeeeeeseeeneceteeeees 108 Figure 6 43 RMSE _ Links for scenarios with different settings 0 0 0 cee eeeeesseeeeeeeeee 109 Figure 6 44 A time dependent demand pattern eeecceesseceeneeceeeeceeneeceeeeeeenteeeesaes 110 Figure 6 45 RMSE_Links at different time intervals eee ceeeceeeeeeeece
77. abel Features CALPFE Example EST ipfe_ex_tt Ipfe_ex_tl_network Labels are based on field ID v farias o ooo l e oo aw toe Figure 13 Label Features 17 C PFE_Workbook 3_Exercise_3 9GRD pfe 9GRD_OD_BOUNDS I SGRD_DESIRELINES wv MV IGRD_OD a MV SGRD_NETWORK Figure 14 Label of Link ID How to Clear Labels 5 To clear the labels press the Clear Postings button E The function applies to all three types of postings Remarks When a scatter plot shows up the scatter plot axis layer and the marker layer are already labeled with the appropriate labels Press down the Clear Postings button will clear these labels as well To restore the original setting just label the axis layer with the attribute NAME and the marker layer with VALLUE again After a particular posting is cleared from a map the legend is reset To place another posting you need to remember to set the active layer again Figure 15 18 Scatter Plot_SC PFE_Workbook 3_Exercise_3 9GRD pfe MV SGRD_SCATTERPLOT_MARKER SH a M SGRD_SCATTERPLOT_AXIS SHP MV 9GRD_SCATTERPLOT m Figure 15 Scatter Plot Axis Layer How to Create a Class Map 6 Make the layer active by clicking at the name of the layer in the legend then press the tool button Class Map The Class Map Window will appear Figure 16 19 Class Map DER C ALPFE Example EST Ipfe_ex_tl Create classes based on lay
78. able 5 2 shows the association between the original PFE CSV outputs and the formatted Spread tables Table 5 2 LPFE Output Files to Spread Tables LPFE Output Files Converted Spread Table est OD table pfp Path table The details of how to use the software are contained in the user manuals in the Appendix CHAPTER 6 CASE STUDIES 75 Chapter 6 Case studies With the details of LPFE formulation and implementation discussed in previous chapters this chapter presents a series of case studies to examine the performance characteristics of LPFE We first describe a general evaluation framework in Section 5 1 followed by numerical experiments that are carefully designed to examine how the choice of algorithmic parameters affects performance e how different network topologies affect estimation performance how measurement locations and additional inputs such as partial O D information affect LPFE s and TD LPFE s performance and how input errors influence the quality of O D estimates Note that most numerical studies presented in this chapter are devoted to the static problem because the time dependent LPFE is comprised of a sequence of static LPFEs and so findings derived from static studies naturally apply to the dynamic case However we shall discuss a dynamic example in the last section that highlights the effect of carryovers of residual queues across times 6 1 Evaluation Framework Theoreti
79. accuracy and zigzagging requirements For the basic network typology types LPFE is capable of reproducing measured link flows and capturing total demands accurately provided that all links are measured For the tree network the estimated O D table can perfectly match the true O D table For linear ring and derived networks the estimated O D table cannot reproduce the true O D table mainly due to the existence of multiple path solutions Since path solution is usually not unique in most networks this type of error seems inevitable if only link flows are used as inputs Information reflecting the spatial structure of travel demands 1 e a historical or observed O D table greatly improves estimation quality Even when traffic counts are available only on a small set of links e g freeway links LPFE can still produce satisfactory results if such structure information is well maintained in the input O D table The performance of LPFE is not sensitive to the errors contained in the input historical O D table However as errors of the input O D table increases it becomes harder to reproduce the observed link traffic counts accurately On the other hand LPFE seems more sensitive to measurement errors in link counts Nevertheless LPFE can still make improvement over the input O D table even if link measurements are subject to significant errors Explicitly considering measurement errors does not produce better estimati
80. aken from Yang and Meng Yang amp Meng 1998 is adopted to examine the impact of these parameters The network contains 9 nodes 14 links and 9 O D pairs Figure 6 2 shows the network topology and Figure 6 3 lists the O D table We use all link flows obtained from assignment as inputs No additional O D information is considered Q Q X l XK origin destination demand i 1 6 120 IN 1 8 150 S i 1 9 100 3 nr AS 2 6 130 ASS 2 8 200 7 2 9 90 Se 4 6 80 7 s 4 9 110 nr WY NY Figure 6 2 Yang and Meng s network Figure 6 3 O D trip table CHAPTER 6 CASE STUDIES 79 Figure 6 4 6 7 show the values of RMSE _ Link of various scenarios with different algorithmic settings As shown in Figure 6 4 when the number of iteration is larger than 100 resulted RMSE_Link is very small and does not change much implying that the observed link flow pattern is reproduced perfectly Further to achieve a satisfying link flow estimate requires that be set to be less than 0 01 See Figure 6 5 The performance of LPFE seems not sensitive to the value of bn as revealed in Figure 6 6 This is probably due to that this network contains a small number of constraints thus bad iterations are unlikely to appear Figure 6 7 illustrates the impact of different combinations of z and zn As we can see for a fixed z RMSE Link decreases as zn i
81. al complexity to the solution of the O D estimation problem in real size networks In view of these limitations a logit path flow estimator LPFE originally proposed by Bell Bell amp Shield 1995 is adopted in this research for inferring both steady and time dependent O D trip tables LPFE is selected for several reasons First LPFE incorporates the logit based route choice model but avoids the analytical and computational difficulties of pursuing equilibrium flow patterns by bi level programming Second LPFE decomposes the dynamic O D estimation problem into a sequence of static problems and links these static problems across time with queues which can be carried on from one period to subsequent periods This approximation does not require any dynamic network traffic flow assignment model but is still capable of capturing temporal demand fluctuations and one of the most important dynamic traffic phenomena queuing Last but not least LPFE has been validated in a number of scenarios as a potential tool to determine O D flows and path travel times in various transportation networks Bell amp Shield 1995 Bell Shield Busch amp Kruse 1997 Bell amp Grosso 1998 In this research we e extend the original LPFE formulation and improves the efficiency of its solution algorithms Bell s original LPFE assumes that link travel times are independent of traffic volumes and all input data is free of measurement errors Moreover the model does not a
82. ample of the file project 2 b DANET2 type network This format is original designed to address the need of dynamic application which describes a network by four files project net project lin project nod and project odp 1 project net provides basic parameters as described in Table I 3 See Figure I 3 for an example 2 project lin describes link information as described in Table I 4 See Figure I 4 APPENDIX I 4 for an example 3 project nod describes node information as described in Table I 5 See Figure I 5 for an example 4 project odp describes O D information as described in Table I 6 See Figure 1 6 for an example Table I 3 A description of file project net Range Fields Type Description Block 1 Row 1 Field 1 Text Prompt Field 2 Integer Number of nodes Row 2 Field 1 Text Prompt Field 2 Integer Number of links Row 3 Field 1 Text Prompt Field 2 Integer Number of Origins Row 4 Field 1 Text Prompt Field 2 Integer Number of Destinations Row 5 Field 1 Text Prompt Field 2 Integer Number of O D pairs Row 6 Field 1 Text Prompt Field 2 Integer The length of each time interval Row 7 Field 1 Text Prompt Field 2 Integer Number of time intervals Number of nodes 130 Number of links 390 Number of origins 5 Number of destinations 15 Number of OD Pairs 210 Unit Simulation Time sec 300 Assignment Horizon in unit time 6 Figure I 3 An example of the file projec
83. and check the types of results to be compared 42 5 Click at the OK button All the selected result items will be open in corresponding windows Figure 39 Visual PFE File Edit View Network Table Estimate Diagnose Windows Help e e ei a a C PFE_GUI_TDS Network HYNG8 pfe I HYNG8_OD_BOUNDS a aa DX C APFE_GUI_TDS NetworkiHYNG9 pfe gt HYNGS_OD_BOUNDS s I HYNG8_DESIRELINES I HYNGS_DESIRELINES Ww a V HYNGS_OD W HYNGS_OD o a 7 HYNG8_NETWORK I HYNGI_ NETWORK fad fad f 0 D_SC PFE_GUI_TDS Network HYNGS pfe _TDS Network HYNG9 pfe P_SUM P_SUM 38 30 ci 0 00 0 00 20 00 25 00 45 00 A SUM 0 00 13 30 25 00 38 30 A_SUM Figure 39 Compared Result Example Create PFE Networks Creating network input data for PFE requires an understanding of the data format A detailed description of the data specification can be found in the User Manual of Visual PFE Technical notes about the data files are provided at the end of this example for your reference Visual PFE includes tools for users to build the input data from dBase files The dBase data format dbf can be prepared through any software with database capability e g Microsoft Excel What Data are Required to Create PFE Networks Visual PFE network creating tool requires the following three data files to create PFE network e Network topology file e Trip
84. and the number of classes can be selected Users can choose to let the program determine the colors and sizes of the classes by applying auto color and size Users can also set up the color and size by applying custom color and size To do this double click the color blocks to set up the color for the lowest and highest classes Then select the symbol sizes for the lowest and highest classes After clicking the Apply custom color and size button the program will create for all classes a graduate color and size transition from the lowest to highest classes Class Map CALPFE Example EST ipfe_ex_t1 Create classes based on layer Ipfe_ex_t1_network Numeric field Number of classes Figure 13 Class Map Window 20 Bar Chart Window Bar charts based on values of a particular attribute of a layer can be created using the Bar Char Window Bar charts are best suited for visualizing the variation of production and attraction at origins and destinations Note that bar charts are not designed for network links Applying bar chats to network links will cause the links to become invisible i e links are replaced by the bars To activate the Bar Chart Window Figure 14 first make the layer active by clicking at the name of the layer in the legend then press the tool button Chart Map Once the form appears clicking at an attribute from the attribute list box will highlight the attribute Clicking at an attribute twice will d
85. ate decrease of OFV is not CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 43 int badIter double convIndicator double ziggIndicator int maxMainIter double convCriterion double ziggCriterion int maxZigglIter int maxBaditer double lineSearchAccuracy int maxLineSearchIter double stepSizeLB Constructor Void GEN_IA Return Attributes bool ReachMaxIter Return bool ReachMaxBad Return bool ReachAccuracy Return bool ReachZigg achieved the number of iterations during which OFV changes opposite to the expected direction an indicator of convergence an indicator of no improvement maximum number of iterations permitted a threshold value that is used to determine convergence a threshold value that is used to determine no improvement maximum permitted number of no improvement iterations maximum permitted number of bad iteration required accuracy in line search maximum permitted number of line search the minimum permitted step size an empty default constructor none test if the maximum number of iterations is attained a boolean value test if the maximum number of bad iterations is attained a boolean value test if required convergence criterion is achieved a boolean value test if no improvement happens CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 44 Return a boolean value bool ReachMaxZigg test if maximum number of n
86. brium conditions are satisfied for the estimated traffic flow pattern In other words the estimation of the assignment matrix itself is embedded into the O D estimation process The first equilibrium assignment O D estimation model due to Nguyen 1977 is to find an O D matrix that regenerates the observed travel costs hence observed traffic counts when assigned onto the network in a user optimal fashion However the solution of Nguyen s model may not be unique since the optimization problem is not strictly convex with respect to O D demands In other words there exist many possible O D trip matrices that produce the same set of link flows Consequently a priori information often in the form of a target O D table e g an outdated O D table from a survey has to be used to lead to a unique solution A great deal of research work has been focused on introducing a secondary optimization problem to incorporate such a priori information The O D estimation problem thus has a natural bilevel structure where the secondary optimization program forms the upper level problem leader while the traffic assignment CHAPTER 2 LITERATURE REVIEW 7 problem the lower level problem follower The objective of the secondary optimization is either minimizing the least squares distance between the estimated and target O D matrices Turnquist amp Gur 1979 LeBlanc amp Farhangian 1982 Sheffi 1985 Yang et al 1992 Yang 1995 or maximizing an en
87. cally the evaluation of the LPFE s performance requires comparing the estimated O D flows to the true O D flows In reality however obtaining true O D data is extremely difficult We use a combination of historical and synthetic O D data in these cases studies with an evaluation framework as shown in Figure 6 1 CHAPTER 6 CASE STUDIES 76 Historical OD Flows Measured Link Flows Hypothetical True OD Flows Hypothetical True OD Flows Logit Traffic Assignment y Artificial Perturbation Hypothetical True Link Flows Artificial Perturbation Hypothetical historical OD Flows y Hypothetical Measured Link Flows OD estimation i Estimated OD Flows Estimated Link Flows Performance Evaluation ITrue OD Flows True Link Flows Hypothetical True OD Flows Hypothetical True OD Flows m Hypothetical True Link Flows Logit Traffic Assignment Performance Indices 1 Total Demand Captured 2 RMSE of OD Flows L 3 RMSE of Link Flows Figure 6 1 Evaluation framework We assume that a true O D trip table is known as a priori This O D table can be established for example from existing survey data With this true O D table link traffic counts are produced from the corresponding traffic assignment procedure a logit t
88. ccount for historical O D data and or section related measurements derived from vehicle re identification techniques e g automatic vehicle location video detectors The extended LPFE formulation proposed in this research overcomes these limitations Both the iterative balancing algorithm IBA and the method of successive averages MSA are employed to solve the extended LPFE We combine these algorithms with a column generation technique to avoid enumerating paths Heuristics are applied to accelerate the identification of the optimal path set and to CHAPTER 1 INTRODUCTION 3 improve the overall convergence performance e implement both steady state and time dependent LPFE as well as the corresponding logit traffic assignment models an object oriented programming OOP framework is adopted to enhance the reusability and flexibility of computer codes Two existing C class libraries developed at UC Davis TNM and MAT are used as a starting point of implementation This reduces programming efforts because TNM contains well defined network objects while MAT provides supports for programming both general and network specific optimization problems Our implementation consists of 17 subclasses derived from MAT e test and validate LPFE using synthetic and real data and quantify the accuracy and reliability of O D trip table estimates various scenarios are set up to examine the impact of 1 the choice of measurement locations 2 additional input
89. cognizing the fact that the formats required by Visual PFE are quite restrictive and laborious to prepare for real applications network creating tool being illustrated next was also developed to assist the creation of PFE network The minimum requirement for this tool is that network nodes must be numbered according to the node numbering scheme mentioned above Example Consider the sample network in Figure 47 All shaded nodes which are either origins or destinations are numbered from 1 to 6 which are smaller than IDs of all other intermediate nodes nodes 11 through 13 The user may also be renumbered TAZs in many different ways see below as long as the required numbering scheme is satisfied The O D structure see Table 1 must be consistent with node IDs defined by the uSer o_o Figure 47 Example Network o o Remark gap in the sequence of node IDs for TAZs should be avoided as much as possible 53
90. connectors are the links locating at the entrance exit of each origin destination TDC RMSE _OD and RMSE link of estimation results corresponding to different inputs are shown in Figure 6 26 Figure 6 27 and Figure 6 28 respectively TDC 100 90 F 80 t 70 60 F 50 f 40 f 30 F 20 f 10 f 0 f f f i 1 all measured congested efficient freeway dummy links amp links 267 links 45 links 33 links 27 freeway links 53 Figure 6 26 TDCs for different sets of measurements CHAPTER 6 CASE STUDIES 93 RMSE_OD veh hr 800 00 700 00 600 00 500 00 400 00 300 00 200 00 100 00 0 00 all measured congested efficient freeway dummy links amp links 267 links 45 links 33 links 27 freewaylinks 53 Figure 6 27 RMSE_ODs for different sets of measurements RMSE_Link veh hr 140 00 120 00 100 00 80 00 60 00 40 00 20 00 0 00 Figure 6 26 indicates that in most scenarios more than 90 of total demands are captured except the scenario where only freeway links are measured in which TDC 78 15 Interestingly the total demand captured by the scenario with as much as 267 links all measured links is not very different from what captured by the scenario with only 33 links efficient links suggesting that LPFE can capture the total demand with a all measured congested efficient freeway dummy links amp links 267 links 45 links 33 links 27 freeway links 53 Figure 6 28 R
91. d Otherwise the change is discarded 8 To export the network data dbf to a different set of PFE input files pfe pfp and pfx go to menu item Network Export 9 Save the edited network in a different name e g 9GRDx pfe Remarks Open a File Explorer window and observe for yourself if all three PFE files are created in the data folder specified You can also go to File Open and open the newly exported pfe file and see if the change is correctly written to the file 41 Example 8 Compare Scenarios If multiple estimation runs have been done for a network all of the previous results can be opened and compared at the same time To compare different results How to Compare Previously Estimated Results l Make sure all of the previously opened output windows are now closed to avoid file sharing violation Go to the menu item Diagnose Compare The Compare Estimated Networks Window will open Figure 38 a5 Compare Estimated Networks Click to browse data folders C PFE_Workbook 7_exercise_7 SER A Select from the followings to compare Estimated Networks M HYNGS Py HYNGS Figure 38 Compare Estimated Networks On the window click at the Browse button and go to the folder e g the folder PFE_Wookbook 7_exercise_7 where all estimation results are stored Once the data folder is selected all available results will be shown in the corresponding list boxes Select from the lists
92. d on Equations 2 6 2 7 are often termed as path flow estimators PFE CHAPTER 2 LITERATURE REVIEW 6 2 2 Static O D Estimation According to ways in which an assignment matrix is determined static O D estimation methods can be classified into proportional assignment methods and equilibrium assignment methods If traffic congestion in a network is minor i e travel time is roughly independent of changes in traffic flow the assignment matrix is assumed to be exogenously determined and obtained by means of some proportional assignment procedures which can for example be a simple all or nothing AON assignment or a more advanced stochastic assignment The earlier research efforts based on the proportional assignment assumption were credited to Willumsen 1981 for introducing the entropy maximization approach Van Zuylen 1980 for using the concept of minimizing information and Cascetta 1984 for casting the problem in a generalized least squares framework Many researchers such as Bell 1983 1991a McNeil and Hendrickson 1985 Brennigner Gthe et al 1989 Lo et al 1996 proposed improvements and or conducted tests along the line of proportional assignment However as congestion gets heavier in the network the proportional assignment assumption no longer holds In this case the assignment matrix can no longer be determined exogenously Instead a traffic assignment model has to be incorporated to ensure that designated equili
93. derived classes none test if the solution process should be terminated a boolean value this function is called before InitializeQ in the solution process It is used to accommodate some special building initialization operations none this function is called after the solution process is terminated a boolean value write solutions obtained from Solve into disk files 0 if succeeds a non zero value otherwise Open report files and write headers It must be called before Report 0 if succeeds a non zero value otherwise Close report files 0 if succeeds a non zero value otherwise CLASS TNM_IA PARENT CLASS GEN_IA Data Members TNM_SNET network a pointer of a TNM_SNET object TINM_SNET is a static network class defined in TNM This network object is initialized in the overridden CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 47 Build function double costScalar a positive scalar to re scale link travel times ENUMI pf an enumeration type of link performance functions Constructor void TNM_IA Q an empty default constructor Return none CLASS TNM_MPEN PARENT CLASS TNM_IA Data Members double theta The dispersion parameter O in logit models double costCoef The coefficient of travel cost term in the objective function i e in Equation 4 1 vector volConLink a vector of pointers of TNM_SLINK defined in TNM objects associated with constraint 4 4
94. directly The idea is to restrict link flow from exceeding the weighted sum of link capacity and queue rather than just capacity itself By not imposing any limit on queue length one ensures that the feasible solution set is always non empty i e there is always at least one feasible solution The formulation of this revised model reads RBSUE inf c L nf D 0 5 v D min f c LE mf 1 0 S v Dv a5 subject to 3 12 nonnegative constraints are ignored and Af lt C v 3 21 CHAPTER 3 LPFE FORMULATION AND ALGORITHM 19 where v isa vector of link queues D is a diagonal matrix as follows Ci O D 0 0 0 Cn Note that the quadratic term is added into the objective function value in order to discourage the spreading of queues RBSUE assumes that some traffic stays in queues at the end of the analysis period which conflicts with the assumption that all trip be completed in steady state assignment models Nevertheless as we shall see soon the existence of such residual queues makes it possible to model the carryover of congestion across time using steady state assignment models The optimality conditions of RBSUE include Equations 3 14 3 17 3 18 and C Af v gt 0 3 22 u C Af v 0 3 23 1 Dv H 3 24 Equation 3 24 simply states that the equilibrium queue is equal to the equilibrium delay times the capacity In the time dependent case a sequence of steady state RBSUEs is used t
95. double tdLink Vol a two dimensional array storing the time dependent link flows int timeInterval the number of time intervals of interest 1 for the steady state case int curTime current time interval Constructor void TNM_LODE at mt ep t default constructor Return none ENUM at the type of solution algorithm only applies to the time dependent case ENUM mt the type of sub problem bool ep whether or not enumerate all paths double t dispersion parameter Attributes int GetTimelInterval get the total number of time intervals Return timeInterval int GetCurTime get the current time intervalcurTime Operations void EnableMsLinkTimer m set the value of m_useMsLinkTimenone bool m true if allow to consider measured link travel times int SaveSol t save the solution at time t into an intermediate binary file Return 0 if succeeds non zero value otherwise bool t the time index int LoadSol t load the solution at time t from a binary file into memory Return 0 if succeeds non zero value otherwise bool t the time index CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 57 CLASS TNM_LODE_TD PARENT CLASS TNM_LODE Data Members double tdTarDemand a two dimensional array storing the measured time dependent O D information double tdLinktime a two dimensional array storing the measured time dependent link travel times Constructor void TNM_LODE_TD at ep t default c
96. dows e Post on Features of a Layer e Manage OD Tables e Visualize Paths e View Reports and Text Files e Edit Networks e Compare Previously Estimated Results e Create Networks Example 1 Estimate OD Tables for a Particular Network In this example you are given a PFE network named 9GRD which consists of three separate text files 9 GRD pfe 9GRD pfx and 9GRD pfp You will learn how to create these three files in the final example How to Run a PFE Estimation To estimate an OD table for the 9GRD network 1 Open the Visual PFE program select menu item Estimate Static to open the Static PFE Estimation GUI see Figure 1 S Visual PFE File Edit view Network Table S0 Diagnose Windows Help a anam w E Figure 1 Estimate Static 2 On the Estimation GUI click at the Browse button to find the folder PFE_workbook 3_Exercise_3 9GRD pfe 3 Enter 1 50 for Dispersion Parameter 4 Select 5 000 for Max Iteration 5 Select 4 gt 0 0001 for Convergence level 6 Select Manual Adjustment Figure 2 to use measurement errors specified in the input files 7 Click OK to run PFE estimation 2 Static PFE Estimation Network k PFE_VVorkbook 3_Exercise_3 9GRD pte Browse Parameter Dispersion Parameter gt 0 15 Max Iteration 1 000 100 000 000 Convergence 10 0 10 h lt Estimation Method Manual Adjustment Uniform Error Bound Ua
97. e average O D trip rates using the average traffic counts over a relatively long period such as a morning or evening peak Two problems dominate the research efforts in the static O D estimation modeling traveler s route choice behavior in the presence of congestion and ensuring a unique solution in a highly under determined system In the dynamic context existing estimation methods can be roughly categorized into two classes based on the type of road topology they apply to intersection oriented and network oriented Intersection oriented methods assume the complete information for all the origin entry and destination exit counts thus are often applied to handle isolated intersections or a fraction of freeways 2 1 Notation and preview Consider a transportation network G N A where N and A are the sets of nodes and links respectively Let R and S represent the set of origins and destinations respectively K the set of paths joining an OD pair rs and q a positive traffic rs demand associated with O D pair rs Each directed link ae A is associated with a positive travel time fa a as a convex and non decreasing function of link flow Xa i PENE G 7 k For any path k K its travel time is calculated as c t 8 where n 1 a a rs if path k uses link a and 0 otherwise and its flow is denoted by fis For simplifying notation we also use x X X X X to represent a vector of link n fl
98. e LPFE text files to the shapefiles used by Visual PFE Table 5 1 LPFE Output Text Files to Shapefiles LPFE Output File Converted Shapefile lfp Network lines zne OD points est Desire lines lfp Scatter plot points Visual PFE TD converts the LPFE output text files to shapefiles These shapefiles are stored in the same folder as the input network data The shapefiles are used to visually depict the network the origins the destinations and the desire lines Figure 5 12 shows a side by side view of the list of shapefiles and the legend of the network map layers It can be seen that three files i e shp shx and dbf are used to draw a layer i e ESRI shapefile specification The name of the layer is the same as that of the three shapefiles that make up the layer Each layer name includes reference to the input network and the feature i e network od desire lines or boundary points of the layer CHAPTER 5 VISUAL PFE TD 73 Name Size Type N gt Ipfe_ex_t pFp 658KB PFP File Ipfe_ex_t sum 2KB SUM File 8 Ipfe_ex_t6 zne 3KB ZNE File a mi ipfe_ex_t1_di dbf 116K6 DEF File C LPFE Example EST pfe_ex_t1 aai E Ipfe_ex_t1_dl shp 40KB SHP File I LPFE_EX_T1_OL ipfe ex ti dl shx 4KB_SHX File p d Sl lpfe_ex_t1_network dbf 265KB DBF File F LPFE_EX_T1_NETWORK E Ipfe_ex_t1_network shp 77 KB SHP File v E Ipfe_ex_t1_network shx 8KB SHX File E LPFE_EXT1_00
99. e Visual PFE copyright form Toolbar There are 19 toolbar buttons Figure 3 in the Visual PFE TD The name of a toolbar button is shown when the mouse is placed over the button aanas a A BE S E E Figure 3 Toolbar Buttons The first five buttons from left are toggle buttons Only one button can be pressed down at a time The toggle button that is pushed down will remain active until another toggle button is pressed down The five toggle buttons are e Toolbar Button Zoom In o Zoom in a map window or a scatter plot window e Toolbar Button Zoom Out a Zoom out of a map window or a scatter plot window e Toolbar Button Pan El Pan a map window or a scatter plot window e Toolbar Button Identify B Click at a feature on the active layer of a map or scatter plot to show information of the feature e Toolbar Button Display Link Bi Relate a point in the scatter Plot to the corresponding link in the network When this button is pressed down click at a scatter plot point and the focus will be move to the network window with the corresponding network link highlighted Other than the five toggle buttons rest of the buttons are push buttons The function of a push button is activated after the button is pushed After the function is completed a push button returns inactive and does not stay pushed down The push buttons are e Toolbar Button Full Scale wl Return the scale of a map window or a scatter plot window to full scale
100. e and could be greater than 100 percent if highly inconsistent data are expected If this option is selected the error bounds specified in the input file pfe will be disregarded o Large measurement errors e g gt 50 percent could be employed in the estimation to ensure the existence of feasible solution and fast convergence i e ease to obtain the solution o However it was observed that an unreasonably large measurement error could lead to the underestimation of travel demand in the network Chen et al 2004 A balance between solution quality and computational time requirement should be cautiously considered i Chen A Chootinan P Recker W and Zhang H M 2004 Development of a Path Flow Estimator for deriving steady state and time dependent origin destination trip tables California PATH Research Report UCB ITS PRR 2004 29 5 3 Heuristic adjustment utilizes the information e g the difficulty of matching individual observations obtained after the estimation process to automatically adjust expand the error bounds and re estimates What are the PFE Return Codes A set of return codes has been developed to report possible sources of error and possible remedies for the execution of PFE Code Description Solution 0 Program is terminated successfully 1 At least one of the required inputs is missing Check the existence of input files input folder 2 Size of the working ne
101. e highlight the attribute Multiple attributes can be selected at the same time Each attribute will appear on the map as a bar of varying height based on the value of the attribute Users can choose to let the program determine the colors and sizes of the classes by applying auto color and size Users can also set up the height and width of the bars by applying custom height and width To do this simply select the height and width from the two pull down boxes After clicking the Create Bar Chart button the program will create the bar chart accordingly Bar Chart DER CALPFE Example EST Ipfe_ex_t3 The map window title The active layer ipfe_ex_t3_od ZNID Figure 14 Bar Chart Window 21 Scatter Plot Window One of the most common and important diagnostic graphs for the OD estimation problem is the observed versus estimated scatter plot of network link flows The scatter plot is implemented in Visual PFE TD as a collection of map layers The scatter plot point layer uses the observed value of a link as the X coordinate and the estimated value as the Y coordinate A link layer is used to represent the two axes and other boundary lines delineating the levels of accuracy of the estimation The scatter plot points the axes and the markers are actually shapefiles and presented in a map window Thus functions of a scatter plot window are the same as a map window A scatter plot window is shown i
102. e title of the fist window Visual PFE TD File Edit View Table Estimate Diagnose Windows Help e i fe te TE TEE Report_ C LPFE Example EST lpfe_ex_t2 fe er Paths _SC LPFE Example EST lpfe_ex_t2 Scatter Plot_SC LPFE Example EST lpfe_ex_t2 D_SC LPFE Example EST pfe_ex_t2 C LPFE Example ES I lpfe_ex_t2 9 LPFE_EX_T2_0D_BOUNDS G EC LPFE_EX_T2_DL E E E MV LPFE_EX_T2_0D o V LPFE_EX_T2_NETWORK Figure 5 1 Multiple Document Interface 5 2 1 Estimation GUI The process of OD estimation with Visual PFE TD begins with the Estimation GUI see Figures 5 2 and 5 3 Users can use this GUI to set up a LPFE estimation CHAPTER 5 VISUAL PFE TD 63 provided LPFE network data have been prepared This GUI feeds the user inputs to the LPFE and the program returns the estimation results to the GUI once estimation is completed or specific problems are encountered during estimation The original output files generated by the LPFE estimation program are all text based Visual PFE contains components that can convert the text files to the GIS and spreadsheet files Algorithm Input DER Algorithm Input Selectthe input network _PFE Example ESTilpfe_exnet 1 Meximum Allowed Iterations 1 701 000 000 foo o 2 Accuracy 1E 16 To 1 for O O O o O 3 Minimum Allowed Stepsize 1E 9 To 1 aooo atett lt C stst S S 4 Desirable Line Search Accuracy 1E 9 To 1 aooo tt lt s sti
103. earch 14B 243 255 Fisk C S 1988 On combining maximum entropy trip matrix estimation with user optimal assignment Transportation Research 22B 66 79 Fisk C S amp Boyce D E 1983 A note on trip matrix estimation from link traffic count data Transportation Research 17B 245 250 Jornsten K amp Nguyen S 1980 On the estimation of trip matrix from network data Technical Report NITH MAT R79 36 Linkoping institute of technology Linkoping Sweden LeBlanc L amp Farhangian K 1982 Selection of a trip table which reproduces observed link BIBLIOGRAPHY 118 flows Transportation Research 22B 83 88 Lo H P Zhang N amp Lam W H K 1996 Estimation of an origin destination matrix with random link choice proportions a statistical approach Transportation Research 30B 309 324 McNeil S amp Hendrickson C 1985 A regression formulation of the matrix estimation problem Transportation Science 19 278 292 Nguyen S 1977 Estimating an OD matrix from network data a network equilibrium approach Technical Report 60 University of Montreal Nguyen S 1984 Transportation Planning Models Edited by M Florian Elsevier Science Publishers Amsterdam chapter Estimating origin destination matrices from observed flows pp 363 380 Nie Y amp Lee D H 2002 An uncoupled method for the equilibrium based linear path flow estimator for origin destinatio
104. eceeceeeeeeeneeeenaes 111 Figure 6 46 RMSE_ODs at different time intervals 2 0 0 0 ceeeeeeseceeeseeeenteceeneeeenaeeeenee 112 Figure 6 47 Accumulation and dissipation of queues on link 307 and 428 112 CHAPTER 1 INTRODUCTION 1 Chapter 1 Introduction Reliable origin destination trip data are critical to many applications in transportation planning design and operations In freeway corridor management for example time of day ramp metering algorithms require the knowledge of origin destination flow fractions and adaptive ramp control strategies often need to know origin destination flow in order to distribute expected flow reductions from a bottleneck to various metered ramps upstream Because true O D data are rarely if ever directly obtainable in practice their estimation from limited observations of traffic conditions on the network has been the subject of many research efforts Traditionally O D trip matrices are derived from household or roadside surveys However survey based approaches have two major limitations they are labor intensive and costly to obtain and they often fail to capture temporal demand pattern changes The latter is particularly detrimental to devising effective real time traffic management strategies for relieving traffic congestion These limitations of the survey based approach have spurred a stream of research that focused on inferring static or dynamic O D matrices from traffic counts in parts of the n
105. emarks There are 9 nodes and 14 links as stated IDs of intermediate nodes nodes 11 12 13 were renumbered after the IDs of TAZs immediately Nodes 11 12 and 13 were renumbered to 7 8 and 9 respectively see Figure 44 The pfx based on the trip table structure file entered 3 1 2 3 9 4 5 6 4 5 6 4 5 6 48 Remarks If you left the trip table structure empty in the Create Network Window and the PFE determine the structure of the pfe file the result will look like the one in the following figure pfx determined through network topology 5 1 2 3 4 5 3 2 3 4 5 6 4 5 6 4 5 6 6 6 Figure 45 PFX file and Paths on Network Based on network topology nodes 4 and 5 can also be the origin The total number of origin nodes increases from 3 to 5 Similarly the number of possible O D pairs is 13 compared to 9 O D pairs specified in the 9GRDOD dbf see Figure 45 49 pfp the path file of the created network Remarks If there is no path specified by the user e g leave the User specified Path file blank the 9GRD pfp file will contain 0 as the number of paths specified and the list of paths will be empty Path 1 4 10 which is defined by a link sequence is equivalent to Path 1 gt 2 gt 7 11 gt 4 defined by a node sequence 7 is the new ID of node 11 see Figure 46 Path 2 Figure 46 Paths Data 50 What are the PFE Input Data Files
106. ened and compared at the same time The comparison is setup via the GUI in Figure 5 9 CHAPTER 5 VISUAL PFE TD 70 fa Compare Estimated Networks Click to browse data folders CALPFE Example EST Select from the followings to compare Available Networks Figure 5 9 Scenario Comparison Window 5 2 8 Windows Help A standard windows help document Figure 5 10 is created and built in with Visual PFE TD Users can access instruction of particular tasks via the document Visual PFE e s Hide Back Forward Home Contents Index Search Fad gt Introduction sig Options amp Print There are nine menu items in the Visual PFE QQ Visual PFE pen El e Toolbar 2 Run PFE 2 Main Results Compare Estimated Nety E 0 D Estimation Problem Static Path Flow Estimator Ea e Creating Updating PFE Nety Reference isual Fie Edit View Network Table Estimate Diagnose Windows Help 1 File e New This is used to create a new Text File Open Save e Exit 2 Edit e Undo e Cut Copy e Paste Select All 3 View e Zoom In e Zoom Out Figure 5 10 Windows Help CHAPTER 5 VISUAL PFE TD 71 5 3 Technical Specification Visual PFE TD integrates the LPFE program with three other software components The architecture of the system is shown in Figure 5 11 Display and query Data MapObjects Management Visual PFE TD VB NET application
107. ent matrix could be determined by a two step stochastic route choice model In the first step fractions of time dependent paths are given by a discrete choice model Second path flows are mapped onto links using a dynamic network loading DNL procedure hence producing a stochastic dynamic assignment matrix However the authors did not address how to CHAPTER 2 LITERATURE REVIEW 12 determine a path set used in the discrete path choice model Moreover their DNL model still assumes the knowledge of the dynamic link travel times That is the time dependent link travel times through the whole network have to be completely observable If this is impossible the authors noted that a DTA model may provide substitutes As mentioned before however this is not yet feasible for large networks Ashok and Ben Akiva 1993 proposed an improved version for Okutani s approach Instead of using the Okutani s autoregressive specification for O D flows Equation 2 9 Ashok and Ben Akiva introduced the notion of deviation from target O D flows and reformulate the transition equation as follows ds GS DVD Dae Td 64 2 11 l t p r s Obviously by imposing the target O D flows often coming from historical estimates the estimates can avoid the risk of losing structural information about trip patterns Based on the Kalman filter technique the approach provides both real time estimation and predictions The determination of the assignment matrix in the As
108. er Ipfe_ex_t1_network Numeric field Number of classes Figure 16 Class Map Features Once the form appears select a particular attribute from the numeric fiend and select the number of classes To let the program determine the colors and sizes of the classes click at the Apply button in the Auto Color and Size panel Figure 17 20 C PFE_Workbook 3_Exercise_3 9GRD pfe M SGRD_OD_BOUNDS a 9GRD_DESIRELINES M 9GRD_0D o M SGRD_NETWORK ESTIMAT 2L Less than 155 6666 155 6666 311 3333 Greater than 311 3333 Figure 17 Auto Color and Size Class Map 9 To set up the color and size by applying custom color and size double click at the color blocks to set up the colors for the lowest and highest classes Then select the symbol sizes for the lowest and highest classes After clicking the Apply Custom Color and Size button the program will create for all classes a graduate color and size transition from the lowest to highest classes Figure 18 Remarks After a class map is generated the legend will be reset To place another posting you need to remember to set the active layer again 21 C PFE_Workbook 3_Exercise_3 9GRD pfe 9GRD_OD_BOUNDS a M 9GRD_DESIRELINES fad M IGRD_OD o MV SGRD_NETWORK ESTIMAT m Less than 155 6666 A 155 6666 311 3333 Greater than 311 3333 Figure 18 Custom Color and Size Class Map How to Clear a Class Map 10 To
109. esponding to the OD pair will be highlighted If a cell in the row sum or the column sum is the active cell one to all or all to one desire lines will be highlighted If the active cell of the OD table stays on the table total all of the desire lines will be highlighted Save an OD Table as Excel File An OD table in Visual PFE TD can be saved as a Microsoft Excel file To use this function when the OD Table window is opened go to the menu item File Save as Excel The Save File As dialog box will open for users to enter a desired file name for the Excel File 26 Path Table Window The estimates of path flows between origins and destinations are also generated by LPFE as a text file i e the pfp file Similar to the OD tables the Visual PFE TD program converts the path text file and formats it as a spreadsheet using the Spread software component see Technical Specification A resulting path table is shown in Figure 19 Note that the title of the Path Table Window is also created by prefixing the word Paths_ with the title of the corresponding network Map Window i Paths_SC LPFE Example EST pfe_ex_t1 mj Origin Dest Demand PathiD Flow Cost TT LIMIN olp alaisi tiov wx Ya 226 229 1406 107 034 841 56 60 64 70 19 22 25 29 80 85142 147 203 844 226 229 14 06 038 0 3 841 5 115 172 176 182 122 126 130 134 138 143 844 226 229 14 06 O91 0 26 841 13 16 19 22 25 29 80 85143 844 226 229 14 06 0 66 0 35 841 57 115
110. etwork This latter approach provides a faster and cheaper alternative to household or roadside surveys and can produce estimates of time dependent O D trip tables It can also incorporate historical O D trip data from other sources such as surveys to improve its estimates Conventional O D estimation methods concern only static matrices representing O D trips made over a relatively long time period within which traffic condition is assumed to be at steady state Accordingly steady state O D matrices are estimated from average link traffic counts of that period Static O D data cannot provide the temporal variations in traffic demand within the designated analysis period thereby not adequate for dynamic applications such as traffic simulation integrated control systems etc However unlike its steady state counterpart the methods for estimating dynamic O D data are still in its infancy In part this is due to the difficulty in obtaining accurate CHAPTER 1 INTRODUCTION 2 historical dynamic O D data Yet to develop a reliable dynamic traffic assignment model is a more challenging in some sense unresolved issue Consequently most existing dynamic estimation methods either focus on small networks to rule out route choices or assume that time dependent travel times can be obtained from a surveillance system or from a simulation model to help assign traffic onto the network Furthermore the introduction of the time dimension adds computation
111. fe M 9GRD_OD_BOUNDS m I 9GRD_DESIRELINES M 9GRD_0D a M SGRD_NETWORK Figure 32 Display of All to One Paths d Toolbar Button One to One Paths When the button is clicked all the paths beginning at the origin and ending at the destination of the active row of the Path Table will be highlighted Figure 33 35 C PFE_Workbook 3_Exercise_3 9GRD pfe BAE M 9GRD_OD_BOUNDS a 1 2 M 9GRD_DESIRELINES w M 9GRD_OD a Z 9GRD_NETWORK Figure 33 Display of One to One Paths How to Clear the Paths 19 To clear the magenta highlight from the map when the network map window is the active window press the Clear Track Lines button El The button also applies to the magenta highlights on links and desire lines Remarks On a large network the number of paths can be so substantial such that tracking links in all the paths becomes an extremely time consuming operation The one to all and the all to one path tracking may actually fail when the number of links making up all the paths exceeds the limitation of the software When this happens users will be informed that the limitation is reached and be advised to use the one to one path option instead 36 Example 6 View Report and Text Files Every PFE estimation generates a text file documenting summary statistics of the estimation The estimation statistics of the estimation can be viewed in Visual PFE using the Report
112. fic assignment problem through decomposes the dynamic O D estimation problem into a sequence of static problems yet takes into account of queuing by linking the static problems across time with residual queues which can be carried over from one period to subsequent periods and finally 3 it has been validated in a number of scenarios as a potential tool to determine O D flows and path travel times in various transportation networks In this research we extended the original LPFE formulation and improved the efficiency of solution algorithms implemented both steady state and time dependent LPFE in an object oriented programming OOP framework tested the performance of LPFE using synthetic data and quantify the accuracy and reliability of its O D trip table estimates We also developed Visual PFE and Visual PFE TD the graphic user interfaces GUI for both static and time dependent LPFE Our test case studies show that LPFE is able to produce path flows and O D travel demands that accurately match traffic counts under the logit traffic assignment assumption We also found that information reflecting the spatial structure of travel demands e g a historical O D table is of great value to the improvement of the quality of O D trip estimates and that LPFE can still produce satisfying estimates even when traffic counts are only available on a small portion of links as long as such structural information is maintained in the base O D table
113. g order of the layers can also be CHAPTER 5 VISUAL PFE TD 65 changed by dragging the layer name up or down in the legend area A network map consists of four ESRI Shapefiles each presented as a map layer Network links All of the link attributes are stored in this layer including the observed and estimated link flows Origins and destinations The production and attraction of the origins and destinations are stored in this point layer Desire lines A desire line represents the flow between a pair of OD The desire lines layer is hidden by default Users can choose to display or hide them Map boundary points Two boundary points are included in the network map to create sufficient margins around the network such that all features of the network can be displayed within the map window C LPFE Example ES T lpfe_ex_t1 M LPFE_EX_T1_OD_BOUNDS a oe a a a V LPFE_EX_T1_O0D EERO EAR V LPFE_EX_T1_NETWORK Figure 5 4 Network Map 5 2 3 OD and Path Tables The OD table see Figure 5 5 is presented as a spreadsheet The color of each cell CHAPTER 5 VISUAL PFE TD 66 can be adjusted based on the value of the OD flow The size of the cells can also be adjusted to facilitate visualization of the flow patterns over the entire OD table fer O D_SC LPFE Example EST pfe_ex_t1 DER 241 ZNE 245 a7 ag os EAs 1918 16 29 27 84 1262 16 35 11 om e oy LS S S T E E EE LE E er m pad 10 89 0 8
114. getError t Set the value of m_useTargetError Return none bool t true if allow to consider link travel time measurements int GetLinkError lerFile Read link measurement errors from a disk CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 55 file Return 0 if succeeds non zero otherwise ifstream lerFile a file pointer int GetTargetError terFile Read O D measurement errors from a disk file Return 0 if succeeds non zero otherwise ifstream terFile a file pointer double RmsetLink compute root mean squares of the measured and estimated link flows Return calculated root mean square double RmsetOD type compute root mean squares of two specified vectors of O D flows Return calculated root mean square enum type specify two vectors of O D flows Overridables int GetMsLink oFile Read link measurements from a disk file Return 0 if succeeds non zero otherwise ifstream oFile a file pointer in tGetMsLinkTime mFile Read measured link travel times from a disk file Return 0 if succeeds non zero otherwise ifstream mFile a file pointer int GetTargetOD tFile Read measured O D flows or historical O D from a disk file Return 0 if succeeds non zero otherwise ifstream tFile a file pointer CLASS TNM_LODE PARENT CLASS TNM_ODE Data Members double tdDemand a two dimensional array storing the time dependent O D table CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 56
115. h an example in which the titles of the OD table scatter plot path table and report all include the name and the file path of the network i e the title of the fist window Visual PFE TD File Edit View Table Estimate Diagnose Windows Help eje 7 EM i ee Report_ C LPFE Example EST lpfe_ex_t2 B Paths_ C LPFE Example EST lpfe_ex_t2 Scatter Plot_SC LPFE Example EST pfe_ex_t2 d im O D_S C LPFE Example EST lpfe_ex_t2 C LPFE Example EST lpfe_ex_t2 5 LPFE_Ex_T2_0D_BOUNDS w a LCI LPFE_EX_T2_DL M j LPFE_EX_T2_0D a V LPFE_EX_T2 NETWORK N Figure 1 Multiple Document Interface The Main Window The Main Window is the MDI parent form of Visual PFE TD Figure 2 shows the program s main window Visual PFE TD File Edit View Table Estimate Diagnose Windows Help Tw SLI fete ty Figure 2 Main Window Main Menu There are eight menu items in the main menu of Visual PFE Each menu item contains sub items e File Control functions related to creating opening and saving of individual MDI child forms o New Open a new text editor window which can be used to create PFE network text files Open Open an existing text file in a text document form Save As Excel Save an OD table as a Microsoft Excel file Save As Text Save the text file in the text document form Exit Exit Visual PFE TD O00 0 e Edit Control common functions of a text document form Undo Undo changes
116. he available networks and scatter plots are shapefiles Only those created in the Create Shapefiles and Tables Window can be open for comparison If the network or scatter plots for a particular time period is never created it will not be available in the list box However the OD tables and reports are text files and they are available for every time period of a LPFE estimation The text files of the selected OD tables will be converted to a spreadsheet on the fly Windows Help A standard windows help document Figure 22 is created and built in with Visual PFE Users can access instruction of particular tasks via the document To access the Help document go to the menu item Help Visual PFE TD Help The Help document will be open for user to search for particular information There are also Help buttons placed on various GUIs Click at these buttons will also open a particular topic of the Help document E Visual PFE Hide Back Contents Index Search Fas gt tas Home J Introduction QQ Visual PFE There are nine menu items in the Visual PFE E Visual PFE File Edit view Network Table Estimate Diagnose Windows Help MEM e Toolbar 2 Run PFE 2 Main Results 2 Compare Estimated Nety e O D Estimation Problem Static Path Flow Estimator g e Creating Updating PFE Nety Reference 1 File e New This is used to create a new Text File e Open e Save Exit 2 Edit e Undo e Cut e
117. heir limited results have shown up to 20 improvements have been observed over the basic scenario by using cordon lines The Chang and Tao model does not address how the assignment matrix CHAPTER 2 LITERATURE REVIEW 10 might be obtained a question that any estimation model for general networks which the proposed model claimed to be cannot ignore Constructing cordon lines arbitrarily raises another serious feasibility issue namely how the entry and exit flows for all these cordon lines should be observed 2 4 Network Oriented Dynamic O D Estimation Network oriented dynamic O D estimation methods focus on extending the modeling concept of static O D estimation by assuming the knowledge of a dynamic assignment matrix and often historical dynamic O D trip tables A fundamental estimation relationship is of the similar form described by Equation 2 1 which reads yD ah x VreR se S t he l T 2 8 where Prsh denotes the proportion of the demand 4s occupying link a during time interval h Unlike the steady state relation defined by Equation 2 1 Equation 2 8 reflects the contributions of O D flows embarking during prior intervals to link counts in later intervals The determination of dynamic assignment factors P He calls for a reliable dynamic traffic assignment DTA model in general However no existing dynamic O D estimation method incorporates an assignment model as in static cases mainly because a DTA mode
118. hen the estimated link flow is less than the lower bound of the traffic count Conceivably this link is more likely to be selected by a shortest path algorithm in the next round since its cost may be significantly lowered Note that we restrict the link travel times to be non negative to avoid creating negative cycles that would cause the shortest path search to fail One could also use a K shortest path algorithm to generate new paths That is in each iteration not only the shortest path but the second third and Kth shortest paths are generated for each O D pair Although the K shortest path algorithm is more computationally demanding it may accelerate the stabilization of A thereby improve the overall convergence speed of Algorithm CGA 3 3 4 Time dependent case Now we turn to the solution algorithms for E TD LPFE As in the steady case we first assume that link travel times are fixed and the matrix A is given for each time interval Similarly iterative balancing algorithm can be used to sequentially examine Kuhn Tucker conditions However in this case we need to deal with an additional optimal condition the relationship between queue and delay Equation 3 45 The revised iterative balancing algorithm for the time dependent case RIBATD is given as below ALGORITHM RIBATD CHAPTER 3 LPFE FORMULATION AND ALGORITHM 36 Step 0 Initialization Set 47 0 47 0 v7 0 v 0 K a 1 0 Set ve max 0 v
119. hok and Ben Akiva s model follows the idea from Cascetta et al 1993 namely either an entirely observable network or a DTA model has to be available In a subsequent work Ashok 1996 indicated that the assignment matrix itself is an estimate whose random errors should not be ignored This is because an assignment matrix is obtained from random variables such as link travel times and path fractions It was shown that the estimator will become biased and inconsistent if this issue is not correctly addressed In order to remedy the problem a revised procedure is presented to take the stochastic assignment matrix into account Treating all assignment factors as decision variables is not acceptable because it considerably increases the computational load These authors thus provided a simplification in which only P state equations are used To determine the state augmentation required to transform this stochastic formulation to the standard transition and measurement equations the method has to estimate each state variable as many times as the size of the lag when applying a Kalman filter procedure Most recently Ashok and Ben Akiva 2000 suggested an alternative approach defining the state vector by deviation of departure rates from each origin and the shares headed to each destination Except its transition equation this approach has a CHAPTER 2 LITERATURE REVIEW 13 similar framework as those proposed previously by Ashok and Ben Akiva
120. i TA 44s t 150 i e il 100 i Se 5 4 D 50 ag 0 0 20 40 60 80 100 120 140 160 180 RMSE of the historical OD veh hr b freeway links 27 amp historical OD Figure 6 40 RMSE_Links for scenarios with different settings on the consideration of O D flow errors In general these figures suggest that explicitly considering errors of input O D trip rates produces worse rather than better estimates in terms of RMSE This observation seems counterintuitive in the first glance Recall that the errors of input O D tables are considered in our formulation by confining estimated O D flows within an interval centered at observed values the interval length represents the confidence level Although this strategy ensures that true OD values are contained within the feasible set of the optimization program it enlarges the feasible region thus makes it harder to find the optimum Moreover our algorithm always fixes the infeasibility of a constraint by setting the estimated value to its boundary Such adjustment may thus push estimates away from the true O D trip rates since true values are in the interior of the feasible region instead of on its boundaries 6 6 2 Considering errors of link measurements Following similar logic we in this subsection evaluate the effect of explicitly considering errors in link counts The 20 scenarios used in Section 6 5 2 were rerun with the measurement errors of link flows con
121. i il 0 5 10 15 20 25 Time Interval Figure 6 45 RMSE_Links at different time intervals CHAPTER 6 CASE STUDIES 112 RMSE of estimated and target O D matrices 10 aa Estimated O D Matrix I i I i go Target O D Matrix i 4 80L 60L RMSE T 4o 20L 0 1 i L L 1 L L i 1 0 5 10 15 20 25 Time Interval Total Demand Captured TDC 10 i T T T i T 80L 60L 3 TDC 4o 20L 0 1 i 1 i 1 h 1 i 1 Time Interval Figure 6 46 RMSE_ODs at different time intervals Time dependent queues on Link 428 40 T T T T T T T oe True queues 35 a Estimated queues 300 250 vehicle 200_ 15 Queue 100_ 50L 0 1 4 1 r 1 1 L L 20 25 Time Interval Time dependent queues on Link 307 30 T T T T T T T oo True queues j l sa Estimated queues 25 200_ vehicle 150 Queue T 10 50L 25 Time Interval Figure 6 47 Accumulation and dissipation of queues on link 307 and 428 CHAPTER 7 CONCLUSIONS 113 Chapter 7 Conclusions Getting travel demands is the starting point of many transportation planning and operational applications To supplement the traditional survey approaches this research implements and tests a class of methods for estimating both steady state and time dependent travel demands from traffic surveillance data which can be automatically collected at relatively low costs and p
122. i oono e 32 3 3 3 Column penera O a a a e a tte ele a thas A 34 3 3 4 Time dependent Case sca ckttieieiane nnn a e E 35 Chapter 4 An Object Oriented Implementation ccsssccssssscsssssccsssccssssscessssees 39 4 1 Class Hierarchy arana in aa E a A a t 39 4 2 Cl ss Descriptio aran T T E a 42 4 3 Class Library and Its Usages a a T 58 4 3 1 Use mat lib in programming es sesssssessseesseesseestestessressressresstesstesseesteesressresrese 58 4 3 2 A console interface ccccccsccssscesccesscescceoscessceosceosceosceoscessceoncensceosceoscenceseenses 59 Chapter 5 Visual PFE TD A GIS Based Decision Support System for Time Dependent Origin Destination Trip Table Estimation scssesssees 61 Sel Whatus Visual PREY ies else sede acs a iG se ace sce eee 61 5 2 Key POAtUreS sien ate spss viet rsd ee ates thet edd ee a al Dee iad ee oats 62 5 21 Es mation GUL reene a E arene cece ead a eh oe ete 62 5 2 2 NetWork Maps sccissticeisceissescasviansdaacisdsiaa ss e ea OE ta scceat ec ER E 64 5 2 3 OD and Pate Table Siisti leasiconl do teatsceslutato tedster aedbrlehentinn dacs bess 65 5 2 4 Link Flow Scatter Plots saciid cc vevcsissanste bedeoust ticbosei ded aves usceosshbaduavelcdsuargaraaeteren 67 5 2 gt Report Docum nt 24 ocsacaeicucedep tec cunted ates derwteieudys wis jams teqeuetaaes tarsasmdudvaetede 68 DOING L WOU EAEE ties Pins tice i e iets eae aaielde eal inl ciated 69 5 2 1 Scehatio Compar
123. ider OD flow error 120 100 80 a A 60 a i A A aA A as A A 40 A A A A A AA gt 4 20 44 Ped se E 0 0 50 100 150 200 RMSE of the historical OD veh hr a all measured links 267 amp historical OD CHAPTER 6 CASE STUDIES RMSE of the estimated link flows veh hr 180 rp Historical OD lt 160 p lt Estimated OD not consider OD flow error o 140 A Estimated OD consider OD flow error 6 120 D t 100 80 A oO A 5 60 a 5 ra 1a A R WH 40 a wa 4 se 20 aape te 0 0 50 100 150 200 RMSE of the historical OD veh hr b freeway links 27 amp historical OD Figure 6 39 RMSE_ODs for scenarios with different settings on the consideration of O D flow errors 90 r Estimated OD not consider OD flow error 80 p a a A Estimated OD consider OD flow error 70 f i A 60 A A 50 re 5 y x re bA 40 A A 4 ae A aA t ol bi 30 co a z 20 3 s 10 a 0 0 20 40 60 80 100 120 140 160 180 RMSE of the historical OD veh hr a all measured links 267 amp historical OD 106 CHAPTER 6 CASE STUDIES 107 m 400 Estimated OD not consider OD flow error A c 350 A Estimated OD consider OD flow error 300 A x c 250 A D A af QA f D 2 200 pea
124. ighted Toolbar Button Single Path E Relate a record in the path table to the corresponding path in the network When the button is clicked the path corresponding to the active row of the Path Table will be highlighted Toolbar Button One to All Paths E When the button is clicked all the paths originating from the origin of the active row of the Path Table will be highlighted Toolbar Button All to One Paths El When the button is clicked all the paths ending at the destination of the active row of the Path Table will be highlighted Toolbar Button One to One Paths E When the button is clicked all the paths beginning at the origin and ending at the destination of the active row of the Path Table will be highlighted 10 e Toolbar Button Clear Track Lines Bl Clear highlighted lines e g desire lines and paths Algorithm and Parameter Input Windows To run the LPFE estimation program within Visual PFE TD two GUIs are created for the users to enter parameters of a LPFE estimation run The first window is the Algorithm Input window Figure 4 and the second is the Parameter Input Window Figure 5 The first window can be activated by accessing the menu item Estimate Time Dependent After data on the Algorithm Input Window are properly entered the Next button will be enabled i e the LPFE input file alg is created successfully If the parameters entered do not conform to the specification of the LPFE program users will
125. ilable for download from ESRI web site Visual PFE TD uses the DLL version of the ArcViewShapeFile to convert the text files generated by LPFE to Shapefiles The converted shapefiles can be displayed with the Visual PFE TD map component and common GIS software Table 1 shows the conversion between the LPFE text files to the shapefiles used by Visual PFE Table 1 LPFE Output Text Files to Shapefiles LPFE Output File Converted Shapefile lfp Network lines zne OD points est Desire lines lfp Scatter plot points 32 The Shapefiles of the Network Map and Scatter Plot Windows Visual PFE TD converts the LPFE output text files to shapefiles These shapefiles are stored in the same folder as the input network data The shapefiles are used to visually depict the network the origins the destinations and the desire lines Figure 24 shows a side by side view of the list of shapefiles and the legend of the network map layers It can be seen that three files i e shp shx and dbf are used to draw a layer i e ESRI shapefile specification The name of the layer is the same as that of the three shapefiles that make up the layer Each layer name include reference to the input network and the feature i e network od desire lines or boundary points of the layer Name Size Type A ipfe_ex_t6 pfp 658KB PFP File ipfe _ex_t6 sum
126. iles to Spread Tables iis jas iccsstsieses iuens ices leached seas suasstesyncesiaesecsalers 74 Table 6 1 RMSE_ODs for hypothetical historical O D flow trip tables eee 97 Table 6 2 RMSE_Links for hypothetical measured link flOWS eee eeeeeseeesteeeteeeees 102 LIST OF FIGURES Figure 4 l A class eraneny trecina e a treads Netegial RA weenie 40 Figure 4 2 A sample C code using mat lib oe eee eeseceeeeeseeeeseeceaeceseeeseeeeaeeenaeens 59 Fig re4 3 A example lpfe Pat Fle is sSavetnassiaiyees sadelnasstavghoatantceesdedeeed aa a ie i 60 Figure 5 1 Multiple Document Interface ssseseseeeeeeeseseeseeseesresresserseesressresrsereseeseeseeesee 62 Figure 5 2 Algorithm Input Window sesesseseesesesessessessesressersresessersessreeseeseeseesseeseeseresee 63 Figure 5 3 Parameter Input WindoW eeseseeseeseseseseessessresressessresresserstesreeseestesreeseeseeseeesee 64 Fig re 54 Network MaParderssngmes i ishias ia te essiri 65 Fisure 5 OD Table Window vi a a a a EEE ei ihe 66 Figure 5 6 Path Table WdoWa taae E E RE AA SS 67 Figure 5 7 Scatter Plot Wand Ow secetest occas eccicties Sondecatiict actenaseecasieedavecebiateneionaae 68 Figure 5 8 Report WdoWa Aci ae ia Be ee sg cae ete Sees ale 69 Figure 5 9 Scenario Comparison Window sscesccsssceessecsseceseeeseeeeaeeceaecneeeeeeesaeeenaeens 70 Pigure 5 10 Windows Help7iti a ceiee loin Me hn le oi ele oe ee net 70 Figure 5 11 Visual PFE TD Software Components 1 00 0
127. ink counts should be available by associating each unmeasured link with an explicit capacity constraint We shall explore the properties of LPFE in great detail in Chapter 3 Nie and Lee 2002 suggested replacing the column generation procedure of linear PFE Sherali Sivanandan amp Hobeika 1994 by a K shortest path ranking KSPR algorithm that determines UE paths columns exogenously This scheme decouples linear PFE into two simple and relatively separate components Nie Zhang and Recker 2005 incorporated this decoupled structure into a generalized least squares GLS framework to develop a GLS path flow estimator The method is attractive due to its computational advantage and convenience of analyzing estimation errors However to determine UE paths the method requires that all link traffic counts be available and of sufficient accuracy which is not CHAPTER 2 LITERATURE REVIEW 8 often realizable in real world applications 2 3 Intersection Oriented Dynamic O D Estimation Models The idea of estimating dynamic O D trip tables originated from a series of pioneering work of Cremer and Keller 1981 1984 1987 in which time dependent traffic counts were first employed to transform the underdetermined static model to an over determined dynamic model The goal of this type of dynamic models are to identify the time varying demand split parameters or turning proportions that represent O D flows at intersections or along a smal
128. interfaces In the following we develop the interface for the console application CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 59 Table 4 1 A guideline for the selection of algorithm objects Logit traffic assignment Logit path flow estimator Steady state CSTAP_B TNM_LODE Time dependent CSTAP_B_ TD TNM_LODE_TD 1 include lt mat h gt 2 include lt tnm h gt 3 int main a 4 5 TNM_LODE lode new TNM_LODE LOGIBA true false 0 1 6 lode gt lpf CSTLK 7 lode gt EnableTarget 8 lode gt EnableTargetError 9 if lode gt Build c in c out NETFORT 0 10 Tl cout lt lt tFail to build an an algorithm object lt lt endl 12 return 1 13 14 lode gt Solve 15 lode gt PrepareReport 16 lode gt Report 17 lode gt CloseReport 18 delete lode 19 return 0 20 Figure 4 2 A sample C code using mat lib 4 3 2 A console interface The console program named LPFE is originally designed to provide the general purpose PFE GUI an external access to classes defined in mat lib As mentioned the general purpose PFE GUI is coded using Visual Basic VB Although it simplifies the GIS related programming the use of VB makes it a bit more difficult to directly communicate with mat lib The console interface bridges the gap That is PFE GUI first offers a user friendly way to prepare input files for the console pr
129. ints but consider travel costs On the other branch both MPEN_DC and MPEN_DC_MC include the flow conservation constraints with o 0 0 in the former and 1 0 in the latter Further subclasses TNM_LPFE and TNM_LTAP explicitly set up the constraint structure for assignment and O D estimation problems respectively thus serve as base classes for the two types of problems TNM_LPFE actually implements Algorithm RIBA for E LPFE SUB discussed in Section 3 3 1 Derived from TNM_LPFE LPFE_RQ deals with the logit path flow estimator with residual queues the formulation used in the time dependent case LPFE_RQ s two subclasses LPFE_RQ_MSA LPFE_RQ_IBA implement Algorithms MSATD and RIBATD respectively A similar design applies to the subclass TNM_LTAP and its derived classes which solve corresponding assignment problems Subclass LOGWRAP_RMP implements Algorithm DDAG to handle the flow dependent link travel times LOGWRAP_RMP is able to deal with most formulations discussed in the last chapter provided a correct sub problem solver is selected For example to solve E LPFE TD with the method of successive average the sub problem solver of DDAG should be an LPFE_RQ_MSA object TNM_LOGWRAP provides a CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 42 general wrapper for performing column generation and requires an object of LOGWRAP_RMP to solve the sub problem TNM_ODE is a base class for general O D estimation problems This s
130. ip making Cascetta et al 1993 suggested an optimization framework for estimating dynamic O D flows which can be viewed as an extension of classic static O D estimators Equation 2 8 is employed to describe the basic measurement relation and a target O D matrix is assumed to get a unique solution Cascetta et al s model takes the following form mind q q d2 x x q gt 0 2 10 where q is the target O D flows X and X represent the estimated from Equation 2 8 and observed link volumes respectively Different distance functions will lead to estimators the optimal solution of 2 10 with different statistical properties For example log likelihood function and generalized least squares GLS function will respectively lead to a maximum likelihood estimator and an GLS estimator Two different estimators are presented to address different applications A simultaneous estimator designed for off line application infers in one step the entire set of time dependent O D flows by using link traffic counts from all time intervals On the other hand a sequential estimator derives the O D flows for a given time interval by using both previous O D estimates and the current and previous traffic counts The sequential estimator is suitable for on line application because its computation time is relatively modest and it is able to make use of a priori estimated O D matrices Cascetta et al 1993 further showed that the dynamic assignm
131. ison essene a aiaa aaa 69 3 2 8 Windows Help nereerunine nn ee ea E A AE 70 5 3 Technical Specificatie istrenn E a a ened 71 J NTP merna A E E AE E E N 71 5 3 2 The ArcViewShapefile Read Write OCX s ssssessseseessissriessiesseesrresseesreesressress 72 3 3 ESRI Ma pObJECtS nnen ee e a aoi E EEEE 74 5 3 4 FarPoint Spread tescciteessdereaccdantpteiaciccsdanidiedeued alba E N 74 Chapter 6 Case studies seiccecscicecictesvesadcessnncavenssdeaneacvactoevnsedeeendovedoeseduasgesucsseeaseaebuceeeescsen 75 6 1 Evaluation Framework eessessseesessesesesressessrssressessrertesseessesrestesseseresresseseressesee 75 0 2 Algorithmic Settings eca rons ere e eae teisa eee bers a i g aas a 11 6 3 The Impact of Network Topology ssssssesssessssesesssessseessersseesseresseesssresseesseessee 81 6 3 1 The case with a tree network sedated cadaede wield usGuiled a eSlced daSbaleda wSacoh ts 83 6 3 2 The case with a linear etwoOEk sis cwisisieeedl ins canshietdeais yo aarsiieucde maarameatsenioge inten 85 6 3 3 The case with a ring Network ccc cadstaninavinkniiaiininaieieiadel 86 6 3 4 The case with a derived general network eeeceeseseeeseeeeteeeeeeeeteneeeeeenens 88 6 4 The Impact of Additional puts wiv asespousatteadsalies tice cacstaaas aterseec de ways 90 6 4 1 Effects of measurement location and the number of measurement locations on estimation performance 0 0 eeeeeeeeeeeeneeesseeceaeceeeseeeeeaeeeaeen 91 6 4 2 The effects of historical O D floW
132. it path choice model i e epee Vr Rs S k e K Pr rs Dd expor 3 5 where Pk is the probability of travellers between O D pair rs use path k and Tk is travel cost on path k Note that in FSUE 7 equals to the path travel time Unlike its deterministic counterpart the optimal SUE path solution is unique because the Hessian matrix is strict positive definite with respect to path flow Fisk s original logit model assumes that the link cost function t is an increasing function of link flow Because travel times given by such functions remain finite whenever link flows are finite the model may predict unrealistically high link flows sometimes well exceed the physical capacities of roads This problem can be resolved by introducing explicit capacity constraints into the formulation and the Lagrangian multipliers associated with these new constraints can be interpreted as queuing delay caused by insufficient road capacities Bell 1997 took this approach but assumed that the link travel cost is constant and delay only exists on links operating at capacity Bell s logit assignment model reads CHAPTER 3 LPFE FORMULATION AND ALGORITHM 17 m ieee GD r Inf 1 3 6 subject to Equations 3 2 to 3 4 and Xa S Cy VEE A 3 7 Note that Ca denotes the capacity of link a and ta represents a constant travel time cost on link which is independent of link flows By using the link path relationship 3 3
133. k Ee Kt a where K denotes all paths existing between all O D pairs The second term in the objective function a weighted total system cost helps guide the solution toward more likely efficient paths A path generation algorithm is devised to solve the optimization CHAPTER 2 LITERATURE REVIEW 14 problem iteratively The algorithm begins with solving a restricted master problem based on an initial choice of a set of O D paths then attempts to augment the master problem with paths from time dependent shortest path search upon a time space expanded network The method will terminate and claim an optimum if no new time dependent shortest path can be found Dynamic link travel times are assumed to be known inputs thus not modelled in Sherali et al s work 2001 This is true for all existing network oriented dynamic O D estimation methods Other limitations of this method include the requirement for a complete observation of all link flows which is typically not available in reality and its inability to take into account observation errors 2 5 Summary Although many approaches have been proposed to solve the O D trip table estimation problem the validity and applicability of most approaches to large scale networks remain to be investigated Particularly existing dynamic O D estimation methods are far from producing satisfactory results on real sized networks Above all the determination of dynamic assignment matrices is separated from the
134. k in a central business district CBD Usually commuters have one primary path to travel from home to the work location The linear network Figure 6 8b and the ring network Figure 6 8c are simplifications to corridor networks in multi centric cities In a linear type network the home places and work places of people locate along a linear arterial road while in a ring network major economic activities happen along a ring arterial road Finally a derived network is usually more complex and contains elements of the above three types of topologies For example the network in the same suburban neighborhood might be a tree type network where people from different local roads drive to the same freeway connecting the CHAPTER 6 CASE STUDIES 83 suburban neighborhood and the CBD area of the city Within the CBD area there might be either a linear road or ring road connecting all the freeways coming from different suburban neighborhoods Again we assume that all link flows are measured and no observed historical O D information is available 6 3 1 The case with a tree network The tested tree network is shown in Figure 6 9 which consists of 16 nodes 15 links seven origins and one destination The number of OD pairs is seven The true OD flows are listed in Figure 6 10 Figure 6 11 and Figure 6 12 visualize the estimated O D profile and link flow profile The red points in both plots represent the true values O D flow or link flow while
135. l section of a freeway In the Cremer Keller intersection model the sequence of O D flows and exit flows are assumed to be dependent on the time varying patterns of entry flows through a linear relationship Different algorithms have been proposed to solve this intersection oriented dynamic model Among the competing methods are the nonrecursive approach such as the cross correlation method Cremer amp Keller 1987 the constrained ordinary least squares method Cremer amp Keller 1987 Sherali Arora amp Hobeika 1997 the iterative maximum likelihood technique Nihan amp Davis 1989 and the fixed point method Nihan amp Hamed 1992 on one hand and the recursive approach such as the method of recursive estimation Cremer amp Keller 1987 the recursive least squares RLS Nihan amp Davis 1987 and the Kalman filter Cremer amp Keller 1987 Nihan amp Davis 1987 on the other hand Nihan and Davis 1987 showed all recursive methods relate to a family of recursive prediction error RPE techniques and later Nihan and Davis 1989 compared RPE with the iterative maximum likelihood method Bell 1991b made the first attempt to extend the Cremer Nihan model on more general networks Two approaches are proposed to permit the distribution of travel times to span a number of different intervals The first approach which is suggested to be suitable for single intersections and small networks assumes that travel times follow geometrical di
136. l that is widely accepted does not exist Instead the dynamic assignment matrix need to be determined externally often by assuming dynamic link travel times can be obtained from either simulations or observations The first known work along this line is due to Willumsen 1984 who proposed to extend the entropy maximization method to handle time dependent traffic counts Simulation based models e g CONTRAM and SATURN were suggested to establish the relationship between time varying O D demands and link flows Okutani 1987 proposed a network oriented dynamic estimation method based on Kalman filtering which is suitable for on line application The measurement equation is defined in the same way as the fundamental equation 2 8 The transition equation given in Okutani s model is autoregressive taking the following form S yD te Dg te 2 9 l t p r s CHAPTER 2 LITERATURE REVIEW 11 where P is the number of lagged O D flows assumed to affect the O D flows in interval t 1 and FK D reflects 4ps on git ef is the random error Okutani applies a standard linear Kalman filter to get optimal estimates for O D flows sequentially Okutani s original paper does not describe how dynamic assignment matrices might be obtained Furthermore as Ashok amp Ben Akiva 1993 argued the use of autoregressive transition equation 2 9 makes it hard to capture the complex structure of activities that result in the spatial and temporal pattern of tr
137. le are presented in Figure 6 23 and Figure 6 24 CHAPTER 6 CASE STUDIES 89 origin destination demand origin destination demand 18 30 200 22 30 150 7 18 26 30 22 26 35 AU fP 18 27 50 22 27 25 N A 18 28 20 22 28 25 A 18 29 50 22 29 20 19 30 150 23 30 150 i 19 26 25 23 26 15 NU P 19 27 40 23 27 20 S y f 19 28 30 23 28 20 K 19 29 60 23 29 25 VA f 20 30 100 24 30 150 A a 20 26 10 24 26 20 J Xe J N 20 27 20 24 27 15 po i 20 28 25 24 28 20 Sf 20 29 20 24 29 25 21 30 100 25 30 200 21 26 20 25 26 15 21 27 25 25 27 20 fe 21 28 20 25 28 25 a Y 21 29 30 2 29 30 Figure 6 21 A derived general network Figure 6 22 True O D trip table O D estimation profile plot for time interval 1 RMSE 19 4774 100 00 percent total demand is captured EAS line Estimated True O D flow 0 0 50 100 150 200 250 True O D flow 5 Histogram plot for estimated O D B 14 gt v G 2 Nn 3 2 10 o gt U 5 8 wn a amp a A a O 5 2 2 v E 0 3 2 1 2 3 4 5 6 z Deviation from True O D flows Figure 6 23 O D estimation profile for the derived network CHAPTER 6 CASE STUDIES 90 Estimated link flow profile plot for time interval 1 Number of measured links 33 RMSE 0 0000 1400 1200 t Estimated True link flow 2 Co 400 0 200 400 600 800 1000 1200 140 True link flow Figure 6 24 Estimated link flow profile for the
138. le for the linear network 00 0 eee eeeeeeeeeereeeneeees 85 Figure 6 16 Estimated link flow profile for the linear network 0 0 0 0 eeeeeeeeeereeeneeees 86 Figure 6 17 Ring network se2c322cccs0is teccedincvediadisaeiea hdeecledaenies asiain siiis isa 87 Fig re 6 18 True O D trip table sistiese a estote ee i e ges kreisi ees 87 Figure 6 19 Estimated O D profile for the ring network ssssesesssesssssressresseessersseressees 87 Figure 6 20 Estimated link flow profile for the ring netWOrk ee eee eeeeeeeeeeereeeeeeees 88 Figure 6 21 A derived general network 22 ciieciseecsdihs dieieeiatleecdeti geisha nieies 89 Fig re 6 22 Wire O D Gri pita le speci cs da leeestesaunanseesoptatatenctaceiann at esaumuia ese lasau ne ie 89 Figure 6 23 O D estimation profile for the derived network 00 ese eeeeeseeeeeeeeeeeeeeenaeees 89 Figure 6 24 Estimated link flow profile for the derived network ceseeeeeeeeeereeeeeees 90 Figure 6 25 The Dallas Fort Worth network ceceesecsseceseeeseeeeseecaecesaeceseesseeeeseeenaeens 91 Figure 6 26 TDCs for different sets of measurements ee eee eeeceseceeeeeeeeeeeeeeeaeeeaeens 92 Figure 6 27 RMSE _ODs for different sets of measurements eee eeseeeeeeeeeeeneeeneeees 93 Figure 6 28 RMSE _ Links for different sets of measurements 0 00 0 cee eeeeeeseeeeeeeeeeee 93 Figure 6 29 TDCs for different link sets with and without historical O D data 0 94 Figure 6 30 RMSE
139. line underneath the layer name see the legend of the network layer in Figure 10 Labels colors and charts based on attributes can only be applied to features of the active layer When varying colors are applied to features of a layer by classes the legend of the layer will show the colors and the corresponding values Making a layer invisible A layer can be made invisible by un checking the check box right next to the layer s name in the legend area i e the desire line and the boundary points are made invisible in the map window Changing the drawing order Drawing order of the layers can also be changed by dragging the layer name up or down in the legend area Adjusting the width of the legend When a layer s name is longer than the default legend width the border between the map and the legend can be dragged and moved to accommodate the width of the legend 17 Identify Features Window Attributes of map features can be identified and displayed using the Identify toolbar button To identify a particular feature in a layer first make the layer active by clicking at the name of the layer in the legend then press the tool button Identify The mouse cursor when placed above the map window will change to the information symbol Move the mouse cursor to the feature and click at it The Identify Features Window will appear with attributes of the form displayed in a spreadsheet Figure 11 i_ Identify Features 2 features f
140. lizing the variation of production and attraction at origins and destinations Note that bar charts are not designed for network links Applying bar chats to network links will cause the map to be entirely filled with bars and the network links will become invisible i e links are replaced by the bars 24 Example 3 Manage OD Tables After a successful PFE estimation the OD table will be opened automatically by the program How to Open an OD Table If a previously opened OD table window is now closed and the users wish to see it again there are two ways to open an OD table 1 When the network map is the active window go to the menu item Tables Open OD Table to open the corresponding OD table 2 Ifno network window is opened go to the menu item Diagnostic Compare and select from the available OD Tables Figure 21 Co O D_SC PFE_Workbook 3_Exercise_3 9GRD pfe Figure 21 OD Table Window Note that when the OD table is opened the view is reduced so the color pattern of the entire table can be viewed without using the scrolling bars 25 How to Enlarge the OD Table View 3 Make the OD table the active window 4 Click at the toolbar button Table Zoom In al The OD Table will return to the normal view Figure 22 fe O D_SC PFE_Workbook 3_Exercise_3 9GRD pfe 370 01 0 00 0 00 0 00 0 00 0 00 330 00 530 00 300 001160 00 Figure 22 The Enlarged OD Table How to Reduce the OD Table View
141. ly made invisible on the network map because they tend to obstruct the view of the network links Visual PFE is built with a unique function for users to view desire lines via the OD Table To use this function 10 Make sure both the network Map and the OD Table windows are both opened 11 Click at a cell in the OD table to make it the active cell the cell will be encircled with faint dash lines 12 Press down the Display Desire Line toolbar button E The corresponding desire line s will be highlighted in the Map Window If the active cell of the OD table stays on an internal cell when the button is clicked the focus will be move to the network map window and the desire line corresponding to the OD pair will be highlighted Figure 25 28 at O D_SC PFE_Workbook 3_Exercise_3 9GRD pfe 3 ae e sl 0 00 0 00 0 00 6 95 139 35 Ewa 370 01 00 0 00 0 00 30 37 206 12 l 419 99 0 00 0 00 0 00 000 D 0 00 0 00 ooo 0 00 0 00 0 00 2 00 O00 TT 0 00 0 00 0 00 330 00 530 00 300 001160 00 on fF wm UM 0 00 4 C PFE_Workbook 3_Exercise_3 9GRD pfe M SGRD_OD_BOUNDS a M SGRD_DESIRELINES Figure 25 Display of Desire Line via OD Table vw MV 9GRD_OD s I 9GRD_NETWORK vw 13 Ifa cell in the row sum or the column sum is the active cell one to all or all to one desire lines will be highlighted Figure 26 29 fer O D_ C PFE_Workbook 3_Exercise_ 3 9GRD
142. mates as a much larger set It would therefore be of considerable economic interest if one can develop a selection procedure that optimizes the estimation results with a minimal set of measurements TABLE OF CONTENTS Chapter 1 Tito dict Oitiy caiccaces dese cvscnkcteasesciess ccecaueivedesscndunateenseandecsavecevennsdecnsnesoacteaseseansest 1 Chapter 2 Related Literature is sccccsscccsseccecctecss sce cbcsdaccesdesstievesssccecsspatiedvedsskeudsinceesesnveeeeees 4 Ze Ls Not tion and PTS VAC W sti iert ghed e eeo etes ee aan ae o aoaia s iat 4 2 2 Static O D Estimation is iiisninii sinnini claret aini 6 2 3 Intersection Oriented Dynamic O D Estimation Models 00 0 0 eee eeseeeseeeeeeeeeee 8 2 4 Network Oriented Dynamic O D Estimation ce eeceeeeeeseceseeeeeeeeaeecnaeenseenees 10 DO SMAYOO teecsuanabdaumeneeeaanes 14 Chapter 3 LPFE Formulation and Algorithim cccccssssccssssscsssccssssssssssscsssssees 15 3 1 Logit Traffic Assignment Model sacar Qaida iaeaues 15 Dediel MEMES SEAMS CASE 1h irt n e n a ee T eanetiines 15 3 1 2 The time dependent Casen iiinn E 18 3 2 Logit Path Flow ESUMAtOr A na aanta an n A E R R eee 20 32 VTH static Casen eenn a aa A E vents 20 3 22 The timesde pendent case seni inenen ae en a e a AS 21 3 2 3 Extend d Bad nl eer o a a a a Oey pete 22 JI Solution Al rithis se e irtete bevy e eti oes leee sgir 27 3 3 1 Solly E LPFE SUB rnp e a a a mR E ee ii 28 3 3 2 A descent direct ots
143. matically appears on top and become the active window with the corresponding link highlighted Figure 12 Scatter Plot_ C PFE_Workbook 3_Exercise _3 9GRD pfe I 9GRD_SCATTERPLOT_MARKER SH a I 9GRD_SCATTERPLOT_AXIS SHP yw M 9GRD_SCATTERPLO C PFE_Workbook 3_Exercise_3 9GRD pfe 9GRD_OD_BOUNDS a 9GRD_DESIRELINES ad 9GRD_OD oa 7 9GRD_NETWORK w Figure 12 Display Link Features 15 How to Clear Track Lines 14 To clear the magenta highlight from the map when the network map window is the active window press the Clear Track Lines button El The button also applies to the magenta highlights on desire lines and paths 16 Example 3 Feature Postings With Visual PFE you can place three types of postings on features of a map layer based on the values of the features The postings apply to both the network map window and the scatter plot windows The three types of postings are e Label e Class Map e Bar Chart Map Placing of all three postings require setting an active layer How to Label Features of a Layer 1 Make the layer of the features active 2 Press down the Label Feature button E The Label Feature Window will open Figure 13 3 Once the form appears a particular attribute can be selected for labeling and the font for the label can also be adjusted using the Font button 4 Click the Apply button the labels will be placed next to the features on a map Figure 14 L
144. modating multiple time intervals is given as follows ALGORITHM MTI Step 0 Initialization Set t O vt 0 Step 1 Solve the steady state problem Set t 1 call Algorithm CGA to obtain ft Vt compute estimated O D matrix qt according to ft Step2 if t T stop otherwise return Step1 where T is the total number of time intervals CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 39 Chapter 4 An Object Oriented Implementation The algorithms described in the last chapter are implemented using an object oriented programming OOP design Compared to the conventional programming approaches an OOP design is preferable because OOP provides a clear modular structure to define abstract data types objects that encapsulate data and functions operating on it OOP enhances the reusability of programs through the use of inheritance and polymorphism OOP provides a good framework for code libraries where supplied software components can be easily adopted and modified by the programmer The reusability and extensibility of the OOP design make it easy to maintain and upgrade the developed PFE software tool as needs arise e g when new formulations algorithms need to be implemented An OOP based PFE tool also provides great convenience and flexibility for developing graphical user interfaces We shall first present the overall class hierarchy of our implementation and then go through the details of classes Finally we will explai
145. n Department of Civil and Environmental Engineering Utah State University Will W Recker Department of Civil and Environmental Engineering University of California Irvine Final Report for TO 5502 ABSTRACT Reliable origin destination O D data are critical to many applications in transportation planning design and operations Because of the high costs of and challenges in obtaining reliable O D trip matrices from surveys or other direct sampling methods estimating O D trip tables from a readily available data source traffic counts provides an attractive economical alternative This project investigates one such an estimation method and implements it in a user friendly software tool called Visual PFE TD The developed O D estimation tool can be used to obtain both static and dynamic O D trip tables for traffic simulation studies project evaluations and transportation planning in a more streamlined and less time consuming manner For example it has been used to obtain an initial seed matrix for Paramics O D estimator to speed up the latter s O D estimation process A logit path flow estimator LPFE originally proposed by Michael Bell 1995 is adopted in this research for inferring both steady and time dependent O D trip tables LPFE is chosen because 1 it incorporates the logit based route choice model while avoiding several difficulties encountered in the conventional bi level formulation 2 it avoids the difficult dynamic traf
146. n Figure 15 Note that the title of the Scatter Plot Window is created by prefixing the word Scatter Plot_ with the title of the corresponding network Map Window The title enables the users to associate different output windows with the corresponding network When preparing the LPFE network input network data please make sure that the character is not used to make up the file name A network file with a file name containing the character will cause the program to malfunction Scatter Plot_SC LPFE Example EST Mpfe_ex_t1 jv LPFE_EX_T1_SCATTERPLO a M LPFE_EX_T1_SCATTERPLO vw V LPFE_EX_T1_SCATTERPLO m Figure 15 Scatter Plot Window 22 There are three ways to open a Scatter Plot Window e Select the Scatter Plot option in the Create Shapefiles and Tables Window e When a network map is the active window go to the menu item Diagnostic Graph e Go to the menu item Diagnostic Compare and select from the available scatter plots Link SP to Map A unique function of the scatter plot is the dynamic linkage between a scatter plot point and the location of the corresponding link on the map To use this function when the network Map and the Scatter Plot windows are both opened select the scatter plot point layer as the active layer Click the Link SP to Map button and the corresponding network link will be highlighted in the Map Window 23 OD Table Window The estimated OD flows between the origins and de
147. n how the classes can be complied as a class library and discuss its potential usage 4 1 Class Hierarchy The hierarchy of the implemented classes is demonstrated in Figure 4 1 As shown all subclasses are derived from the generic class GEN_IA which provides a framework for implementing general iterative algorithms Among others GEN_IA imposes a loop structure that consists of three fundamental components initialization main operation and convergence test CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 40 GEN_IA Yy TNM_IA LOGWRAP RMP x TNM_ODE TNM_MPEN AA TNM_LOGWRAP ee MPFE LMC TNM_LUPFE MPFE_DC TNM_LODE TNM_LODE_TD y y y CSTAP B LPFE_RQ MPFE_DC_MC TNM_LTAP CSTAP_B_TD LPFE_RQ_MSA LPFE_RQ_IBA LTAP_RQ LTAP_RQ_MSA LTAP_RQ_IBA Figure 4 1 A class hierarchy tree The first derived class of GEN_ network related algorithms The most important function of TNM_I IA TNM_ A IA lays a foundation for developing is to offer its subclasses an access to network objects defined in a C class library called TNM TNM defines both static and dynamic network objects and provides numerous functions to solve a variet
148. n of slackness conditions are detected associated multipliers are reduced so as to reactivate the constraints 3 3 2 A descent direction In this section we relax the assumption that all link travel times are fixed Instead the travel time on link a A are treated as an increasing function of the link flow Xa In this case algorithm RIBA cannot directly obtain the optimal solution since a subset of travel times are flow dependent However the following proposition shows that RIBA can be used to provide a descent direction Proposition 3 2 Assume that a path set is predetermined for E LPFE Let f bea feasible path flow pattern and the associated path cost is If solves E LPFE SUB in which is replaced by e then f f provides a descent direction for E LPFE at f Proof Let lt f denote the objective function of E LPFE To show f f isa descent direction we need to show Vz f f f lt 0 This equals to o L x 0 0 lp 0 0 1 0 c gBP f lt 0 c f gE Inf lt e f Bf nf TR Now let y f Inf y f _ is a strictly convex function because its Hessian is always positive definite for any f gt 0 Thus we have the following y f gt y f Vy f9 f 9 gt f Inf gt f Inf f f CHAPTER 3 LPFE FORMULATION AND ALGORITHM 33 When f gt f we obtain f Inf gt f Inf Incorporate this relationship into 3 75 we have
149. n trip matrices Transportation Research Record 1783 72 79 Nie Y Zhang H M amp Recker W W 2005 Inferring origin destination trip matrices with a decoupled gls path flow estimator Transportation Research 39B 497 518 Nihan N L amp Davis G A 1987 Recursive estimation of origin destination matrices from input output counts Transportation Research 21B 149 163 Nihan N L amp Davis G A 1989 Application of prediction error minimisation and maximum likelihood to estimate intersection o d matrices from traffic counts Transportation Science 23 77 90 Nihan N L amp Hamed M M 1992 Fixed point approach to estimating freeway origin destination matrices and the e ect of erroneous data on estimate precision Transportation Research Record 1357 18 28 Okutani I 1987 The Kalman filtering approach in some transportation and traffic problems In Proceedings of 10th International Symposium on Transportation and Traffic Theory pp 397 416 Powell W B amp Sheffi Y 1982 The convergence of equilibrium with predetermined step sizes Transportation Science 16 45 55 Sheffi Y 1985 Urban Transportation Networks Equilibrium Analysis with Mathematical BIBLIOGRAPHY 119 Programming Methods Prentice Hall Englewood cli s NJ Sherali H D Arora N amp Hobeika A G 1997 Parameter optimization methods for estimating dynamic origin de
150. ncreases However a very loose setting of z say 9 5 or 1 0 can adversely affect LPFE s capability to reproduce measured link counts no matter how many zigzagging iterations are allowed In short for this small network satisfying results can be obtained using the following setting n 100 lt 0 01 bn gt 1 z lt 0 1 zn gt 5 100 pa oO veh hr RMSE_Link oO 0 01 0 001 1 10 100 1000 maximum iteration number Figure 6 4 Scenarios with different n 0 001 bn 10 z 0 001 zn 10 CHAPTER 6 CASE STUDIES 80 100 10 veh hr 0 1 RMSE_link 0 01 0 001 0 001 0 010 0 100 1 000 accuracy Figure 6 5 Scenarios with different n 1000 bn 10 z 0 001 zn 10 0 1 veh hr RMSE_Link 0 001 1 2 3 4 5 6 7 8 9 10 maximum bad iterations Figure 6 6 Scenarios with different bn n 1000 0 001 z 0 001 zn 10 CHAPTER 6 CASE STUDIES 81 100 10 veh hr 0 1 RMSE_Link 0 01 0 001 1 2 3 4 5 6 7 8 9 10 maximum zigzagging iterations Figure 6 7 Scenarios with different z amp zn n 1000 0 001 bn 10 Although the setting of algorithmic parameters is usually problem specific a general guideline can still be drawn In most cases if an estimation result is regarded as unsatisfying users should so adjust the algorithmic parameters
151. ndent case The time dependent LPFE can be formulated using a similar approach described in Section 3 1 2 namely residual queues are explicitly added into the objective function and capacity constraints such that congestion effects can be carried over from one time interval to others At time t TD LPFE is formulated as L TD LPFE min f cr Elfe Inf I 0 5 vt De vt 0 3 37 subject to t _ yt l Aft lt Cu Vu Vu 3 38 CHAPTER 3 LPFE FORMULATION AND ALGORITHM 22 St Aoft Xo 3 39 where X is the vector of observed link flows at time period t Vu is the vector of queues on unobserved links at t For each time period TD LPFE seeks a path flow pattern that satisfies the logit path choice model and replicates observed link flows simultaneously while taking into account of the queues accumulated in previous time intervals The entropy term encourages trips to spread across paths while the quadratic term discourages queuing Let H and be the multipliers associated with constraints 3 38 and 3 39 the optimality conditions of TD LPFE are expressed as L int Ce Au Ue a Ao At 0 6 3 40 Cu Auf vi vit 0 3 41 Hi Cu Aue vh vit 0 3 42 ie 0 3 43 Aoft 36 0 3 44 Divi 4 3 45 3 2 3 Extended LPFE Several extensions to the original LPFE are presented in this section We shall use the static case to illustrate the major ideas First of all the link
152. near network The tested linear network is shown in Figure 6 13 The network consists of 16 nodes four origins and four destinations 15 links and ten O D pairs The true O D flows are listed in Table 6 14 The estimated O D flow profile and link flow profile are shown in Figure 6 15 and Figure 6 16 origin destination demand 9 10 200 9 12 200 9 14 100 9 16 50 11 12 200 TI 14 500 11 16 450 5 E E eee S eee 13 14 400 1 2 3 4 5 6 7 8 j 7 Pr Ay gt Ay ON 13 16 150 ii Wis ie vw ne o D A OLO 1s 15 16 400 Figure 6 13 A linear network Figure 6 14 True O D trip table O D estimation profile plot for time interval 1 RMSE 71 6507 100 00 percent total demand is captured o ESen ea 8S line Estimated True O D flow 0 100 200 300 400 500 600 True O D flow 5 Histogram plot for estimated O D 6 4 5 gt o 4 o 5 3 5 a GS 3 gt 6 25 2 2 oO a oO 15 i O i Ma o 5 0 5 2a E o0 3 a 1 0 1 2 3 4 5 6 2 Deviation from True O D flows Figure 6 15 Estimated O D flow profile for the linear network CHAPTER 6 CASE STUDIES 86 Estimated link flow profile plot for time interval 1 Number of measured links 15 RMSE 0 0001 1800 1600 1400 1200 link flow 1000 Estimated True a So o a te 400 1000 1200 1400 1600 180 800 True link flow Figure 6 16 Estimated link flow profile for the linea
153. next example shows how to edit attributes of a network using the GUIs For more details on editing and creating PFE input networks please see the PFE Workbook How to Create New Text Files 5 To create a new file go to the menu item File New and a blank Report Window will be opened as a text editor 39 Example 7 Edit Networks After examining the estimation results users can change attributes e g the observed flows of the network and export the data back to the original PFE data format for another estimation with improved results How to Edit Network Attributes 1 Make the network map the active window 2 Make the Network layer the active layer 3 Click at the toolbar button Identify Li and move the mouse cursor over the map 4 Select the link on which the attributes are to be changed i Identify Features DER 1 features found LINK NO A_NODE B_NODE Ax 143 67861 AY 59 92237 Bx 143 65861 BY 59 90237 LNKGRP LNK_CAP SPEED DISTANCE ALPHA No change Help Update Close Figure 37 Edit Network Attributes 5 Double click at a cell on the form to highlight the cell Figure 37 Change the value of the highlighted cell 6 Click at the Update button to register the value change 40 7 After the Close button is clicked users will be prompted for final confirmation of the change Answer Yes will save the change to the database 1 e the shapefile dbf will be change
154. nodes defining paths from the origin to the destination Description of a Sample Network The sample grid network 9GRD depicted in Figure 1 consists of 9 nodes and 14 links There are 6 traffic analysis zones TAZs all shaded nodes nodes 1 through 6 and 9 O D pairs To synthesize observed traffic volumes it is assumed that the true O D trip table is available as shown below Table 1 Network characteristics and synthesized link volumes are summarized in Table 2 Table 1 True trip table for 9GRD network From To 4 5 6 1 120 150 100 2 130 200 90 3 80 180 110 Table 2 Link characteristics and observed volumes ANode B Node Capacity Speed Length 2 1 2 280 00 1 00 2 00 124 00 1 3 290 00 1 00 1 50 137 00 1 12 280 00 1 00 3 00 109 00 2 11 280 00 1 00 1 00 77 00 2 12 600 00 1 00 1 00 467 00 3 12 500 00 1 00 2 00 212 00 3 13 400 00 1 00 1 00 295 00 4 6 300 00 1 00 1 00 50 00 5 6 220 00 1 00 1 00 165 00 11 4 300 00 1 00 2 00 77 00 12 4 500 00 1 00 1 50 303 00 12 5 700 00 1 00 1 00 400 00 12 6 250 00 1 00 2 00 85 00 13 5 350 00 1 00 1 00 295 00 52 Node and Link Numbering Scheme Node numbering scheme must follow the requirement of Visual PFE as stated below TAZs origins or destinations must be numbered with a smaller ID compared to all other intermediate nodes e g road intersections Similarly links also need to be numbered according to a certain scheme format stated in the manual By re
155. o approximate the temporal traffic evolution Specifically residual queues generated in previous periods must be processed in subsequent periods The temporal overloading of links is captured because the effective link capacity may be reduced by residual queues from predecessor periods Let V 1 represent the vector of equilibrium queues generated at time t 1 we have the following time dependent model TD BSUE min f Ct fe nfe 1 0 5v Dvi ae subject to Af lt Cv Vea 3 26 CHAPTER 3 LPFE FORMULATION AND ALGORITHM 20 Mite Sa 3 27 Each time period of a dynamic assignment problem is thus represented by a steady state assignment problem as described by TD BSUE where the subscript t denotes the index of time period The structure of TD BSUE is similar to RBSUE except that residual queues from the last time period appears in the right hand side of Constraints 3 21 As mentioned the role of 4 is to reduce link capacity in the current period This approximation roughly captures the temporal flow propagation since the residual queues are processed before the new arrivals and new queues are only formed when the reduced capacities are exceeded 3 2 Logit Path Flow Estimator Now we turn to the formulation of the logit path flow estimator LPFE LPFE derives path flows hence an estimation of O D demands using a mathematical program similar to logit assignment models in structure The major difference is
156. o 100 Even for the scenario of freeway links only which performed unsatisfactorily before TDC 78 15 the TDC becomes 102 27 with a CHAPTER 6 CASE STUDIES 96 disturbed historical O D table RMSE OD is reduced significantly too with the included historical O D information For all scenarios except the one using efficient links the RMSE _ODs are all below 60velVhr For the efficient link scenarios the RMSE _OD also shows a dramatic drop from 706 89veb hr to 343 23vel hr although it is still greater than the RMSE OD of the historical O D flows itself 110 41 vebv hr The change of RMSE Link in presence of O D information is different they increase instead of decrease in all cases As shown in algorithm IBA for E LPFE SUB the checking of O D constraints always follows after that of link constraints As a result the algorithm might favor the consistency of O D constraints to that of link constraints In short the estimation results of all scenarios are substantially improved when a historical O D trip table is included as inputs Note that the estimated result based on historical O D trip table and 267 links all measured links does not show significant difference from the result obtained by the historical O D trip table and 27 links freeway links In other words for this network we can get a pretty good estimation result by making use of a small set of the link counts as well as historical O D flows Note that the historical
157. o improvement iterations is attained a boolean value bool ReachError test if an error is encountered a boolean value bool ReachUser test if the solution process is terminated externally most likely by a terminal user Return a boolean value Bool ReachUser test if the solution process is terminated externally most likely by a terminal user Return a boolean value Operations TERMFLAGS Solve the underlying operation Call this function to solve the optimization program associated with the class Return The termination reason of the solution process int SolveSubProblem solve the sub problem OFV will be automatically updated using the OFV obtained from sub problem Return 0 if solving succeeds 1 otherwise int SolveAuxProblem solve the auxiliary problem Return 0 if solving succeeds otherwise int ExportPar parFile write algorithmic parameters e g maxMainIter convCriterion etc into a file named parFile alg Return 0 if succeeds 1 otherwise string parFile a string specifying the output file name int ReadPar parFile reading parameters from a disk file named parFile alg Return if succeeds 1 otherwise string parFile astring specifying the input file name void ImportDynamicMem rhs import data members pertinent to the CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 45 solution process such as OFV convIndicator etc from a given algorithm object Re
158. o that the shortest path algorithm would be in favor disfavor the choice of paths containing associated links This idea is exhibited in the following column generation algorithm CGA ALGORITHM CGA Step 0 Initialization Set iteration index i 0 xa OVa A ta ta 0 Va Au Compute shortest paths for all O D pairs and build path link incidence matrix A accordingly Set K as the number of shortest paths Step 1 Solve the restricted master problem RMP Call Algorithm DDAG to get the current path and link solutions Step 2 Column generation Step 2 1 Update link costs For each link a Ay ta taxi Ma For each link a Ao if Xa l Oa lt Xa Xa l Ya ta ta CHAPTER 3 LPFE FORMULATION AND ALGORITHM 35 elseif Xa gt Xa 1 Ya ta ta t A t else ta max ta 27 0 Step 2 2 Compute shortest paths for all O D pairs based on updated link travel times t expand the matrix A with new paths Step 3 Convergence test Set i i 1 calculate the current number of shortest paths Ki tf K K K lt el stop otherwise return to Step 1 Algorithm CGA terminates when the number of new generated paths is small enough implying that the matrix A is not changing much with the few new columns In Step2 1 link travel times are modified by the corresponding multipliers For unmeasured links this means that the queuing delay is taken into consideration On measured links link costs are reduced by A w
159. of Spread is that it facilitates all of the typical spreadsheet functions with a dimension limitation 1 million columns by 1 million rows that is unlikely to be violated by any OD tables Visual PFE contains codes that process the PFE CSV outputs and formulate the spreadsheets stored and displayed with Spread Once a spreadsheet is created in Spread it can be saved as a Microsoft Excel file Table 2 shows the association between the original PFE CSV outputs and the formatted Spread tables Table 2 LPFE Output Files to Spread Tables LPFE Output Files Converted Spread Table est OD table pfp Path table 35 Appendix II Visual PFE Visual PFE 1 0 A Quick Start Tutorial June 2006 Visual PFE and Visual PFE TD are authored at the Utah State University Copyright application for Visual PFE and Visual PFE TD is currently in process Please do not quote or reference the names without the authors permission A Quick Start Tutorial This tutorial is designed to give users the essential instruction to begin using Visual PFE for OD estimation in a timely fashion The tutorial uses step by step examples to help users become familiar with the GUIs and the functions of the program At the end an example is provided to show users how to prepare the input network data In this tutorial you will learn how to e Estimate OD trip tables for a particular network e Navigate through the Map and Scatter Plot Win
160. ogram then executes it to solve specified problems and finally visually displays outputs Although it is not convenient the console program LPFE can also be independently used for testing purpose The usage of LPFE is briefly summarized in the following LPFE LPFE h or LPFE H Print help message This command will also produce a file Ipfe hlp that explains how CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 60 to set up parameters in Ipfe par LPFEnor LPFEN Create a default Ipfe par file LPFE par is a required input file that specifies important control parameters such as input and output file names the dispersion factor etc It has to be placed in the same folder as LPFE exe Users need to specify the parameters in this file according to their own needs Missing the file will lead to running error Figure 4 3 shows an example Ipfe par file LPFE aor LPFE A Create a default algorithm parameter file alg This file include parameters that affect algorithmic performance Its details will be explained in Appendix A LPFE ASN or LPFE asn Perform logit traffic assignment A hypothetical O D estimation scenario can be produced based on assignment results Specifically the link flows obtained from assignment will be used to produce observed link traffic counts required for estimation problems LPFE EST LPFE est or LPFE Perform logit O D estimation Input File Name EXAMPLE est danet Input file format NE
161. on Yale University Press New Haven Connecticut Bell M G H 1983 The estimation of an origin destination matrix from traffic counts Transportation Science 17 198 217 Bell M G H 1991a The estimation of origin destination matrices by constrained generalized least squares Transportation Research 25B 13 22 Bell M G H 19915 The real time estimation of origin destination flows in the presence of platoon dispersion Transportation Research 25B 115 125 Bell M G H amp Grosso S 1998 The path flow estimator as a network observer Traffic Engineering and Control pp 540 549 Bell M G H amp Shield C M 1995 A log linear model for path flow estimation Proceedings of the Fourth Internatial Conference on the Application of Advance technologies in Transporation Engineering Capri pp 695 699 Bell M G H Shield C M Busch F amp Kruse K 1997 A stochastic user equilibrium path flow estimator Transportation Research 5C 197 210 Brenninger Gthe M Jrnsten K O amp Lundgren J T 1989 Estimation of origin destination matrices from traffic counts using multi objective programming formulations Transportation Research 23B 257 269 BIBLIOGRAPHY 117 Cascetta E 1984 Estimation of trip matrices from traffic counts and survey data a generalized least squares estimator Transportation Research 18B 289 299 Cascetta E Inaudi D
162. on results This is mainly due to the fact that the algorithm always searches the corner points instead of the interior of the enlarged feasible region Users therefore do not need to provide error bounds for the traffic counts e As shown in the time dependent case it becomes more difficult to accurately reproduce measured link traffic counts as a network gets more congested However the quality of estimated O D trip rates is not substantially affected by congestion levels Further the formation and dissipation of queues are captured reasonably well by TD LPFE 7 2 Future Work Our studies indicate that besides the number of measurement locations the location CHAPTER 7 CONCLUSIONS 115 of the loop detectors and the network topology seem to substantially affect the quality of the estimates Thus some guidelines should be established to optimally pick measurement locations Such a sensor location problem can be formulated in two ways either seeking a deployment plan with a minimum number of sensors to achieve a given threshold of estimation quality or given a number of sensors finding a deployment plan that optimize the estimates A major limitation of the implemented PFE is its capability of replicating realistic dynamic traffic phenomena After all time dependent PFE is essentially a static model The simplification employed in PFE i e transforming a dynamic problem into a sequence of static problems only works for relatively coar
163. onstructor Return none ENUM at the type of solution algorithm bool ep whether or not enumerate all paths double t dispersion parameter CLASS CSTAP B PARENT CLASS TNM LODE Constructor void CSTAP_B at mt ep t default constructor none ENUM at the type of solution algorithm only applies to the time dependent case ENUM mt the type of sub problem bool ep whether or not enumerate all paths double t dispersion parameter CLASS CSTAP_B_TD PARENT CLASS CSTAP_B Constructor void CSTAP_B_TD at ep t default constructor ENUM at the type of solution algorithm bool ep whether or not enumerate all paths double t dispersion parameter CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 58 4 3 Class Library and Its Usage All the twenty one classes can be complied as a static class library mat lib to facilitate various applications In this section we first discuss how to make use of the class library at a programming level then introduce two primitive user interfaces developed based on the library 4 3 1 Use mat lib in programming With the class library prepared it is easy to write a piece of code to solve either a logit assignment or an O D estimation problem Figure 4 2 provides an example for solving a steady state LPFE First the main interface mat h has to be included to get access to class definitions as shown in the first line of Figure 4 2 We also include the interface tnm h for
164. or O D observations This file is optional The HOMO format of NetName ter is same as project ler thus its description is ignored here APPENDIX I There are N identical blocks after the first block each corresponds to an link 271 6 Table I 8 A description of the file project obs Block 1 1 row Field 1 Field 2 Row 1 Field 1 Field 2 Field 3 Row2 Multiple fields Float SCC ange Fel ds Type Description Integer Number of links 11 Integer Number of time intervals Integer Link ID Integer Starting node ID Integer Ending node ID Each field i corresponds to the observed link traffic counts at the time interval i They can be put in more than one rows Block 1 _ _ Jo Block associated with link 1 1 T 2 9 54 28 62 38 16 38 16 28 62 9 54 2 1 11 40 26 120 78 3 2 1 60 75 182 25 4 2 3 10 08 30 24 6 3 2 D348 172129 7 3 4 30 45 91 39 8 3 13 21 8875 57 4225 9 4 3 36 26 106 82 10 4 5 22 275 66 825 se 4 14 5 28 15 84 161 04 243 40 32 2295 121 8 TOeA9 142 1 89 1 21 412 161 04 40 32 2299 121 8 75 19 142 1 21 12 120 78 40 26 182 25 60 75 30 24 10 08 172 125 D7 2 B19 9139 30 45 57 4225 21 8875 106 82 36 26 66 825 2224S 15 84 5 28 Figure I 9 An example of the file project obs APPENDIX I 12 Table I 9 A description of the file project tar ___Range Fields Type Description Block 1 1 row
165. ound MEASURED MSDLB MSDUB g E Ko 1 Help Close Figure 11 Identify Features Window 18 Label Features Window Features on a map layer can be labeled with attributes of the layer For example each link on the network layer can be labeled with link ID Feature labeling is set up through the Label Feature Window Figure 12 To activate the Label Feature Window first make the layer active by clicking at the name of the layer in the legend then press the tool button Label Features Once the form appears a particular attribute can be selected for labeling and the font for the label can also be adjusted using the Font button Label Features CALPFE Example EST ipfe_ex_t The map window title Ipfe_ex_t _network Labels are based on field 1D The attribute to be labeled te oo toe Figure 12 Label Features Window 19 Class Map Window Features on a map layer can be drawn with different colors and sizes based on values of a particular attribute of the layer For example links on the network layer can be grouped into five classes based on the values of estimated link flows Each class of links will be drawn with the same color and width Class mapping is set up through the Class Map Window Figure 13 To activate the Class Map Window first make the layer active by clicking at the name of the layer in the legend then press the tool button Class Map Once the form appears a particular attribute
166. own the Identify button the mouse cursor will turn into the information symbol Click ata feature of the layer will open the Identify Feature Window showing all the attributes of the feature identified Figure 11 C PFE_Workbook 3_Exercise_3 9GRD pfe M 9GRD_OD_BOUNDS i Identify Features maf C M 9GAD_DESIRELINES 1 features found fad V 9GRD_OD o Z 9GRD_NETWORK va LINK NO ANODE B_NODE ax 143 67861 ay 53992237 Bx 143 65861 BY 59 90237 LNKGRP 1 LNK_CAP 280 SPEED 1 _ DISTANCE 3 ALPHA 0 15 z KE gt No change Help Update Close Figure 11 Identify Features 14 How to Navigate through the Scatter Plot Window Display Link A scatter plot has the same form as a network map window The navigation functions for the network map also apply to the scatter plot window The only exception is that a scatter plot has one exclusive function the Display Link toolbar button E which allows users to see the location of the link for which a scatter plot point represents To use this function 10 Make the scatter plot window the active window by clicking at the title bar of the scatter plot window 11 Make the 9GRD_SCATTERPLOT layer the active layer by clicking at the name of the layer in the legend area 12 Press down the Display Link button E Move the mouse cursor over the scatter plot and click at a particular scatter plot point 13 The network map window will auto
167. ows Similarly and f denote vector of path travel times and flows respectively It is known that a stable and unique link flow pattern x can be predicted from a traffic assignment model given appropriate assumptions on the traveller s route choice behavior For example if travellers always try to minimize their own travel costs and have perfect information the resulting stable flow pattern is a user equilibrium UE CHAPTER 2 LITERATURE REVIEW 5 pattern Thus a relationship between O D trip table q4 and flow pattern x can be established as follows De Dy Phas x4 Va r s 2 1 where p denotes the proportion of trips between O D pair rs using link a In matrix notation Equation 2 1 becomes 2 2 P is termed as assignment matrix because it is determined from a traffic assignment If we assume the relationship depicted in Equation 2 2 holds in a real world q can be inferred from an observation of x e g traffic counts measured at loop detectors denoted as X Note that we have where is a vector representing measurement errors This is the basic idea of O D estimation from traffic counts Another way to relate observed link flows to O D demands is using path flows as an intermediate We have the following two relationships for an equilibrium flow pattern x So x Va Ayk Kns f s k 2 4 I k drs Vk e K rs k 2 5 or in matrix notation Af x 2 6 Mf q 2 7 O D estimation methods base
168. plot_axis dbf il Bote ex_t1_scatterplot_axis shp il F7 LPFE_EX_T1_SCATTERPLOT_AMS SHP j Fi g1 p p re ex_t1_scatterplot_marker dbf pfe ex_t1_scatterplot_marker shp ipfe ex_t1_scatterplot_marker shx F7 LPFE_EX TI _SCATTERPLOT_MARKER SHP Figure 25 Shapefiles and the Scatter Plot Layers ESRI MapObjects MapObjects is a set of mapping software components that let users add GIS maps to software applications MapObjects comprises an ActiveX control OCX called the Map control and a set of over forty five ActiveX Automation objects In Visual PFE a map control is used to display the shpafiles created by the ArcViewShapeFile component The map control facilitates all of the GIS functions for the converted shapefiles Another OCX control is added to a map form to display the legends of different map layers The legend control is internally connected to the map control A layer can be made active through the legend control On the active layer labels and thematic mapping can be applied to features on the layer For example networks links can be varied by colors and width based on estimated link flow Bar charts can be applied to display the varying magnitude of production and attraction at the origins and destinations 34 FarPoint Spread Spread by the FarPoint Technologies is a software component built to Microsoft s latest NET software architecture Spread is used to create spreadsheet applications The strength
169. ports 28 Creating and Editing Text Files A Report Window is actually a rich text box that can serve as a text editor User can use the Report Window to edit or create LPFE input network data To edit an existing text file go to the menu item File Open and select one of the LPFE input text files To create a new file go to the menu item File New and a blank Report Window will be opened as a text editor The menu item Edit contains common text editing tools such as Undo Cut Copy Paste and Select All Once a new network data text file is created the file can be saved by going to the menu item File Save Text The Save As dialog box will open for users to enter a desired file name for the text file Scenario Comparison Window If multiple estimation runs have been done for a network all of the previous results can be opened and compared at the same time The comparison is setup via the GUI in Figure 21 x Compare Estimated Networks Click to browse data folders ee Te CALPFE Example EST Select from the followings to compare Available Networks Figure 21 Scenario Comparison Window 29 To compare different results click at the Browse button and go to the folder where all estimation results are stored Once the data folder is selected all available results will be shown in the corresponding list boxes Select from the lists and click OK All the selected result items will be open in corresponding windows Note that t
170. r Plot windows created in example 1 How to Make a Window Active 1 Click at the title bar of the Network Map Window to make it the active window see Figure 6 The map window should appear on top of every other opened window See for yourself how the titles of the OD table scatter plot path table and report all include the name and the file path of the network 1 e the title of the fist window Visual PFE File Edit Yiew Network Table Estimate Diagnose Windows Help e ie 77 A GR Scatter Plot_ C PFE_Workbook 3_Exercise_3 9GRD pfe Ma Report_C PFE_Workbook 3_Exercise_3 9GRD pfe k f O D_ C PFE_Workbook 3_Exercise_3 9GRD pfe N O C PFE_Workbook 3_Exercise_3 9GRD pfe viTom scrp_op_BouNps o M SGRD_DESIRELINES Tor al qo 4 9GRD_op E To 2D D N A Z 9GRD_NETWORK nd Figure 6 Active Window How to Make a Layer Active 2 You can make the layer 9GRD_ NETWORK active by clicking at the title of in the legend area A thin line will appear underneath the layer name in the legend indicating the current active layer Figure 7 C PFE_Workbook 3_Exercise_3 9GRD pfe 9GRD_OD_BOUNDS a SGRD_DESIRELINES vw MV IGRD_OD o V SGRD_NETWORK wv Figure 7 Legend and Active Layer How to Make a Layer Invisible 3 You can make a layer invisible by un checking the check box next to the name of the layer in the legend For example un checking the legend of the 9
171. r network Figure 6 16 shows that the estimated link flow profile replicates exactly the true link flow profile with RMSE Link 0 In addition the total amount of demand is captured accurately too with TDC 100 However Figure 6 15 indicates that there are discrepancies between the estimated O D flows and the true O D flows with RMSE OD 71 6507 This is expected because for a certain link flow profile in a linear network there can be more than one path flow solutions corresponding to it What LPFE predicts is just one of the path solutions which may not be the true one Such errors are of un intrinsic nature due to the under determined property of O D estimation problems 6 3 3 The case with a ring network The tested ring network is made up of 16 nodes four origins and four destinations 16 links and 16 O D pairs as illustrated in Figure 6 17 Figure 6 18 provides the true O D flows The estimated O D flow profile and the link flow profile are shown in Figure 6 19 and Figure 6 20 CHAPTER 6 CASE STUDIES 87 Estimated True O D flow Number of O D pairs Of various deviation ee a 3 ee 1 gt Ce 3 E io NS oa Sf 1 E origin destination demand origin destination demand 10 11 40 14 11 140 10 13 20 14 13 200 sy 10 15 125 14 15 300 8 D lt 10 9 34 14 9 200 N y a I aL A AN p 11 50 16 11 100 ff L b 22 13 100 16 13 50 GC 2 Se sd 15 130 16 15 20 10
172. raffic assignment in our case Perturbations can be further introduced to emulate measurement errors Similarly one can obtain a historical or observed O D table by applying a perturbation to the predetermined O D table Using these inputs we can evaluate the performance of LPFE by comparing the estimated O D link flows to those presumed to be known as true The measurements of effectiveness MOE adopted in our evaluation framework include 1 TDC total demand captured 2 RMSE OD root mean square error of estimated OD flows 3 RMSE _ Link root mean square error of estimated link flows Mathematically These MOEs can be expressed as CHAPTER 6 CASE STUDIES 77 TDC Total Demand Captured 2 M 2 Dp p l 6 1 M OM a D Y RMSE_OD RMSE of O D flows 4 7 6 2 N _ D X Xx RMSE Link RMSE of link flows 4 T 6 3 where Dp p 1 M_are the estimated O D flows D p 1 M_are the true O D flows X k 1 N are the estimated link flows Xr k 1 M are the true link flows TDC measures the percentage that the total true O D flows are captured by estimated O D flows Thus a TDC closer to 1 may suggest a better estimate RMSE _ OD depicts the average variation of the estimated O D flows with respect to the true values The smaller the RMSE OD the better the spatial structure of travel demands is captured Similarly the value of RMSE Link measures the extent to which
173. re o o Uod 0 0 j Heuristic Error Bound OK Cancel Help Figure 2 Manual Adjustment 8 After the run is completed the dialog box informing the status of the estimation appears Figure 3 VisualP FE Figure 3 Status of Estimation Remarks If errors occur during the estimation the dialog box will inform the users the specific errors and the suggested solution At the end of this example technical notes about the estimation methods the parameters and the potential error messages are provided for your reference For complete coverage of the technical details on PFE please refer to the PFE Workbook 9 Visual PFE will display the network and estimated O D trip table Figure 4 l O D_SC PFE_Workbook 3_Exercise_3 9GRD pfe C PFE_Workbook 3_Exercise_3 9GRD pfe 9GRD_OD_BOUNDS a 9GRD_DESIRELINES yw M S3GRD_OD a SGRD_NETWORK n Figure 4 Network and Estimated O D Trip Table 10 Open the scatter plot and the estimation report Figure 5 a Make the network map window the active window click on the title bar of the map window b Select Diagnose gt gt Statistics Select Diagnose gt gt Graphs d Select Windows gt gt Tile Visual PFE File Edit View Network Table Estimate Diagnose Windows Help rt elena amp Report_K PFE_Workbook 3_Exercise_3 9GRD pfe V 9GRD_SCATTERPLOT_MAF Number of link observations 14 a Number of target O D flows 0 17 9G
174. rk Create see Figure 43 Enter the followings Network Topology File PFE_workbook 2_Exercise_2 9GRD dbf Trip Table Structure File PFE_workbook 2_Exercise_2 9GRDOD dbf User specified Path File PFE_ workbook 2_Exercise_2 9GRD_Path dbf The largest node ID of TAZs 6 Name of network 9GRD Location of network being created PFE_workbook 2_Exercise_2 46 Creating Network SEE Network Topology File C PFE_Workbook 2_Exercise_2 9GRD dbf Browse Trip Table Structure File Optional C PFE_Workbook 2_Exercise_2 SGRDOD dbf Browse Path specific File Optional C PFE_Workbook 2_Exercise_2 9GRD_Path dbf Browse Location of Network being built Ic PFE_Workbook 2_Exercise_2 Browse Network Name MyTest Largest Node ID among Zones ja OK Cancel Figure 43 Creat Network Feature 3 In Visual PFE go to menu item File Open and open the pfe pfp and pfx files you just created 47 The pfe File 143 678615 59 922371 143 658615 59 922371 143 678615 59 902371 143 638615 59 902371 143 658615 59 882371 143 638615 59 882371 143 638615 59 922371 143 658615 59 902371 143 678615 59 882371 280 00 1 00 290 00 1 00 280 00 1 00 280 00 1 00 600 00 1 00 500 00 1 00 400 00 1 00 300 00 1 00 220 00 1 00 300 00 1 00 500 00 1 00 700 00 1 00 250 00 1 00 350 00 1 00 aAganaARARAMDOWANAWND ODWDANUOTARWWNDY HH H Figure 44 PFE File R
175. rors 20 sets of hypothetical measured link flows are generated in a similar way as in the previous section we assume all links are measured and only consider four upper bounds i e 10 20 30 40 RMSE Links for all the scenarios are listed in Table 6 2 The historical O D trip table in these scenarios is the same as the one used in Section 6 4 2 OD RMSE OD 110 41veh hr The MOEs are shown in Figures 6 35 6 36 and 6 37 CHAPTER 6 CASE STUDIES Table 6 2 RMSE_Links for hypothetical measured link flows uniform error RMSE_Link veh hr 10 20 30 244 49 296 12 337 95 330 33 354 95 287 65 352 61 40 105 00 103 00 101 00 TDC 99 00 z 97 00 95 00 0 00 100 00 200 00 300 00 400 00 500 00 600 00 RMSE of the measured link flows veh hr Figure 6 35 TDCs for scenarios with different link flow errors CHAPTER 6 CASE STUDIES 103 90 00 80 00 70 00 60 00 s 50 00 ee sp To 40 00 lt 20 00 RMSE of the estimated OD veh hr 10 00 0 00 100 00 200 00 300 00 400 00 500 00 600 00 RMSE of the measured link flows veh hr Figure 6 36 RMSE_ODs for scenarios with different link flow errors 600 500 400 300 4 200 we 100 RMSE of the estimated link flows veh hr 0 00 100 00 200 00 300 00 400 00 500
176. rovide up to date and time dependent traffic information The path flow estimator PFE considered in this research has several appealing features First it formulates the estimation problem as a one level convex optimization problem and thus avoids the bi level programming structure which requires to repeatedly solve traffic assignment problems and does not ensure global optimality and convergence Second PFE properly takes into account users route choice behavior consistent with the stochastic user equilibrium Finally PFE provides a reasonable compromise to cope with traffic dynamics i e decomposing a dynamic problem to a sequence of static problems through carrying queues over different times This research presented several improvements over the original PFE and implemented the algorithms into a software tool with a friendly GIS based user interface In this chapter we summarize the major findings of this research and provide some thoughts on the follow up research work 7 1 Major Findings Regarding the Performance of LPFE Based on extensive numerical studies we made the following observations and findings Improper algorithmic parameter settings may lead to either poor estimation results or high computational cost If default parameters do not produce satisfactory results users are suggested try greater maximum number of iterations and maximum number of zigzagging iterations combined with tighter CHAPTER 7 CONCLUSIONS 114
177. rs choose the minimum cost path with certain probability Stochastic traffic assignment models can further be classified as multinomial logit and multinomial probit assignment models Probit models are theoretically sound but incur great computational obstacles that hinder its application particularly for large networks it requires either Monte Carlo techniques or path enumeration e g Daganzo amp Sheffi 1977 Powell amp Sheffi 1982 On the other hand the logit model is known to have some undesirable properties such as the IIA property but is much more tractable both analytically and computationally therefore is the favored probability model used in stochastic traffic assignment 3 1 1 The static case The most widely used logit stochastic user equilibrium SUE model is due to Fisk 1980 who added a scaled path entropy term into the objective function of the Beckmann formulation of DUE Deterministic User Equilibrium Beckmann McGuire amp Winsten 1956 Fisk s model takes the following mathematical form _ FSUE CHAPTER 3 LPFE FORMULATION AND ALGORITHM 16 min gt f now D fo Un f D 3 1 subject to Sofi as Yre Rs Sk e K k 3 2 Ip ey roak Z Xa Va A k eK reRseS pm 3 3 t 20 Vk EK reRseS 3 4 where 0 is called a dispersion parameter which represents traveller s sensitivity to path costs It is shown that the optimality condition of this mathematical program is equivalent to the log
178. s Please do not quote or reference the names without the authors permission Table of Contents TOC CHO nnen aE day ddeca was tad evan AE A EAEE sda AA a aE TES EER S 4 How to Wise Chis Manial access aneren a A S E T 4 Installing Visual PFE TD on i a E E dans A eae 5 Gr phical UserInterfaces aa A R a E e a aS 6 M ltiple Document Int rfac ss nessen n e e Sees ie 6 The M n Window sss secs seccansvasjicces ain esa e a E A E T RR 7 Ma Me A NS 7 IREI loti SE E E NE A TE E 9 Algorithm and Parameter Input Windows cccceesceeesceceeceeceeeeeceseeeceeeeeeeeeeneeeees 11 Create Shapefiles and Tables Window c ccessccseseceessececseeeecesececseeeecseeeecseeeeseeeees 14 Network Map Wace cca ane ease sec aaa i ceeeees 16 Identity Feat res WaT OO We goa castes sc ace ssecaueasspsessesavseedaiae cc aden SEE TE S 18 Label Features WINdOW Gisex ssc teyeiicnasa sees deeey sus deastucsgees ieee oie e E iaasa eiea i eie 19 Class Map Window isccsseciesececdiscavaisi nason ar ana O E TE E TAAS 20 Pa Gard OV a eae ee 21 Scatter Plot VV ILO cS ie e E acne sin heels ea A E EEO 22 LK SP to Map rrinnnno srann nnn dea R VA G TA 23 COED TAB Less WNdOW isn e Gece waa a es aca ae aca nudes Maes agar Aa EEA does ane iie 24 OD C lor WW INO W serie eaae enan E de Meee Aaah loa a at ate 25 Reduced OD Tabe ME AE E EE RRS 26 Lik OD Fable 00 Mapin rinta n a shes a a 26 Saye an OD Table as Excel File sscssrnscsssnnssrnenesansinin iena inani
179. s such as historical O D data and subpath information obtained from section related measurements 3 measurement errors and 4 network topology Based on numerical experiments guidelines are drawn for the applicability and optimal setting of LPFE under different circumstances Discussions on future research are also given e develop a graphic user interface GUI for LPFE A LPFE GUI was built using Microsoft Visual Basic and commercially available software component The end result Visual PFE and Visual PFE TD is an integrated software suite that combines the Path Flow Estimator PFE with other software components to facilitate the estimation visualization and refinement of Origin Destination OD trip tables with user friendly Graphical User Interfaces GUI This report is organized into six chapters Chapter 2 reviews the steady state and time dependent O D estimation methods Chapter 3 introduces the mathematical formulations and solution algorithms of the original LPFE and its extension An object oriented programming framework of LPFE as well as implementation details is provided in Chapter 4 and Chapter 5 describes the Graphic User Interface GUI of LPFE Numerical experiments are reported in Chapter 6 Finally Chapter 7 provides conclusions and recommendations for future research CHAPTER 2 LITERATURE REVIEW 4 Chapter 2 Related Literature O D matrix estimation methods were first developed in a static context They estimat
180. s useful structural information about O D flow patterns that can greatly improve estimation quality Moreover the direct observation of O D flows becomes increasingly feasible thanks to recent technological innovations e g section related measurement based on vehicle re identification Although such observations can only cover a small portion of O D entries in most cases the up to date information provided by them can still be of great help To account for available O D information we assume that a partial O D table qo exists which is obtained from either a historical O D table or real time section related measurements Recall that in assignment problems O D demands q are related to path flows f through conservation law q Mf For a partially available O D table we have the following relationship MSMs 3 51 where Mo contains rows of M that correspond to observed O D entries Adding 3 51 into LPFE as constraints will enforce the estimated flow pattern to replicate these additional observations However given the O D measurements may contain errors it is better to introduce confidence levels as in link measurements Thus the following constraints will be considered Mof lt qo Jo No 3 52 CHAPTER 3 LPFE FORMULATION AND ALGORITHM 25 Mof gt o Jo Qo 3 53 Similarly Jo No and Po are lo x lo diagonal matrices lo is the number of observed O D entries l1 0 ni 0 gi o0 Jo pa 0 Yo oe 0
181. se double theta the dispersion parameter Overridables int InitPathFlow Compute path flows using the logit choice model based on the initial values of multipliers CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 49 Return 0 if succeeds non zero value otherwise double Get VolLinkMuChange link Compute the required change of a multiplier associated with a constraint of link measurement Return the change of the multiplier ENUM link a pointer of a TNM_SLINK object double GetCapLinkMuChange link Compute the required change of a multiplier associated with a constraint of link capacity Return the change of the multiplier ENUM link a pointer of a TNM_SLINK object CLASS MPEN_MC PARENT CLASS TNM_MPEN Constructor void MPEN_MC theta default constructor in which costCoef is set to 1 0 Return none double theta the dispersion parameter Os CLASS MPEN_DC PARENT CLASS TNM_MPEN Constructor void MPEN_DC theta default constructor Return none double theta the dispersion parameter 0 Operations void UpdateODMultiplier Update path and link flows according to the multiplier associated with the flow conservation constraint Return none CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 50 CLASS MPEN_DC_MCMPEN_DC Constructor void MPEN_DC_MC theta default constructor in which costCoef is set to 1 0 Return none double theta the dispersion parameter 0 TNM_LPF
182. se time resolution i e longer time intervals Note that a trip is assumed to complete within the time interval it departs from the origin and this is true only when the corresponding time period is long enough Only a true dynamic traffic flow model can remove this drawback Nevertheless in studies that need a finer time resolution such as in a micro simulation application TD LPFE can still be used to obtain an initial estimate of the time dependent O D trip tables and use these estimates as the base O D tables can speed up the convergence of the O D estimators that come with the simulation tools We have applied this procedure to the estimation of O D tables for Paramics applications and obtained satisfactory results BIBLIOGRAPHY 116 Bibliography Ashok K 1996 Estimation and Prediction of Time Dependent Origin Destination Flows Ph d thesis Massachusetts Institute of Technology Cambridge MA Ashok K amp Ben Akiva M 1993 Dynamic origin destination matrix estimation and prediction for real time traffic management systems In Proceedings of 12th International Symposium on the Theory of Traffic Flow and Transportation pp 465 484 Ashok K amp Ben Akiva M 2000 Alternative approaches for real time estimation and prediction of time dependent origin destination flows Transportation Science 34 21 36 Beckmann M McGuire C B amp Winsten C B 1956 Studies in the Economics of Transportati
183. sidered The MOEs of the estimation results are CHAPTER 6 CASE STUDIES shown in Figures 6 41 6 42 and 6 43 TDC 105 103 101 99 97 95 00 00 00 00 00 00 108 RMSE of the estimated OD veh hr 120 100 80 60 40 20 0 00 Estimated OD not consider link flow error A Estimated OD consider link flow error 2 4 100 Be A A s Fe AA A A A A A A A 100 00 200 00 300 00 400 00 500 00 600 00 RMSE of the measured link flows veh hr Figure 6 41 TDCs for scenarios with different settings on the consideration of link flow errors Estimated OD not consider link flow error A A A A A Estimated OD consider link flow error A A l oe A A A R x A i hd Ta 0 00 50 00 100 00 150 00 200 00 250 00 300 00 350 00 400 00 RMSE of the measured link flows veh hr Figure 6 42 RMSE_ODs for scenarios with different settings on the consideration of link flow errors CHAPTER 6 CASE STUDIES 109 450 400 Estimated OD not consider link flow error A 350 7 A Estimated OD consider link flow error re 300 A 250 A Ae 200 150 re 100 50 o gt RMSE of the estimated link flows veh hr 0 00 50 00 100 00 150 00 200 00 250 00 300 00 350 00 400 00 RMSE of the measured link
184. sressreseeseresee 15 Figure 9 Create Shapefiles Window for Previously Estimated Outputs eee 15 Figure 10 Network Map WindoW eeesesseeseseseseeseeseessrserssresseseresressessresrensesseesreesreseeseresee 16 Figure 11 Identify Features W 1d Oe 3 6 slack eae Wants se elas saeco ceeded 18 Figure 12 Label Features Window sad 5 lt c1o cac ccsies scat taeetioice caus aD NETSE a aa E as 19 Figure 13 Class Map Window sssesseeseseeseeseessesreeseeseseresreseserssressesetesrensesstesesseeseeseeeste 20 Figure 14 Bar Chart Window cvssccsisisepsascisaascaea tesvaasasa cactus decaen shes cdeatucsnetesenceavasoesneadperacees 21 Figure 15 Scatter Plot Windows ie nicia aos eae he aa ease iced es 22 Figure 16 OD lt Table Wi wigan sea 24 Figure 17 OD Color Window ics sisi seeceenetetideenhiccin snini 25 Figure 18 Reduced OD Table VieW eeeseeeeseeeseseeesrseresressrserssressessrerressessresresseeseseeesee 26 Figure 19 Path Table WINdOW pisesnccisojoonin a n A NE 27 Figure 20 Repott WindOW aers ae E ies he ES OETA Oi hada 28 Figure 21 Scenario Comparison WindoW esesseeesesesesesresseserssressereresressesseesreesreseeseresee 29 Figure 22 Windows Help isssnunusiioisinssininninina at akan dened euseeaalens 30 Figure 23 Visual PFE TD Software Component 000 ce eeeesceeeeeeeneecneeceeeeeeeeeeaeeenaeens 31 Figure 24 Shapefiles and Network Map Layers 0 0 eeseesseceseceseeeenceceeeceseeeseeeeneeenaeees 33 Figure 25 Shapefiles and
185. ssed in different ways A commonly used approach is to consider link measurements in the objective function as follows min JS f ta w dw LE nf D Af Xo T7 Af Xo 3 47 subject to Equations 3 30 where T is the covariance matrix of link measurements Although this approach incorporates measurement errors naturally it may introduce numerical instabilities in the logit path choice model Note that the exponential of link measurement mismatch Aof Xo can lead to very large path flows Such a problem arises often in the earlier stage in a numerical solution procedure An alternative is to change constraints so that the link counts fall into a range of values rather than equal to an exact value i e mn X f ta w dw L nf 1 3 48 subject to Equation 3 30 and Aof lt Ko lo Yo 3 49 Aof Ko Io o 3 50 where I Yo and o areall IA lxlA diagonal matrices and CHAPTER 3 LPFE FORMULATION AND ALGORITHM 24 1 O yl e 0 l ows 0 I x 0 Yo E 0 Op i 0 Yo 0 66 0 0 0 1 0 0 yhe 0 0 oy Note that yo and o reflect the confidence level of measurements on link do E Ao Obviously a more reliable link measurement will constrain the observed flow within a smaller tolerance while a less reliable measurement will allow a large error range The original LPFE does not exploit existing O D information in its formulation However quite often a historical O D table maintain
186. st block each corresponds to an origin Table I 7 A description of the file project dmd 1 row Field 1 Integer Number of time intervals Field 2 Integer The length of each time interval in seconds Row 1 Field 1 Text Prompt Field 2 Integer ID of origin node Row 2 Field 1 Text Prompt Field 2 Integer ID destination node Each field i corresponds to the demand of the O D pair at the time interval i they can be put in more than one row Block 1 Origin Dest 0 31250 Dest 0 37500 Dest 0 31250 Dest 0 37500 Dest 0 L750 Dest 0 06250 Dest 0 37500 Dest 0 37500 Dest 0 56250 Dest 0 62500 Dest 0 56250 Dest 0 31250 Dest O 06250 Dest 0 06250 Origin Dest 0 Dest 68750 20 22 24 26 28 30 03 02 06 293750 12500 93750 12500 296250 18750 12500 12500 68750 1 87500 68750 93750 18750 218750 06250 1 25000 1 25000 0 93750 0 31250 1 50000 1 50000 1 12500 0 37500 1 25000 1 25000 0 93750 0 31250 1 50000 1 50000 1 12500 0 37500 0 75000 0 75000 0 56250 0 18750 0 25000 0 25000 0 18750 0 06250 1 50000 1 50000 1 12500 0 37500 ee 1 50000 1 50000 1 12500 0 37500 V 2 25000 2 25000 1 68750 0 56250 2 50000 2 50000 1 87500 0 62500 2 25000 2 25000 1 68750 0 56250 1 25000 1 25000 0 93750 0 31250 0 25000 0 25
187. stic scatter plots Link the scatter plots to the network for identification of outliers Create and edit LPFE networks as text files Compare different scenarios How to Use this Manual This manual is designed to explain various functions of the software including instructions for software installation Users of the software are referred to the LPFE User Manual for technical details about the LPFE program and how to prepare the input data The LPFE User Manual can be found in the program folder of LPFE After installing the program users are advised to go through the Introduction and the Graphical User Interfaces sections for knowledge of program functions To get an advanced knowledge of the software users can go through the Technical Specification section of the manual to get an overview of the software components used to build the Visual PFE TD Installing Visual PFE TD Before installing Visual PFE TD the LPFE program needs to be installed first To install LPFE run LPFE_Setup msi Follow the instructions of the set up program to complete the installation After LPFE is installed in the folder where the program files are stored there is a folder called Bin The Bin folder contains the LPFE executable and other Dynamic Linking library DLL files Before running LPFE from Visual PFE TD all of the files in the bin folder need to be copied and pasted to the data folder where the LPFE input network text files are stored
188. stination trip tables Transportation Research 31B 141 157 Sherali H D amp Park T 2001 Estimation of dynamic origin destination trip tables for a general network Transportation Research 35B 217 235 Sherali H D Sivanandan R amp Hobeika A G 1994 A linear programming approach for synthesizing origin destination trip tables from link traffic volumes Transportation Research 28B 213 233 Turnquist M amp Gur Y 1979 Estimation of trip tables from observed link volumes Transportation Research Record 730 295 303 Van Zuylen J H amp Willumsen L G 1980 The most likely trip matrix estimated from traffic counts Transportation Research 14B 281 293 Wardrop J G 1952 Some theoretical aspects of road traffic research Proceedings of the Institute of Civil Engineers Part IT 1 325 378 Willumsen K G 1984 Estimating time dependent trip matrices from traffic counts In Proceedings of the 9th International Symposium on Transportation and Traffic Theory pp 397 411 Willumsen L G 1981 Simplified transport models based traffic counts Transportation 10 257 278 Wu J amp Chang G L 1996 Estimation of time varying origin destination distributions with dynamic screenline flows Transportation Research 30B 277 290 Yang H 1995 Heuristic algorithms for the bilevel origin destination matrix estimation problem Transpor
189. stinations are generated by LPFE as a text file i e the est file The Visual PFE TD program converts the text file and formats it as a spreadsheet using the Spread software component see Technical Specification A resulting OD table is shown in Figure 16 Note that the title of the OD Table Window is also created by prefixing the word O D_ with the title of the corresponding network Map Window fee 0 D_SC LPFE Example EST Ipfe_ex_t1 DER 2s ea aps 18 90 16 52 A B LES ma EEE a pad ay pre 719 e A E a T A_SUM 164 80 173 87 133 04 138 23 185 35 280 00 207 33 188 78 288 50 142 57 198 82 127 11 155 31 162 73 166 62 200 16 51 aft Figure 16 OD Table Window There are three ways to open an OD table Select the OD Table option in the Create Shapefiles and Tables Window e When a network map is the active window go to the menu item Tables Open OD Table e Go to the menu item Diagnostic Compare and select from the available OD Tables 24 OD Color Window The cell colors of the OD table can be adjusted using the OD Color Window Figure 17 To open the OD Color Window first make the OD table the active window go to the menu item Table OD Table Color or click at the toolbar button OD Color Once the OD Color Window is opened the values of OD flows are broken down into four classes Double click at each color block to set up the color After clicking at the Apply button the
190. stributions and makes use of the platoon dispersion model The second approach makes no specific assumption about the form of the travel time distribution thus can be applied for larger networks such as freeway sections Both approaches adopt a constrained weighed least squares method and are solved sequentially Chang and Wu 1994 generalized Bell s model to consider vehicle travel times between each O D pairs more realistically The decision parameters include not only the CHAPTER 2 LITERATURE REVIEW 9 time dependent O D split parameters but also the dynamic assignment parameters The latter is closely related to the time dependent link travel time and introduced to define the proportion of the previous intervals O D flows that arrive at any given exits during some future interval The introduction of dynamic assignment parameters significantly increases the number of state variables to be estimated Thus a simplification is made to assume that all vehicles that reach exit during time are distributed within intervals t nt where ni denotes the number of time intervals that the travel time between O D pair rs at time t will cover If m s is not an integer another interval is added to remove rounding errors To estimate dynamic travel time hence generate proper assignment factors the authors proposed a simple two step method based on the simple speed density volume relationship This further requires the information about mainline
191. t 1 C u D1 ve Step 1 Set Ko K Iteratively check constraints and update path flows Step 1 1 Calculate path flow ft according to Equation 3 55 Set Xt Aft qe Mfr Step 1 2 Foreachlink a Ay compute l Ca Ca vi vi e Inx n Ca vi v s If e gt 0 set H4 Hh e otherwise if Ha gt O set Ua Wa te Update f and Set va Cami If K lt lel set K lel Step 1 3 Foreachlink a Ao compute Int In l ya If e gt 0 set Aat Aast de otherwise if Mae gt 0 set Nat Aor e Update ft Xt and 4 if K lt lel set K lel Step 1 4 Foreachlink a Ao compute Int Inxa 1 67 If e lt O set Aas Aare Qe otherwise if Aas gt 9 set Aan Aate Update ft Xt and 4 if K lt lel set x lel Step 1 5 Foreach O D pair rs for which the target O D information exists Compute e Ing lng 1 nis If e gt 0 set Vist Vist d otherwise if Vist gt 0 set Vist Vente Update ft Xt and qt If lt lel set K lel Step 1 6 For each O D pair rs for which the target O D information exists Compute e Ing ng 1 Pis If e lt 0 set Vist Vise 4 otherwise if Vrs gt 9 set Vrt Vier e Update ft Xt and t If K lt lel set lel Step2 Convergence test Step 2 1 If K a lt stop otherwise go to Step2 2 Step 2 2 If k Ko Kok set a return to Step1 CHAPTER 3 LPFE FORMULATION AND ALG
192. t net APPENDIX I 5 Table I 4 A description of the file project lin Range Fields Type Description Block 1 1 row Field 1 9 Text Prompt Block 2 n rows Field 1 Integer Link id Field2 String Link type this type is of NO use in this project Field 3 Integer Starting node ID Field 4 Integer ending node ID Field 5 float Link length mile Field 6 float Free flow speed mile per hour Field 7 float Capacity vehicle hour lane Field 8 float Holding capacity vehicle mile This value is of NO use in this project Field 9 Integer Number of lanes ID Type From To LEN m FFS m h Cap v h RHOJ v m Lane I WRLK 1 2 1 25 1323 L71 1 2 WRLK 1 11 i 45 1560 164 2 3 WRLK 2 1 1 65 1976 AES 2 4 WRLK 2 3 1 35 1394 175 2 5 WRLK 2 12 1 25 1240 176 2 6 WRLK 3 2 1 65 2252 178 4 7 WRLK 3 4 1 55 1859 176 2 8 WRLK 3 13 1 45 1629 EZS 1 9 WRLK 4 3 1 35 1394 171 2 10 WRLK 4 5 1 55 1582 166 1 LI WRLK 4 14 45 1473 LTS 3 12 WRLK 5 4 55 1622 166 3 13 WRLK 3 6 25 1142 180 2 14 WRLK 5 15 45 1491 175 3 Figure I 4 An example of the file project lin APPENDIX I 6 Table I 5 A description of the file project nod Range Fields ype Description Block 1 1 row Field 1 3 Text Prompt Block 2 n rows Field 1 Integer Node ID String Node type this type is of NO use in this project Integer X coordinate in feet Integer Y coordinate in feet D Type Xcord Ycord 1
193. t the behavior of road users before the estimation Max Iteration the maximum number of iterations allowed for the adjustment of path flows to match observed link volumes The default value recommended is set at 1 000 Note that the algorithm could terminate before 1 000 iterations if it reaches convergence The maximum iteration allowed to set is 100 000 Convergence the criterion used for terminating the PFE The program will check for the maximum change of balancing factors If the maximum change is less than the convergence criterion the program will be terminated The convergence value of 10 is recommended to obtain a reasonable solution within a reasonable computational time A more strict convergence criterion e g smaller value lt 10 can also be used of course with the expense of higher computational time Method to handle inconsistency the method for handling the inconsistency of traffic data e g traffic counts etc in the estimation In the static PFE there are three options available 5 1 Manual adjustment allows the users to manually specify the error for each individual observation i e percentage error through the first PFE network file pfe 5 2 Uniform adjustment uniformly specifics the same measurement error across all observations Percentage error e g 5 needs to be specified by the user in the provided text box see Figure 3 Noted that o The value of percentage error must be positiv
194. t the estimated OD tables to Microsoft Excel Files Change the colors and zoom levels of the OD table cells Interactively display and query OD desire lines Interactively display and query paths between any pair of OD Convert the PFE outputs to GIS files ESRI shapefiles Create thematic maps of network links and traffic analysis zones Generate diagnostic scatter plots Link the scatter plots to the network for identification of outliers Create and edit LPFE networks as text files CHAPTER 5 VISUAL PFE TD 62 Compare different scenarios 5 2 Key Features Visual PFE TD is developed with Microsoft Visual Basic NET It implements Microsoft s Multiple Document Interface MDI software architecture within which multiple windows forms can be created and viewed within the main window The main window is referred to as the MDI parent form and each sub window opened within the MDI parent is called a MDI child form With Visual PFE a MDI child form can take on the form of a map a table a graphic plot or a text document The program functions are controlled using Graphical User Interfaces GUI When multiple result windows are opened in Visual PFE TD the titles of the MDI child windows are formatted in a way that results of the same network and time period can be identified Figure 5 1 shows such an example in which the titles of the OD table scatter plot path table and report all include the name and the file path of the network 1 e th
195. tained Network lpfe_ex has not been built Perform 0 D estimation Current time interval 1 Figure 6 DOS Command Window 13 Create Shapefiles and Tables Window A successful LPFE estimation will create output text files that will be converted by Visual PFE TD for the visualization of the outputs Each LPFE estimation produces OD and link flow estimates for multiple time periods The Create Shapefiles and Tables Window Figure 7 is created to let users choose which time periods and what kinds of results they want to see Once the selection is made multiple windows forms will be opened for the selected time periods Figure 8 The Create Shapefiles Window can be launched for previously estimated outputs for which the shapefiles had not been created To do this go to the menu item Diagnose Create Shapefiles and the Create Shapefiles Window will show up Figure 9 Note that a Browse button is placed next to the input network path label Clicking at the browse button will enable users to select the data folder in which previously estimated outputs are stored a Create Shapefiles and Tables The input network C LPFESExample S T ipfe_ex net Select from the following time intervals Time Intervals Create and show Ipfe_ex_tl Ipfe_ex_t2 Ipfe_ex_t3 Ipfe_ex_t4 l Scatter Plot Ipfe_ex_t5 Ipfe_ex_t6 l Network F OD Table Report Cancel OK Help Figure 7 Create Shapefiles and Tables Window 14
196. tation Research 29B 231 242 Yang H amp Meng Q 1998 Departure time route choice and congestion toll in a queuing network with elastic demand Transportation Research 32 4 247 260 Yang H Meng Q amp Bell M G H 2001 Simultaneous estimation of the origin destination matrices and travel cost coefficient for congested networks in a stochastic user equilibrium Transportation Science 35 107 123 Yang H Sasaki T lida Y amp Asakura Y 1992 Estimation of origin destination matrices from traffic counts on congested networks Transportation Research 26B 417 433 APPENDIX I 1 Appendix I File formats In most cases users will prepare input files through the graphical interface However the format of input files is introduced here for the reference purpose All input files are named by a base plus a suffix For narrative convenience we assume the base is project hereafter I 1 Input files for assignment 1 Network files Two types of network format are accepted FORT and DANET2 a FORT type network In this format a network is described by two files project 1 and project 2 1 project 1 describes network topology as explained in Table I 1 An example is given in Figure I 1 2 project 2 describes O D information as described in Table I 2 An example is shown in Figure I 2 Table I 1 A description of the file project 1 Range Fields Type Description Block 1 1 row
197. that LPFE would perform more DDAG iterations To achieve this objective one can try increase n zn bn and or reduce z In general such adjustment helps produce a result better fulfilling the constraints However note that the CPU time increases rapidly with the number of iterations spent in the sub problem Thus users should exercise caution when making such parameter adjustments particularly for large scale problems 6 3 The Impact of Network Topology To study the impact of network topology on O D estimation results we focus on several basic network topologies Most transportation networks can be considered as a combination of these basic types The basic topology types in consideration include tree linear ring a special linear type and the combination of the above three called a derived type in our discussion Figure 5 8 illustrates these basic types CHAPTER 6 CASE STUDIES 82 Lo SO fo N VA INN CE C OZ O v gt O N Y i L a A tree network b A linear network Pa N pT a j x Pa Q va SS a A NS N Pi o 4 N N Pa 4 J NA S W f f Fd A N Z N N f g L E a ao oa wo c A ring network d A derived network Figure 6 8 Basic types of network topology A tree network Figure 6 8a can be regarded as a typical network in mono centric cities where people live in the suburbs and wor
198. the Scatter Plot Layers 00 ee eee eeseeeseeseeeeneeceeeceeeeseeeeneeenaeens 34 List of Tables Table 1 LPFE Output Text Piles to Shapettles 4444c0 0 406 dade dees 32 Table 2 LPFE Output Files to Spread Tables 3 ccccc c ssccsssassdevsssedaasasecnacessnsceetnndeanmeansiaatas 35 Introduction Welcome to a new dimension in OD estimation Visual PFE TD is a special edition of Visual PFE an integrated software suite that combines the Path Flow Estimator PFE with other software components to facilitate the estimation visualization and refinement of Origin Destination OD trip tables with user friendly Graphical User Interfaces GUD The Logit Path Flow Estimator LPFE was developed at the Traffic Lab of University of California Davis LPFE facilitates the estimation of time dependent OD tables LPFE operates under the DOS command prompt with no GUIs and no graphical presentation of the output data To expand the capability of LPFE this special edition of Visual PFE is created to integrate LPFE with components of Visual PFE With Visual PFE TD users can Run LPFE with GUIs Convert the estimated OD tables to Microsoft Excel Files Change the colors and zoom levels of the OD table cells Interactively display and query OD desire lines Interactively display and query paths between any pair of OD Convert the PFE outputs to GIS files ESRI shapefiles Create thematic maps of network links and traffic analysis zones Generate diagno
199. the blue points represent the estimated values O D flow or link flow For a perfect estimation in which true O D and link flows are exactly reproduced by estimates all the red points should overlap the blue points Lv Jo S origin destination demand N 10 17 200 O 6 o 11 17 200 N fo 12 V7 200 YY _ 13 17 200 AO 14 17 200 N 15 17 200 OO ae 16 iy 100 Figure 6 9 A tree network Figure 6 10 True O D trip table CHAPTER 6 CASE STUDIES 84 O D estimation profile plot for time interval 1 RMSE 0 0004 100 00 percent total demand is captured Est engted BS tine Estimated True O D flow 0 100 120 140 160 180 200 220 True O D flow Histogram plot for estimated O D Number of O D pairs Of various deviation p5 2 1 0 1 2 3 4 5 6 Deviation from True O D flows Figure 6 11 Estimated O D flow profile for the tree network Estimated link flow profile plot for time interval 1 Number of measured links 7 RMSE 0 0002 1400 1200 1000 Estimated True link flow o o o 400 200 0 200 400 600 800 1000 1200 140 True link flow Figure 6 12 Estimated link flow profile for the tree network CHAPTER 6 CASE STUDIES 85 From Figure 6 11 and Figure 6 12 we observe that both the estimated OD flows and the estimated link flows equal the true values with TDC 100 RMSE OD 0 and RMSE Link 0 That is a perfect estimation is obtained 6 3 2 The case with a li
200. tive row of the Path Table will be highlighted e Toolbar Button One to All Paths When the button is clicked all the paths originating from the origin of the active row of the Path Table will be highlighted e Toolbar Button All to One Paths When the button is clicked all the paths ending at the destination of the active row of the Path Table will be highlighted 27 e Toolbar Button One to One Paths When the button is clicked all the paths beginning at the origin and ending at the destination of the active row of the Path Table will be highlighted Report Window Every LPFE estimation generates a text file documenting summary statistics of the estimation The estimation statistics of the estimation can be viewed in Visual PFE TD using the Report Window Figure 20 amp Report_SC LPFE Example EST lpfe_ex_t1 E mj Maximum allowed iter 100 Required accuracy 0 001000 Minimum allowed step 0 000100 Allowed line searchiiter 10 Termination reason Required accuracy achieved Total iteration 10 Accuracy indicator 0 000003 Number of line search D Objective value 21411 717056 CPU time consumed 43 65 Figure 20 Report Window There are three ways to open a Report Window e Select the Report option in the Create Shapefiles and Tables Window e When a network map is the active window go to the menu item Diagnostic Statistics e Go to the menu item Diagnostic Compare and select from the available re
201. to zoom in the mouse cursor will appear as a magnifying glass and drag a rectangle with the mouse cursor The rectangle will be the extent to which the map will be zoomed in Once you are satisfied with the extent of the rectangle release the mouse button The map will be zoom in accordingly Figure 10 C PFE_Workbook 3_Exercise_3 9GRD pfe M SGRD_OD_BOUNDS a SGRD_DESIRELINES yw MV 9IGRD_OD a V 9GRD_NETWORK wv Figure 10 Navigation through the Network Map 6 While the map is zoomed in you can move the displayed portion of the map to another spot by pressing down the toolbar button Pan wil Clicking at the map then will turn the mouse cursor to a palm symbol Moving the mouse cursor while holding down the mouse button will allow you to move the map window to another spot on the network 13 7 To zoom out click at the toolbar button Zoom Out al The map will be zoomed out by a certain proportion If you are not satisfied with the scale click at the button again will further reduce the map scale 8 Ifyou want to return the map to the original full scale of the network map simply press the Full Scale button m 9 Ifyou are interested in finding out the attribute of a particular map feature you can use the toolbar button Identify Lii To do this first make the feature layer the active layer by clicking at the name of the layer in the legend A line underneath the layer name will appear in the legend Press d
202. travel time is assumed in the original LPFE to be the sum of a constant link traversal time and a queuing delay which is positive so long as links operate at their capacities This assumption accords with many real world observations particularly on arterial streets where intersection control dealy dominates the delay experienced by drivers On freeways however queuing delay may not fully account for all congestion effects It is thus useful to treat link traversal time as flow dependent This conservation equation assumes that all trips depart from an assignment interval also complete within that time interval CHAPTER 3 LPFE FORMULATION AND ALGORITHM 23 through an appropriate link performance function When considering flow dependent link traversal times the term related path costs in the objective function of LPFE is replaced with an integral expression as in Fisk s model min gt f ta w dw L nf 1 7 3 46 subject to Equations 3 29 3 30 and path flow incidence relationship 3 3 Using measurement constraints such as 3 29 implies extreme confidence on the quality of link observations However measurement errors are unavoidable in real applications Ignoring these errors can of course lead to inaccurate estimation More severely inconsistent link flow patterns e g flow conservation law might be violated due to such errors can be introduced thereby leading to possibly no feasible solution The problem can be addre
203. tropy function that leads to the most likely O D matrix Jornsten amp Nguyen 1980 Fisk amp Boyce 1983 Nguyen 1984 Fisk 1988 Yang Sasaki Iida amp Asakura 1992 While the above formulations used deterministic user equilibrium conditions Yang et al 2001 extended the bilevel programming formulation to include the stochastic user equilibrium SUE The major drawbacks of these bilevel programming formulations based on either UE or SUE principles are the inherent difficulty of obtaining global optimum and the computational inefficiency for large scale networks iteratively solve the traffic assignment problem Path flow estimator PFE in which path flows instead of O D demands are treated as solution variables was introduced in order to resolve the analytical and computational difficulties of the bilevel formulation Sherali et al 1994 proposed the first path flow estimator formulated as a linear programming problem User equilibrium route choice behavior is considered in the method The path decomposition of O D flows that reproduce the observed link flows are directly determined by a column generation procedure such that the resulting O D matrix is the closest to a target one Using a stochastic user equilibrium assumption Bell 1997 extended Sherali s model to a logit path flow estimator LPFE that seeks to maximize the path entropy and assign trips on least cost paths simultaneously LPFE relaxes the assumption that all l
204. truct the hypothetical dynamic true O D flows in the time dependent case For brevity the O D trip table is not listed here Figure 6 25 The Dallas Fort Worth network 6 4 1 Effects of measurement location and the number of measurement locations on estimation performance According to the observations made in Section 6 3 LPFE s capability of reproducing the true O D flows depends on network topology We first examine for this CHAPTER 6 CASE STUDIES 92 real network whether or not LPFE can provide reasonable results when inputs are ONLY measured link flows The different sets of measurements in consideration include 53 flows on all links are measured number of links 267 flows on congested links are measured number of links 45 flows on efficient links are measured number of links 33 flows on freeway links are measured number of links 27 flows on centroid connectors and freeway links are measured number of links The set of all measured links consists of the links whose volume capacity ratio is larger than 0 1 The set of congested links include all the links with volume capacity ratio larger than 0 5 Efficient links form a minimal link set covering all the used path This link set is designed to capture some information of the spatial structure of the demand Freeway links are the links on the freeway connecting the two main OD pairs across the city The centroid
205. ts discussed in the last section The MOEs of estimation results with and without the observed O D trip table are shown in Figure 6 29 Figure 6 30 and Figure 6 31 TDC 120 00 E Without historical OD E With historical OD 100 00 p 80 00 p 60 00 p 40 00 p 20 00 p 0 00 allmeasured congested efficient freeway dummy links links 267 links 45 links 33 links 27 amp freeway links 53 Figure 6 29 TDCs for different link sets with and without historical O D data CHAPTER 6 CASE STUDIES 95 RMSE_OD veh hr 800 00 p E Without historical OD 700 00 E With historical OD 600 00 500 00 400 00 300 00 200 00 100 00 p 0 00 all measured congested efficient freeway dummy links links 267 links 45 links 33 links 27 amp freeway links 53 Figure 6 30 RMSE_ODs for different link sets with and without historical O D data RMSE_Link veh hr 1200 00 rp E Without historical OD E With historical OD 1000 00 p 800 00 p 600 00 p 400 00 p 200 00 p a 0 00 allmeasured congested efficient freeway dummy links links 267 links 45 links 33 links 27 amp freeway links 53 Figure 6 31 RMSE_Links for different link sets with and without historical O D data As indicated by Figure 6 29 by including historical O D data into the input set the TDCs of all the scenarios except the scenario with the input set of efficient links are getting even closer t
206. turn none GEN_IA rhs a pointer to a GEN_IA object intBisecSearch search step size using the bisection method Return 0 if descent 1 otherwise void GoldentSearch search step size using Golden method Return none Overridables int Build inFile outFile format build the algorithm object including reading required input data allocating memory and open I O files An algorithm object must be built before its Solve function can be called Return 0 if building succeeds a non zero number otherwise string inFile input file name string outFile the output file name ENUM format an enumeration type that describes input file format int Build rhs build the algorithm object from an existing object It is often used to build a sub problem according to its host object 0 if building succeeds a non zero number otherwise GEN_IA rhs a pointer to an GEN_IA object void Initialize initialize the solution process It must be overridden in derived classes Return none void ComputeOF V compute the objective function value update OFV accordingly Return void MainLoop Return bool Terminate Return void PreProcess Return void PostProcess Return int Report Return int PrePareReport Return int CloseReport Return CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 46 none define major operations of the solution process It must be overridden in
207. twork exceeds capacity of the program current capacity is 5 000 nodes 10 000 links 500 zones and 250 000 OD pairs 3 Dispersion parameter cost sensitivity is too Consider the reduction of high which is not suitable for the current unit dispersion parameter of travel cost of the working network 4 Path building mechanism fails e g impossible Check the locations of problematic to build paths passing through some observed traffic counts links Check network connectivity or Provide paths in the input to cover such observation 5 The execution exceeds the maximum number Enlarge the measurement errors of iterations specified by the user By examining the trend of convergence the algorithm seems to diverge 6 The execution exceeds the maximum number Enlarge the measurement errors of iterations specified by the user By or examining the trend of convergence the Increase the maximum number of algorithm however seems to converge iterations Remarks o With the return codes 1 2 and 3 PFE outputs will not be created o The estimation result is meaningful only when the program is terminated with the return code 0 o With the return codes 4 5 and 6 the outputs are however created so that the user can review the problem associated to the estimation through the map scatter plot etc Example 2 Navigate through the Network Map and Scatter Plot Windows In this example we will begin start the example by working with the Map and Scatte
208. ubclass contains functions specific to O D estimation problems particularly input output I O functions such as reading measured link traffic counts from disk files and preparing estimation reports Derived from TNM_ODE TNM_LODE is further specified to target logit path flow estimators TNM_LODE can be regarded as the outmost wrapper of LPFE objects containing an object of TNM_LOGWRAP as an internal solver and providing necessary I O supports TNM_LODE_TD implements the framework described in Algorithm MTI for solving time dependent LPFE and overriding the I O functions accordingly to meet the need of processing multiple time intervals Similarly CSTAP_B and CSTAP_B_TD are outmost wrappers for steady state and time dependent logit traffic assignment problems BSUE and TD BSUE in Section 3 1 2 respectively 4 2 Class Description This section provides implementation details of all classes Note that the class members of minor importance are not presented here CLASS GEN_IA PARENT CLASS N A Data Members GEN_IA subProblem a pointer of a sub problem GEN_IA auxProblem a pointer of an auxiliary problem double OFV objective function value int curlIter current iteration index double stepSize current step size float cpuTime consumed CPU time int ziggIter the number of iterations of no improvement No improvement means that an expected improvement i e an adequ
209. ubproblem ENUM at the type of solution algorithm only applies to the time dependent case double t dispersion parameter bool ep whether or not enumerate all paths Attributes bool GetPathEnum Check if the path enumeration is activated Return a boolean value Operations void SetInitPath n Set the value of initPaththe number of paths void SetGenPath n Set the value of genPaththe number of paths CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 54 CLASS TNM_ODE PARENT CLASS TNM_IA Data Members bool m_useTarget whether or not consider O D measurements bool m_useLinkError whether or not consider link measurement errors bool m_useTargetError whether or not consider O D measurement errors bool m_useMsLinkTime whether or not consider link travel time measurements vector msLink a vector of pointers of TNM_SLINK objects associated with measured links vector umsLink a vector of pointers of TNM_SLINK objects associated with unmeasured links vector dmdVector a vector of pointers of TNM_SDEST objects associated with measured O D pairs Constructor void TNM_ODE default constructor Return none Operations void EnableTarget t Set the value of m_useTarget Return none bool t true if allow to consider O D measurements void EnableLinkError t Set the value of m_useLinkError Return none bool t true if allow to consider link measurement errors void EnableTar
210. users add GIS maps to software applications MapObjects comprises an ActiveX control OCX called the Map control and a set of over forty five ActiveX Automation objects In Visual PFE a map control is used to display the shapefiles created by the ArcViewShapeFile component The map control facilitates all of the GIS functions for the converted shapefiles Another OCX control is added to a map form to display the legends of different map layers The legend control is internally connected to the map control A layer can be made active through the legend control On the active layer labels and thematic mapping can be applied to features on the layer For example networks links can be varied by colors and width based on estimated link flow Bar charts can be applied to display the varying magnitude of production and attraction at the origins and destinations 5 3 4 FarPoint Spread Spread by the FarPoint Technologies is a software component built to Microsoft s latest NET software architecture Spread is used to create spreadsheet applications The strength of Spread is that it facilitates all of the typical spreadsheet functions with a dimension limitation 1 million columns by 1 million rows that is unlikely to be violated by any OD tables Visual PFE contains codes that process the PFE CSV outputs and formulate the spreadsheets stored and displayed with Spread Once a spreadsheet is created in Spread it can be saved as a Microsoft Excel file T
211. we can replace In Ca va va in 3 76 by the right hand side of the above inequality After some simple algebra we obtain lui gt wh Unt nC vf vp Se__ Catvi vi The above inequality implies that the adjustment the second term on the right hand side is smaller than the maximum possible value However it effectively avoids CHAPTER 3 LPFE FORMULATION AND ALGORITHM 38 over adjustment and ensures convergence Apparently Step 2 of RIBATD employs this reduced adjustment This completes the proof There exist other methods to update 44 and v4 according to Equation 3 76 The method of successive averages MSA for example can be fitted as follows ALGORITHM MSATD Step 0 Step 1 Step 1 2 Foreachlink a Ay if Ca lt va i vi vil Ca else vi 0 Compute va vali vidG DA e uh v4 Ca uh v4 Ca Update f and 4 If lt lt lel set K lel Step 2 Since MSATD is the same as RIBATD except in Step 2 we ignore the other steps in the above description to save space The convergence of MSA is well known thus its proof is not repeated here Algorithm DDAG and CGA presented earlier can be applied to handle flow dependent link travel times and path generation in the time dependent case The only difference is that in DDAG either Algorithm RIBATD or MSATD not RIBA should be called to produce a sub problem solution Finally an algorithmic framework accom
212. y of network problems including shortest and K shortest path problems maximum flow problems path enumeration dynamic shortest path problems stochastic routing problems and dynamic network loading simulation This significantly reduces the programming task involved in this project for many required functions e g the calculation of shortest K shortest paths in the column generation algorithm have been defined in TNM Subclass TNM_MPEN deals with the following mathematical program which can be regarded as a composite of logit traffic assignment models and path flow estimators TNM is developed by Professor H M Zhang s research group at UC Davis in an independent research effort CHAPTER 4 AN OBJECT_ORIENTED IMPLEMENTATION 41 min f Inf D olc f 4 1 subject to Mf q Flow conservation conditions 4 2 AF C Capacity constraints 4 3 Ko Io 60 lt Aof lt Ro lo Yo Link flow measurements 4 4 ToJo Po lt Mof lt o Jo No O D flow measurements 4 5 Apparently only a subset of constraints should be considered in a particular problem Further we may need to include travel costs in the objective function in one problem but need not in another The derived classes of TNM_MPEN aim at realizing such polymorphism Specifically TNM_MPEN itself does not consider constraints 4 2 and exclude travel costs in the object function o 0 0 MPEN_MC uses the same constra

Development of A Path Flow Estimator for Inferring Steady

Contents

Download Pdf Manuals

Related Search

Related Contents