Finding the nearest facility for travel and waiting time in a transport network

Document Type : Research Paper

Authors

1 M.Sc., Grad. Industrial Engineering Department, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran

2 Associate Professor, Industrial Engineering Department, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran

3 Assistant Professor, Civil Engineering Department, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran

Abstract

One of user's queries from navigation service is to find the nearest facility in terms of time. The facility that is being questioned by the user as a destination may have a queuing service system (e.g. bank), which means that the cost function of the shortest path includes the waiting time at the destination as well as the travel time. This research conducts in the zone 1 of Mashhad with Bank at destination. In this research, we first calibrate the volume-travel time function to predict travel time by using history volume data of SCATS. The results of the analysis show the Moving-Average model with a period of 4 weeks is more precise to predict volumes and consequently travel time. Then we use Simulation-based method to predict waiting times in Bank. A* algorithm with different scenarios is applied to solve the shortest path problem. This algorithm is compared with the Dijkstra’s algorithm in different networks. Results show by increasing the nodes of network, the required time to solve the A* algorithm is significantly lower than the Dijkstra’s algorithm. In general, this study indicates the A* algorithm and the suggested heuristic function reduce run time for solving the shortest path problems.

Keywords

References

-Ahmadi, S., Ebadi, H. and Valadan, Z. (2008) "A new method for path finding of power transmission lines in geospatial information system using raster networks and minimum of mean algorithm", World Applied Sciences Journal, Vol. 3, pp. 269-77.
-Ahmed, M.S. and Cook A.R. (1979) "Analysis of freeway traffic time-series data by using Box-Jenkins techniques", Research Report, Universirt of Oklahoma.
-Akcelik, Rahmi. (1988) "The highway capacity manual delay formula for signalized intersections", ITE Journal, Vol. 58, pp. 23-27.
-Al-Deek, HM, D'Angelo M.P. and Wang MC. (1998) "Travel time prediction with non-linear time series", In Fifth International Conference on Applications of Advanced Technologies in Transportation Engineering.
-Ardakani, M.K. and Tavana, M. (2015) "A decremental approach with the A∗ algorithm for speeding-up the optimization process in dynamic shortest path problems", Measurement, Vol. 60, pp. 299-307.
-Arem, V., Bart, M., Van Der Vlist, J. M., Muste, M. R. and Smulders, S. A. (1997) "Travel time estimation in the GERDIEN project", International Journal of Forecasting, Vol. 13, pp. 73-85.
-Aron, M., Bhouri N. and Guessous Y. (2014) "Estimating travel time distribution for reliability analysis", Research Report, University Pris-Est.
-Banks, J., Carson, J. S. and Nelson, B. L. (1996) "Discrete-event System Simulation", Prentice Hall.
-Bellman, R. (1958) "On a Routing Problem", Quarterly of Applied Mathematics, Vol. 16, pp. 87-90.
-Bhat, U.N. (2015) "An introduction to queueing theory: modeling and analysis in applications", Birkhäuser.
-Box, G. E. P., Jenkins, G. M., Reinsel, G. C. and Ljung, G. M. (2015) "Time series analysis: forecasting and control", John Wiley & Sons.
-Chandak, A., Bodhale, R. and Burad, R. (2016) "Optimal shortest path using HAS, A star and Dijkstra algorithm", Imperial Journal of Interdisciplinary Research, Vol. 2, pp. 978-80.
-Cherkassky, Boris V, Goldberg A.V. and Radzik, T. (1996) "Shortest paths algorithms: Theory and experimental evaluation", Mathematical Programming,  Vol. 73, pp. 129-74.
-Contain, T. A. (2008) "Real-time travel time estimates using media access control address matching", ITE Journal, Vol. 78, pp. 20-23.
-Cook, J. D. (1999) "All Pairs shortest path algorithms", Engineering Reports, University of Canterbury.
-Cooke, Kenneth L, and Halsey, E. (1966) 'The shortest route through a network with time-dependent internodal transit times", Journal of Mathematical Analysis and Applications, Vol. 14, pp. 493-98.
-Dean, Brian C. (2004) "Shortest paths in FIFO time-dependent networks: Theory and algorithms", Rapport technique, Massachusetts Institute of Technology.
-Gosper, Jeffrey J. (1998) "Floyd-Warshall All Pairs Shortest Pairs Algorithm", Research Report, Brunei University.
-Guessous, Y., Aron, M., Bhouri, N. and Cohen, S. (2014) "Estimating travel time distribution under different traffic conditions", Transportation Research Procedia, Vol. 3, pp. 339-48.
 
