Métodos Heurísticos aplicados na construção de roteiros de Transporte Escolar para o Estado do Paraná

Autores

  • Paulo Henrique Siqueira Universidade Federal do Paraná
  • Luzia Vidal de Souza Universidade Federal do Paraná

DOI:

https://doi.org/10.4237/transportes.v20i3.567

Resumo

Neste trabalho, o problema de roteirização de veículos é aplicado ao transporte escolar. A metodologia utilizada é composta de três fases: a primeira consiste na determinação de pontos de parada dos veículos, considerando uma distância máxima que os alunos podem andar de suas residências até estes pontos; na segunda são calculadas as distâncias reais a partir das informações das vias de cada município e na terceira as rotas são formadas aplicando a heurística Location Based Heuristic (LBH) com algumas modificações para atender ao problema. Os testes foram realizados em 32 municípios do estado do Paraná. Os resultados obtidos foram comparados às rotas que são efetivamente realizadas em cada município, verificando-se uma economia que varia de3,1 a 33,55% na quilometragem total percorrida e no número de veículos utilizados, além de uma redução considerável na quantidade de pontos de parada dos veículos. 

Downloads

Não há dados estatísticos.

Biografia do Autor

Paulo Henrique Siqueira, Universidade Federal do Paraná

Professor adjunto do Departamento de Expressão Gráfica. Atuo nos programas de pós-graduação em Métodos Numéricos em Engenharia e Engenharia de Produção da UFPR.

Luzia Vidal de Souza, Universidade Federal do Paraná

Departamento de Expressão Gráfica - UFPR

Referências

Bodin, L.; B. Golden; A. Assad e M. Ball (1983) The state of the art in the routing and scheduling of vehicles and crews. Computers & Operations Research, v. 10, n. 2, p. 63–211. DOI:10.1016/0305-0548(83)90030-8

Bowerman, R.; B. Hall e P. A. Calamai (1995) A Multi-Objective optimization approach to urban school bus outing: formulation and solution method. Transportation Research, v. 29A, n. 2, p. 107–123. DOI: 10.1016/0965-8564(94)E0006-U

Braca, J.; J. Bramel; B. Posner e D. Simchi-Levi (1997) A computerized approach to the New York City school bus routing problem. IIE Transactions, v. 29, n. 8, p. 693–702. DOI:10.1023/A:1018526202990

Bramel, J. e D. Simchi-Levi (1995) A location based heuristic for general routing problems. Operations Research, v. 43, n. 4, p. 649–660. DOI:10.1287/opre.43.4.649

Dulac, G.; J. Ferland e P. A. Fogues (1980) School bus routes generator in urban surroundings. Computers & Operations Research, v. 7, p. 199–213. DOI:10.1016/0305-0548(80)90006-4

Fisher, M.L. (1995) Vehicle routing. Handbooks in Operations Research and Management Science: Network Routing, v. 8, p. 1–33. DOI:10.1016/S0927-0507(05)80105-7

Laporte, G.; M. Gendreau; J. Y. Potvin e F. Semet (2000) Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, v. 7, n. 4-5, p. 285–300. DOI:10.1111/j.1475-3995.2000.tb00200.x

Li, L.Y.O. e Z. Fu (2002) The school bus routing problem: a case study. Journal of the Operational Research Society, v. 53, n. 5, p. 552–558. DOI:10.1057/PALGRAVE/JORS/2601341

Lu, Q. e M. Dessouky (2004) An Exact algorithm for the Multiple Vehicle Pickup and Delivery Problem. Transportation Science, v. 38, n. 4, p. 503–514. DOI:10.1287/trsc.1030.0040

Modares, A.; S. Somhom e T. A. Enkawa (1999) A self-organizing neural network approach for multiple traveling salesman and vehicle routing problems. International Transactions in Operational Research, v. 6, n. 6, p. 591–606. DOI:10.1111/j.1475-3995.1999.tb00175.x

Park, J. e B. I. Kim (2010) The school bus routing problem: A review. European Journal of Operational Research, v. 202, n. 2, p. 311–319. DOI:10.1016/j.ejor.2009.05.017

