Blucher Engineering Proceedings

Dezembro 2020, vol.7, num.3 - VIII Simpósio de Engenharia de Produção
Artigo completo - Open Access Idioma principal | Segundo principal

DIFERENTES FORMULAÇÕES DE PROGRAMAÇÃO LINEAR INTEIRA PARA A ROTEIRIZAÇÃO NO TRANSPORTE DE FUNCIONÁRIOS

DIFERENTES FORMULAÇÕES DE PROGRAMAÇÃO LINEAR INTEIRA PARA A ROTEIRIZAÇÃO NO TRANSPORTE DE FUNCIONÁRIOS

Sati, Tarek Nasser; Scarpin, Cassius Tadeu; Pécora Júnior, José Eduardo; Lopes, Roza Maria Zoellner

Artigo completo:

Diversas empresas oferecem opção de transporte para seus funcionários. Por ser uma tarefa realizada diariamente, otimizar este processo pode resultar em uma considerável diminuição de custos para a empresa. Neste artigo é comparada a roteirização do transporte de funcionários, em uma empresa na cidade de Curitiba, por meio de diferentes modelos exatos de Programação Linear Inteira mista (PLIM). São realizadas três diferentes propostas de resolução para o caso, utilizando metodologias baseadas na formulação dos seguintes problemas: Travelling Salesman Problem (TSP) ou Problema do Caixeiro Viajante; Vehicle Routing Problem (VRP) ou Problema de Roteirização de Veículos; e P-median Problem (PMP) ou Problema das P-medianas. Os resultados mostraram grande diferença no tempo computacional quando se divide o problema em duas fases, porém relativamente pequena diferença na distância percorrida. Todos os testes computacionais foram processados no software Gurobi, utilizando o Software Excel e o suplemento Open Solver como interface para entrada de dados.

Diversas empresas oferecem opção de transporte para seus funcionários. Por ser uma tarefa realizada diariamente, otimizar este processo pode resultar em uma considerável diminuição de custos para a empresa. Neste artigo é comparada a roteirização do transporte de funcionários, em uma empresa na cidade de Curitiba, por meio de diferentes modelos exatos de Programação Linear Inteira mista (PLIM). São realizadas três diferentes propostas de resolução para o caso, utilizando metodologias baseadas na formulação dos seguintes problemas: Travelling Salesman Problem (TSP) ou Problema do Caixeiro Viajante; Vehicle Routing Problem (VRP) ou Problema de Roteirização de Veículos; e P-median Problem (PMP) ou Problema das P-medianas. Os resultados mostraram grande diferença no tempo computacional quando se divide o problema em duas fases, porém relativamente pequena diferença na distância percorrida. Todos os testes computacionais foram processados no software Gurobi, utilizando o Software Excel e o suplemento Open Solver como interface para entrada de dados.

Download (PDF)

Palavras-chave:

DOI: 10.5151/viisimep-315858

Referências bibliográficas
  • [1] BEKTAS, Tolga. The multiple traveling salesman problem: An overview of formulations and
  • [2] solution procedures. Omega, v. 34, n. 3, p. 209–219, 2006.
  • [3] CHRISTOFIDES, N., EILON, S. An Algorithm for the Vehicle-dispatching Problem.
  • [4] Journal of the Operational Research Society, v. 20, p. 309–318, 1969.
  • [5] DANTZIG, G. B.; FULKERSON, D. R.; JOHNSON, S. M. Solution of a Large-Scale
  • [6] Traveling Salesman Problem. Operations Research, v. 2, p. 393-410, 1954.
  • [7] DANTZIG, G. B.; RAMSER, J. H. The Truck Dispatching Problem. Management Science,
  • [8] v. 6, n. 1, p. 80–91, 1959.
  • [9] GIL, Antonio Carlos. Como elaborar projetos de pesquisa. 4ª Edição. São Paulo: Atlas S.A,
  • [10] 2002.
  • [11] GODOY, Arilda S. Introdução à pesquisa qualitativa e suas possibilidades. Revista de
  • [12] Administração de Empresas, São Paulo, 1995, v.35, n. 2, p. 57-63.
  • [13] Hakimi, S.L. Optimum Location of Switching Centers and the Absolute Centers and Medians
  • [14] of a Graph. Operations Research, v.12, p. 450–459, 1964.
  • [15] Hakimi, S.L. Optimum Distribution of Switching Centers and Some Graph-Related Theoretic
  • [16] Problems. Operations Research, v.13, p. 462–475, 1965.
  • [17] LAKATOS, Eva Maria; MARCONI, Marina de Andrade. Fundamentos de metodologia
  • [18] científica. 5. ed. São Paulo: Atlas, 2003.
  • [19] LAPORTE, Gilbert. Fifty years of vehicle routing. Transportation Science, v. 43, n. 4,
  • [20] p. 408–416, 2009.
  • [21] Miller, C.E.; Tucker, A.W. & Zemlin, R.A. Integer programming formulation of traveling
  • [22] salesman problems. Journal of Association for Computing Machinery, v. 7, p. 326–9,
  • [23] 1960.
  • [24] ReVelle, C.S. & Swain, R.W. Central facilities location. Geographical Analysis, v. 2, p. 30-
  • [25] 42, 1970.
  • [26] TIBURCIO, Dalvana Matilde. Técnicas da pesquisa operacional na abordagem do
  • [27] problema de roteamento no transporte de funcionários de empresas. 2012. 86 f.
  • [28] Dissertação (Mestrado) - Curso de Engenharia de Produção, Universidade Federal do Paraná,
  • [29] Curitiba, 2012.
Como citar:

Sati, Tarek Nasser; Scarpin, Cassius Tadeu; Pécora Júnior, José Eduardo; Lopes, Roza Maria Zoellner; "DIFERENTES FORMULAÇÕES DE PROGRAMAÇÃO LINEAR INTEIRA PARA A ROTEIRIZAÇÃO NO TRANSPORTE DE FUNCIONÁRIOS", p-3027-3039. In: Anais do VIII Simpósio de Engenharia de Produção . São Paulo: Blucher, 2020.
ISSN 23577592, DOI 10.5151/viisimep-315858

últimos 30 dias

143
downloads

358
visualizações

864
indexações