Abstract
This research work focuses on the study of different models of solution reflected in the literature, which treat the optimization of the routing of vehicles by nodes and the optimal route for the university transport service. With the recent expansion of the facilities of a university institution, the allocation of the routes for the transport of its students, became more complex. As a result, geographic information systems (GIS) tools and operations research methodologies are applied, such as graph theory and vehicular routing problems, to facilitate mobilization and improve the students transport service, as well as optimizing the transfer time and utilization of the available transport units. An optimal route management procedure has been implemented to maximize the level of service of student transport using the K-means clustering algorithm and the method of node contraction hierarchies, with low cost due to the use of free software.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959)
Toth, P., Vigo, D.: Vehicle Routing Problem, Methods, and Application (2014)
Martí, R.: Procedimientos Metaheurísticos en Optimización Combinatoria. Dep. d’Estadística i Investig. Oper. pp. 1–60 (2001)
Eldrandaly, K.A., Abdallah, A.M.F.: A novel GIS-based decision-making framework for the school bus routing problem. Geo-Spatial Inf. Sci. 15(1), 51–59 (2012)
Huo, L., Yan, G., Fan, B., Wang, H., Gao, W.: School bus routing problem based on ant colony optimization algorithm. In: 2014 IEEE Conference of Expo and Transportation Electrification, Asia-Pacific (ITEC Asia-Pacific), no. 1, pp. 1–5 (2014)
Shiripour, S., Mahdavi-Amiri, N., Mahdavi, I.: Optimal location-multi-allocation-routing in capacitated transportation networks under population-dependent travel times. Int. J. Comput. Integr. Manuf. 29(6), 652–676 (2016)
Hashi, E.K., Hasan, M.R., Zaman, M.S.U.: GIS based heuristic solution of the vehicle routing problem to optimize the school bus routing and scheduling. In: 9th International Conference on Computer and Information Technology, ICCIT 2016, pp. 56–60 (2016)
Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 319–333. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68552-4_24
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transp. Sci. 46(3), 388–404 (2012)
Batz, G.V., Geisberger, R., Sanders, P., Vetter, C.: Minimum time-dependent travel times with contraction hierarchies. J. Exp. Algorithm. 18, 1.1–1.43 (2013)
Open Source Routing Machine DEMO (2017). http://map.project-osrm.org/. Accessed 23 Mar 2017
Fu, L., Sun, D., Rilett, L.R.: Heuristic shortest path algorithms for transportation applications: state of the art. Comput. Oper. Res. 33(11), 3324–3343 (2006)
Jain, A.K.: Data clustering: 50 years beyond K-means. Pattern Recognit. Lett. 31(8), 651–666 (2010)
Shen, C.-W., Quadrifoglio, L.: Evaluation of zoning design with transfers for paratransit services, no. 2277 (2012)
Ng, W.L., Leung, S.C.H., Lam, J.K.P., Pan, S.W.: Petrol delivery tanker assignment and routing: a case study in Hong Kong. J. Oper. Res. Soc. 59(9), 1191–1200 (2008)
Yossi, S.: Logistics Clusters. Mit Press, Cambridge (2012)
Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: An efficient k-means clustering algorithms: analysis and implementation. IEEE Trans. Pattern Anal. Mach. Intell. 24(7), 881–892 (2002)
OSMF, OpenStreetMap (2017). https://www.openstreetmap.org/#map=5/51.500/-0.100. Accessed 07 Apr 2017
Kim, B.-I., Kim, S., Sahoo, S.: Balanced clustering algorithms for improving shapes on vehicle routing problems. In: IIE Annual Conference and Exhibition 2004 (2004)
Herrera, I.: Diseño y evaluación de un algoritmo genético para ruteo vehicular que permita optimizar la distribución en una empresa comercializadora de autopartes en quito, Escuela Superior Politécnica del Litoral (2015)
R Project: R: K-Means Clustering (2016). https://stat.ethz.ch/R-manual/R-devel/library/stats/html/kmeans.html
Rueda, S.: Plan Especial de Indicadores de Sostenibilidad Ambiental de la Actividad Urbanística de Sevilla. Agencia Ecol. Urbana Barcelona, Barcelona (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Herrera-Granda, I.D. et al. (2018). Optimization of the University Transportation by Contraction Hierarchies Method and Clustering Algorithms. In: de Cos Juez, F., et al. Hybrid Artificial Intelligent Systems. HAIS 2018. Lecture Notes in Computer Science(), vol 10870. Springer, Cham. https://doi.org/10.1007/978-3-319-92639-1_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-92639-1_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-92638-4
Online ISBN: 978-3-319-92639-1
eBook Packages: Computer ScienceComputer Science (R0)