Gestão & Produção (Aug 2004)
Uma proposta de solução para o problema da construção de escalas de motoristas e cobradores de ônibus por meio do algoritmo do matching de peso máximo A proposed solution for bus driver and fare collector scheduling problems using the maximum weight matching algorithm
Abstract
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 companhias de transporte público são minimizados. Na primeira fase do trabalho, supondo-se que as tabelas de horários já estejam divididas em escalas de curta e de longa duração, as escalas de curta duração são 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, no qual 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 horas ociosas. Na segunda fase, uma jornada de final de semana é designada para cada jornada semanal de dias úteis. Por meio destas duas fases, as jornadas semanais de trabalho para motoristas e cobradores de ônibus podem ser construídas com custo mínimo. A terceira e última fase deste trabalho consiste na designação das jornadas semanais de trabalho para cada motorista e cobrador de ônibus, considerando-se suas preferências. O Algoritmo do Matching de peso máximo é utilizado para esta fase também. Este trabalho foi aplicado em três empresas de transporte público da cidade de Curitiba - PR, nas quais os algoritmos utilizados anteriormente eram heurísticos, baseados apenas na experiência do encarregado por esta tarefa.The purpose of this paper is to discuss how the maximum weight Matching Algorithm can be applied to schedule the workdays of bus drivers and bus fare collectors. This scheduling should be based on the best possible use of timetables in order to minimize the number of employees, overtime and idle hours, thereby minimizing the operational costs of public transportation companies. In the first phase of this study, assuming that the timetables are already divided into long and short duration schedules, the short schedules can be combined to make up an employee's workday. This combination is done by the maximum weight Matching Algorithm, in which the scales are represented by vertices on a graph and the maximum weight is attributed to combinations of scales that do not lead to overtime or idle hours. In the second phase, a weekend schedule is assigned for every weekly work schedule. Based on these two phases, the weekly work schedules of bus drivers and bus fare collectors can be arranged at a minimal cost. The third and final phase of this study consisted of assigning a weekly work schedule to each bus driver and collector, considering his/her preferences. The maximum weight Matching Algorithm was also used in this phase. This method was applied in three public transportation companies in Curitiba, state of Paraná, which had until then used old heuristic algorithms based solely on managerial experience.
Keywords
