Tecnicas de roteirização de veículos aplicadas ao transporte escolar

Abstract

Resumo: O objetivo deste trabalho é apresentar uma solução para o problema de roteirização do Transporte Escolar. O problema foi estudado para um caso real de uma escola com sede na região metropolitana de Curitiba, porém a roteirização foi feita na cidade, já que a grande maioria dos alunos residem nesta. Considerou-se neste problema, as distâncias a serem percorridas por m veículos, a disponibilidade e capacidade destes, e além disso, as demandas de cada um dos n pontos. Para a resolução deste problema foram estudados vários algoritmos heurísticos e exatos, e testes foram realizados com alguns destes algoritmos, dos quais foram selecionados aqueles que forneceram os melhores resultados. Preliminarmente à utilização destes algoritmos, foi utilizado um modelo matemático de Programação Linear Inteira, para a obtenção das quantidades ótimas de veículos e suas respectivas capacidades; em seguida foi utilizado o algoritmo heurístico para obtenção das sementes (depósitos artificiais), procedimentos para obtenção dos clusters ótimos [Bodin et al.,1983] que numa primeira fase é utilizado sem considerar as capacidades dos veículos e na segunda fase considera as capacidades [Ciarke and Wright, 1964] e [Bodin et al., 1983] e o algoritmo da Inserção mais Econômica [Bodin et al., 1983], para a construção das rotas.O problema do Transporte Escolar requer vários veículos partindo de um depósito central, visitando vários pontos de parada para a coleta de alunos e levando-os até a escola, onde permanecem até o final das aulas devendo então ser entregues às suas residências. O objetivo principal do trabalho é minimizar a distância total percorrida pela frota inteira, fazendo reduzir assim, o tempo de permanência dos alunos nos ônibus escolares. Pode-se avaliar a boa performance dos métodos utilizados, através dos resultados que mostraram uma redução de custos de transporte em torno de 20%. Isto sem considerar a economia que a empresa obteve, em realizar o trabalho com um ônibus a menos do que vinha utilizando, acarretando com isto uma redução nos custos com pessoal e também com a manutenção e locação de um veículo, com pessoal e também com a manutenção e locação de um veículo

Abstract: The objective of this work is to present a solution for the problem of school bus transportation problem. The problem was studied taking an account a real situation of a school located in a metropolitan region of Curitiba, but the routing was done in the city, once most of the students live in this area. To solve this problem, many exact and heuristic algorithms were studied, tests were done with some of these algorithms, from wich were selected those that provided the best results. Previously to the utjlization of these algorithms, it was used a mathematical model of Linear and Integer Programing, in order to get the optimal quantities of vehicles and their respective capacities. After that, it was used the heuristic algorithms in order to get the seeds (dummy depots) and then procedures to get the optimal clusters (Bodin et al., 1983) that in an initial phase they were used without considering the vehicles capacities, and in a second phase they considered the capacities (Clarke and Wright, 1964) and (Bodin, 1983). Finally, the algorithm of More Cheapest Insertion (Bodin, 1983) was used to get the routes. The problem of school bus transportation requires many vehicles leaving from a central depot, visiting many demand points to pick up the students and take them to the school, where they stay until the end of the classes, and afterwards delivere them to their homes.The main objective of the work is to minimize the total distance covered by the total fleet, in order to reduce the time that the students stay in the school buses. It is possible to analyze the performance of the methods used, through the results that showed a saving transportantion costs in about 20% to do the same work with oneless bus then that they had been using, generating a reduction in costs with the stoff, as well as with the maintenance and rent of one vehicle