The crew scheduling problem of an interurban public transport bus company

Abstract

Una planificación de los conductores adecuada impacta en el coste operacional de las empresas de transporte público. La dificultad de esta tarea se debe principalmente a dos aspectos (Esclapés 2001, Bonrostro, Yusta 2003, Ernst et al. 2004, Van den Bergh et al. 2013, Ibarra-Rojas et al. 2015, Li et al. 2015): por un lado, la planificación de los conductores es parte de un problema mayor, la planificación de los vehículos y conductores. Por otro lado, las diferencias entre las características de las redes de transporte, los recursos de las empresas, las restricciones reglamentarias o los acuerdos laborales hacen que las soluciones sean particulares para cada empresa. El objetivo principal de esta investigación es desarrollar un algoritmo eficiente que minimice en un tiempo de ejecución aceptable el problema de la planificación de los conductores de una compañía de autobuses de transporte de pasajeros público interurbano, permitiendo relevos ilimitados en cualquier parada de la red, es decir, al principio, final o cualquier otra parada intermedia de una línea. De esta manera, haciendo uso de la herramienta en una empresa real, se han examinado dos lagunas de investigación encontradas en el análisis de la literatura. Por un lado, el impacto de permitir relevos ilimitados al principio, al final o en cualquier otra parada intermedia de una línea. Por otro lado, el impacto del proceso de planificación cuando las restricciones a cumplir varían según el tipo de servicio que se incluye en las jornadas. Se han analizado dos procesos: el dividir el problema en problemas independientes según las características de los servicios, o el llevar a cabo una planificación global bajo las restricciones más restrictivas. Con respecto a la metodología de investigación, se han seguido los siete pasos de la Investigación Operativa (Winston, Goldberg 2004): (1) formular el problema, (2) observar el sistema, (3) formular un modelo del problema, (4) verificar el modelo y usarlo para la predicción, (5) seleccionar una alternativa adecuada, (6) presentar los resultados y conclusiones del estudio e (7) implementar y evaluar las recomendaciones. Los resultados muestran que en ocasiones vale la pena considerar los factores investigados.

Gidarien lanaren plangintza egoki batek zuzenki eragiten du garraio publikoko enpresen kostu operatiboan. Tripulazioaren plangintzaren zailtasuna bi arrazoiengatik ematen da bereziki (Esclapés 2001, Bonrostro, Yusta 2003, Ernst et al. 2004, Van den Bergh et al. 2013, Ibarra-Rojas et al. 2015, Li et al. 2015): alde batetik, gidarien plangintza beste arazo handiago baten parte da, ibilgailu eta gidarien plangintzaren arazoaren parte. Bestalde, garraio sareen arteko ezberdintasunek, enpresen baliabideen arteko ezberdintasunek edota arautegi edo lan-akordioen arteko ezberdintasunek, enpresa bakoitzarentzako soluzio partikular bat garatzea behartzen dute. Ikerketa honen helburu nagusia "algoritmo eraginkor bat garatzea da, zeinek exekuzio denbora apropos baten, eta lehen, azken edo beste edozein bitarteko geldialditan errelebua baimenduz, hiriarteko sare baten diharduen garraio publikoko autobus konpainia batek behar duen tripulazioa minimizatzen duen". Horrela, eta konpainia erreal baten tripulazioaren planifikazioa oinarritzat hartuta, literaturan aurkitutako bi ikerketa-hutsune aztertu dira. Alde batetik, zenbatetan mugatu ezak eta lehen, azken edo beste edozein bitarteko geldialditan errelebuak baimentzeak daukan inpaktua aztertuko da. Bestalde, planifikatzerakoan ezaugarri ezberdinak dituzten zerbitzuek errestrikzio ezberdinak kontsideratzea behartzen dutenean, planifikazio prozesua aztertu da. Bi prozedura aztertu dira: arazoa zerbitzuen ezaugarrien araberako planifikazio independentetan banatzea edo errestrikzio gogorrenak kontsideratuta, planifikazio bakar bat osatzea. Ikerketaren metodologiari dagokionez, Eragiketen Ikerketako (Winston, Goldberg 2004) zazpi urratsak jarraitu dira: (1) arazoa formulatzea, (2) sistemaren behaketa, (3) arazoaren eredua formulatu, (4) eredua egiaztatzea eta aurreikuspenerako erabiltzea, (5) aukera egokia aukeratzea, (6) azterketaren emaitzak eta ondorioak aurkeztea eta (7) gomendioak ezartzea eta ebaluatzea. Emaitzen arabera, kasu batzuetan ikertu diren bi faktoreek emaitza hobeagoak dakartzatela baieztatu da.

A proper crew scheduling impacts on the operational cost of public transport companies. The difficulty of the crew scheduling is due to two main aspects (Esclapés 2001, Bonrostro, Yusta 2003, Ernst et al. 2004, Van den Bergh et al. 2013, Ibarra-Rojas et al. 2015, Li et al. 2015): first, it is part of a larger problem, the Vehicle and Crew Scheduling Problem. Second, the differences among network features, resources of companies, regulatory restrictions or labour agreements make the solutions particular to each company. The main objective of the present research work is “to develop an efficient algorithm which minimizes in an acceptable execution time the Crew Scheduling Problem of an interurban passenger public transport bus company, allowing unlimited drivers’ reliefs that can occur at first, last or any other intermediate stop of a line”. So, using this tool on a real company’s crew scheduling problem, two research gaps found in the analysis of the literature have been examined. On one hand, the impact of allowing unlimited drivers’ reliefs that can occur at first, last or any other intermediate stop of a line. On the other hand, the impact of the scheduling procedure when restrictions vary depending on the type of service that is included in the duty. Two procedures have been studied: dividing the problem into independent problems or scheduling globally under the most limited restrictions. Concerning the research methodology, the seven steps of Operations Research (Winston, Goldberg 2004) have been followed: (1) formulate the problem, (2) observe the system, (3) formulate a model of the problem, (4) verify the model and use the model for prediction, (5) select a suitable alternative, (6) present the results and conclusion of the study and (7) implement and evaluate the recommendations. The results show that occasionally it is worthy to consider both investigated factors.