Given the current connected vehicles program in the United States, as well as other similar initiatives in vehicular networking, it is highly l ikely that vehicles will soon wirelessly transmit status data, such as speed and position, to nearby vehicles and infrastructure. This will drastically impact the way traffic is managed, allowing for mor e responsive traffic signals, better traffic information, and more accurate travel time predicti on. Research suggests that to begin experiencing these benefits, at least 20% of vehicl es must communicate, with benefits increasing with higher penetration rates. Because of bandwidth limitations and a possible slow deployment of the technology, only a portion of vehicles on th e roadway will participate initially. Fortunately, the behavior of these communicating ve hicles may be used to estimate the locations of nearby non-communicating vehicles, thereby artif icially augmenting the penetration rate and producing greater benefits. We propose an algorithm to predict the locations of individual non- communicating vehicles based on the behaviors of ne arby communicating vehicles by comparing a communicating vehicle's acceleration with its exp ected acceleration as predicted by a car- following model. Based on analysis from field data, the algorithm is able to predict the locations of 30% of vehicles with 9-meter accuracy in the sam e lane, with only 10% of vehicles communicating. Similar improvements were found at o ther initial penetration rates of less than 80%. Because the algorithm relies on vehicle intera ctions, estimates were accurate only during or downstream of congestion. The algorithm was applied to an existing ramp metering algorithm, and was able to significantly improve its performan ce at low connected vehicle penetration rates, and maintain performance at high penetration rates. INTRODUCTION In 2010, American drivers wasted 4.8 billion hours and 1.9 billion gallons of fuel due to traffic congestion (Schrank, Lomax, & Eisele, 2011). Severa l strategies have been proposed to reduce congestion, including dynamic signal timing, ramp m etering, and dynamic speed limits. These strategies often rely on historical data supplement ed with real-time point detection such as in- pavement loop or video detectors. Because point det ection cannot cover the entire roadway, these data are often aggregated over time and space . The high installation and maintenance costs of point detection also prevent wide-scale deployme nt. Even when detectors are deployed, they are often spread far apart and the conditions betwe en detectors must be estimated. Noah J. Goodall, Research Scientist, Virginia Cente r for Transportation Innovation and Research, 530 E dgemont Road, Charlottesville, VA 22903-2454. Email: noah.g oodall@vdot.viginia.gov Brian L. Smith, Professor, Department of Civil and Environmental Engineering, University of Virginia, P.O. Box 400742, Charlottesville, VA, 22904-4742. Email: bri ansmith@virginia.edu Byungkyu “Brian” Park, Associate Professor, Departm ent of Civil and Environmental Engineering, Univers ity of Virginia, P.O. Box 400742, Charlottesville, VA, 229 04-4742. Email: bpark@virginia.edu March 12, 2014 2 Most modern vehicles are heavily instrumented, and at a minimum are aware of their locations via GPS, and their headings and speeds through othe r on-board sensors. Research suggests GPS may achieve lane-level accuracy in the near future (Du & Barth, 2008; He & Head, 2010), with accuracies of 1.5 meters 95% of the time (Popovic & Bai, 2011). This information can then be wireless transmitted to other vehicles or roadside listening devices. In the United States, the communication between vehicles and the roadside inf rastructure is often referred to as “connected vehicles” (CV). As methods for collecting mobile vehicle data are d efined and implemented, researchers have proposed mobility applications that utilize these n ew mobile data to improve traffic flow and reduce congestion. Several new algorithms have been developed that, rather than estimate vehicle trajectories from loop detectors or histori cal data, rely on the locations and speeds of individual vehicles. A ramp metering scheme that is based on detecting platoons of vehicles in the mainline rather than aggregated density measure ments is an example of an application that requires the locations of individual vehicles (Park , 2008). Many of these applications function most effectively when all, or the majority of vehic les are equipped with sensing technology (Smith et al., 2010b). Simply put, these applicatio ns are not designed for detector or historical data only, but instead require knowledge of individ ual vehicle locations. Some proposed applications include adaptive traffic signal contro l (Datesh, Scherer, & Smith, 2011; He, Head, & Ding, 2012; Lee and Park, 2012; Priemer & Friedrich , 2009; Smith et al., 2010a), ramp metering (Park, 2008), and dynamic gap-out (Agbolosu-Amison et al., 2012), with others in development. The deployment of mobile sensors among roadway user s will not be instantaneous. Bandwidth shortages and battery life restrict the use of smar t phones, and the John A. Volpe National Transportation Systems Center estimated that only 5 0% of vehicles will have connected vehicle communications capabilities nine years after the pr ogram’s initiation (John A. Volpe National Transportation Systems Center, 2008). In any scenar io, there will likely be transition period where only a portion of vehicles are equipped. The developers of mobility applications have been careful to study the effect of low connected v ehicle penetration rates on the application's performance, testing their applications across a wi de range of penetration rates. The locations of vehicles that are not participating as connected ve hicles are referred to as unequipped vehicles and are ignored in most applications. Unsurprisingl y, mobility applications produce greater benefits with higher equipped vehicle penetration r ates, and most require a minimum percentage of participating vehicles to experience any benefit s at all. Table 1 shows a summary of the minimum required percentage of equipped vehicles fo und in several mobility applications. March 12, 2014 3 Table 1: Connected vehicle applications and corresp onding minimum required connected vehicle penetration rates Connected Vehicle Application Minimum CV Penetratio n Rate Traffic signal control 1,2 ,3 20-30% Freeway incident detection 4 20% Lane-level speed estimation 5 20% Arterial performance measurement 6 10-50% Intersection analysis 7,8,9 10-30% 1(Smith et al., 2010b), 2(He et al., 2012), 3(Priemer & Friedrich, 2009) 4(Barria & Thajchayapong, 2011), 5(Rim, Oh, Kang, & Kim, 2011), 6(Li, Zou, Bu, & Zhang, 2008), 7(Ban, Herring, Hao, & Bayen, 2009), 8(Ban et al., 2011), 9(Hao, Ban, Bennett, Ji, & Sun, 2012). We expect that with a reasonable approximation of t he locations of unequipped vehicles, the performance of mobility applications that require i ndividual vehicle locations will be significantly improved. We propose a method to esti mate the individual locations of unequipped vehicles on a freeway by analyzing the behavior of connected vehicles. By estimating the locations of these unequipped vehicles, the “effect ive” penetration rate of equipped vehicles is increased, theoretically improving the performance of connected vehicle applications. To measure the algorithm's potential benefits, an exis ting connected vehicle application, ramp metering, is then tested both with and without the location estimation algorithm. BACKGROUND Predicting the locations of individual vehicles bas ed on wirelessly transmitted data is a recent area of interest. Preliminary work focused on estim ating freeway travel states rather than individual vehicle locations. The earliest work was based on vehicle location and travel time information as determined from cell tower signal tr iangulation (Bargera, 2007; Sanwal & Walrand, 1995; Westerman, Litjens, & Linnartz, 1996 ). Later work focused on the much more accurate, although sparsely collected, GPS data (Fe rman, Blumenfeld, & Dai, 2005; Krause, Horvitz, Kansal, & Zhao, 2008). Mobile sensor data were eventually integrated with point detection data, and used to estimate vehicle travel time by Nanthawichit et al. (2003). Herrera and Bayen used Kalman filtering techniques and Newt onian relaxation to integrate point detection and mobile sensors into a high resolution traffic state estimation of a freeway (2010). Their algorithms were evaluated using both empirica l ground truth freeway data (Federal Highway Administration, 2010) and actual in-vehicle cell phones with GPS receivers (Herrera et al., 2008). They were able to estimate vehicle dens ities of multilane 120-foot segments with a root-mean-square error (RMSE) of 1.78-2.44 vehicles depending on assumptions, but did not estimate individual vehicle locations. One technique has been proposed to estimate vehicle locations based on their travel times through a section. Ban et al. used the reported tra vel times of a portion of vehicles traveling through an intersection to calculate their individu al delays (2011). This information was then used to determine the amount of time each vehicle w as in the signal’s queue. Using this information, Ban et al. could estimate the arrival rate at the intersection, and by assuming March 12, 2014 4 uniform flow rate and constant discharge rate, coul d estimate the total length of the queue with only 30% of vehicles reporting their locations. Building on this technique, Sun and Ban attempted t o estimate the precise trajectories of the unequipped vehicles that make up the total queue, w hose length was estimated using the technique described above (Sun & Ban, 2011). Howeve r, the number of unequipped vehicles arriving between equipped vehicles is known, implyi ng the use of an upstream detector. Later work was able to relax this assumption without a si gnificant difference in performance (Sun & Ban, 2012). The behavior of these unequipped vehicl es did not follow a car-following model, but instead showed immediate speed changes from free fl ow to stopped and back again. No techniques have yet been proposed to estimate indiv idual vehicle locations based on the behavior of equipped vehicles beyond queuing analysis. DESCRIPTION OF THE ALGORITHM To develop a microscopic estimation of vehicle loca tions and speeds, the proposed algorithms determine when an equipped vehicle is behaving diff erently than would be expected based on the locations and speeds of vehicles directly ahead. Th is requires a definition of expected vehicle behavior. Car-following models, which attempt to pr edict the behavior of individual vehicles, are used here as an approximation of a vehicle's expect ed behavior. For this study, the Wiedemann model is used as the car-following model. The Wiede mann model is a psychophysical model which estimates the thresholds for a driver's decis ion to accelerate or decelerate based on drivers' perceptions of changes in relative velocity. The mo del uses four stages: free driving, following, approaching, and braking/emergency (Wiedemann, 1974 ). A vehicle’s current stage is based on its change in headway and relative velocity to the leading vehicle. The Wiedemann model has gained acceptance as the basis for the microscopic simulation software VISSIM (PTV, 2011). To avoid overfitting the model to the evaluation da ta set, the Wiedemann model as applied here uses the calibration parameters based on empirical freeway data as proposed by Wiedemann and Reiter (1992). Some model parameters were found in the original paper, while others were extrapolated from charts by Olstam and Tapani (2004 ). For the proposed algorithm, the Wiedemann model is also limited to in-lane car-foll owing; lane changing decisions are not modeled. To estimate the location of unequipped vehicles, fi rst the locations, speeds, and accelerations of all vehicles at a given time t are used to populate a virtual roadway. The expect ed position of all vehicles are updated to time t+ 1 based on the Wiedemann model considering all know n equipped vehicles as well as the estimated position s of unequipped vehicles at time t. The positions of all vehicles, equipped and estimated, are checked against two criteria. First, if an estimated vehicle is found to overlap with an equip ped vehicle, the estimated vehicle is erased from the rolling estimation. Second, if an equipped vehicle is found to have an acceleration that is less than expected by a predetermined threshold, it is assumed that the equipped vehicle is following the Wiedemann model and is reacting to a previously undetected unequipped vehicle, referred to here as the estimated vehicle. Refer to Figure 1 for a description of the algorithm's parameters. March 12, 2014 5 Figure 1 Parameters used in the location estimation algorithm. The speed of the estimated vehicle can be predicted from an empirical relationship between lead vehicle speed, following vehicle speed, and followi ng vehicle acceleration. The relationship is defined in Equation 1. { }0 , max 1 n n n b v v λ+ =− (1) In Equation 1, vn-1 is the speed of the estimated lead vehicle, vn and bn are the speed and acceleration of the equipped following vehicle, and λ is a calibration factor. Using linear regression on the Next-Generation Simulation data s et of empirical vehicle trajectories described in the Evaluation section, λ = 0.162 when using m/s and m/s 2 for speed and acceleration respectively, with R 2 = 0.831. This value was used in all evaluations, r egardless of network. In the Wiedemann model, there are three regimes whe re a following vehicle reacts to a lead vehicle: following, closing, and emergency. The equ ipped vehicles were assumed to be in the closing regime if traveling faster than the estimat ed vehicle, and in the following regime if traveling slower than the lead vehicle. Therefore, if vn-1 < v n, then the closing regime was used to determine the unequipped vehicle's position. The fo rmula for acceleration of vehicle n is defined in Equation 2. () 12 21 −+∆−∆⋅=n n bx ABX vb (2) In Equation 2, ABX is the desired minimum space headway at low speed differences, ∆v is the difference in speed between vehicle n (the equipped following vehicle) and the n-1 lead vehicle, ∆x is the space headway from vehicle n and vehicle n-1, and bn-1 is the acceleration of the n-1 lead vehicle. A more detailed description of the mo del can be found in the literature (Olstam & Tapani, 2004; Wiedemann & Reiter, 1992). Because the actual acceleration bn of vehicle n is known, Equation 1 can be rearranged to determine the space headway, thereby predicting the location of the leading vehicle n-1. The lead vehicle's speed was estimated from Equation 1, and ∆v can thereby be determined from Equation 3. March 12, 2014 6 { }n n n n va vvv , min 1 λ− = − =∆− (3) The leading vehicle is assumed to have an accelera tion of zero and a standard vehicle length of 4.75 meters. Equation 4 demonstrates this rearrange ment of Wiedemann and Reiter’s closing acceleration equation with the new assumptions. { } ( ) nn n bvaABX x2, min 21 λ−⋅− =∆ (4) If the lead vehicle's speed is estimated to be grea ter than or equal to the following vehicle's speed, i.e. an ≥ 0, then the following vehicle is assumed to be in the following regime. The space headway is simply the desired minimum space headway ABX as defined in Equation 5. ∆:g1875=:g1827:g1828:g18.< (5) By assuming the unequipped vehicle's speed using Eq uation 2, and assuming its acceleration of zero, the headway of the two vehicles is quickly ca lculated, and the lead vehicle is inserted at the appropriate location and speed. The new vehicle’s l ocation can be found using Equation 6. x x xn n ∆+ =−1 (6) The new vehicle is an estimate of the position of a n unequipped vehicle. The estimated vehicle is inserted into the rolling estimation of the traffic network, and continues to move forward and interact with other equipped and unequipped vehicle s according to the Wiedemann car-following model, although it never changes lanes. The estimat ed vehicle is removed from the simulation when an equipped vehicle no longer reacts to it and overlaps positions. The acceleration difference threshold that initiate s a estimated vehicle insertion is a critical value in the analysis, and for all testing in this paper, the value was set to 0.2g (1.96 m/s 2). This value was chosen based on the threshold of 0.5g for deter mining a potential incident in naturalistic driving studies (Dingus et al., 2006). Also, the ca r-following model used here has a maximum acceleration of 0.36g (3.5 m/s 2) when a vehicle is at standstill, with this maximu m rate of acceleration inversely related to the vehicle's spe ed. Therefore any equipped vehicle traveling less than 17 m/s with no acceleration, and which is predicted to have the maximum acceleration, will insert a single vehicle estimate. In this way , the algorithm is effective at low-speed synchronized traffic flow and queuing, even when ve hicles are not decelerating. Finally, the algorithm assumes that equipped vehicl es report their lane, location, speed (which if not reported directly can be determined from the di fference in location since the last transmission), and instantaneous acceleration. The vehicles are assumed to report once per second, as this allows for the periodic message dro ps expected in a 10 Hz transmission rate in a connected vehicle environment (Society of Automotiv e Engineers, 2009). March 12, 2014 7 EVALUATION The proposed algorithm was tested using vehicle tra jectories from the Next-Generation Simulation (NGSIM) project, a field-collected data set of vehicle movements along several corridors in the United States (Federal Highway Adm inistration, 2010). Vehicle movements were collected from video recordings, and then extr acted via specialized software. This study used the data set collected from a 500 meter sectio n of Interstate 80 in Emeryville, California between 5:00 PM and 5:30 PM on April 13, 2005. The roadway has five lanes in the northbound direction, along with a one on-ramp and a weave are a. The activity on the ramps and merge lanes are not analyzed, only the behavior of vehicles tra veling in the through lanes. Figure 2 shows an overview of the network. Because the NGSIM data lis t the position of every vehicle ten times per second, they are considered ground truth data. Figure 2 Section of I-80 highway used in the NGSIM data. A portion of vehicles in the data set were randomly assigned as connected vehicles and their movements are pulled from the full data set, and al l other vehicle records were removed from the evaluation set. Because the location estimation algorithm requires vehicle interactions to produce any estimates, it requires not only warm up time, but also warm up space. Figure 3 shows estimated vehicle densities for the final 220 meters of the freeway s egment after a 60 second initialization at various penetration rates. The left side shows only equipped vehicles, while the right shows the densities of both equipped vehicles, and estimated vehicle locations. Densities are much more accurate downstream of congestion (vehicles travel bottom to top in the figures) as seen at 25% penetration rates. The algorithm occasionally misse s traffic phenomenon at low penetration rates, such as the wide moving jam at between 5:18 and 5:2 0 which only becomes visible at 50% penetration rate using the location estimation algo rithm. At higher penetration rates, because there are so few unequipped vehicles in the network , the algorithm often overestimates densities as seen in at 100% penetration rate, and to a lesse r extent at 70% penetration. In spite of its shortcomings, the algorithm provides a remarkable i mprovement over equipped vehicles alone at low and mid penetration rates near congestion. Data range (500 m) Evaluation area (220 m) March 12, 2014 8 Figure 3 Heat map of densities each second for 30-m eter segments of I-80 at various penetration rates, both with and without the locati on estimation algorithm. Accuracy is improved at low-penetration rates, but densities ar e often overestimated at high penetration rates. The characteristics of the location estimation algo rithm can be demonstrated by analyzing vehicle trajectories. Figure 4 shows the trajectori es of equipped, unequipped, and estimated unequipped vehicles over a small portion of the I-8 0 data set at a 25% penetration rate. In the figure, estimated vehicles are often initially plac ed near an unequipped vehicle. However, because the locations of all unequipped vehicles ha ve not been estimated, there is often little traffic nearby with which to interact. As a result, the vehicle accelerates to free flow speed until it encounters an estimated or equipped vehicle, ess entially "driving" itself into position. Estimated vehicles are continually inserted behind the original equipped vehicle, and continue to drive themselves into place. This occurs several ti mes in Figure 4 between 1140 and 1160 Ground Truth Distance (220m) 5:10 5:20 5:30 Ground Truth Distance (220m) 5:10 5:20 5:30 10%, Equipped-only Distance (220m) 5:10 5:20 5:30 10%, Equipped and Estimated Distance (220m) 5:10 5:20 5:30 25%, Equipped-only Distance (220m) 5:10 5:20 5:30 25%, Equipped and Estimated Distance (220m) 5:10 5:20 5:30 50%, Equipped-only Distance (220m) 5:10 5:20 5:30 50%, Equipped and Estimated Distance (220m) 5:10 5:20 5:30 70%, Equipped-only Distance (220m) 5:10 5:20 5:30 70%, Equipped and Estimated Distance (220m) 5:10 5:20 5:30 100%, Equipped-only Distance (220m) 5:10 5:20 5:30 100%, Equipped and Estimated Distance (220m) 5:10 5:20 5:30 2 4 6 8 10 12 14 16 18 20 Number of Vehicles Per Lane Per 30 Meter Segment March 12, 2014 9 seconds. As a result, vehicle speeds as estimated b y the algorithm are often higher than in actuality, e.g. at 25% penetration rate the average speed of estimated vehicles was 27% higher than speeds of unequipped vehicles. Figure 4 Trajectories of equipped, unequipped, and estimated unequipped vehicles over a portion of I-80 at a 25% equipped vehicle penetrati on rate. Measuring the performance of the algorithm is a cha llenge. Normally the difference between observed and estimated values can be measured and a veraged, which requires a one-to-one relationship between estimates and observations. Th e location estimation algorithm, by contrast, often has a different number of estimates than obse rvations. To provide some understanding of the algorithm's performance, we introduce a new met ric called the effective penetration rate, PR eff . To calculate effective penetration rate, the indi vidual estimates and observations within the same lane and time are sorted into exclusive pairs based on nearest neighbor. Only one observation for any time and lane may be matched wi th a single estimation at the same time and lane, and vice versa. The one-dimensional distance between these two values are recorded as the minimum absolute distance between any single estima ted location and observed location. This March 12, 2014 10 procedure is defined in the iterative process, perf ormed from n = 1 to #O t,l , as described in Equations 7 through 11. :g18.<:g3<37,:g3<39(:g1855)=:g3321:g185.:g1851:g1855:g3575:g3598:g333.:g1831 :g3<37,:g3<39×:g1831:g3<37,:g3<39:g3339:g3<35−:g333.:g1831:g3<37,:g3<39×:g1831:g3<37,:g3<39:g3339:g3<37:g3598:g3577, :g1855≤#:g1831 :g3<37,:g3<39 ∞,:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9 :uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:uni<<<9:g1855>#:g1831 :g3<37,:g3<39:g1 (7) :g1827=:g3319:g1831:g3<37,:g3<39∉:g1831:g3<37,:g3<39(:g1851):g3323 (8) :g1831:g3<37,:g3<39=:g1827 (9) :g1828=:g3319:g1831:g3<37,:g3<39∉:g1831:g3<37,:g3<39(:g1852):g3323 (10) :g1831:g3<37,:g3<39=:g1828 (11) O is the set of all observations (locations of unequi pped vehicles) and X is the set of errors for each vehicle location estimation in the set E for each lane l in the set of all lanes L and each time interval t in the set T. In each iteration n, variables i and j represent the minimum respective observation and estimation with the closest relativ e error of the set, as shown in Equation 7. These individual records are removed from the set i n Equations 8 through 11, using sets A and B as placeholders. To calculate effective penetration rate, each locat ion estimation error in X which is less than or equal to the threshold ρ is classified as an accurate measurement, and each greater than the threshold is classified as inaccurate. The metric e ssentially defines all equipped vehicles as accurate measurements, and furthermore ensures that any inaccurate measurement cancels out an accurate measurement. The effective penetration rat e for a given accuracy ρ is defined in Equation 12. :g1832:g1833 :g3<32:g3<33:g3<33,:g3<95=#:g183.+2#:g3558:g1875∈:g18.<::g1875<:g2<2. :g3559−#:g1831 #:g1831 (12) In Equation 12, S is the set of all equipped vehicles, E is the set of all estimated positions, O is the set of all unequipped positions, X is the set of all location errors, and ρ is the acceptable distance error threshold. Table 2 shows the effective penetration rates of th e I-80 data at various accuracy levels and actual penetration rates. At very high accuracy lev els of three meters or less, the algorithm generates more inaccurate than accurate estimates. Additionally at actual penetration rates above 80%, there are few unequipped vehicles to detect an d therefore the algorithm performs poorly. The algorithm is most effective at penetration rate s of 70% or less, with minimum accuracy rates of 5-10 meters. March 12, 2014 11 Table 2 Effective penetration rates of I-80 at vari ous accuracies and actual penetration rates. Highlighted values indicate improvements ove r the actual penetration rates. Distance Penetration Rate (m) 5% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 1 -7.5% - 11.6% - 10.6% -3.0% 6.7% 18.4% 30.1% 43.2% 56.2% 69.8% 83.5 % 2 -2.8% -3.2% 1.3% 9.6% 18.9% 29.3% 39.5% 50.6% 61. 4% 72.5% 83.5% 3 1.8% 4.9% 12.5% 21.3% 30.0% 39.2% 48.0% 57.1% 65. 9% 74.8% 83.5% 4 5.9% 12.2% 22.4% 31.5% 39.6% 47.6% 55.0% 62.4% 69.5% 76.6% 83.5% 5 9.4% 18.2% 30.4% 39.6% 47.1% 54.2% 60.5% 66.7% 72.4% 78.1% 83.5% 6 12.1% 22.7% 36.6% 45.8% 52.9% 59.2% 64.6% 69.8% 74.5% 79.1% 83.5% 7 14.1% 26.2% 41.1% 50.4% 57.2% 62.8% 67.7% 72.1% 76.1% 79.9% 83.5% 8 15.6% 28.6% 44.4% 53.8% 60.3% 65.5% 69.9% 73.8% 77.2% 80.5% 83.5% 9 16.7% 30.5% 46.9% 56.3% 62.6% 67.4% 71.5% 75.1% 78.0% 80.9% 83.5% 10 17.5% 31.8% 48.7% 58.0% 64.3% 68.9% 72.7% 75.9% 78.6% 81.2% 83.5% 11 18.2% 32.8% 50.0% 59.4% 65.5% 69.9% 73.5% 76.6% 79.1% 81.4% 83.5% 12 18.6% 33.6% 51.0% 60.4% 66.5% 70.7% 74.2% 77.1% 79.4% 81.6% 83.5% 13 19.0% 34.2% 51.8% 61.2% 67.2% 71.4% 74.7% 77.5% 79.7% 81.7% 83.5% 14 19.3% 34.7% 52.5% 61.8% 67.8% 71.9% 75.1% 77.8% 79.9% 81.8% 83.5% 15 19.6% 35.1% 53.0% 62.4% 68.3% 72.3% 75.4% 78.0% 80.0% 81.9% 83.5% 16 19.8% 35.4% 53.4% 62.8% 68.7% 72.6% 75.7% 78.2% 80.2% 81.9% 83.5% 17 19.9% 35.7% 53.8% 63.2% 69.0% 72.9% 75.9% 78.4% 80.3% 82.0% 83.5% 18 20.0% 35.9% 54.1% 63.5% 69.3% 73.2% 76.2% 78.6% 80.4% 82.1% 83.5% 19 20.2% 36.1% 54.4% 63.8% 69.6% 73.5% 76.4% 78.8% 80.5% 82.1% 83.5% 20 20.3% 36.3% 54.6% 64.0% 69.9% 73.7% 76.6% 78.9% 80.6% 82.2% 83.5% Ramp Metering Application Used alone, the location estimation algorithm is us eful for detecting highway conditions and providing an estimate of densities in low- or no-de tection segments. However, by providing estimates of individual vehicle locations, the algo rithm should also be able to improve the performance of some connected vehicle applications at low penetration rates. To test this theory, the location estimation algorithm was applied to a connected vehicle ramp metering algorithm called the GAP algorithm (Park, 2008). Description of the GAP Algorithm The GAP algorithm analyzes the speeds, acceleration s, and locations mainline vehicles upstream of a freeway on-ramp to predict future gaps in the right-most lane at the merge area in the near future. On-ramp vehicles are queued at a ramp signa l until a gap is predicted on the mainline, at which point one or several vehicles are given a gre en signal and released onto the mainline. Whereas traditional ramp metering algorithms releas e vehicles at a fixed rate over a set time period, the GAP algorithm releases vehicles at irre gular rates based on the prediction of gaps in mainline traffic. March 12, 2014 12 The GAP algorithm relies on two calculations: the p osition of the on-ramp vehicle, and the positions of the mainline vehicles. The on-ramp veh icle is expected to follow the Wiedemann car-following model. An on-ramp vehicle upon receiv ing a green phase is expected to hold its current speed for one second as the driver reacts t o the signal, then accelerates at a rate described in Equation 13. :g18.3:g3<37=3.5+:g2871.:g2873 :g2872:g2858 v:g293<:g2879:g2859 (13) In Equation 13, at is acceleration in m/s 2, and vt-1 is speed in m/s at the previous time step. The GAP algorithm then predicts the positions of vehicl es on the mainline in the right lane nearest the on-ramp. Vehicle positions are predicted using the fundamental equation as shown in Equation 14. :g1875:g3<37=:g1875:g2858+:g2859 :g287<:g18.3:g2858:g1872:g287<+:g1873:g2858:g1872 (14) In Equation 14, xt and x0 are the vehicle positions at time t and the initial time of measurement, respectively. In the GAP algorithm, at each time st ep the vehicle on the on-ramp next in line at the meter has its position projected several time s teps into the future. The positions of vehicles in the mainline right lane are also projected. If ther e exists a gap at the on-ramp vehicle’s position before the on-ramp vehicle is projected to reach th e end of the merge area, then the on-ramp vehicle receives a green signal. If no gap is detec ted, then the ramp meter is set to red. Vehicle positions are re-calculated every second, and a gre en signal’s minimum duration is two seconds. To prevent backups, the ramp meter is set to green if there are any stopped vehicles in the last 50 meters of the on-ramp. Evaluation of GAP Algorithm with and without Locati on Estimation The GAP algorithm was originally developed for a 10 0% connected vehicle environment. At low CV penetration rates, the algorithm frequently pred icts gaps where there are none. The GAP algorithm was tested at CV penetration rates of 10, 25, 50, 75, and 100% both with and without the location estimation algorithm. The algorithms w ere also tested against a fixed time metering strategy designed for the expected flow rate at the ramp of one vehicle every six seconds. The test network consisted of a two-lane freeway with a single-lane on-ramp volume of 600 vehicles per hour. Table 3 shows the results of the analysis . March 12, 2014 13 Table 3 Performance of the GAP ramp metering algori thm both with and without the location estimation algorithm, and compared against a fixed time metering strategy. In all cases, n = 10, and bold values represent p < 0.10. CV Penetration Rate Vehicle Prediction Algorithm Delay / Vehicle (s) Network Speed (km/hr) Distance Traveled (km) Number of Stops Speed Near Merge Area (m/s) - Fixed Time Meter 95.5 48.1 8597.9 7819.2 17.1 10% Off 94.0 48.5 8618.7 7745.1 15.7 On 87.7 50.1 8680.0 7481.6 17.1 Difference -6.6% 3.4% 0.7% -3.4% 8.4% Loc. Est. p-value 0.261 0.108 0.073 0.352 0.056 Fixed Time p-value 0.133 0.126 0.029 0.222 0.991 25% Off 94.4 48.3 8605.2 7768.1 15.6 On 86.9 50.3 8675.5 7443.8 16.8 Difference -8.0% 4.1% 0.8% -4.2% 7.2% Loc. Est. p-value 0.085 0.014 0.017 0.107 0.031 Fixed Time p-value 0.077 0.086 0.031 0.152 0.808 50% Off 87.7 49.9 8659.9 7390.0 16.4 On 84.1 51.0 8682.8 7252.0 17.2 Difference -4.2% 2.1% 0.3% -1.9% 4.8% Loc. Est. p-value 0.262 0.032 0.107 0.275 0.012 Fixed Time p-value 0.024 0.027 0.021 0.031 0.892 75% Off 84.6 50.8 8682.5 7261.7 17.8 On 84.3 50.9 8682.1 7303.5 18.0 Difference -0.4% 0.3% 0.0% 0.6% 1.3% Loc. Est. p-value 0.909 0.646 0.965 0.441 0.540 Fixed Time p-value 0.029 0.032 0.019 0.050 0.494 100% Off 80.0 52.0 8695.3 7246.3 20.7 On 80.8 51.8 8689.1 7285.7 20.5 Difference 1.0% -0.4% -0.1% 0.5% -1.1% Loc. Est. p-value 0.620 0.314 0.214 0.155 0.599 Fixed Time p-value 0.006 0.006 0.015 0.043 0.013 The location estimation algorithm demonstrates a st atistically significant effect on the performance of the GAP algorithm at low and medium penetration rates. At a 10% penetration rate, the performance of the GAP algorithm experien ced improved speed in the merge area distance traveled, with no measurable effect in any other area. The location estimation algorithm's effect was more noticeable at 25% and 5 0% penetration rates, several metrics either within or near a 10% significance level. As expecte d, the location estimation algorithm produces more inaccurate than accurate estimates at high pen etration rates, and no measurable benefit was found at 75% or 100% penetration rate. It is worth noting that the GAP algorithm did not reduce March 12, 2014 14 benefits at high penetration rates, even when produ cing many inaccurate vehicle location estimates. This suggests that the algorithm can rem ain active even during periods of high connected vehicle penetration rates without degradi ng the performance of the GAP algorithm. CONCLUSIONS AND FUTURE RESEARCH The introduction of individual vehicle location dat a through connected vehicles will allow the development of new types of mobility applications. Research has shown that with higher rates of connected vehicles, these applications produce high er benefits. An algorithm to estimate the locations of unequipped vehicles in a connected veh icle freeway environment was introduced here as a way to both estimate freeway vehicle posi tions as well as improve the performance of connected vehicle applications at low penetration r ates. The algorithm compares the behavior of connected vehicles against the expected behavior pr edicted from a car-following model, in this case the Wiedemann model. Any actual accelerations lower than the expected accelerations by a pre-determined threshold (0.2g as tested here) inse rts an estimated vehicle into a rolling simulation of the network. This vehicle moves as pr edicted by the car-following model without changing lanes until it is overlapped by a connecte d vehicle and deleted from the set of estimates. A new metric, the effective penetration rate, was i ntroduced to measure the performance of the algorithm. Analysis shows that the algorithm is abl e to make more accurate than inaccurate estimates of vehicle locations when penetration rat es are less than or equal to 80%, and when the required accuracy level is five meters or greater i n one-dimension, i.e. within the same lane. Because the algorithm analyzes vehicle interaction in order to make predictions, some congestion upstream of the study area is required f or correct estimates. Furthermore, because estimated vehicles move according to the Wiedemann model, and because the algorithm's model must self-populate, many estimated vehicles have no other vehicles with which to interact, and accelerate to free flow speed. This causes the loca tion estimation algorithm to over-estimate speeds. The location estimation algorithm was tested in the GAP ramp metering algorithm using data from connected vehicles. The GAP algorithm allows o n-ramp vehicle into the freeway when gaps in the merge lane are predicted at a future ti me of merge. By using the location estimation, the performance of the GAP algorithm was improved s ignificantly at low equipped vehicle penetration rates. Most benefits were experienced b etween 10% and 50% connected vehicle penetration rates. At higher penetration rates, the location estimation algorithm did not improve nor degrade the performance of the GAP algorithm, a nd was able to improve upon a static fixed time ramp metering strategy. Statistical significan ce of the improvement of the GAP algorithm was difficult to measure, as ramp metering often pr oduces only minor improvements in simulation. Future research should investigate specific factors in a vehicle's behavior that may improve or reduce the accuracy of a location estimate. For exa mple, certain parts of the roadway such as weaving areas may be known for unusual acceleration s that do not indicate a leading vehicle. Also, the lifespan of an estimated vehicle may be r elated to the quality of the estimate, e.g. an estimated vehicle than can "survive" longer in the simulation without being overlapped by an equipped vehicle may indicate greater confidence in the estimate. March 12, 2014 15