Resumen

El problema de planificación de líneas de autobuses o de diseño de redes de transporte con rutas integradas para pasajeros es un problema combinatorio complejo. Aunque existen instancias de referencia bien conocidas para este problema desde hace décadas, el estado del arte carece de soluciones óptimas para estas instancias. El algoritmo branch and bound, presentado en este trabajo, introduce tres conceptos novedosos para determinar estas soluciones óptimas: (1) un nuevo método de generación de grupos de líneas basado en la dominancia, (2) la introducción de enlaces esenciales, es decir, enlaces que pueden determinarse de antemano y que deben estar presentes en la solución óptima, y (3) una nueva representación de la red basada en la adición únicamente de aristas adicionales. Además de presentar las nuevas soluciones óptimas obtenidas, cada uno de los conceptos mencionados se examina de forma aislada en los experimentos, y se demuestra que contribuyen significativamente al éxito del algoritmo.

• Materias:Infraestructura de transportes Ingeniería del transporte Accidentes de transito Seguridad del transporte Planificación de ruta
• Subjects:Transport infrastructure Transport engineering Traffic accidents Transport safety Path planning
• Palabras claves:soluciones óptimas, problema de planificación de líneas de autobuses, nuevo método de generación de grupos de líneas, problema de diseño de redes de tránsito, problema combinatorio desafiante, encaminamiento integrado de pasajeros, nueva representación de la red, algoritmo, conceptos mencionados, instancias de referencia
• Keywords:optimal solutions, bus line planning problem, new line pool generation method, transit network design problem, challenging combinatorial problem, integrated passenger routing, new network representation, algorithm, abovementioned concepts, benchmark instances