VNS_BLS, um algoritmo com busca locais simultâneas para a resolução do problema de escalonamento de motorista de transporte público

Abstract

Resumo: O Problema de Escalonamento de Motoristas de Transporte Público consiste em construir escalas de trabalho para motoristas de uma empresa de transporte público, de forma que as escalas geradas respeitem restrições impostas e minimizem custos operacionais. Este trabalho aborda instâncias de dados de grande escala oriundas de casos reais de empresa de transporte público. A utilização de meta-heurísticas para resolução deste problema é bastante explorada, uma vez que são capazes de encontrar boas soluções em um tempo computacional razoável. No entanto, dependendo da dimensão das instâncias do problema o tempo computacional consumido para estes casos pode ser elevado mesmo utilizando técnicas heurísticas. Por outro lado, com o crescente desenvolvimento de novos hardwares, há cada vez mais computadores com multinúcleos, o que segure o desenvolvimento e estudo de novas técnicas heurísticas que explore estes recursos de processamento. Sendo assim, este trabalho propõe o VNS_BLS, uma meta-heurística baseada em VNS que utiliza 36 buscas locais diferentes executadas de forma simultânea. O VNS_BLS possui quatro versões que se diferem em questão de comunicação com memória compartilhada e ociosidade. O algoritmo foi testado com instâncias de dados reais com 412 até 3478 tarefas. Os resultados obtidos pelas versões foram comparados entre elas e com outras abordagens da literatura. Com base nos experimentos realizados foi possível perceber que nem todas as 36 buscas locais do algoritmo são de fato efetivas na melhoria da solução. Notou-se, também, que comparado com outras propostas o VNS_BLS se mostra competitivo, pois alcança bons resultados em menor tempo computacional

Abstract: The Bus Driver Scheduling Problem consists of construct work schedules for drivers of a public transport company, that the scales generated respect imposed constraints and minimize operation costs. This paper addresses large-scale data instances from real cases of a public transport company. The use of metaheuristics to solve this problem is well explored, since metaheuristics are able to find good solutions in a reasonable computational time. However depending on the size of instances of the problem the computational time consumed for these cases can be high, even using heuristic techniques. However, with the increasing development of new hardware, there are more computers with multi-cores. This increase the need to development and study of new heuristic techniques that exploits these processing resources. Thus, this work proposes VNS_BLS, a VNS-based metaheuristic that uses 36 different local searches performed simultaneously. VNS_BLS has four versions that differ in terms of communication with shared memory and idleness. The algorithm was tested with real data instances with 412 to 3478 tasks. The results obtained by the versions were compared between them and with other approaches in the literature. Based on the experiments was possible to realize that not all 36 local searches of algorithm are effective in improving the solution. It was also noticed that, compared to other proposals, the VNS_BLS is competitive because achieves good results in less computational time