O problema do caixeiro viajante

Prévia do material em texto

O problema do caixeiro viajante é muito antigo, é o que afirma Santos Neto e Santana (2015, p.99) no passado a logística compreendia o transporte de alimentos e munição para as tropas no campo de combate. Atualmente, representa o controle de processos gerenciais, desde o transporte para entrada de matéria prima nas empresas até a distribuição de produtos ao consumidor final. Hoje, a logística faz parte, das disciplinas que atuam na alta administração das organizações, incluindo toda a parte de movimentação de produtos e informações em toda uma cadeia de suprimento. A importância da logística está justamente na hora que a empresa se encontra com dificuldades. O empresário considera que o problema pode ser resolvido com uma reestruturação nos seus processos operacionais, principalmente no sistema logístico.
É importante expressar a importância da logística para compreendermos o problema do caixieiro viajante. Ballou (2009) diz que a logística é definida como a conjuntura de quatro atividades fundamentais: aquisição, movimentação, armazenagem e entrega de produtos e, para que este conjunto seja funcional, é necessário um planejamento logístico e a interatividade dos processos , ou seja, ele afirma que planejamento é primordial para que se tenha um atendimento de qualidade e eficiência.
O roteirismo vem para auxiliar definir menor rota para atravessar cidades, esse método surgiu da necessidade do caixeiro viajante obter maiores resultados em menos tempo, desse modo criou-se através de estudos feitos por formulas de problemas algoritimos combinatórios, com objetivo de calcular o percuso dos viajantes. 
O modelo matemático inicial do PCV compreende determinar origens e destinos dos viajantes, com o principal objetivo de reduzir custos, sendo a formula (FO), (1)-(3). 
Para Dantzig, Fulkerson e Johnson (1954), apresentam formulas exponenciais implementada a (FO), (1)-(3): ∑ 𝑖,𝑗∈𝑆 𝑥𝑖𝑗 ≤ |𝑆| − 1, 𝑆 ⊆ {2, … , 𝑛}, 2 ≤ |𝑆| ≤ 𝑛 − 1 (4) onde ocorre restrição de eliminação de sub-rotas, estabelecendo subconjuntos de vértices 𝑆 apenas |𝑆| − 1 arcos sejam definido como solução e mostrando outra rota caso um imprevisto aconteça. 
Já para Miller, Tucker e Zemlin (1960) afirmam que uma formulação considerada clássica é demonstrada, no entanto, esta é da forma polinomial, sendo declarada como: 𝑢𝑖 − 𝑢𝑗 + (𝑛 − 1)𝑥𝑖𝑗 ≤ 𝑛 − 2, 𝑖,𝑗 = 2, … , 𝑛 (5), 1 ≤ 𝑢𝑖 ≤ 𝑛 − 1, 𝑖 = 2, … 𝑛 (6), eles consideram a variável 𝑢𝑖 para indicar quando cada vértice 𝑖 é visitado, sendo um modelo de fácil aplicação e assim com passar do tempo esses modelos sofreram diversas alterações.
É importante falar que em busca de diversas formulas que garantissem a eficácia dos serviços a roteirização passou fazer parte do cenário empresarial, dinamizando seus serviços e fomentando melhorias nos sistemas, Ballou (2001) afirma, a roteirização é a atividade que tem por fim buscar os melhores trajetos que um veículo deve fazer através de uma malha. Esta busca, que geralmente tem como objetivo minimizar o tempo ou a distância, é uma decisão frequente na logística empresarial.
Concluo que a logística está diretamente ligado ao PCV e que uma organização que quer investir no sucesso da empresa precisa está atualizada com ferramentas que auxiliem nos serviços, como programas que monitoram, reduz rotas, e minimizam custos tem maior chance de se destacar no mercado, não só pela agilidade e também pela eficiência, gerando mais lucros e fidelizando seus cliente .
REFERENCIAS
SANTOS NETO, U.J.; SANTANA, L.C. Logística e serviço ao cliente como estratégia competitiva. Revista de Iniciação Científica – RIC, Vol 02, n° 02, p. 97-111. ISSN 2258-1166. Cairu, Jun. 2015.
BALLOU, R. H. Logística Empresarial: Transportes, administração de materiais e distribuição física. São Paulo: Atlas, 2009.
BALLOU, Ronald Arold . 2001. Gerenciamento da Cadeia de Suprimentos. 1° edição. Bookman.
https://www.amazon.com.br/Gerenciamento-Cadeia-Suprimentos-Ronald-Ballou/dp/8573078510/ref=sr_1_4?qid=1663261741&refinements=p_lbr_books_authors_browse-bin%3ARonald+H.+Ballou&s=books&sr=1-4
DANTZIG, G; FULKERSON, R; JOHNSON, S. Solution of a large-scale travelingsalesman problem. Journal of the operations research society of America, v. 2, n. 4, p. 393-410, 1954.
https://docs.ufpr.br/~volmir/PO_II_12_TSP.pdf
MILLER, C. E.; TUCKER, A. W.; ZEMLIN, R. A. Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), ACM New York, NY, USA, v. 7, n. 4, p. 326–329, 1960.
https://docs.ufpr.br/~volmir/PO_II_12_TSP.pdf
https://www.cobli.co/blog/o-que-e-roteirizacao/?campaignid=6815575114&adgroupid=78534266054&adid=502383823121&utm_source=google&utm_term=aud-808923658065:dsa-894257289118&utm_medium=cpc&utm_campaign=br-dsa-blog&hsa_net=adwords&hsa_kw=&hsa_tgt=aud-808923658065:dsa-894257289118&hsa_acc=6887042085&hsa_grp=78534266054&hsa_mt=&hsa_cam=6815575114&hsa_ver=3&hsa_ad=502383823121&hsa_src=g&gclid=Cj0KCQjw94WZBhDtARIsAKxWG-87gLFELyI01OrVoFX5TWBBfb9k4oEu3Yr0SL3L1cLYn4NBy758KJEaApSEEALw_wcB
O
 
