An Agent-based Route Choice Model with Learning and Exchange of Information

Recently published

Abstracturbansci-02-00058-g001-550

Planning models require consideration of travelers with distinct attributes (value of time (VOT), willingness to pay, travel budgets, etc.) and behavioral preferences (e.g., willingness to switch routes with potential savings) in a differentiated market (where routes have varying tolls and levels of service). This paper proposes to explicitly model the formation and spreading of spatial knowledge among travelers, following cognitive map theory. An agent-based route choice (ARC) model was developed to track choices of each individual decision-maker in a road network over time and map individual choices into macroscopic flow pattern. ARC has been applied to both the Sioux Falls and Chicago sketch networks. Comparisons between ARC and existing models (user equilibrium (UE) and stochastic user equilibrium (SUE)) on both networks show ARC is valid and computationally tractable. In brief, this paper specifically focuses on the route choice behavior, while the proposed model can be extended to other modules of transportation planning under an integrated framework.

Keywords: agent-based model; route choice; traffic assignment; travel demand modeling

An empirical study of the deviation between actual and shortest travel time paths

Recently published

DeviationAbstract: This study evaluates routes followed by residents of the Minneapolis–St. Paul metropolitan area, as measured by the Global Positioning System (GPS) component of the 2010/11 Twin Cities Travel Behavior Inventory (TBI). It finds that most commuters used paths longer than the shortest path. This is in part a function of trip distance (+, longer distance trips deviate more), trip circuity (−, more circuitous trips deviate less), number of turns (+, trips with more turns per kilometer deviate more), age of driver (−, older drivers deviate less), employment status (+, part-time workers deviate more), flexibility in work hours (+, more flexibility deviate more), and household income (−, higher-income travelers deviate less). Some reasons for these findings are conjectured.

Author keywords: Global positioning system (GPS); Shortest path; Route choice; Wardrop’s principles; Travel behavior.

 Indifference Bands for Route Switching.

Printed, (after more than a year in “online first” purgatory) and now available for FREE Viewing.11116_2016_9699_Fig3_HTML

Abstract: The replacement I-35W bridge in Minneapolis saw less traffic than the original bridge though it provided substantial travel time saving for many travelers. This observation cannot be explained by the classical route choice assumption that travelers always take the shortest path. Accordingly, a boundedly rational route switching model is proposed assuming that travelers will not switch to the new bridge unless travel time saving goes beyond a threshold or “indifference band”. To validate the boundedly rational route switching assumption, route choices of 78 subjects from a GPS travel behavior study were analyzed before and after the addition of the new I-35W bridge. Indifference bands are estimated for both commuters who were previously bridge users and those who never had the experience of using the old bridge. This study offers the first empirical estimation of bounded rationality parameters from GPS data and provides guidelines for traffic assignment.

Keywords:

Bounded rationality, Indifference band, Empirical estimation, GPS study, Route Choice

 

Multiday GPS Travel Behavior Data for Travel Analysis

I am pleased to report that a new FHWA-supported study: “Multiday GPS Travel Behavior Data for Travel Analysis” (PDF) is out. Our contribution is Chapter 4.0 An Empirical Study of the Deviation between Actual and Shortest-Travel-Time Paths. The report was coordinated by RSG, and the overview is below:

Introduction to Report

By Mark Bradley (RSG)

The use of GPS devices to collect trip-specific data as part of household travel surveys has increased steadily in recent years, and will likely become the main mode of travel survey data collection in the future as smartphone-based platforms for collecting travel data come into use. Compared to diary-based methods, the advantages of GPS data capture include the following:

  • The time and location of each trip end can be captured with more precision.
  • There is less potential for respondents to omit entire trips or activities from the survey.
  • The data can be used to trace the route traveled for any particular trip.
  • It becomes more cost-effective to capture multiple days of travel for each respondent.

These unique aspects of GPS data enable new types of behavioral analysis relative to those conducted with more traditional travel survey data. In particular, multiday data capture, in combination with more precise and complete travel data on each day, allows researchers to investigate day-to-day variability in travel behavior at the individual and household level. Such analyses can provide more insight into peoples’ travel patterns at a broader level, and guide future efforts in modeling and predicting travel behavior and designing transportation policies.

Large-sample, multiday GPS datasets from household travel surveys are still relatively limited in quantity, as is the expertise required to process point-by-point GPS trace data into trip-level data that can be used by most analysts. To address these issues, the US Department of Transportation and the National Renewable Energy Laboratory (NREL) have created the Transportation Secure Data Center (TSDC).[1] The TSDC allows researchers to access preprocessed data from almost one dozen different multiday GPS travel datasets from across the United States; it also allows researchers to analyze these data in a secure environment that ensures the protection of data privacy.

