Performance evaluation of choice set generation algorithms for analyzing truck route choice: insights from spatial aggregation for the breadth first search link elimination (BFS-LE) algorithm

ABSTRACT

A new approach is presented to evaluate route choice set generation algorithms, which is based on comparing algorithm-generated choice sets for an origin-destination (OD) location pair against the portfolio of observed routes for that OD pair. The approach offers the ability to evaluate both the generation of relevant routes that are considered by travelers and the generation of extraneous routes that are seldom chosen. The approach is used to evaluate the performance of a breadth-first search link elimination (BFS-LE) algorithm to generate route choice sets for freight trucks. Based on the evaluation, the paper offers guidance on effectively using BFS-LE to maximize generation of relevant routes. It is found that aggregating route choice sets across trips with spatially proximate trip ends can reduce the need to generate large choice sets for each trip. However, such spatial aggregation might yield greater benefits if extraneous routes are eliminated from the choice sets.

KEYWORDS:

• Route choice
• choice set generation
• BFS-LE
• truck-GPS data
• spatial aggregation

Acknowledgements

The authors are grateful to the American Transportation Research Institute (ATRI) for providing the GPS data. Thanks are due to Siva Srinivasan for helpful discussions on the implementation aspects of the BFS-LE algorithm. An early version of this paper was presented at the 2018 Transportation Research Board Annual Meeting. Four anonymous reviewers and the Editor provided valuable comments that helped improve the overall study and its positioning.

Disclosure statement

No potential conflict of interest was reported by the author(s).

ORCID

Divyakant Tahlyan http://orcid.org/0000-0002-1129-6172

Abdul Rawoof Pinjari http://orcid.org/0000-0002-3056-4259

Notes

1 Route choice set generation is important but not always essential. Recent work in two different directions obviates the need to explicitly generate choice sets. The first direction is the sampling of alternatives approach, which assumes a universal choice set from which a subset of routes is sampled with known probability distributions (Frejinger et al., 2009). Route choice models using such sampled choice sets are corrected using correction terms in the utility functions such that the parameter estimates become consistent to the universal choice set. The second direction is the link-based approach, where individuals’ path choices are viewed as a series of successive link choices at each node, beginning from the trip origin (Fosgerau et al., 2013; Zimmermann, Mai, and Frejinger 2017). Specifically, recursive choice models are used within a dynamic programming framework to model the choice of a series of links. Most traditional (and still widely used) approaches to route choice modeling, however, relies on choice set generation.

2 Although aggregation leads to homogeneous choice sets for different travelers between the same OD locations, it is not inconceivable that route alternatives chosen by one traveler are relevant to (and potentially considered by) another traveler. In fact, application of route choice models for prediction purposes in transport model systems with spatially-aggregated OD pairs potentially will benefit from allowing such aggregated choice sets that are inclusive of differences in traveler and spatial characteristics (Hoogendoorn-Lanser and Van Nes 2004).

3 Other variants of repeated least cost search algorithms are (1) simulation (Bierlaire and Frejinger, 2005; Prato and Bekhor, 2006; Ramming, 2001), where stochasticity in travelers’ perceptions of travel costs and/or their preferences is simulated to generate multiple least cost routes, (2) path labeling (Ben-Akiva et al., 1984), where several least cost paths are obtained based on different criteria/labels for the cost function, and (3) link penalty (de la Barra, Perez, and Anez 1993), where links in the current shortest path are penalized with additional impedance to search for the next least cost path.

4 Python code written for implementing BFS-LE in this study is available here: https://github.com/dtahlyan/BFS_LE

5 We explored the use of generalized travel time functions as well. However, our analysis showed better results with free flow travel times than those with the generalized functions explored for this study. Additional discussion on this is provided at the end of section 4.2.

6 A total of 8,211 trips were available from TAZ-level OD pairs that had a minimum of 50 trips per OD pair (Table 1 reports this number). Of these 8,211 trips, we used 6,453 (80%) for route choice model estimation and 1,758 (20%) for model validation. Although it would be desirable to use all available data for model estimation, only these trips were used in this analysis to maintain consistency among the observations used for model estimations across various spatial aggregations. That is, the same set of trips ought to be used to evaluate the route choice sets generated at TAZ-level as well as link-level so that any differences in model performance may be attributed to differences in spatial aggregation as opposed to differences in the data used.

7 Such issues with estimation of value of time are not uncommon, particularly when the cost variable is correlated with the time variable making it difficult to estimate positive values of travel time savings. However, as discussed later, since the findings in the context of choice set generation are similar across all 16 route choice models estimated in this study, the findings are robust to model specification issues.

8 Another measure of predictive ability would be the log-likelihood value over the validation dataset. However, such predictive log-likelihood values cannot be calculated when the chosen alternative is not in the choice set as it was not generated by the choice set generation algorithm (to be precise, the predictive likelihood s zero and log-likelihood is negative infinity). Therefore, the expected overlap measure was chosen as a metric of predictive performance.