An Emergency Vehicle Routing Model in Small and Medium Transportation Networks

Document Type : Scientific - Research

Authors

1 Faculty of Civil Engineering, Department of Transportation Planning, Islamic Azad University, Science and Research Branch, Tehran, Iran

2 Faculty of Civil and Environment Engineering, Tarbiat Modares University, Tehran, Iran

3 Faculty of Industrial Engineering, Islamic Azad University, Tehran South Branch, Tehran, Iran

Abstract

These days, emergency request responding in a short time is a highly challenging issue. The main goal of current research is modeling an optimization problem for emergency vehicle routing on small and medium-sized networks and solving the problem by a novice algorithm. The suggested algorithm inputs are the network, location and number of requests, vehicles, and hospitals. The objective is to minimize total travel time of vehicles plus the time that the last request is responded completely. The algorithm output is the vehicle and hospital assignment to each request and requests' responding order on the network. After developing the mathematical model of the problem, 138 random samples are produced on a network with 7 nodes and 16 links. The number of feasible answers, which is depended on the number of requests, vehicles, and hospitals, is tried to be reduced by assuming a fixed order for responding the requests. Hence, 3 different scenarios of request order are examined and it is found out that arranging the requests based on distance from the nearest vehicle results in better answers (lower total travel times). An innovative algorithm is presented for solving the problem which reduces the solving time to 5 seconds; while finding the precise answer needs time up to 810 seconds. The results show that the difference between more than 80 percent of answers found with the suggested algorithm and the precise answer is lower than 10 percent and this difference is less than 30 percent in more than 94 percent of the answers.

Keywords

References

- اعتباری، ف. و دشتیان، ز. (1397) “مدلسازی مسئله مسیریابی-موجودی سبز با در نظر گرفتن وسائل نقلیه هیبریدی و حل آن توسط الگوریتم جستجوی همسایگی بزرگ”، فصلنامه مهندسی حمل و نقل، انتشار آنلاین
- معماری، پ.، پرتویی، م.، جولای، ف. و توکلی مقدم، ر. (1396) «توسعه مدل مکان‌یابی- مسیریابی با در نظر گرفتن رضایت مشتری و دریافت و تحویل همزمان»، فصلنامه مهندسی حمل و نقل، انتشار آنلاین
- صبوحی، ف. و بزرگی امیری، الف. (1396) «مسیریابی و زمان‌بندی وسایل حمل و نقل برای توزیع کمک‌های امدادی با در نظر گرفتن تحویل جزئی و انبار چندگانه»، فصلنامه مهندسی حمل و نقل، دوره 9، شماره 1
- Caric, T. and Gold, H. (2008) “Vehicle routing problem”, Vienna: I-Tech Education and Publishing KG
- Cordeau, J. F. and Laporte, G. (2003) “A tabu search heuristic for the static multi-vehicle dial-a-ride problem”, Transportation Research Part B, *Vol. 37, No. 6, pp. 579-594
- Cordeau, J. F. and Laporte, G. (2007) “The dial-a-ride problem: models and algorithms”, Annals of Operations Research, Vol. 153, No. 1, pp. 29-46
- Cimen, M. and Soysal, M. (2017) “Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm”, Transportation Research Part D, Vol. 54, pp. 82-98
- Dantzig, G. B. and Ramser, J. H. (1959) “The truck dispatching problem”, Management science, Vol. 6, No. 1, pp. 80-91
- El-Sherbeny, N. A. (2010) “Vehicle routing with time windows: An overviewof exact, heuristic and metaheuristic methods”, Journal of King Saud University (Science), No.  22, pp. 123–131
- Jlassi, J., Euchi, J. and Chabchoub H. (2012) “Dial-a-Ride and Emergency Transportation Problems in Ambulance Services”, Computer Science and Engineering, Vol. 2, No. 3, pp. 17-23
- Kirchler, D. and Wolfer Calvo, R. (2013) “A granular tabu search algorithm for the dial-a-rideProblem”, Transportation Research Part B, Vol. 56, pp. 120-135
- Kirci, P. (2016) “An optimization algorithm for a capacitated vehicle routing problem with time windows”, Sadhana Academy proceedings in Engineering Sciense, Vol. 41, No. 5, pp. 519-52
- Liu, M., Luo Z. and Lim, A. (2015) “A branch-and-cut algorithm for a realistic dial-a-ride problem”, Transportation Research Part B, No. 81, pp. 267-288
- Muelas, S., LaTorre, A. and Peña, J. (2015) “A distributed VNS algorithm for optimizing dial-a-rideproblems in large-scale scenarios”, Transportation Research Part C, No. 54, pp. 110–130
- Parragh, S. N. (2011) “Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem”, Transportation Research Part C, Vol. 19, No.5, pp. 912-930
- Ritzinger, U., Puchinger, J. and Hartl R. F. (2016) “A survey on dynamic and stochastic vehicle routing problems”, International Journal of Production Research (online), Vol. 54, No. 1, pp. 215-231
- Talarico, L., Meisel, F. and Sörensena K. (2015) “Ambulance routing for disaster response with patient groups”, Computers & Operations Research, No. 56, pp. 120-133
- Zhang, Z., Liu, M. and Lim, A. (2015) “A Memetic Algorithm for the Patient Transportation Problem”, Omega-the International Journal of Management Science, No. 54, pp. 60-71
Quarterly Journal of Transportation Engineering
Volume 12, Issue 1 - Serial Number 46
September 2020
Pages 139-161

Files

History

  • Receive Date: 07 March 2018
  • Revise Date: 10 June 2019
  • Accept Date: 10 August 2019

Share

How to cite

Statistics