The two main objectives of this project are: 1) to provide new examples of the type of valuable research that can be done using multiday GPS travel survey data; and 2) to demonstrate that such research can be conducted in the TSDC research environment. Each of the following four chapters describes a research project that was funded and carried out as part of this project. The four research topics were originally specified by RSG, with input from FHWA, and then further refined by the authors during the course of their research.

In “The Effect of Day-to-Day Travel Time Variability on Auto Travel Choices,” Jennifer Dill, PhD, and Joseph Broach, PhD (candidate), of Portland State University address the important research topic of measuring the effect of auto network reliability on drivers’ choices. Using data from a 7-day vehicle-based GPS survey in the Atlanta region and a longer-duration vehicle-based GPS survey in the Seattle region, the authors identified several cases where respondents made multiple car trips between the same origin-destination (O-D) pairs during the survey period, and measured the actual experienced day-to-day travel time variation for those O-D pairs. The authors report several interesting analyses showing that such variability is related to trip and traveler characteristics, including trip purpose, distance, and household income.

In “Multiday Variation in Time Use and Destination Choice in the Bay Area Using the California Household Travel Survey,” Kate Deutsch-Burgner, PhD, of Data Perspectives Consulting, investigates day-to-day variation in the number, types, and level of dispersion (distance) of destinations visited during the specific days of a 3-day person-based GPS survey in the California Bay Area. Using the technique of latent class cluster analysis (LCCA), she is able to distinguish clearly different patterns of variability in terms of number of trips and type and dispersion of destinations. This analysis method shows promise for addressing the complexity of multiday travel data, and may become even more useful as future person-based (e.g., smartphone-based) GPS datasets include a greater number of travel days and a potentially wider variety of different patterns across the days.

In “Capturing Personal Modality Styles Using Multiday GPS Data-Findings from the San Francisco Bay Area,” Yanzhi “Ann” Xu, PhD, and Randall Guensler, PhD, of Trans/AQ, Inc., analyze the same multiday GPS dataset from the Bay Area that was used for the analysis described in the preceding chapter. In this analysis, however, the focus is on day-to-day variation in mode choice-research for which person-based, rather than vehicle-based, GPS data collection is clearly necessary. The authors were able to identify distinct groups of individuals in terms of whether they always used the same mode or used a variety of modes, and in terms of whether auto or alternative modes were used more often. They were also successful in relating these groupings to different person and household characteristics. The propensity to use multiple modes would benefit standard travel modeling methods, as someone who usually uses auto but also uses transit one or two days per week may be more likely to increase his or her transit use in response to service changes, as compared to someone who never uses transit at all.

Finally, in “An Empirical Study of the Deviation between Actual and Shortest-Travel-Time Paths,” Wenyun Tang, PhD (candidate), and David Levinson, PhD, of the University of Minnesota, use multiday person-based GPS data from the Minneapolis region Travel Behavior Inventory (TBI) to determine how often drivers use the shortest path for their home-to-work trip, and look at patterns in the deviation in travel time between the shortest path and the actual path. In terms of day-to-day variability, the authors were not able to identify many cases where respondents made the same direct home-to-work auto trip on multiple days. This outcome indicates that analyses that measure travel behavior across multiple days (rather than simply treating them as separate single days) will tend to require large sample sizes, particularly when the analysis focuses on a specific type of behavior (e.g., direct home-to-work auto trips).

The research presented in the following four chapters provides interesting findings in their own right, and insights into the types of research designs and methods that will be valuable in analyzing multiday GPS data as it becomes more ubiquitous and accessible in the future. The authors generally recognize that their methods could benefit from larger sample sizes, in terms of the number of respondents, and particularly in terms of the number of days per respondent. (For example, use of 7-day GPS data capture periods would allow analysis of patterns, including both weekdays and weekends.) The authors also note the critical importance of how the GPS trace data are processed into trip-level data, and the need for evolving practices and standards in GPS data processing. Finally, the authors describe the value of the TSDC in making these unique datasets available while providing a secure and productive research environment.

PathFinding.js

Pathfinding
Rafael Pereira sends me to “Efficiency Comparison of Pathfinding Algorithms

A very cool interactive comparison of efficiency in pathfinding algorithms (via @hmason).

A Portfolio Theory of Route Choice

PortfolioTheory

Recently published:

