Solving of school bus routing problem by ant colony optimization

The school bus routing problem (SBRP) seeks to plan an efficient schedule of a fleet of school buses that must pick up students from various bus stops and deliver them by satisfying various constraints: maximum capacity of the bus, maximum riding time of students, time window to arrive to school. In...

Full description

Autores:
Arias-Rojas, Juan S.
Jiménez-Gordillo, J. F. (José Fernando)
Montoya-Torres, J. R. (Jairo Rafael)
Tipo de recurso:
Article of journal
Fecha de publicación:
2011
Institución:
Universidad EIA .
Repositorio:
Repositorio EIA .
Idioma:
eng
OAI Identifier:
oai:repository.eia.edu.co:11190/137
Acceso en línea:
https://repository.eia.edu.co/handle/11190/137
Palabra clave:
REI00186
HEURÍSTICA
HEURISTIC
INFRAESTRUCTURA Y GESTIÓN DEL TERRITORIO
INFRAESTRUCTURE AND LAND PLANNING
SCHOOL BUS
ROUTING
ANT COLONY
CASE STUDY
BUSES ESCOLARES
RUTEO
COLONIA DE HORMIGAS
ESTUDIO DE CASO
Rights
openAccess
License
Derechos Reservados - Universidad EIA, 2020
id REIA2_6fa885b523799b260be0a8485b5bedd4
oai_identifier_str oai:repository.eia.edu.co:11190/137
network_acronym_str REIA2
network_name_str Repositorio EIA .
repository_id_str
dc.title.spa.fl_str_mv Solving of school bus routing problem by ant colony optimization
dc.title.alternative.spa.fl_str_mv Resolução do problema de ruteo de ônibus escolares com otimização por colônia de formigas
Resolución del problema de ruteo de buses escolares con optimización por colonia de hormigas
title Solving of school bus routing problem by ant colony optimization
spellingShingle Solving of school bus routing problem by ant colony optimization
REI00186
HEURÍSTICA
HEURISTIC
INFRAESTRUCTURA Y GESTIÓN DEL TERRITORIO
INFRAESTRUCTURE AND LAND PLANNING
SCHOOL BUS
ROUTING
ANT COLONY
CASE STUDY
BUSES ESCOLARES
RUTEO
COLONIA DE HORMIGAS
ESTUDIO DE CASO
title_short Solving of school bus routing problem by ant colony optimization
title_full Solving of school bus routing problem by ant colony optimization
title_fullStr Solving of school bus routing problem by ant colony optimization
title_full_unstemmed Solving of school bus routing problem by ant colony optimization
title_sort Solving of school bus routing problem by ant colony optimization
dc.creator.fl_str_mv Arias-Rojas, Juan S.
Jiménez-Gordillo, J. F. (José Fernando)
Montoya-Torres, J. R. (Jairo Rafael)
dc.contributor.author.spa.fl_str_mv Arias-Rojas, Juan S.
Jiménez-Gordillo, J. F. (José Fernando)
Montoya-Torres, J. R. (Jairo Rafael)
dc.subject.lcsh.spa.fl_str_mv REI00186
topic REI00186
HEURÍSTICA
HEURISTIC
INFRAESTRUCTURA Y GESTIÓN DEL TERRITORIO
INFRAESTRUCTURE AND LAND PLANNING
SCHOOL BUS
ROUTING
ANT COLONY
CASE STUDY
BUSES ESCOLARES
RUTEO
COLONIA DE HORMIGAS
ESTUDIO DE CASO
dc.subject.arcmarc.spa.fl_str_mv HEURÍSTICA
HEURISTIC
dc.subject.eia.spa.fl_str_mv INFRAESTRUCTURA Y GESTIÓN DEL TERRITORIO
INFRAESTRUCTURE AND LAND PLANNING
dc.subject.keywords.spa.fl_str_mv SCHOOL BUS
ROUTING
ANT COLONY
CASE STUDY
BUSES ESCOLARES
RUTEO
COLONIA DE HORMIGAS
ESTUDIO DE CASO
description The school bus routing problem (SBRP) seeks to plan an efficient schedule of a fleet of school buses that must pick up students from various bus stops and deliver them by satisfying various constraints: maximum capacity of the bus, maximum riding time of students, time window to arrive to school. In this paper, we consider a case study of SBRP for a school in Bogotá, Colombia. The problem is solved using ant colony optimization (ACO). Computational experiments are performed using real data. Results lead to increased bus utilization and reduction in transportation times with on-time delivery to the school. The proposed decision-aid tool has shown its usefulness for actual decision-making at the school: it outperforms current routing by reducing the total distance traveled by 8.3 % and 21.4 % respectively in the morning and in the afternoon.
publishDate 2011
dc.date.submitted.spa.fl_str_mv 2011-09-21
dc.date.created.spa.fl_str_mv 2012-07
dc.date.accepted.spa.fl_str_mv 2012-06-16
dc.date.accessioned.spa.fl_str_mv 2013-11-13T19:31:21Z
dc.date.available.spa.fl_str_mv 2013-11-13T19:31:21Z
dc.date.issued.spa.fl_str_mv 2013-11-13
dc.type.spa.fl_str_mv Artículo de revista
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.coar.spa.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/article
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/publishedVersion
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv https://purl.org/redcol/resource_type/ART
dc.type.coarversion.spa.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
format http://purl.org/coar/resource_type/c_6501
status_str publishedVersion
dc.identifier.issn.spa.fl_str_mv ISSN 17941237
dc.identifier.uri.spa.fl_str_mv https://repository.eia.edu.co/handle/11190/137
dc.identifier.bibliographiccitation.spa.fl_str_mv Arias-Rojas, Juan S., Jiménez, J. F., and Montoya-Torres, J. T. (2012). Solving of school bus routing problem by ant colony optimization, Revista EIA, 9 (17), 193-208. doi: http://hdl.handle.net/11190/137
identifier_str_mv ISSN 17941237
Arias-Rojas, Juan S., Jiménez, J. F., and Montoya-Torres, J. T. (2012). Solving of school bus routing problem by ant colony optimization, Revista EIA, 9 (17), 193-208. doi: http://hdl.handle.net/11190/137
url https://repository.eia.edu.co/handle/11190/137
dc.language.iso.spa.fl_str_mv eng
language eng
dc.relation.ispartof.spa.fl_str_mv Revista EIA
dc.relation.references.spa.fl_str_mv Angel, R. D.; Caudle, W. L.; Noonan, R. and Whinston, A. (1972). “Computer-assisted school bus scheduling”. Management Science, vol. 18, No. 6 (February), pp. 279-288.
Bennett, B. T. and Gazis, D. C. (1972). “School bus routing by computer”. Transportation Research, vol. 6, No. 4 (December), pp. 317-325.
Bodin, L. D. and Berman, L. (1979). “Routing and scheduling of school buses by computer”. Transportation Science, vol. 13, No. 2, pp. 113-129.
Bowerman, R.; Hall, B. and Calamai, P. (1995). “A multiobjective optimization approach to urban school bus routing: Formulation and solution method”. Transportation Research Part A, 29, pp. 693-702.
Braca, J.; Bramel, J.; Posner, B. and Simchi-Levi, D. (1997). “A computerized approach to the New York City school bus routing problem”. IIE Transactions, vol. 29, No. 8, pp. 693-702.
dc.rights.spa.fl_str_mv Derechos Reservados - Universidad EIA, 2020
dc.rights.uri.spa.fl_str_mv https://creativecommons.org/licenses/by-nc/4.0/
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.creativecommons.spa.fl_str_mv Atribución-NoComercial
dc.rights.coar.spa.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv Derechos Reservados - Universidad EIA, 2020
https://creativecommons.org/licenses/by-nc/4.0/
Atribución-NoComercial
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.extent.spa.fl_str_mv 16 p.
dc.publisher.editor.spa.fl_str_mv Fondo Editorial EIA
institution Universidad EIA .
bitstream.url.fl_str_mv https://repository.eia.edu.co/bitstreams/23325a0c-aa24-418e-911d-6ef20c108dfa/download
https://repository.eia.edu.co/bitstreams/e498c4e2-3b9c-48cd-b25d-68840af92267/download
https://repository.eia.edu.co/bitstreams/f1c736f5-0400-496f-a353-42a7c86f0459/download
https://repository.eia.edu.co/bitstreams/dcf8012e-b1b1-4486-b487-80cfc19d3403/download
bitstream.checksum.fl_str_mv 480ca16814b4eb353c9da5a09aaf5ba0
7000bfc8db3ddb22c15f8d6fff3d4739
66874b0b9366b748c60895d2fb6339f8
8962a8e00a21c7af951317825f62cc07
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
MD5
repository.name.fl_str_mv Repositorio Institucional Universidad EIA
repository.mail.fl_str_mv bdigital@metabiblioteca.com
_version_ 1814100874643898368
spelling Arias-Rojas, Juan S.c6392f8fe14f4a3df1302cc88a482021-1Jiménez-Gordillo, J. F. (José Fernando)68dca8873b3e7cf68e9f3cc98aed1d31-1Montoya-Torres, J. R. (Jairo Rafael)9b36650fe9a840aeca4a4fa1a52fe9c6-1juan.arias@javeriana.edu.coj-jimenez@javeriana.edu.cojairo.montoya@unisabana.edu.co2013-11-13T19:31:21Z2013-11-13T19:31:21Z2012-072013-11-132011-09-212012-06-16ISSN 17941237https://repository.eia.edu.co/handle/11190/137Arias-Rojas, Juan S., Jiménez, J. F., and Montoya-Torres, J. T. (2012). Solving of school bus routing problem by ant colony optimization, Revista EIA, 9 (17), 193-208. doi: http://hdl.handle.net/11190/137The school bus routing problem (SBRP) seeks to plan an efficient schedule of a fleet of school buses that must pick up students from various bus stops and deliver them by satisfying various constraints: maximum capacity of the bus, maximum riding time of students, time window to arrive to school. In this paper, we consider a case study of SBRP for a school in Bogotá, Colombia. The problem is solved using ant colony optimization (ACO). Computational experiments are performed using real data. Results lead to increased bus utilization and reduction in transportation times with on-time delivery to the school. The proposed decision-aid tool has shown its usefulness for actual decision-making at the school: it outperforms current routing by reducing the total distance traveled by 8.3 % and 21.4 % respectively in the morning and in the afternoon.El problema de ruteo de buses escolares (SBRP) busca encontrar el programa más eficiente para una flota de buses escolares que deben recoger y despachar estudiantes en varias paradas de bus satisfaciendo varias restricciones: capacidad máxima del bus, máximo tiempo de recorrido de los estudiantes, ventanas de tiempo para la llegada al colegio. En este artículo se considera un caso de estudio de un problema SBRP para un colegio en Bogotá, Colombia. El problema se resuelve usando la metaheurística de colonia de hormigas (ACO). Los experimentos computacionales se realizan empleando datos reales. Los resultados muestran el incremento en el nivel de utilización de los buses y una reducción en los tiempos de transporte con despacho a tiempo en el colegio. La herramienta ha mostrado su utilidad para la planeación regular de buses en el colegio: se redujo la distancia total recorrida en 8,3 % en la mañana y en 21,4 % en la tarde.16 p.engRevista EIAAngel, R. D.; Caudle, W. L.; Noonan, R. and Whinston, A. (1972). “Computer-assisted school bus scheduling”. Management Science, vol. 18, No. 6 (February), pp. 279-288.Bennett, B. T. and Gazis, D. C. (1972). “School bus routing by computer”. Transportation Research, vol. 6, No. 4 (December), pp. 317-325.Bodin, L. D. and Berman, L. (1979). “Routing and scheduling of school buses by computer”. Transportation Science, vol. 13, No. 2, pp. 113-129.Bowerman, R.; Hall, B. and Calamai, P. (1995). “A multiobjective optimization approach to urban school bus routing: Formulation and solution method”. Transportation Research Part A, 29, pp. 693-702.Braca, J.; Bramel, J.; Posner, B. and Simchi-Levi, D. (1997). “A computerized approach to the New York City school bus routing problem”. IIE Transactions, vol. 29, No. 8, pp. 693-702.Derechos Reservados - Universidad EIA, 2020https://creativecommons.org/licenses/by-nc/4.0/El autor de la obra, actuando en nombre propio, hace entrega del ejemplar respectivo y de sus anexos en formato digital o electrónico y autoriza a la ESCUELA DE INGENIERIA DE ANTIOQUIA, para que en los términos establecidos en la Ley 23 de 1982, Ley 44 de 1993, Decisión andina 351 de 1993, Decreto 460 de 1995, y demás normas generales sobre la materia, utilice y use por cualquier medio conocido o por conocer, los derechos patrimoniales de reproducción, comunicación pública, transformación y distribución de la obra objeto del presente documento. PARÁGRAFO: La presente autorización se hace extensiva no sólo a las dependencias y derechos de uso sobre la obra en formato o soporte material, sino también para formato virtual, electrónico, digital, y en red, internet, extranet, intranet, etc., y en general en cualquier formato conocido o por conocer. EL AUTOR, manifiesta que la obra objeto de la presente autorización es original y la realiza sin violar o usurpar derechos de autor de terceros, por lo tanto la obra es de exclusiva autoría y tiene la titularidad sobre la misma. PARÁGRAFO: En caso de presentarse cualquier reclamación o acción por parte de un tercero en cuanto a los derechos de autor sobre la obra en cuestión, EL AUTOR, asumirá toda la responsabilidad, y saldrá en defensa de los derechos aquí autorizados; para todos los efectos la ESCUELA DE INGENIERÍA DE ANTIOQUIA actúa como un tercero de buena fe.info:eu-repo/semantics/openAccessAtribución-NoComercialhttp://purl.org/coar/access_right/c_abf2REI00186HEURÍSTICAHEURISTICINFRAESTRUCTURA Y GESTIÓN DEL TERRITORIOINFRAESTRUCTURE AND LAND PLANNINGSCHOOL BUSROUTINGANT COLONYCASE STUDYBUSES ESCOLARESRUTEOCOLONIA DE HORMIGASESTUDIO DE CASOSolving of school bus routing problem by ant colony optimizationResolução do problema de ruteo de ônibus escolares com otimização por colônia de formigasResolución del problema de ruteo de buses escolares con optimización por colonia de hormigasArtículo de revistahttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1info:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionTexthttps://purl.org/redcol/resource_type/ARThttp://purl.org/coar/version/c_970fb48d4fbd8a85Fondo Editorial EIAPublicationTHUMBNAILREI00186.pdf.jpgREI00186.pdf.jpgGenerated Thumbnailimage/jpeg10164https://repository.eia.edu.co/bitstreams/23325a0c-aa24-418e-911d-6ef20c108dfa/download480ca16814b4eb353c9da5a09aaf5ba0MD54ORIGINALREI00186.pdfREI00186.pdfapplication/pdf1863323https://repository.eia.edu.co/bitstreams/e498c4e2-3b9c-48cd-b25d-68840af92267/download7000bfc8db3ddb22c15f8d6fff3d4739MD51LICENSElicense.txtlicense.txttext/plain; charset=utf-81494https://repository.eia.edu.co/bitstreams/f1c736f5-0400-496f-a353-42a7c86f0459/download66874b0b9366b748c60895d2fb6339f8MD52TEXTREI00186.pdf.txtREI00186.pdf.txtExtracted texttext/plain42023https://repository.eia.edu.co/bitstreams/dcf8012e-b1b1-4486-b487-80cfc19d3403/download8962a8e00a21c7af951317825f62cc07MD5311190/137oai:repository.eia.edu.co:11190/1372023-07-25 16:46:14.259https://creativecommons.org/licenses/by-nc/4.0/Derechos Reservados - Universidad EIA, 2020open.accesshttps://repository.eia.edu.coRepositorio Institucional Universidad EIAbdigital@metabiblioteca.comRWwgYXV0b3IgZGUgbGEgb2JyYSwgYWN0dWFuZG8gZW4gbm9tYnJlIHByb3BpbywgSGFjZSBlbnRyZWdhIGRlbCBlamVtcGxhciByZXNwZWN0aXZvIHkgZGUgc3VzIGFuZXhvcyBlbiBmb3JtYXRvIGRpZ2l0YWwgbyBlbGVjdHLDs25pY28uIAoKWSBhdXRvcml6YSBhIGxhIEVTQ1VFTEEgREUgSU5HRU5JRVJJQSBERSBBTlRJT1FVSUEsIHBhcmEgcXVlIGVuIGxvcyB0w6lybWlub3MgZXN0YWJsZWNpZG9zIGVuOgoKIC0gbGEgTGV5IDIzIGRlIDE5ODIKIC0gTGV5IDQ0IGRlIDE5OTMKLSBEZWNpc2nDs24gYW5kaW5hIDM1MSBkZSAxOTkzCiAtIERlY3JldG8gNDYwIGRlIDE5OTUKCiB5IGRlbcOhcyBub3JtYXMgZ2VuZXJhbGVzIHNvYnJlIGxhIG1hdGVyaWEsIHV0aWxpY2UgeSB1c2UgcG9yIGN1YWxxdWllciBtZWRpbyBjb25vY2lkbyBvIHBvciBjb25vY2VyLCBsb3MgZGVyZWNob3MgcGF0cmltb25pYWxlcyBkZSByZXByb2R1Y2Npw7NuLAogY29tdW5pY2FjacOzbiBww7pibGljYSwgdHJhbnNmb3JtYWNpw7NuIHkgZGlzdHJpYnVjacOzbiBkZSBsYSBvYnJhIG9iamV0byBkZWwgcHJlc2VudGUgZG9jdW1lbnRvLiAKCiBQQVJHUkFGTzogTGEgcHJlc2VudGUgYXV0b3JpemFjacOzbiBzZSBoYWNlIGV4dGVuc2l2YSBubyBzb2xvIGEgbGFzIGRlcGVuZGVuY2lhcyB5IGRlcmVjaG9zIGRlIHVzbyBzb2JyZSBsYSBvYnJhIGVuIGZvcm1hdG8gbyBzb3BvcnRlIG1hdGVyaWFsLCAKIHNpbm8gdGFtYmnDqW4gcGFyYSBmb3JtYXRvIHZpcnR1YWwsIGVsZWN0csOzbmljbywgZGlnaXRhbCwgeSBjdXlvIHVzbyBzZSBkZSBlbiByZWQsIGludGVybmV0LCBleHRyYW5ldCwgaW50cmFuZXQsIGV0Yy4sIHkgZW4gZ2VuZXJhbCBlbiBjdWFscXVpZXIKIGZvcm1hdG8gY29ub2NpZG8gbyBwb3IgY29ub2Nlci4gCgogRUwgQVVUT1IsIG1hbmlmaWVzdGEgcXVlIGxhIG9icmEgb2JqZXRvIGRlIGxhIHByZXNlbnRlIGF1dG9yaXphY2nDs24gZXMgb3JpZ2luYWwgeSBsYSByZWFsaXphIHNpbiB2aW9sYXIgbyB1c3VycGFyIGRlcmVjaG9zIGRlIGF1dG9yIGRlIHRlcmNlcm9zLAogcG9yIGxvIHRhbnRvIGxhIG9icmEgZXMgZGUgZXhjbHVzaXZhIGF1dG9yw61hIHkgdGllbmUgbGEgdGl0dWxhcmlkYWQgc29icmUgbGEgbWlzbWEuClBBUkFHUkFGTzogRW4gY2FzbyBkZSBwcmVzZW50YXJzZSBjdWFscXVpZXIgcmVjbGFtYWNpw7NuIG8gYWNjacOzbiBwb3IgcGFydGUgZGUgdW4gdGVyY2VybyBlbiBjdWFudG8gYSBsb3MgZGVyZWNob3MgZGUgYXV0b3Igc29icmUgbGEgb2JyYSBlbiAKY3Vlc3Rpw7NuLCBFTCBBVVRPUiwgYXN1bWlyw6HCoSB0b2RhIGxhIHJlc3BvbnNhYmlsaWRhZCwgeSBzYWxkcsOhwqEgZW4gZGVmZW5zYSBkZSBsb3MgZGVyZWNob3MgYXF1w60gYXV0b3JpemFkb3M7IHBhcmEgdG9kb3MgbG9zIGVmZWN0b3MgTGEgRVNDVUVMQSAKREUgSU5HRU5JRVJJQSBERSBBTlRJT1FVSUEgYWN0w7phIGNvbW8gdW4gdGVyY2VybyBkZSBidWVuYSBmZS4K

Publicaciones similares