U.S. Department of Transportation
Federal Highway Administration
1200 New Jersey Avenue, SE
Washington, DC 20590
202-366-4000


Skip to content
Facebook iconYouTube iconTwitter iconFlickr iconLinkedInInstagram

Federal Highway Administration Research and Technology
Coordinating, Developing, and Delivering Highway Transportation Innovations

Fact Sheet
This fact sheet is an archived publication and may contain dated technical, contact, and link information
Publication Number: FHWA-HRT-06-136
Date: December 2006

Freeway Lane Selection Algorithm

PDF version of Fact Sheet (1.64 MB)

At the heart of the Next Generation SIMulation (NGSIM) program is the development of freely available driver behavior algorithms that represent the fundamental logic within microscopic traffic simulation models. A comprehensive survey of NGSIM stakeholder groups, coupled with an assessment of existing microsimulation systems and driver behavior algorithms, revealed a number of high-priority needs for algorithm development under the NGSIM program. As a result, researchers developed the Freeway Lane Selection (FLS) algorithm as one of the first of several algorithms under the NGSIM program.

Description

The FLS algorithm will enable transportation professionals to more accurately model lane-changing behavior on freeways. Existing traffic simulation models typically simulate the behavior of drivers changing lanes only to the immediate left or right lane. The FLS algorithm, however, incorporates the "target lane" concept, in which drivers target the "best" lane on the entire freeway and may make multiple lane changes on their way to the target lane. This behavior is especially prevalent on freeways with high-occupancy vehicle (HOV) lanes, where a driver may target an HOV lane and need to make several lane changes to get there. Whereas existing simulation models consider only the adjacent lanes for each lane change, the FLS algorithm more realistically captures a driver's intention to target an HOV lane as a single decision and make multiple lane changes to get to the target lane.

Based on a generalized lane-changing model, the FLS algorithm consists of two steps: choice of target lane and gap acceptance decisions. The target lane is the lane the driver perceives as most desirable by considering a wide range of factors and goals. The FLS algorithm assigns a "score" to each lane based on 22 variables, such as the average speed of drivers in each lane and the distance to an upcoming exit, to determine the most desirable target lane. If a driver decides to target another lane besides their current lane, then the FLS algorithm will determine whether the gap, or space between vehicles, in an adjacent lane is acceptable for the driver to then proceed with changing lanes. The structure of the lane-changing model is shown in figure 1. An illustration of a driver making a gap acceptance decision is shown in figure 2.

Figure 1. Chart. Figure 1. Example illustration of the lane selection algorithm. In this example, there are five lanes on the freeway, so the driver can target any one of the five lanes. This top row of this illustration is labeled Current lane and includes a box labeled Lane 3. Beneath that box, five arrows lead down toward the next lower row, which is labeled Choose target lane. In that row sit three circles, labeled from left to right, Lane 1, Lane 3, and Lane 5. Each of the outer circles has two arrows leading on diagonals to the next lower horizontal row; the center circle has one vertical arrow, for a total of five arrows. The four outer arrows point to four circles in the next lower row, which is labeled Look for gap. The four circles are labeled, from left to right, Accept Gap, Reject Gap, Accept Gap, Reject Gap. The arrow from the center circle in the Choose target lane row leads directly to a box in the bottom row, which is labeled Make choice. Each of the circles in the Look for gap row also point toward boxes in the bottom row. Altogether, there are five boxes in the bottom row. Those boxes from left to right read, Change Left, No Change, No Change, Change Right, and No Change.

Figure 1. Example illustration of the lane selection algorithm. In this example, there are five lanes on the freeway, so the driver can target any one of the five lanes.

Figure 2. Illustration. This illustration shows how a driver makes a gap acceptance decision. In the illustration, vehicle C has chosen the left-most lane as the target lane primarily because it is less congested than the other two lanes (based on calculations from the FLS algorithm) and is now determining whether the adjacent gap between vehicles A and B is acceptable to make a lane change maneuver. This illustration shows three lanes of freeway traffic with numerous vehicles in each lane. A vehicle in the right-most lane is labeled as vehicle C, and two consecutive vehicles in the middle lane are labeled as vehicles A and B. No other vehicles are labeled. Vehicle C is positioned in between vehicles A and B. There is a line pointing to the back of vehicle A and another line pointing to the front of vehicle B. The distance between these two lines is labeled as “Adjacent Gap”.  In the illustration, vehicle C intends to change lanes to the middle lane and is determining whether the Adjacent Gap is acceptable.

