Applying branch & bound technique to route choice set generation

Carlo Giacomo Prato, Shlomo Bekhor

Research output: Contribution to journalJournal articleResearchpeer-review


An algorithm to solve explicitly the path enumeration problem is proposed. This algorithm is based on the branch-and-bound technique and belongs to the class of deterministic methods along with existing approaches that combine heuristic or randomization procedures with shortest-path search. The branch-and-bound algorithm is formulated, and a methodology is designed for the application of deterministic approaches to a real case study. Path sets generated with different methods are compared for behavioral consistency, namely, the ability to reproduce actual routes chosen by individuals driving habitually from home to work. Choice set compositions for modeling purposes are determined for the consistency of the path generation process with the observed behavior. Further, model estimates and performance for different route choice specifications are examined for both path set compositions. Results suggest that the proposed branch-and-bound algorithm generates realistic and heterogeneous routes, reproduces better the observed behavior of the interviewed drivers, and produces a good choice set for route choice model estimation and performance comparison.
Original languageEnglish
Book seriesTransportation Research Record
Pages (from-to)19-28
Publication statusPublished - 2006
Externally publishedYes
Event85th Annual Meeting of the Transportation Research Board - Washington, D.C.
Duration: 1 Jan 2006 → …


Conference85th Annual Meeting of the Transportation Research Board
CityWashington, D.C.
Period01/01/2006 → …


Dive into the research topics of 'Applying branch & bound technique to route choice set generation'. Together they form a unique fingerprint.

Cite this