Track: Logistics, Transport and Traffic Management

Abstract

Described here are three hybrid constructive algorithms which combine heuristic and exact methods for solving the scheduling of passenger’s vehicles for public transportation with multiple depots (MDVSP). The first algorithm assigns each one of the scheduled trips to the depots, taking into account the chronological order of the trips and the cost of serving each trip from the depot and then the itineraries are built on a heuristic way (Concurrent Scheduler). The second method depicts a general attention sequence with all the services. This combines two criteria: chronological order and Nearest Neighbor for the trips. In order to establish the depot that serve the set of trips, the mathematical model of the Generalized Assignment Problem is used. The third method assimilates graph theory to build itineraries of minimum cost using models of general assignment and minimum flow in a network. In order to validate each one of the algorithms, 90 cases were extracted from the literature, having between 2 and 5 depots, and 100 and 500 trips. The algorithms have response times ranging from 0.015 to 1.7 seconds approximately. The focus of this work is to provide efficient methods in computation times for the real-time reprogramming of vehicle itineraries. Primarily to ease the operation when there are contingencies in the Mass Transit System of the Centro Occidente de Centro Metropolitana de Colombia AMCO, whose operation consists of about 5000 trips daily. These algorithms have been applied successfully in our cohort of trips.