Um estudo de diferentes metaheur?sticas para resolver o problema de programa??o de tripula??es do sistema de transporte p?blico.

Este artigo explora diferentes m?todos de busca associados ? metaheur?stica Iterated Local Search (ILS) para resolver o Problema de Programa??o de Tripula??es de um Sistema de Transporte P?blico. Os resultados obtidos com o ILS foram comparados com um trabalho pr?vio, dos mesmos autores, que utilizou a metaheur?sica Variable Neighborhood Search (VNS). Inicialmente ambas as metaheur?sticas foram implementadas utilizando como procedimento de busca o m?todo cl?ssico First Improvement, realizando realoca??o e troca ?guiada? das tarefas das tripula??es. Esta realoca??o/troca guiada substitui a componente rand?mica dos m?todos cl?ssicos por uma busca da melhor posi??o para a inser??o das tarefas. Posteriormente, foi utilizada a t?cnica denominada Very Large-scale Neighborhood Search (VLNS) como procedimento de busca nas respectivas metaheur?sticas. Esta t?cnica produz um n?mero muito maior de vizinhos do que vizinhan?as 2-opt, pois ela permite a realoca??o de tarefas entre uma s?rie de diferentes tripula??es. Ambas as vers?es das metaheur?sticas foram aplicadas a um conjunto de dados reais de uma empresa que opera em Belo Horizonte, produzindo programa??es mais econ?micas do que aquelas adotadas pela empresa. Os resultados s?o apresentados e discutidos neste trabalho.This paper explores different local search methods associated with the metaheuristic Iterated Local Search (ILS) to solve the Crew Scheduling Problem (CSP) of a Public Transportation System. The results from ILS were compared to those obtained in a previous work from the same authors that used the Variable Neighborhood Search (VNS). Initially, both metaheuristics were implemented using, as local search, the classical First Improvement Method, performing ?guided? reallocation and exchange of crew tasks. The guided reallocation/exchange replaces random components from the classical method by searching the best position to insert the task. Further, the Very Large-scale Neighborhood Search (VLNS) technique was used as a local search procedure in the metaheuristics. This technique has substantially more neighbors than the 2-opt neighborhoods, since it performs a chain exchange of tasks from different crews. Both versions of metaheuristics were applied to a set of real data from a company operating in the city of Belo Horizonte, producing more economical schedules than those adopted by the company. The results are presented and discussed in this work.http://dx.doi.org/10.1590/2238-1031.jtl.v8n4a