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

Paulo Henrique Siqueira, Luzia Vidal de Souza

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. 


Texto completo:

PDF

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




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

Métricas do artigo

Carregando Métricas ...

Metrics powered by PLOS ALM


Direitos autorais 2012 Paulo Henrique Siqueira, Luzia Vidal de Souza

Licença Creative Commons
Esta obra está licenciada sob uma licença Creative Commons Atribuição 4.0 Internacional.

TRANSPORTES (ISSN: 2237-1346) é uma publicação da ANPET - Associação Nacional de Pesquisa e Ensino em Transportes (www.anpet.org.br)

 

Licença Creative Commons

Este obra está licenciado com uma Licença Creative Commons Atribuição-NãoComercial-CompartilhaIgual 4.0 Internacional.