Algoritmos baseados na meta-heurística VNS aplicados ao problema de escalonamento de motoristas de ônibus

• Ano de defesa: 2016
• Autor(a) principal: Santos, Allainclair Flausino dos
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual de Maringá; Brasil; Departamento de Informática; Programa de Pós-Graduação em Ciência da Computação; UEM; Maringá, PR; Centro de Tecnologia
• Palavras-chave em Português: Problema de escalonamento de motoristas de ônibus; Escalonamento; Motoristas de ônibus; Meta-heurística VNS; Tripulação; Problema de Escalonamento de Tripulação; Brasil.; Bus driver scheduling problem; Crew scheduling problem; VNS; Metaheuristic; Brazil.; Ciências Exatas e da Terra; Ciência da Computação
• Link de acesso: http://repositorio.uem.br:8080/jspui/handle/1/2529

For the public transport system being provided with quality, it is need to tackle numerous problems and one of them is the Bus Driver Schedule Problem (BDSP) which is NP-hard. This work presents four new algorithms of the VNS meta-heuristic for the BDSP, one GVNS and three VNS named adaptatives. The four algorithms have a constructive common phase and an improved phase that differs them, such that in the improved phase, the Cut and Combine Process and k-swap were applied. The algorithms were evaluated applying them on instances of Maringá, PR, Brazil city. In the algorithm evaluations was found that all are competitive when they were compared with another recent approach, because they generated better solutions with respect to the cost function, such that the best algorithm obtained better solutions in the range of 4% to 14%. With respect to a lower bound the best algorithm got the range of 12% to 25% over this bound.