Figure 2. This illustration shows how a driver makes a gap acceptance decision. In the illustration, vehicle C has chosen the left-most lane as the target lane primarily because it is less congested than the other two lanes (based on calculations from the FLS algorithm) and is now determining whether the adjacent gap between vehicles A and B is acceptable to make a lane change maneuver.

Led by a member of the NGSIM team from the Massachusetts Institute of Technology, the FLS algorithm development process consisted of estimating the algorithm from the Interstate 80 vehicle trajectory dataset and then validating the algorithm using aggregate data, such as the data available from vehicle loop detectors. (For more information about the Interstate 80 dataset, see the Interstate 80 Freeway Dataset NGSIM Fact Sheet, FHWA-HRT-06-137.) The NGSIM stakeholders provided valuable feedback throughout the process based on their diverse expertise in the field of traffic simulation. Once complete, the algorithm was validated using real-world datasets with commercial microsimulation software systems (VISSIM, AIMSUN NG, and Paramics). The developers of the software systems also were involved in the entire algorithm development process. Their willingness to incorporate and validate the algorithm illustrates the success of the public-private partnerships developed through the NGSIM program.

Benefits

NGSIM research indicated that the FLS algorithm is statistically more accurate than conventional lane-changing algorithms for estimating several performance measures, including average speeds, lane distribution, and lane changes by vehicle. Due to this improved accuracy, the integration of the FLS algorithm can improve traffic simulation models compared to typical state-of-the-practice models.

As commercial developers incorporate the FLS algorithm into their simulation software, transportation practitioners will be able to use simulation software confidently, with the knowledge that traffic simulation experts developed the software's core algorithms using high-quality, real-world datasets. Improving the core algorithms will ultimately lead to more reliable and valid transportation decisions, which is critical in the current environment of both shrinking transportation budgets and growing demand for accountable and efficient transportation investments.

Algorithm Availability

The FLS algorithm, along with supporting documentation, is available for download free of charge at the NGSIM Web site at http://ops.fhwa.dot.gov/trafficanalysistools/ngsim.htm. In addition, the developers of VISSUM, AIMSUN NG, and Paramics plan to incorporate the FLS algorithm into the commercially available versions of their software, as do the developers of Cube Dynasim and TransModeler™.

For more information, visit the NGSIM Web site at http://ops.fhwa.dot.gov/trafficanalysistools/ngsim.htm or contact:

John Halkias
Federal Highway Administration
Office of Transportation Management
Room 3404, HOTM-1
400 Seventh Street, SW
Washington, DC 20590
202-366-2183
john.halkias@fhwa.dot.gov

James Colyar
Federal Highway Administration
Office of Operations Research and Development
6300 Georgetown Pike
McLean, VA 22101
202-493-3282
james.colyar@fhwa.dot.gov

 

The Turner-Fairbank Highway Research Center (TFHRC) has more than 24 laboratories for research in the following areas: safety; operations, including intelligent transportation systems; materials technology; pavements; structures; and human centered systems. The expertise of TFHRC scientists and engineers covers more than 20 transportation-related disciplines. These laboratories are a vital resource for advancing this body of knowledge created and nurtured by our researchers. The Federal Highway Administration's Office of Research, Development, and Technology operates and manages TFHRC to conduct innovative research to provide solutions to transportation problems both nationwide and internationally. TFHRC is located in McLean, Virginia. Information on TFHRC is available on the Web at www.fhwa.dot.gov/research/tfhrc.

This Next Generation SIMulation fact sheet provides concise information about a TFHRC facility.

Publication No. FHWA-HRT-06-136

PDF files can be viewed with the Acrobat® Reader®