Aplicação do algorítmo do matching no problema da construção de escalas de motoristas e cobradores de ônibus

Abstract

Resumo: O objetivo deste trabalho é mostrar a aplicação do algoritmo do matching de peso máximo na elaboração de jornadas de trabalho para motoristas e cobradores de ônibus. Este problema deve ser resolvido levando-se em consideração o maior aproveitamento possível das tabelas de horários, com o objetivo de minimizar o número de funcionários, de horas extras e de horas ociosas. Desta forma, os custos das empresas são minimizados. O serviço de transporte urbano difere dos outros serviços, pois tem características próprias. Existe uma grande demanda em alguns horários, como no início da manhã e no final da tarde. Nos demais horários, existe demanda, embora seja menor. Além disso, as tabelas de horários são feitas de acordo com a demanda de usuários, o que implica em horários de início e término desencontrados, o que dificulta a elaboração das jornadas de trabalho. Outra dificuldade deste problema é a necessidade do cumprimento da legislação trabalhista e dos acordos com o Sindicato dos Trabalhadores, pois este conjunto de regras impede, muitas vezes, um melhor aproveitamento dos horários. As tabelas das escalas de horários dos ônibus são compostas de escalas com diversas durações, onde as maiores são divididas em escalas menores, de tal modo que o custo seja mínimo. Com estas tabelas divididas, as escalas de curta duração podem ser combinadas para a formação da jornada diária de trabalho de um funcionário. Esta combinação é feita com o algoritmo do matching de peso máximo, onde as escalas são representadas por vértices de um grafo, e o peso máximo é atribuído às combinações de escalas que não formam horas extras e nem horas ociosas. As demais combinações têm pesos proporcionais às suas durações. Deste modo, as jornadas para os dias úteis, sábados e domingos são construídas. De acordo com as regras mencionadas, uma jornada de final de semana pode ser designada para cada jornada de dia útil. O algoritmo do matching de peso máximo é utilizado novamente, atribuíndo-se um peso máximo às combinações de jornadas que não formam horas extras e nem horas ociosas. Assim, a jornada semanal de trabalho dos motoristas e dos cobradores de ônibus pode ser construída, representando um custo mínimo. A última fase deste problema consiste na designação das jornadas semanais de trabalho para cada motorista e cobrador. O algoritmo do matching é também utilizado nesta fase, onde o peso máximo é atribuído às jornadas que mais aproximam-se da escala anterior de cada funcionário. Este trabalho foi aplicado em três empresas de transporte coletivo da cidade de Curitiba, onde os algoritmos usados são todos heurísticos. Os resultados do algoritmo exato do matching são melhores do que os resultados dos algoritmos heurísticos, e seu tempo computacional não é tão elevado.

Abstract: The purpose of this work is show the application of maximum weight matching algorithm in elaboration of workdays for bus drivers and conductors. This problem must be solved take into consideration the utmost utilization of schedules, in order to obtain the minimal number of officers, of overtimes and of idles hours. With this application, the costs of companies of public transport are minimized. The work of public transport differ of other works, because possess own characteristic. Exist a great demand in a few timetable, like in dawn and in the end of afternoon. In other timetables, exist a demand, although be less. Moreover, the schedule are made in line with the demand of users, what involve in start and end of timetables with a failure of meeting, what difficult the construction of workdays. Other difficulty in this problem is the necessity of accomplishment of laborite legislation and agreements with the Workers Syndicate, because this set of rules impede, many times, a better utilization of timetables. The tables of scales of buses are composed of scales with many durations, where the biggers are divided in smallers scales, so that the cost be minimal. With these tables divided, the scales of small duration can be combinated to the formation of workday of an officer. This combination is made with the maximum weight matching algorithm, where the scales are represented like nodes of an graph, and the maximum weight is assigned to the combinations of scales without overtime and idles hours. The others combinations have weights proportionals to his durations. From this form, the workdays of weekdays, Saturdays and Sundays are constructed. In accordance with the rules mentioned, one workday of weekend can be assigned to each workday of weekday. The maximum weight matching algorithm is used, where the maximum weight is assigned to the combinations of workdays without overtime and idles hours. With this application, the weekly scale of work for the bus drivers and conductors can be constructed with minimal cost. The final phase of this problem consist in assignment of weekly scales for each bus driver and conductor. The maximum weight matching algorithm is used in this phase too, where the maximum weight is assigned to the workdays more approach of previous scale of each officer. This work was applied in three companies of public transport of city of Curitiba, where the algorithms used are all heuristics. The results of exact matching algorithm are better of that the results of heuristics algorithms, and your computational time isn't much high.