Problema do caixeiro viajante

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO PARANÁ
ESCOLA POLITÉCNICA – CAMPUS LONDRINA
CURSO DE ENGENHARIA DE PRODUÇÃO

Aplicação do Problema do Caixeiro Viajante.

Anderson Senhoreli
Guilherme Mota
Vinícius Santana Michelino

LONDRINA
2014

Resumo

Este trabalho pretendeu mostrar uma forma de aperfeiçoar um caso pratico de uma empresa, utilizando um programa que apresenta uma forma de otimizar problemas reais, que possam ser modelados como o Problema do Caixeiro Viajante (PCV) clássico. Para mostrar o PCV, trabalhou-se com uma empresa de velas que tem o problema em suas entregas e deseja programar de forma a diminuir a sua rota, na cidade de Osasco e região. Considerou-se que o roteiro ótimo corresponderia ao caminho de menor distância entre os endereços a serem entregues a mercadoria, de forma que o caminhão responsável pela entrega sairia da empresa, percorreria todas as demais localidades a fim de realizar a entrega dos materiais, sem passar mais de uma vez no mesmo local. Após retornaria ao seu ponto de origem. Optou-se por realizar a otimização do problema através do programa computacional Excel, utilizando a ferramenta contida no mesmo, denominado Solver.

Palavras-chaves: Otimização, Problema do Caixeiro Viajante, Modelagem Matemática.
1. introdução

Ao trabalhar com transporte temos um problema que requer uma otimização de seus processos com o objetivo de minimizar os gastos. Procurou assim encontrar a forma mais econômica de distribuir um bem disponível em certa quantidade, não necessariamente em um mesmo local, para outros locais principalmente.

Ao fornecer algum produto para várias pessoas automaticamente recebeu-se um grande número de encomendas para ser entregue em várias cidades sendo assim foi traçado um percurso onde o produto seja entregue em um tempo mais curto e assim traçou vários caminhos a ser percorridos apontando sua quilometragem até chegar ao destino.

Segundo Ballou após