Solving the Extended Vehicle Scheduling Problem using

The Vehicle Scheduling Problem is a well-known combinatorial optimization problem that emerges in mobility and transportation sectors. The heterogeneous fleet with multiple depots extension arises in major urban public transportation companies due to different demands throughout the day and some restrictions in the use of different vehicle types. This extension introduces complexity to the problem and makes the known deterministic methods unable to solve it efficiently. This thesis describes a comprehensive model to interpret the Multiple Depot Vehicle Scheduling Problem as an Asymmetric Traveling Salesman Problem. An approach known for its application to the A-TSP, the Ant Colony based meta-heuristic, was adapted to the problem through this interpretation. The results achieved on solving problems from some of the Portuguese major public transportation companies planning databases show the usefulness of the proposed approach. i ii Resum