The authors present a case study of a multimodal routing system that takes into account both dynamic and stochastic travel time information. A multimodal network model is presented that makes it possible to model the travel time information of each transportation mode differently. This travel time information can either be static or dynamic, or either deterministic or stochastic. Next, a Dijkstra-based routing algorithm is presented that deals with this variety of travel time information in a uniform way. This research focuses on a practical implementation of the system, which means that a number of assumptions were made, like the modelling of the stochastic distributions, comparing these distributions, and so on. A tradeoff had to be made between the performance of the system and the accuracy of the results. Experiments have shown that the proposed system produces realistic routes in a short amount of time. It is demonstrated that routing dynamically indeed results in a travel time gain in comparison to routing statically. By making use of the additional stochastic travel time information even better (i.e. faster), more reliable routes can be calculated. Moreover, it is shown that routing in the multimodal network may have its advantages over routing in a unimodal network, especially during rush hours.

References

1. 1)
  - 5. Kieritz, T., Luxen, D., Sanders, P., Vetter, C., Festa, P.: ‘Distributed time-dependent contraction hierarchies’, in Festa, P. (Ed.): ‘Experimental algorithms’, (Springer, Berlin–Heidelberg, 2010) LNCS, pp. 83–93.
2. 2)
  - 27. Jagadeesh, G.R., Srikanthan, T.: ‘Route computation in large road networks: a hierarchical approach’, IET Intell. Transp. Syst., 2008, 2, (3), pp. 219–227 (doi: 10.1049/iet-its:20080012).
3. 3)
  - 12. Azaron, A., Kianfar, F.: ‘Dynamic shortest path in stochastic dynamic networks: ship routing problem’, Eur. J. Oper. Res., 2003, 144, pp. 138–156 (doi: 10.1016/S0377-2217(01)00385-X).
4. 4)
  - 21. Zografos, K.G., Androutsopoulos, K.N.: ‘Algorithms for itinerary planning in multimodal transportation networks’, IEEE Trans. Intell. Transp. Syst., 2008, 9, (1), pp. 175–184 (doi: 10.1109/TITS.2008.915650).
5. 5)
  - 17. Demeyer, S., Audenaert, P., Slock, B., Pickavet, P., Demeester, P.: ‘Multimodal transport planning in a dynamic environment’. Conf. Intelligent Public Transport Systems (IPTS), Amsterdam, April 2008, pp. 155–167.
6. 6)
  - 11. Ji, X.: ‘Models and algorithm for stochastic shortest path problem’, Appl. Math. Comput., 2005, 170, (1), pp. 503–514 (doi: 10.1016/j.amc.2004.12.015).
7. 7)
  - E.W. Dijkstra . A note on two problems in connexion with graphs. Numerische mathematik , 269 - 271
8. 8)
  - 7. Demiryurek, U., Banaei Kashani, F., Shahabi, C.: ‘A case for time-dependent shortest path computation in spatial networks’. Proc. 18th SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (GIS 10), San Jose, California, 2010, pp. 474–477.
9. 9)
  - 13. Li, H., Bliemer, M.C.J., Bovie, P.H.L.: ‘Strategic departure time choice in a bottleneck with stochastic capacities’. TRB 87th Annual Meeting, Washington DC, January 2008.
10. 10)
  - 29. Bast, H., Carlsson, E., Eignwillig, A., et al: ‘Fast routing in very lage public transportation networks using transfer patterns’. Algorithms – ESA, 2020(LNCS, 6346), pp. 290–301.
11. 11)
  - 6. Nannicini, G., Delling, D., Schultes, D., Liberti, L.: ‘Bidirectional A* search on time-dependent road networks’, Networks, 2012, 59, (2), pp. 240–251 (doi: 10.1002/net.20438).
12. 12)
  - 30. Batz, G.V., Delling, D., Sanders, P., Vetter, C.: ‘Time-dependent contraction hierarchies’. Proc. Workshop on Algorithm Engineering and Experiments (ALENEX), January 2009, pp. 97–105.
13. 13)
  - 23. Caceres, N., Wideberg, J.P., Benitez, F.G.: ‘Review of traffic data estimations extracted from cellular networks’, IET Intell. Transp. Syst., 2008, 2, (3), pp. 179–192 (doi: 10.1049/iet-its:20080003).
