Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Finding the ‘faster’ path in vehicle routing

  • Author(s): Jing Guo 1 ; Yaoxin Wu 2 ; Xuexi Zhang 2 ; Le Zhang 3 ; Wei Chen 2 ; Zhiguang Cao 2 ; Lu Zhang 4 ; Hongliang Guo 5
    • View affiliations
  • Source: Volume 11, Issue 10, December 2017, p. 685 – 694
    DOI:  10.1049/iet-its.2016.0288 , Print ISSN 1751-956X, Online ISSN 1751-9578
© The Institution of Engineering and Technology
Received 04/11/2016, Accepted 13/08/2017, Revised 21/07/2017, Published 30/08/2017

In this study, the authors improve the faster criterion in vehicle routing by extending the bi-delta distribution to the bi-normal distribution, which is a reasonable assumption for travel time on each road link. Based on this assumption, theoretical models are built for an arbitrary path and subsequently adopted to evaluate two candidate paths through probabilistic comparison. Experimental results demonstrate the bi-normal behaviour of link travel time in practice, and verify the faster criterion's superiority in determining the optimal path either on an artificial network with bi-normal distribution modelling link travel time or on a real road network with real traffic data. This study also validates that when the link number of one path is large, the probability density function of the whole path can be simplified by a normal distribution which approximates the sum of bi-normal distributions for each link.

Inspec keywords: vehicle routing; normal distribution

Other keywords: real traffic data; artificial network; theoretical models; real road network; binormal distribution modelling; vehicle routing; arbitrary path; bidelta distribution; road link; probability density function; link travel time

Subjects: Systems theory applications in transportation; Other topics in statistics