-Kamga, Camille N., Kyriacos C. M. and Paaswell, R.E. (2011) "A methodology to
Mahdi Jahangard, Mohammadali Pirayesh , Abolfazl Mohammadzadeh Moghaddam
estimate travel time using dynamic traffic assignment (DTA) under incident conditions", Transportation Research Part C: Emerging Technologies, Vol. 19, pp. 1215-24.
-Kumar, Anil, B., Vanjakshi, L., and Subramanian, S.C. (2013) "Day-wise travel time pattern analysis under heterogeneous traffic conditions", Procedia-Social and Behavioral Sciences, Vol. 104, pp. 746-54.
-Kwon, J., Coifman, B., and Bickel, P. (2000) "Day-to-day travel-time trends and travel-time prediction from loop-detector data", Transportation Research Record: Journal of the Transportation Research Board, Vol. 1717, pp. 120-29.
-Mashhad Traffic and Transportation Organization, (1996) "Comprehensive Transportation Studies in Mashhad, volume- travel time functions", Research Report, Sharif University of Technology.
-Mashhad Traffic and Transportation Organization,(2010)"Updating Comprehensive Transportation Studies in Mashhad,make travel time-volume function models for the main roads", Research Report, Sharif University of Technology.
-Rice, J., and Van Zwet, E. (2004) "A simple and effective method for predicting travel times on freeways", IEEE Transactions on Intelligent Transportation Systems, Vol. 5, pp. 200-07.
-Rilett, Laurence, and Dongjoo P. (2001) "Direct forecasting of freeway corridor travel times using spectral basis neural networks", Transportation Research Record: Journal of the Transportation Research Board, Vol. 1752, pp. 140-47.
-Russell, Stuart J, and Norvig, P. (2002) "Artificial intelligence: a modern approach", Pearson Education Limited.
-Saberian, J., Hamrah M. (2009) "Improving the implementation of routing algorithms in urban networks". In Geomatics Conferences and Exhibitions, K. N. Toosi University of Technology.
-Schmitt, E, and Jula, H. (2006) "Vehicle route guidance systems: Classification and comparison", In Intelligent Transportation Systems Conference, IEEE, pp. 242-47..
-Shiripour, S., and Mahdavi-Amiri, N. (2018) "Optimal distribution of the injured in a multi-type transportation network with damage-dependent travel times: Two metaheuristic approaches", Socio-Economic Planning Sciences, doi.org/10.1016/j.seps.2018.10.011
-Shiripour, S., Mahdavi-Amiri, N., and Mahdavi, I. (2016) "Optimal location-multi-allocation-routing in capacitated transportation networks under population-dependent travel times", International Journal of Computer Integrated Manufacturing, Vol. 29, pp. 652-676.
-Shiripour, S., Mahdavi-Amiri, N., and Mahdavi, I. (2017) "A nonlinear model for location-allocation-routing problem in transportation network with intelligent travel times", International Journal of Operational Research, Vol. 29, pp. 400-431.
-Spencer, M., Labell, L.N., and D May, A. (1989) "Detectors for Freeway Surveillance and Control: An Update", Research Report, University of California, Berkeley.
-Taylor, MAP, Bonsall, P.W., and Young, W. (2000) "Data on travel times. In, Understanding Traffic Systems: Data, Analysis and Presentation". Ashgate Publishing Ltd, pp. 197-206.
-Urbanik, T., Tanaka, A., Lozner, B., Lindstrom, E., Lee, K., Quayle, Sh., Beaird, S., Tsoi, Sh., Ryus, P., and Gettman, D. (2015) "Signal Timing Manual", Research Report, Transportation Research Board.
-Van Lint, JW. (2006) "Reliable real-time framework for short-term freeway travel time prediction", Journal of transportation engineering, Vol. 132, pp. 921-32.
-Wall, JV. (1996) "Practical statistics for astronomers-ii. correlation, data-modelling and sample comparison", Quarterly Journal of the Royal Astronomical Society, Vol. 37, p. 519.
-Wu, Ch.H., Ho, J.M., and Lee, D.T. (2004) "Travel-time prediction with support vector regression", IEEE Transactions on Intelligent Transportation Systems, Vol. 5, pp. 276-81.
-Wu, Q. (2006) "Incremental routing algorithms for dynamic transportation networks", Master of Science, University of Calgary.
-Zhang, X., and Rice, J.A. (2003) "Short-term travel time prediction", Transportation Research Part C: Emerging Technologies, Vol. 11, pp. 187-210.
-Zhu, J.Zh., Cao J.X., and Zhu, Y. (2014) "Traffic volume forecasting based on radial basis function neural network with the consideration of traffic flows at the adjacent intersections", Transportation Research Part C, Emerging Technologies, Vol. 47, pp. 139-54.
 
 

Files

Share

How to cite

Statistics