Ropke, S. e D. Pisinger (2006a) An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, v. 40, p. 455–472. DOI:10.1287/trsc.1050.0135

Ropke, S. e D. Pisinger (2006b) A unified heuristic for a large class of Vehicle Routing Problems with Backhauls. European Journal of Operational Research, v. 171, n. 3, p. 750–775. DOI:10.1016/j.ejor.2004.09.004

Ropke, S. e D. Pisinger (2007) A general heuristic for vehicle routing problems. Computers & Operations Research, v. 34, n. 8, p. 2403–2435. DOI:10.1016/j.cor.2005.09.012

Schittekat, P.; M. Sevaux e K. Sorensen (2006) A mathematical formulation for a school bus routing problem. Anais do ICSSSM’06: International Conference on Service Systems and Service Management, França, p. 1552–1557. DOI:10.1109/ICSSSM.2006.320767

Secretaria Estadual de Desenvolvimento Urbano do Estado do Paraná – SEDU/PR. Disponível em: <http://www.paranacidade.org.br/>. Acesso em 30/03/2012.

Secretaria de Estado da Educação – SEED/PR. Disponível em: <http://www.seed.pr.gov.br/> Acesso em 30/03/2012.

Spasovic, L. e S. Chien (2001) A Methodology for Evaluating of School Bus Routing - A Case Study of Riverdale, New Jersey. Anais do 80th Annual Meeting of Transportation Research Board, Washington.

Steiner, M.T.A.; L. V. Z. Zamboni; D. M. B. Costa; C. Carnieri e A. L. Silva (2000) O Problema de roteamento no Transporte Escolar. Pesquisa Operacional, v. 20, n. 1, p. 83–99. DOI:10.1590/S0101-74382000000100009

Taha, H.A. (1997) Operations research: an introduction (6th ed.), Prentice Hall, New Jersey.

Toth, P. e D. Vigo (2003) The Granular Tabu Search and Its Application to the Vehicle-Routing Problem. INFORMS Journal on Computing, v. 15, n. 4, p. 333–346. DOI:10.1287/ijoc.15.4.333.24890

vol. 20, n. 3, Dezembro 2012

Downloads

Publicado

09-11-2012

Como Citar

Siqueira, P. H., & Souza, L. V. de. (2012). Métodos Heurísticos aplicados na construção de roteiros de Transporte Escolar para o Estado do Paraná. TRANSPORTES, 20(3), 28–40. https://doi.org/10.4237/transportes.v20i3.567

Edição

v. 20 n. 3 (2012)

Seção

Artigos

Licença

Ao submeter um manuscrito para publicação neste periódico, todos os seus autores concordam, antecipada e irrestritamente, com os seguintes termos:

  1. Os autores mantém os direitos autorais e concedem à Revista TRANSPORTES o direito de primeira publicação do manuscrito, sem nenhum ônus financeiro, e abrem mão de qualquer outra remuneração pela sua publicação pela ANPET.
  2. Ao ser submetido à Revista TRANSPORTES, o manuscrito fica automaticamente licenciado sob a Licença Creative Commons Attribution, que permite o compartilhamento do trabalho com reconhecimento da autoria e da publicação inicial neste periódico.
  3. Os autores têm autorização para assumir contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento da publicação inicial nesta revista, desde que tal contrato não implique num endosso do conteúdo do manuscrito ou do novo veículo pela ANPET.
  4. Os autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) depois de concluído o processo editorial. Como a Revista TRANSPORTES é de acesso livre, os autores são estimulados a usar links para o site da Revista TRANSPORTES nesses casos.
  5. Os autores garantem ter obtido a devida autorização dos seus empregadores para a transferência dos direitos nos termos deste acordo, caso esses empregadores possuam algum direito autoral sobre o manuscrito. Além disso, os autores assumem toda e qualquer responsabilidade sobre possíveis infrações ao direito autoral desses empregadores, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
  6. Os autores assumem toda responsabilidade sobre o conteúdo do trabalho, incluindo as devidas e necessárias autorizações para divulgação de dados coletados e resultados obtidos, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.