ISSN 0798 1015

Vol. 41 (Issue 27) Year 2020. Art. 16

Received: 23/04/2020 • Approved: 30/06/2020 • Published 23/07/2020

Constructive matheuristic algorithms for solving the multi-depot vehicle scheduling problem for public transportation

Algoritmos mateheurísticos para solucionar el problema de programación de vehículos multidepósito para transporte público

MARÍN, Cesar A 1
BOLAÑOS, Rubén I 2
ESCOBAR, Luis M 3
ESCOBAR, John W. 4

Abstract
This paper considers the Vehicle Scheduling Problem of public transportation by considering Multi-depots (MDVSP). We propose three hybrid constructive algorithms combining heuristic and exact methods. The proposed approaches are validated by using 90 benchmark instances, having between two and five depots, and between 100 and 500 trips. Also, the efficiency of the algorithms has tested on real instances obtained from the Mass Transit System of the Centro Occidente de Centro Metropolitana de Colombia (AMCO), whose operation consists of about 5000 trips daily.
key words: Multi Depot Vehicle Scheduling Problem, Matheuristic algorithm, Public Transportation.

Resumen
Este documento considera el problema de programación de vehículos del transporte público al considerar los depósitos múltiples (MDVSP). Proponemos tres algoritmos híbridos constructivos que combinan métodos heurísticos y exactos. Los enfoques propuestos se validan mediante el uso de 90 instancias de referencia, que tienen entre dos y cinco depósitos, y entre 100 y 500 viajes. Además, la eficacia de los algoritmos se ha probado en instancias reales obtenidas del Sistema de Tránsito Masivo del Centro Occidente de Centro Metropolitano de Colombia (AMCO), cuya operación consiste en aproximadamente 5000 viajes diarios.
Palabras clave: Problema de programación de vehículos de depósito múltiple, algoritmo matemático, transporte público

Full article in PDF

1. R+D+i, Integra S.A., Universidad Tecnológica de Pereira cmarin@integra.com.co

2. R+D+i, Integra S.A., Universidad Tecnológica de Pereira ribolanos@utp.edu.co

3. R+D+i, Integra S.A.,  Universidad Libre Seccional Pereira luism.escobarf@unilibre.edu.co

4. Associate Professor. Department of Accounting and Finance, Universidad del Valle, Cali. john.wilmer.escobar@correounivalle.edu.co