References

    1. 1)
      • 24. Sun, L., Yang, J., Mahmassani, H.: ‘Travel time estimation based on piecewise truncated quadratic speed trajectory’, Transp. Res. A, Policy Pract., 2008, 42, (1), pp. 173–186.
    2. 2)
      • 13. Boyles, S.D., Waller, S.T.: ‘A mean-variance model for the minimum cost flow problem with stochastic arc costs’, Networks, 2010, 56, (3), pp. 215–227.
    3. 3)
      • 25. Mori, U., Mendiburu, A., lvarez, M., et al: ‘A review of travel time estimation and forecasting for advanced traveller information systems’, Transportmetrica A, Transp. Sci., 2015, 11, (2), pp. 119–157.
    4. 4)
      • 18. DellOrco, M., Marinelli, M., Silgu, M.A.: ‘Bee colony optimization for innovative travel time estimation, based on a mesoscopic traffic assignment model’, Transp. Res. C, Emerg. Technol., 2016, 66, (1), pp. 48–60.
    5. 5)
      • 10. Cao, Z., Guo, H., Zhang, J., et al: ‘Multiagent-based route guidance for increasing the chance of arrival on time’. Proc. 30th AAAI Conf. on Artificial Intelligence, 2016.
    6. 6)
      • 41. Bennett, G.: ‘Probability inequalities for the sum of independent random variables’, J. Am. Stat. Assoc., 1962, 57, (297), pp. 33–45.
    7. 7)
      • 12. Nie, Y.M., Wu, X., Homem-de Mello, T.: ‘Optimal path problems with second-order stochastic dominance constraints’, Netw. Spatial Econ., 2012, 12, (4), pp. 561–587.
    8. 8)
      • 38. Wenjie, C., Liqiang, G., Zhilei, C., et al: ‘An intelligent guiding and controlling system for transportation network based on wireless sensor network technology’. Proc. 5th Int. IEEE Conf. on Computer and Information Technology, 2005, pp. 810–814.
    9. 9)
      • 29. Miller Hooks, E.: ‘Adaptive least expected time paths in stochastic, time varying transportation and data networks’, Networks, 2015, 37, (1), pp. 35–52.
    10. 10)
      • 19. Celikoglu, H.B.: ‘A dynamic network loading process with explicit delay modelling’, Transp. Res. Emerg. Technol., 2007, 15, (5), pp. 279–299.
    11. 11)
      • 17. Celikoglu, H.B., Gedizlioglu, E., Dell'Orco, M.: ‘A node-based modeling approach for the continuous dynamic network loading problem’, IEEE Trans. Intell. Transp. Syst., 2009, 10, (1), pp. 165–174.
    12. 12)
      • 22. Deniz, O., Aksoy, G., Celikoglu, H.B.: ‘Analyzing freeway travel times within a case study: reliability of route traversal times’. Proc. 16th Int. IEEE Conf. on Intelligent Transportation Systems, 2013, pp. 195–202.
    13. 13)
      • 6. Lim, S., Balakrishnan, H., Gifford, D., et al: ‘Stochastic motion planning and applications to traffic’. Algorithmic Foundation of Robotics VIII, 2009, pp. 483–500.
    14. 14)
      • 34. Fastenrath, U., Becker, M.: ‘Process for selection of a route for a dynamic navigation on private transport’. German Patent: EP 2071287A2, 2008.
    15. 15)
      • 26. Celikoglu, H.B.: ‘Dynamic classification of traffic flow patterns simulated by a switching multimode discrete cell transmission model’, IEEE Trans. Intell. Transp. Syst., 2014, 15, (6), pp. 2539–2550.
    16. 16)
      • 39. Mogridge, M., Fry, S.: ‘Variability of car journey times on a particular route in central London’, Traffic Eng. Control, 1984, 25, (HS-038 005), pp. 510–511.
    17. 17)
      • 42. Bondesson, L.: ‘Generalized gamma convolutions’ (Wiley Online Library, 1997).
    18. 18)
      • 14. Nikolova, E.: ‘Approximation algorithms for reliable stochastic combinatorial optimization’. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2010, pp. 338–351.
    19. 19)
      • 36. Davidson, K.: ‘A flow travel time relationship for use in transportation planning’. Proc. 3rd Australian Road Research Board (ARRB) Conf., Sydney, 1966, vol. 3.
    20. 20)
      • 32. Dong, W., Hai, L.V., Nazarathy, Y., et al: ‘Shortest paths in stochastic time-dependent networks with link travel time correlation’, Transp. Res. Rec. J. Transp. Res. Board, 2013, 2338, (1), pp. 58–66.
    21. 21)
      • 37. Allsop, R.E.: ‘Some possibilities for using traffic control to influence trip distribution and route choice’. Proc. Transportation and Traffic Theory, 1974, vol. 6.
    22. 22)
      • 20. Celikoglu, H.B.: ‘Reconstructing freeway travel times with a simplified network flow model alternating the adopted fundamental diagram’, Eur. J. Oper. Res., 2013, 228, (2), pp. 457–466.
    23. 23)
      • 28. Ta, D., Dellaert, N., Van Woensel, T., et al: ‘Vehicle routing problem with stochastic travel times including soft time windows and service costs’, Comput. Oper. Res., 2013, 40, (1), pp. 214–224.
    24. 24)
      • 5. Fan, Y., Nie, Y.: ‘Optimal routing for maximizing the travel time reliability’, Netw. Spatial Econ., 2006, 6, (3–4), pp. 333–344.
    25. 25)
      • 9. Mazloumi, E., Currie, G., Rose, G.: ‘Using GPS data to gain insight into public transport travel time variability’, J. Transp. Eng., 2010, 136, (7), pp. 623–631.
    26. 26)
      • 33. Cao, Z., Guo, H., Zhang, J., et al: ‘Maximizing the probability of arriving on time: a practical q-learning method’. Proc. 31th AAAI Conf. on Artificial Intelligence, 2017, pp. 4481–4487.
    27. 27)
      • 15. Hutson, K.R., Shier, D.R.: ‘Extended dominance and a stochastic shortest path problem’, Comput. Oper. Res., 2009, 36, (2), pp. 584–596.
    28. 28)
      • 4. Montgromery, F., May, A.: ‘Factors affecting travel times on urban radial routes’, Traffic Eng. Control, 1987, 28, (9), pp. 452–458.
    29. 29)
      • 27. Laporte, G., Louveaux, F., Mercure, H.: ‘The vehicle routing problem with stochastic travel times’, Transp. Sci., 1992, 26, (3), pp. 161–170.
    30. 30)
      • 30. Cao, Z., Guo, H., Zhang, J., et al: ‘Finding the shortest path in stochastic vehicle routing: a cardinality minimization approach’, IEEE Trans. Intell. Transp. Syst., 2016, 17, (6), pp. 1688–1702.
    31. 31)
      • 21. Celikoglu, H.B.: ‘Flow-based freeway travel-time estimation: a comparative evaluation within dynamic path loading’, IEEE Trans. Intell. Transp. Syst., 2013, 14, (2), pp. 772–781.
    32. 32)
      • 11. Fan, Y., Kalaba, R., Moore, J.II: ‘Arriving on time’, J. Optim. Theory Appl., 2005, 127, (3), pp. 497–513.
    33. 33)
      • 35. Sigal, C.E., Pritsker, A.A.B., Solberg, J.J.: ‘The stochastic shortest route problem’, Oper. Res., 1980, 28, (5), pp. 1122–1129.
    34. 34)
      • 40. Rakha, H., El-Shawarby, I., Arafeh, M., et al: ‘Estimating path travel-time reliability’. Proc. Int. IEEE Conf. on Intelligent Transportation Systems, 2006, pp. 236–241.
    35. 35)
      • 44. Wang, Y., Zheng, Y., Xue, Y.: ‘Travel time estimation of a path using sparse trajectories’. Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, 2014, pp. 25–34.
    36. 36)
      • 43. Goodman, N.: ‘Statistical analysis based on a certain multivariate complex Gaussian distribution (an introduction)’, Ann. Math. Stat., 1963, 34, (1), pp. 152–177.
    37. 37)
      • 8. Dean, B.C.: ‘Algorithms for minimum-cost paths in time-dependent networks with waiting policies’, Networks, 2004, 44, (1), pp. 41–46.
    38. 38)
      • 2. Li, S., Meng, M.-H., Chen, W., et al: ‘Sp-nn: a novel neural network approach for path planning’. IEEE Int. Conf. on Robotics and Biomimetics, 2007 (ROBIO 2007), 2007, pp. 1355–1360.
    39. 39)
      • 16. Celikoglu, H.B.: ‘A dynamic network loading model for traffic dynamics modeling’, IEEE Trans. Intell. Transp. Syst., 2007, 8, (4), pp. 575–583.
    40. 40)
      • 31. Chien, S.I., Kuchipudi, C.M.: ‘Dynamic travel time prediction with real-time and historic data’, J. Transp. Eng., 2003, 129, (6), pp. 608–616.
    41. 41)
      • 3. Le, M.K., Bhaskar, A., Chung, E.: ‘Public transport travel-time variability definitions and monitoring’, J. Transp. Eng., 2015, 141, pp. 04014068-1–04014068-9.
    42. 42)
      • 7. Miller-Hooks, E.D., Mahmassani, H.S.: ‘Least expected time paths in stochastic, time-varying transportation networks’, Transp. Sci., 2000, 34, (2), pp. 198–215.
    43. 43)
      • 1. Isaac, G., Lange, T.: ‘Split routing as a part of the urban navigation’. 19th ITS World Congress, 2012, pp. 1–8.
    44. 44)
      • 23. Celikoglu, H.B., Silgu, M.A.: ‘Extension of traffic flow pattern dynamic classification by a macroscopic model using multivariate clustering’, Transp. Sci., 2016, 50, (3), pp. 966–981.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-its.2016.0288
Loading

Related content

content/journals/10.1049/iet-its.2016.0288
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address