Constructive matheuristic algorithms for solving the multidepot vehicle scheduling problem for public transportation

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.

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.