Hyperheuristics for public transport planning

Authors

DOI:

https://doi.org/10.31908/19098367.3709

Keywords:

Public transport, hyperheuristics, optimization, location and routing problem

Abstract

This article presents an algorithm that establishes stops and routes for buses to extend the existing transport lines. The newly developed algorithm is based on a hyperheuristic approach, whose main feature is its ability to choose and apply the most convenient metaheuristics at the diff erent stages of the search process. Besides, it is shown how computing times are reduced using parallel programming and through a strategy that minimizes the number of evaluations. The case under study arises from an existing need in Bahia Blanca city (Argentina), where the neighbors have asked for more accessibility in the public transport service.

Author Biographies

  • Diego Alejandro Rodríguez, Universidad Nacional de Salta

    Nació en Salta, Argentina en 1978. Doctorado en Ciencias de la Computación de la Universidad Nacional del Sur, Bahía Blanca, Argentina, en 2015. Desde 2010 es miembro del Laboratorio de Investigación y Desarrollo en Computación Científica (LIDeCC). Es profesor en el Departamento de Informática - Facultad de Ciencias Exactas - Universidad Nacional de Salta. Sus áreas de investigación incluyen algoritmos de búsqueda, optimización combinatoria y procesamiento paralelo. Sus intereses en investigación son optimización combinatoria y el diseño y análisis de algoritmos aplicados a problemas de transporte. Contacto: drodriguez@unsa.edu.ar

  • Paola Patricia Oteiza, Universidad Nacional del Sur-CONICET

    Nació en Bahía Blanca, Argentina en 1982. Doctorado en Ingeniería Química de la Universidad Nacional del Sur, Bahía Blanca, Argentina, y trabaja como becaria posdoctoral en PLAPIQUI (CONICET). Desde 2010 es miembro del Laboratorio de Investigación y Desarrollo en Computación Científica (LIDeCC). Sus intereses en investigación son el diseño de redes de cañerías, transporte público, técnicas metaheurísticas, control dinámico de plantas de procesos y algoritmos evolutivos. Contacto: poteiza@plapiqui.edu.ar

  • Nelida Beatriz Brignole, Universidad Nacional del Sur-CONICET

    Nació en Bahía Blanca, Argentina en 1962. Es profesora de computación científica y directora fundadora del Laboratorio de Investigación y Desarrollo en Computación Científica (LIDeCC) en la Universidad Nacional del Sur, Bahía Blanca, Argentina. Tiene un Doctorado en Ingeniería Química de la Universidad Nacional del Sur, Bahía Blanca, Argentina, y trabaja como investigadora independiente en PLAPIQUI (CONICET). Sus intereses en investigación son las aplicaciones de la computación científica para procesar la ingeniería de sistemas, incluidos el diseño de redes de cañerías, transporte público, control dinámico de plantas de procesos, optimización, algoritmos evolutivos y programación paralela. Contacto: dybrigno@criba.edu.ar.

References

Garau, C., Masala, F., Pinna, F. “Cagliari and smart urban mobility: Analysis and comparison,” Cities. vol. 56, pp. 35-46, 2016, doi.org/10.1016/j.cities.2016.02.012

Prodhon, C., Prins, C., “A survey of recent research on locationrouting problems,” Eur. J. Oper. Res., vol. 238, no 1, pp. 1-17, 2014.

Chandra Mohan B., Baskaran, R. “A survey: Ant Colony Optimization based recent research and implementation on several engineering domain,” Expert. Syst. Appl., vol. 39, no 4, pp. 4618-4627, 2012.

Nagy, G., Salhi, S. “Location-routing: Issues, models and methods,” Eur. J. Oper. Res., vol. 177, no. 2, pp. 649-672, 2007.

Wolsey, L. A. (2000). Integer programming. IIE Transactions, 32(273-285), 2-58.

Lenstra, J.K., Kan, A.H.G. “Complexity of vehicle routing and scheduling problems,” Networks, vol.11, no. 2, pp. 221-227, 1981.

Sörensen, K. “Metaheuristics - the metaphor exposed,” Int. T. Oper. Res. vol. 00, pp. 1-16, 2013, DOI: 10.1111/itor.12001

Boussaïd, I., Lepagnot, J., Siarry, P. “A survey on optimization metaheuristics”. Inf. Sci. 237, 82-117, 2013.

Wolpert, D.H., Macready, W.G. “No free lunch theorems for optimization,” Evol. Comput, in IEEE Transactions, vol. 1, no. 1, pp. 67-82, 1997.

Cowling, P., Kendall, G., Soubeiga, E. “A hyperheuristic approach to scheduling a sales summit,” in Practice and Theory of Automated Timetabling III (Springer Berlin Heidelberg. 2001, pp. 176-190.

Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., Schulenburg, S. “Hyper-heuristics: An emerging direction in modern search technology,” In Handbook of metaheuristics, Springer US, 2003, pp. 457-474.

Ross, P. Hyper-heuristics. In Search methodologies, pp. 529-556, Springer US, 2005.

Burke, E.K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Qu, R. “Hyper-heuristics: A survey of the state of the art”, J. Oper. Res. Soc. Vol. 64, no 12, pp. 1695-1724, 2013.

Reeves, C.R. Modern heuristic techniques for combinatorial problems, John Wiley & Sons, Inc, 1993, 320p..

Luke, S. Essentials of metaheuristics. Lulu, second edition, 2013, 261p.

Haupt, R.L., Haupt, S.E. Practical genetic algorithms. New Jersey. John Wiley & Sons, 2004.

Dorigo, M. “Ant Colony Optimization and Swarm Intelligence” in Proc. 5th International Workshop, ANTS, vol. 4150, Springer, US, 2006.

Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P. “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671-680,1983.

Rodríguez, D.A., Olivera, A.C., Brignole, N.B. “Hiperheurística Diseñada para un Problema de Localización.” Mec. Comp. Vol XXXIII, pp. 2513-2521, 2014.

GAMS. Development Corporation. GAMS. The Solver Manuals. San Francisco, CA, USA, 2013.

Downloads

Published

2018-06-30

Issue

Vol. 12 No. 23 (2018)

Section

Artículos

How to Cite

Hyperheuristics for public transport planning. (2018). Entre Ciencia E ingeniería, 12(23), 103-108. https://doi.org/10.31908/19098367.3709