Applying Branch-and-Bound Technique to Route Choice Set Generation

Abstract

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.

Get full access to this article

View all access options for this article.

References

Cascetta

Russo

and Vitetta

. Stochastic User Equilibrium Assignment with Explicit Path Enumeration: Comparison of Models and Algorithms. Proc., 8th IFAC Symposium on Transportation Systems, Technical University of Crete, Chania, 1997, pp. 1078–1084.

Prashker

J. N.

and Bekhor

. Route Choice Models used in the Stochastic User Equilibrium Problem: A Review. Transport Reviews, Vol. 24, 2004, pp. 437–463.

Dijkstra

E. W.

Note on Two Problems in Connection with Graphs. Numerical Mathematics, Vol. 1, 1959, pp. 269–271.

Van der Zijpp

N. J.

and Fiorenzo-Catalano

. Path Enumeration by Finding the Constrained K-Shortest Paths. Transportation Research, Vol. 39B, 2005, pp. 545–563.

Ben-Akiva

Bergman

M. J.

Daly

A. J.

and Ramaswamy

. Modeling Inter-Urban Route Choice Behaviour. Proc., of the Ninth International Symposium on Transportation and Traffic Theory, VNU Science Press, Utrecht, Netherlands, 1984, pp. 299–330.

Dial

R. B.

Bicriterion Traffic Equilibrium: T2 Model, Algorithm, and Software Overview. In Transportation Research Record: Journal of the Transportation Research Board, No. 1725, Transportation Research Board of the National Academies, Washington, D.C., 2000, pp. 54–62.

Azevedo

J. A.

Santos Costa

M. E. O.

Silvestre Madera

J. J. E. R.

and Vieira Martins

E. Q.

. An Algorithm for the Ranking of Shortest Paths. European Journal of Operational Research, Vol. 69, 1993, pp. 97–106.

De la Barra

Perez

and Anez

. Multidimensional Path Search and Assignment. Proc., 21st PTRC Summer Annual Meeting, PTRC Education and Research Services Ltd., London, 1993.

Park

and Rilett

L. R.

. Identifying Multiple and Reasonable Paths in Transportation Networks: A Heuristic Approach. In Transportation Research Record 1607, TRB, National Research Council, Washington, D.C., 1997, pp. 31–37.

10.

Scott

Pabon-Jimenez

and Bernstein

. Finding Alternatives to the “Best” Path. Presented at 76th Annual Meeting of the Transportation Research Board, Washington, D.C., 1997.

11.

Sheffi

and Powell

W. B.

. An Algorithm for the Equilibrium Assignment Problem with Random Link Times. Networks, Vol. 12, 1982, pp. 191–207.

12.

Fiorenzo-Catalano

and Van der Zijpp

N. J.

. A Forecasting Model for Inland Navigation Based on Route Enumeration. Proc., European Transport Conference, PTRC Education and Research Services Ltd., London, 2001, pp. 1–11.

13.

Bekhor

Ben-Akiva

M. E.

and Ramming

. Route Choice: Choice Set Generation and Probabilistic Choice Models. Proc., 4th TRISTAN Conference, Azores, Portugal, 2001.

14.

Friedrich

Hofsäss

and Wekeck

. Timetable-Based Transit Assignment Using Branch and Bound Technique. In Transportation Research Record: Journal of the Transportation Research Board, No. 1752, TRB, National Research Council, Washington, D.C., 2001, pp. 100–107.

15.

Hoogendoorn-Lanser

Modelling Travel Behaviour in Multi-modal Networks. TRAIL Research School, Netherlands, 2005.

16.

Prato

C. G.

Bekhor

and Pronello

. Methodology for Exploratory Analysis of Latent Factors Influencing Drivers’ Behavior. In Transportation Research Record: Journal of the Transportation Research Board, No. 1926, Transportation Research Board of the National Academies, Washington, D.C., 2005, pp. 115–125.

17.

Prato

C. G.

Latent Factors and Route Choice Behaviour. Ph.D. thesis. Turin Polytechnic, Italy, 2005.

18.

Cascetta

Nuzzolo

Russo

and Vitetta

. A Modified Logit Route Choice Model Overcoming Path Overlapping Problems: Specification and Some Calibration Results for Interurban Networks. Proc., Thirteenth International Symposium on Transportation and Traffic Theory, Pergamon, Lyon, France, 1996, pp. 697–711.

19.

Ramming

Network Knowledge and Route Choice. Ph.D. thesis. Massachusetts Institute of Technology, Cambridge, Mass., 2001.

20.

Prashker

J. N.

and Bekhor

. Investigation of Stochastic Network Loading Procedures. In Transportation Research Record 1645, TRB, National Research Council, Washington, D.C., 1998, pp. 94–102.

21.

Bekhor

and Prashker

J. N.

. Stochastic User Equilibrium Formulation for Generalized Nested Logit Model. In Transportation Research Record: Journal of the Transportation Research Board, No. 1752, Transportation Research Board of the National Academies, Washington, D.C., 2001, pp. 84–90.

22.

Vovsha

and Bekhor

. Link-Nested Logit Model of Route Choice: Overcoming the Route Overlapping Problem. In Transportation Research Record 1645, TRB, National Research Council, Washington, D.C., 1998, pp. 133–142.