FenixEdu™

Dissertação

{pt_PT=Computational Experiments of a Maintenance Scheduling Problem: Carris bus company Case Study } {} EVALUATED

Detalhes: {pt=Em 2018, Rodrigo Arrais Martins desenvolveu um modelo de Programação Linear Inteira Mista implementado em FICO Xpress, com o objectivo de optimizar o planeamento da manutenção numa empresa operadora de autocarros, ultimamente reduzindo os custos de manutenção. Os resultados obtidos, apesar de apresentarem melhorias em relação às práticas da empresa, deixaram a desejar em termos de optimalidade da solução e tempo de computação. A presente dissertação procura melhorar esses aspectos. Uma abordagem de resolução em paralelo, utilizando multiplos modelos e baseada na decomposição Dantzig-Wolfe, foi tentatada não tendo sido conseguido que o modelo gerasse resultados, Seguidamente, foi implementada uma alteração ao modelo original, onde se introduziram novas restriçóes de forma a conduzir o modelo para a solução. Os resultados em termos de tempo computacional foram bastante satisfatórios, havendo pouca melhoria no valor da solução. Por ultimo, foi desenvolvida uma abordagem heurística do problema, em que o planeamento de cada autocarro é resolvido sequencialmente. Este modelo apresentou grandes melhorias à solução original, apresentando uma redução de 99.7% em tempo computacional e de 8.9% na redução de custos. A abordagem heurística assim como a alteração ao modelo original, foram validadas através de um exemplo ilustrativo., en=In 2018, Rodrigo Arrais Martins developed a Mixed Integer Linear Program model that was implemented in FICO Xpress software, in order to optimize the bus maintenance scheduling of a bus operating company with the goal of reducing its maintenance costs. The results obtained, though improving the company’s current schedule, were no great regarding the optimality of the solution and the computational time it took to reach it. The present dissertation searches a way to make improvements in those aspects. A parallel solving multiple model approach based on the Dantzig-Wolfe decomposition was first attempted, resulting in the impossibility to generate results. Then an alteration to the original model by introducing new restrictions, in order to guide the solver to the solution, was implemented. The results regarding computational time showed great enhancement to the original model, but the improvement in terms of optimality was scarce. Lastly, a heuristic approach, in which the problem was solved sequentially for one bus at a time, was developed. This model showed great improvements such in computational time as in optimality. Showing a reduction of 99.7% in computational time and 8.9% in maintenance costs. Both the heuristic approach and the alteration to the original model were validated through an illustrative example.}
Keywords: {pt=Optimização, Planeamento de Manutenção, Experiências Computacionais, Autocarro, Programação Linear Inteira Mista, Resolução em Paralelo, en=Optimization, Maintenance Scheduling, Computational Experiment, Bus transport, Mixed Integer Linear Programming, Parallel Solving}

Discussão: agosto 28, 2019, 11:0