Otimização e planeamento operacional

O problema de escalonamento operacional é um problema de otimização combinatória que surge nos setores de mobilidade e transporte. No âmbito desta tese é tratado o problema de escalonamento de viaturas e também de tripulantes. Relativamente ao escalonamento de viaturas são consideradas as extensões de frota heterogénea e múltiplas estações de recolha, o que implica que o problema tratado seja assim de complexidade "NP-Difícil". A OPT realiza o escalonamento de viaturas e tripulantes em dois passos, e o objetivo principal deste projecto consistiu em estudar/desenvolver métodos/algoritmos que permitissem executar os dois escalonamentos num único passo com a expectativa de melhorar os resultados obtidos. Um outro objetivo foi a adição de um conjunto de restrições, que permitem ao utilizador obter soluções mais configuráveis. No desenvolvimento da solução, numa primeira fase, foram efetuadas experiências com uma amostra de dados reais com o objetivo de melhorar a solução, para que esta produzisse melhores resultados. Posteriormente, na fase de avaliação da solução, a mesma foi sujeita a diferentes amostras de teste com o objetivo de produzir resultados variados e, deste modo, retirar conclusões acerca do tipo de amostras para o qual o sistema é mais apropriado. Da avaliação da solução desenvolvida, conclui-se que o sistema consegue produzir otimizações mais significativas para amostras de menor duração média de viagens e para amostras com maior variedade de nós. Para além disso, o estudo dos algoritmos e casos de teste confirmou a expectativa teórica de que o tempo de processamento aumenta com o aumento do número de viagens, com o aumento da variedade de nós e com a diminuição da duração média de viagens.The vehicle scheduling problem is a combinatorial optimization problem that arises in the mobility and transportation sectors. Within this thesis, the problem of assigning vehicles and also crew members is addressed. In relation to the scheduling of vehicles, heterogeneous fleet extensions and multiple depot are considered, which implies that the problem treated is thus of "NP-Hard"complexity. OPT performs the scheduling of vehicles and crew in two steps, and the main goal of this project was to study/develop methods/algorithms that would allow the two steps to be performed in a single one with the expectation of improving the results obtained. The addiction of restrictions was another goal of the project, allowing the user to obtain more customizable solutions. During the development of the solution, initially, experiments were carried out with a sample of real data in order to improve the solution, so that it would produce better results. Afterwards, in the evaluation phase of the solution, it was subjected to different test samples with the goal of producing diverse results and therefore draw conclusions about the type of samples for which the system is more suitable. From the solution evaluation developed, it is concluded that the system produces better optimizations for samples with shorter average travel time and for samples with a greater variety of nodes. In addition, the study of algorithms and test cases supported the theoretical expectation that processing time increases with the increase of the number of trips and nodes as well as the decrease of the average travel duration