problema do caixeiro viajante é muito antigo,
 
é o que afirma 
Sa
ntos Neto e 
Santana (2015, p.99) n
o passado a logística compreendia o transporte de 
alimentos e munição para as tropas no campo de combate. Atualmente, 
repre
senta o controle de processos gerenciais, desde o transporte para entrada 
de matéria prima nas empresas até a distribuição de produtos ao consumidor 
final. Hoje, a logística faz parte, das disciplinas que atuam na alta administração 
das organizações, inclu
indo toda a parte de movimentação de produtos e 
informações em toda uma cadeia de suprimento. A importância da logística está 
justamente na hora que a empresa
 
se encontra com dificuldades. O empresário 
considera que o problema pode ser resolvido com uma ree
struturação nos seus 
processos operacionais, principalmente no sistema logístico
.
 
É
 
importante expressar a import
â
ncia da 
logística
 
para compreendermos o 
problema do caixieiro viajante.
 
Ballou (2009)
 
diz que 
 
a logística é definida como 
a conjuntura de quatro atividades fundamentais: aquisição, movimentação, 
ar
mazenagem e entrega de produtos e, para que este conjunto seja funcional, é 
necessário um planejamento logístico e a interatividade dos processos
 
, ou seja, 
ele afirma que planejamento é primordial para que se tenha um atendimento de 
qualidade
 
e 
eficiência
.
 
O
 
roteirismo vem para auxiliar 
definir 
menor rota para atravessar cidades, esse 
 
métod
o 
surgiu 
 
da
 
n
ecessidade do caixeiro
 
viajante
 
 
obter maiores resultados 
 
em menos tempo, desse modo criou
-
se através de estudos feitos por formulas 
de problemas algoritimos 
combinatórios
, com 
objetivo de c
alcular o percuso dos 
viajantes
. 
 
 
O
 
modelo
 
matemático
 
inicial do PCV 
 
compreende determinar
 
origens e destinos 
dos viajantes, 
 
com o principal obj
etivo de reduzir custos, 
sendo a formula 
 
(FO), 
(1)
-
(3). 
 
Para 
Dantzig, Fulkerson e Johnson (1954)
, 
apresentam formulas exponenciais 
implementada a (FO), (1)
-
(3):
 
?
 
??
,
??
?
??
 
??
??
??
 
=
 |
??
| 
-
 1, 
??
 
?
 
{2, 
…
 
, 
??
}, 2 
=
 |
??
| 
=
 
??
 
-
 1 
(4)
 
onde ocorre 
 
restrição
 
de
 
eli
mi
nação de sub
-
rotas
, estabelecendo 
subconjuntos de 
vértices
 
 
??
 
apenas |
??
| 
-
 
1 arcos
 
sejam def
inido como solução e 
mostrando outra rota caso um imprevisto aconteça.
 
 
J
á 
para 
Miller, Tucker e Zemlin (1960)
 
 
afirmam que 
uma
 
