| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 1.49 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
O problema Skill Vehicle Routing Problem estudado neste trabalho consiste em determinar rotas para vários técnicos com diferentes especialidades de forma a visitarem os clientes satisfazendo os seus pedidos de serviço consoante a especialidade requisitada e na janela temporal especificada. O objetivo é estudar o Skill Vehicle Routing Problem, comparando o desempenho da heurística de melhoramento LNS com um método exato de programação linear inteira, medindo os tempos de execução e soluções encontrados em ambas as alternativas. Para obter as soluções pelo método exato são propostos dois modelos em programação linear inteira, um que considera a existência de apenas um técnico em cada especialidade e outro a de vários técnicos por especialidade. Ambos os métodos foram implementados em Python, sendo que no método exato foi usado o software de otimização Xpress. Foram testadas seis variações do problema todas elas com 20 amostras e 3 especialidades. Na primeira variação existem 20 clientes, 30 clientes na segunda variação e 40 clientes na terceira variação. Após a análise dos resultados apresentados pelos 2 modelos para as várias instâncias pode-se concluir que o método exato é melhor nas situações em que existem poucos clientes, ou quando existem mais de 30 clientes, mas é possível deixar a correr o Xpress mais tempo. Caso não se possa deixar correr esse tempo deve-se usar a metaheurística LNS no caso de 40 clientes quando o número de técnicos é suficiente para satisfazer as necessidades dos clientes e não existe folga de técnicos, causando ótimos locais.
The Skill Vehicle Routing Problem studied in this work consists of determining routes for different technicians with different specialities to visit customers and satisfy their service requests, depending on the speciality requested and within the specified time window. The aim is to study the Skill Vehicle Routing Problem by comparing the performance of the LNS improvement heuristic with an exact integer linear programming method, measuring the execution times and the solutions found in both alternatives. To obtain the solutions with the exact method, two integer linear programming models are proposed, one considering the presence of only one technician in each speciality and the other considering the presence of several technicians per speciality. Both methods were implemented in Python, with the exact method using the Xpress optimization software. Three variations of the problem were tested, all with twenty samples and three specialities. In the first variation there are twenty customers, thirty customers in the second variation and forty customers in the third variation. After analysing the results presented by the two models for the various instances, it can be concluded that the exact method is better in situations where there are few customers, or when there are more than 30 customers, but it is possible to let the Xpress run for longer. If you can't let it run for that long, you should use the LNS metaheuristic in the case of 40 customers, when the number of technicians is sufficient to meet the customers' needs and there are no extra technicians, causing local optima.
The Skill Vehicle Routing Problem studied in this work consists of determining routes for different technicians with different specialities to visit customers and satisfy their service requests, depending on the speciality requested and within the specified time window. The aim is to study the Skill Vehicle Routing Problem by comparing the performance of the LNS improvement heuristic with an exact integer linear programming method, measuring the execution times and the solutions found in both alternatives. To obtain the solutions with the exact method, two integer linear programming models are proposed, one considering the presence of only one technician in each speciality and the other considering the presence of several technicians per speciality. Both methods were implemented in Python, with the exact method using the Xpress optimization software. Three variations of the problem were tested, all with twenty samples and three specialities. In the first variation there are twenty customers, thirty customers in the second variation and forty customers in the third variation. After analysing the results presented by the two models for the various instances, it can be concluded that the exact method is better in situations where there are few customers, or when there are more than 30 customers, but it is possible to let the Xpress run for longer. If you can't let it run for that long, you should use the LNS metaheuristic in the case of 40 customers, when the number of technicians is sufficient to meet the customers' needs and there are no extra technicians, causing local optima.
Description
Keywords
Problema de roteamento de veículos Problema de roteamento de veículos com especialidades Pesquisa de vizinhança grande Heurística Método exato de programação linear inteira Vehicle Routing Problem SKILL Vehicle Routing Problem Large Neighborhood Search Heuristic Exact Method for Integer Linear Programming
Pedagogical Context
Citation
Silva, Tiago Miguel Gomes (2024). “Planeamento de rotas para técnicos com diferentes habilidades”. Dissertação de Mestrado. Universidade de Lisboa. Instituto Superior de Economia e Gestão
Publisher
Instituto Superior de Economia e Gestão