14. 14)
  - 9. Sigal, E.H., Pritsker, A.A.B., Solberg, J.J.: ‘The stochastic shortest route problem’, Oper. Res., 1980, 28, pp. 1122–1129 (doi: 10.1287/opre.28.5.1122).
15. 15)
  - 25. http://dna.intec.ugent.be/mdsr/, accessed March 2012.
16. 16)
  - 8. Frank, H.: ‘Shortest paths in probabilistic graphs’, Oper. Res., 1969, 17, pp. 583–599 (doi: 10.1287/opre.17.4.583).
17. 17)
  - 20. Grabener, T., Berro, A., Duthen, Y.: ‘Time dependent multiobjective best path for multimodal urban routing’, Electron. Notes Discret. Math., 2010, 36, pp. 487–494 (doi: 10.1016/j.endm.2010.05.062).
18. 18)
  - 18. Van Nes, R.: ‘Design of multimodal transport networks: a hierarchical approach’. TRAIL Thesis Series T2002/5, 2002, DUP, Delft University, The Netherlands, 2002.
19. 19)
  - 2. Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: ‘Efficient models for timetable information in public transportation systems’, J. Exper. Algorithmics, 2008, 12, article 2.4, pp. 1–39 (doi: 10.1145/1227161.1227166).
20. 20)
  - 15. Samaranayake, S., Blandin, S., Bayen, A.: ‘A tractable class of algorithms for reliable routing in stochastic networks’, Transp. Res. Part C, 2012, 20, pp. 100–217 (doi: 10.1016/j.trc.2011.05.009).
21. 21)
  - 22. Bielli, M., Boulmakoul, A., Mouncif, H.: ‘Object modeling and path computation for multimodal travel systems’, Eur. J. Oper. Res., 2006, 175, pp. 1705–1730 (doi: 10.1016/j.ejor.2005.02.036).
22. 22)
  - 14. Chen, B.Y., Lam, W.H.K., Sumalee, A., Li, Z.: ‘Reliable shortest path finding in stochastic networks with spatial correlated link travel times’, Int. J. Geogr. Inf. Sci., 2012, 26, (2), pp. 365–386 (doi: 10.1080/13658816.2011.598133).
23. 23)
  - 26. Cormen, T.H., Leierson, C.E., Rivest, L.R., Stein, C.: ‘Introduction to algorithms: second edition’ (MIT Press, Cambridge, 2001).
24. 24)
  - 28. Geisberger, R., Sanders, P., Schultes, D., Delling, D.: ‘Contraction hierarchies: faster and simpler hierarchical routing in road networks’. Seventh Workshop on Experimental Algorithms, May–June 2008, pp. 319–333.
25. 25)
  - 24. http://www.ibbt.be/en/projects/overview-projects/p/detail/mobiroute-2, accessed March 2012.
26. 26)
  - 16. Grasman, S.E.: ‘Dynamic approach to strategic and operational multimodal routing decisions’, Int. J. Logist. Syst. Manage., 2006, 2, (1), pp. 96–106 (doi: 10.1504/IJLSM.2006.008220).
27. 27)
  - 10. Hall, R.W.: ‘The fastest path through a network with random time-dependent travel times’, Transp. Sci., 1986, 20, (3), pp. 182–188 (doi: 10.1287/trsc.20.3.182).
28. 28)
  - 4. Delling, D., Nannicini, G.: ‘Core routing on dynamic time-dependent networks’, INFORMS J. Comput., 2011, published online, 24, (2), pp. 187–201 (doi: 10.1287/ijoc.1110.0448).
29. 29)
  - 19. Ayed, H., Khadraoui, D., Habbas, Z., Bouvry, P., Merche, J.F.: ‘Transfer graph approach for multimodal transport problems’, in Le Thi, H.A., Bouvry, P., Pham Dinh, T. (Eds.): ‘Modelling, Computation and Optimization in Information Systems and Management Sciences’ (Springer, Berlin–Heidelberg, 2008), pp. 538–547.
30. 30)
  - 3. Delling, D., Wagner, D.: ‘Time-dependent route planning’, in Ahuja, R., Mohring, R., Zaroliagis, C. (Eds.): ‘Robust and online large-scale optimization’ (Springer, Berlin–Heidelberg, 2009), pp. 207–230.

Dynamic and stochastic routing for multimodal transportation systems

References

Related content