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

Authors

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

DOI:

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

Abstract

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

Download data is not yet available.

Author Biographies

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

References

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

Published

2012-11-09

How to Cite

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

Issue

Vol. 20 No. 3 (2012)

Section

Articles

License

Authors who submit papers for publication by TRANSPORTES agree to the following terms:

  1. The authors retain the copyright and grant Transportes the right of first publication of the manuscript, without any financial charge, and waive any other remuneration for its publication by ANPET.
  2. Upon publication by Transportes, the manuscript is automatically licensed under the Creative Commons License CC BY 4.0 license. This license permits the work to be shared with proper attribution to the authors and its original publication in this journal, and to be adapted for non-commercial purposes, provided appropriate credit is given and any derivative works are distributed under the same terms.
  3. Authors are authorized to enter into additional separate contracts for the non-exclusive distribution of the version of the manuscript published in this journal (e.g., publishing in an institutional repository or as a book chapter), with recognition of the initial publication in this journal, provided that such a contract does not imply an endorsement of the content of the manuscript or the new medium by ANPET.
  4. Authors are permitted and encouraged to publish and distribute their work online (e.g., in institutional repositories or on their personal websites) after the editorial process is complete. As Transportes provides open access to all published issues, authors are encouraged to use links to the DOI of their article in these cases.
  5. Authors guarantee that they have obtained the necessary authorization from their employers for the transfer of rights under this agreement, if these employers hold any copyright over the manuscript. Additionally, authors assume all responsibility for any copyright infringements by these employers, releasing ANPET and Transportes from any responsibility in this regard.
  6. Authors assume full responsibility for the content of the manuscript, including the necessary and appropriate authorizations for the disclosure of collected data and obtained results, releasing ANPET and Transportes from any responsibility in this regard.