Design of optimal routes for vehicles and drivers (diseño de rutas óptimas para vehículos y conductores)

Resumo

This thesis focuses on solving two new problems, with the singularity that, in both cases, the routes and the sequences of tasks must be performed by two operators, vehicles and drivers, with different characteristics. Both problems are inspired by some particular characteristics of the local air traffic in the Canary Islands. The main regional airline company must operate a number of commercial flights every day between the airports of the islands and others nearby, using aircraft and crews. There are two main airports at the main islands, Tenerife and Gran Canaria, that are considered to be the depots, where the crews and the aircraft are located. Every two days the aircraft must be checked at the airport of Gran Canaria (LPA). For this reason an aircraft starts a route at one depot and must finish at the other one. In the case of the crews, to avoid overnight costs, they must end the day at the same depot where they started. In this thesis, from this situation, two general problems are proposed, considering these particular singularities that motivates this research. The problems studied in this thesis are called the “Vehicle-and-Driver Scheduling Problem” (VDSP) and the “Driver-and-Vehicle Routing Problem” (DVRP). In addition to the mathematical models and the algorithms proposed to solve the problems, the importance of this thesis is also related to the practical applications. Besides the application to the air transportation, the algorithms proposed could be applied to design transportation networks for all types of means of transport. The benefits obtained using these tools could be very important in comparison with the traditional way of obtaining these solutions.