Otimização de recursos para atendimento de demandas de viagens rodoviárias em organizações

Abstract

Este trabalho dedicou-se ao estudo do problema de otimização da afetação de dois recursos distintos a um conjunto de tarefas, onde a afetação de um dos recursos depende da afetação do outro recurso, sendo que os recursos podem ser partilhados entre as tarefas. Este problema pode ser interpretado como uma extensão do problema de afetação generalizada. O interesse por este problema surgiu pela identificação, numa organização, de dificuldades existentes na determinação da afetação de recursos (veículos e motoristas) à realização de viagens de trabalho, por forma a que se fizesse a melhor utilização possível dos recursos existentes. O objetivo principal do trabalho foi o de desenvolver modelos e algoritmos de otimização que permitissem determinar a afetação destes recursos às requisições de viagem, minimizando o custo total. Considera-se possível a partilha de recursos entre viagens, se os seus períodos de realização e rotas forem compatíveis. Admite-se ainda a possibilidade de utilização de recursos externos (outsourcing), caso os recursos internos se esgotem ou seja mais vantajoso selecionar o outsourcing. Um dos aspetos inovadores dos modelos desenvolvidos prende-se com a consideração implícita da dimensão temporal, o que permite que o número de variáveis do modelo não seja dependente de nenhum tipo de discretização do horizonte temporal considerado. Também este aspeto pode ser considerado em outro tipo de problemas, em que seja necessário considerar o tempo de realização das tarefas para uma correta atribuição de recursos. Os modelos e algoritmos desenvolvidos foram testados considerando quer um estudo de caso, em que foram usados dados reais, quer algumas instâncias geradas a partir destes dados reais, que permitiram compreender o comportamento dos modelos e das correspondentes soluções. Tendo em conta que os modelos desenvolvidos dão lugar a instâncias de grande dimensão, foi desenvolvida uma heurística híbrida (matheurística), tendo por base algoritmos genéticos e um solver de programação inteira. Foi ainda desenvolvido um método determinístico de decomposição do problema em subproblemas. Os modelos desenvolvidos conduzem a soluções que permitem melhorar a gestão de recursos e diminuir os custos, em comparação com as soluções que eram calculadas manualmente na organização. A resolução usando um solver genérico para programação inteira apresentou, em muitas das instâncias, gaps significativos. A matheurística também apresentou dificuldades na resolução do problema, tendo sido o método de decomposição a melhor alternativa, dentro dos desenvolvimentos algorítmicos testados. Foi possível verificar que a possibilidade de partilha de recursos entre tarefas permite uma redução dos custos envolvidos, permitindo uma racionalização da sua utilização. No caso particular do problema estudado, a partilha de viaturas por requisições diferentes, mas compatíveis entre si, permite diminuir o número de lugares não utilizados nos veículos atribuídos às requisições. ABSTRACTThis work studiesthe optimization problem of assigningtwo distinct resources to a set of tasks, where the assignment of one of the resources depends on the assignment of the other resource, and the resources can be shared between tasks. This work was motivated by the identification, in an organization, of existing difficulties in determining the allocation of resources (vehicles and drivers) to the realization of work trips, to make the best possible useof existing resources. The main objective of the work was to developmodels and optimization algorithms that allow determining the assignment of these resourcesto travel requests, minimizing total cost. It is considered thatresources can be shared amongtripsas long astheir realization time periods and routes are compatible. The possibility of using external resources (outsourcing) is also allowed, either becausethe internal resources are not sufficient to assure the realization of all the trips, or because it is more advantageous to select outsourcingfrom cost perspective. One of the innovative aspects of the developed models is related to the implicit considerationof the temporal dimension, which allows the size of the model to beindependent ofany kind of discretization of the time horizon. This aspect can also be considered in other types of problems, in which it is necessary to consider the time to carry out the tasks for a correct allocation of resources.The models and algorithms developed in this work were tested considering a case study withreal data and someother instancesgenerated from these data, which allow to understand the behavior ofthe modelsand the corresponding calculated solutions. The developed models originate large dimension instances, which can be challenging to solve using general solvers. This observation motivated the developmentof a hybrid heuristic (matheuristic) based on genetic algorithms and an integerprogramming solver. A deterministic method of decomposing the problem into subproblems was also developed. The models lead to solutions that improve resource managementand decrease costs, in comparisonto solutions that were manually calculated in the organization. The resolution using a generalsolver yielded significant gaps in many instances. The matheuristicalso presented somedifficulties in solving the problem. The decomposition method was the best alternative, considering the alternative algorithmic developmentstested. The viiipossibility of sharing resources between tasks allows a reduction in the costs involved, allowing a rationalization of their use. In the particular case of the problem studied, sharing vehicles amongdifferent compatible requestsreduces the number of unused seats in the vehicles assigned to the requests.