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

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

Seção

Artigos