formulação considerada 
clássica é demonstrada, no entanto, esta é da forma polinomial, sendo declarada 
como: 
??
??
 
-
 
??
??
 
+ (
??
 
-
 1)
??
??
??
 
=
 
??
 
-
 2, 
??
,
??
 
= 2, … , 
??
 
(5)
, 
1 
=
 
??
??
 
=
 
??
 
-
 1, 
??
 
= 2, … 
??
 
(6)
, 
eles consideram a 
variável??
??
 
para indicar
 
quando
 
cada 
vértice
 
??
 
é visitado
, sendo 
um modelo de 
fácil
 
aplicação 
e assim com passar do tempo esses modelos 
sofreram diversas alterações.
 
É
 
importante falar que em busca de diversas formulas que garantissem a eficácia 
dos serviços 
a roteirização
 
passou fazer parte do cenário empresarial, 
dinamizando seus 
serviços
 
e 
fomentando
 
melhorias nos 
sistemas, Ballou
 
(2001)
 
afirma, a
 
roteirização é a atividade que tem por fim buscar os melhores trajetos 
que um veículo deve fazer através de uma malha. Esta busca, que geralmente 
O problema do caixeiro viajante é muito antigo, é o que afirma Santos Neto e 
Santana (2015, p.99) no passado a logística compreendia o transporte de 
alimentos e munição para as tropas no campo de combate. Atualmente, 
representa o controle de processos gerenciais, desde o transporte para entrada 
de matéria prima nas empresas até a distribuição de produtos ao consumidor 
final. Hoje, a logística faz parte, das disciplinas que atuam na alta administração 
das organizações, incluindo toda a parte de movimentação de produtos e 
informações em toda uma cadeia de suprimento. A importância da logística está 
justamente na hora que a empresa se encontra com dificuldades. O empresário 
considera que o problema pode ser resolvido com uma reestruturação nos seus 
processos operacionais, principalmente no sistema logístico. 
É importante expressar a importância da logística para compreendermos o 
problema do caixieiro viajante. Ballou (2009) diz que a logística é definida como 
a conjuntura de quatro atividades fundamentais: aquisição, movimentação, 
armazenagem e entrega de produtos e, para que este conjunto seja funcional, é 
necessário um planejamento logístico e a interatividade dos processos , ou seja, 
ele afirma que planejamento é primordial para que se tenha um atendimento de 
qualidade e eficiência. 
O roteirismo vem para auxiliar definir menor rota para atravessar cidades, esse 
método surgiu da necessidade do caixeiro viajante obter maiores resultados 
em menos tempo, desse modo criou-se através de estudos feitos por formulas 
de problemas algoritimos combinatórios, com objetivo de calcular o percuso dos 
viajantes. 
O modelo matemático inicial do PCV compreende determinar origens e destinos 
dos viajantes, com o principal objetivo de reduzir custos, sendo a formula (FO), 
(1)-(3). 
Para Dantzig, Fulkerson e Johnson (1954), apresentam formulas exponenciais 
implementada a (FO), (1)-(3): ? ??,????? ?????? = |??| - 1, ?? ? {2, … , ??}, 2 = |??| = ?? - 1 
(4) onde ocorre restrição de eliminação de sub-rotas, estabelecendo 
subconjuntos de vértices ?? apenas |??| - 1 arcos sejam definido como solução e 
mostrando outra rota caso um imprevisto aconteça. 
Já para Miller, Tucker e Zemlin (1960) afirmam que uma formulação considerada 
clássica é demonstrada, no entanto, esta é da forma polinomial, sendo declarada 
como: ???? - ???? + (?? - 1)?????? = ?? - 2, ??,?? = 2, … , ?? (5), 1 = ???? = ?? - 1, ?? = 2, … ?? (6), 
eles consideram a variável ???? para indicar quando cada vértice ?? é visitado, sendo 
um modelo de fácil aplicação e assim com passar do tempo esses modelos 
sofreram diversas alterações. 
É importante falar que em busca de diversas formulas que garantissem a eficácia 
dos serviços a roteirização passou fazer parte do cenário empresarial, 
dinamizando seus serviços e fomentando melhorias nos sistemas, Ballou (2001) 
afirma, a roteirização é a atividade que tem por fim buscar os melhores trajetos 
que um veículo deve fazer através de uma malha. Esta busca, que geralmente