Although many individual route choice models have been proposed to incorporate travel time variability as a decision factor, they are typically still deterministic in the sense that the optimal strategy requires choosing one particular route that maximizes utility. In contrast, this study introduces an individual route choice model where choosing a portfolio of routes instead of a single route is the best strategy for a rational traveler who cares about both journey time and lateness when facing stochastic network conditions. The proposed model is compared with UE and SUE models and the difference in both behavioral foundation and model characteristics is highlighted. A numerical example is introduced to demonstrate how such model can be used in traffic assignment problem. The model is then tested with GPS data collected in metropolitan Minneapolis–St. Paul, Minnesota. Our data suggest there is no single dominant route (defined here as a route with the shortest travel time for a 15 day period) in 18% of cases when links travel times are correlated. This paper demonstrates that choosing a portfolio of routes could be the rational choice of a traveler who wants to optimize route decisions under variability.

JEL-Code: R41, R48, D63
Keywords: Transportation planning, route choice, travel behavior, link performance

Route damn spot, Route I say. or Rooting for a Rout.

Route

In my lab today we had a discussion over the proper way to say the word “Route” dictionaries and professional linguists who were consulted give both “root” and “rout” as acceptable pronunciations, leaving us no wiser than before.
But online, we find this Dialect survey (color matching the map).

Dialect Survey Results:

26. route (as in, “the route from one place to another”) 
     a. rhymes with “hoot” (29.99%)
     b. rhymes with “out” (19.72%)
     c. I can pronounce it either way interchangeably (30.42%)
     d. I say it like “hoot” for the noun and like “out” for the verb. (15.97%)
     e. I say it like “out” for the noun and like “hoot” for the verb. (2.50%)
     f. other (1.40%)
     (11137 respondents)

 

As a north-easterner myself, It was always take Root 29 or Root 95, but in the South, we were on Rout 85. In the midwest, it seems more Rout than Root. In any case the “e” is superfluous, as it doesn’t modify in a consistent way, since we already have a double vowel. The word is also superfluous, since we already have the word “road” from the same root. Damn French imports.

Etymology online says: route (n.)
early 13c., from O.Fr. rute “road, way, path,” from L. rupta (via) “(a road) opened by force,” from rupta, fem. pp. of rumpere “to break” (see rupture). Sense of “fixed or regular course for carrying things” (cf. mail route) is 1792, an extension of the meaning “customary path of animals” (early 15c.).

See also this on Highway Linguistics

Do people use the shortest path? An empirical test of Wardrop’s first principle.

Example of Route Detecting and Comparison of Alternative Paths
Example of Route Detecting and Comparison of Alternative Paths

Working paper:

Most recent route choice models, following either the random utility maximization or rule-based paradigm, require explicit enumeration of feasible routes. The quality of model estimation and prediction is sensitive to the appropriateness of the consideration set. However, few empirical studies of revealed route characteristics have been reported in the literature. This study evaluates widely applied shortest path assumption by evaluating morning commute routes followed by residents of the Minneapolis – St. Paul metropolitan area. Accurate GPS and GIS data were employed to reveal routes people used over an eight to thirteen week period. Most people do not choose the shortest path. Using three weeks of that data, we find that current route choice set generation algorithms do not reveal the majority of paths that individuals took. Findings from this study may provide guidance for future efforts in building better route choice models.

JEL-Code: R41, R48, D63

Keywords: Transportation planning, route choice, travel behavior, link performance

A Portfolio Theory of Route Choice

Trade-offs between travel time and travel time reliability are central to Zhu and Levinson's Portfolio Theory of Route Choice
Trade-offs between travel time and travel time reliability are central to Zhu and Levinson’s Portfolio Theory of Route Choice

Working paper:

  • Zhu, Shanjiang and David Levinson (2010), A Portfolio Theory of Route Choice Presented at 4th International Symposium on Transportation Network Reliability, July 2010, Minneapolis, MN.

Although many individual route choice models have been proposed to incorporate travel time variability as a decision factor, they are typically still deterministic in the sense that the optimal strategy requires choosing one particular route that maximizes utility. In contrast, this study introduces an individual route choice model where choosing a portfolio of routes instead of a single route is the best strategy for a rational traveler who cares about both journey time and lateness when facing stochastic network conditions. The model is then tested with GPS data collected in metropolitan Minneapolis-St. Paul, Minnesota. Our data suggest strong correlation among link speed when analyzing morning commute trips. There is no single dominant route (defined here as a route with the shortest travel time for a 15 day period) in 18% of cases when links travel times are correlated. This paper demonstrates that choosing a portfolio of routes could be the rational choice of a traveler who wants to optimize route decisions under variability.

JEL-Code: R41, R48, D63

Keywords: Transportation planning, route choice, travel behavior, link performance