Trabalho de PO, CAIXEIRO VIAJANTE

Prévia do material em texto

UNIVERSIDADE ESTÁCIO DE SÁ - UNESA
ENGENHARIA DE PRODUÇÃO
Pesquisa Operacional II
Caixeiro Viajante
RIO DE JANEIRO - RJ
JUNHO/ 2019
O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.
As cidades são os vértices, as estradas definem as arestas.
Existem basicamente duas formas: 
- Métodos exatos 
- Métodos heurísticos	
Métodos exatos 
· Basicamente, analisam todas as alternativas possíveis. 
· A complexidade é fatorial! 
· Por isto, os métodos mais usados são os do tipo ”branch-and-bound”. 
· Estes consistem em expandir os nós e cortar caminhos de pesquisa que não são promissores
Métodos heurísticos
 
· Com base em heurísticas é possível encontrar soluções aproximadas, isto é, não são soluções exatas, mas fornecem um resultado satisfatório em tempo hábil. 
· Os métodos exatos não retornam solução alguma para um número de cidades maior do que 14 ou 15
Circuito hamiltoniano 
É um caminho que permite passar por todos os vértices de um grafo G, não repetindo nenhum, ou, seja, passar por toda uma e uma só vez por cada.
Caso esse caminho seja possível descrever um ciclo, este é denominado circuito hamiltoniano.
Importância do Caixeiro Viajante na Logística.
A missão da logística é colocar as mercadorias ou serviços certos no lugar indicado, no instante correto e na condição desejada, ao menor custo possível. Evidentemente, se fosse viável produzir todos os bens e serviços no ponto onde eles são consumidos, ou caso as pessoas desejassem viver onde as matérias-primas e a produção se localizam, então a logística seria pouco importante.
Boas práticas de gestão logística envolvem decisões na área de estoque, localização de facilidades (armazéns, plantas industriais, etc.) e transporte, que absorvem a maior parte dos custos da operação. Um dos pontos de destaque na atividade de transporte de mercadorias consiste na definição do percurso ou rota de entrega a ser feito pelos veículos, de forma a minimizar o custo de operação.
Embora haja variantes dos problemas de distribuição, eles podem ser reduzidos a três tipos básicos. O problema de encontrar um trajeto através de uma rede de vias na qual o ponto de origem seja diferente do ponto de destino (problema do caminho mais curto). Outro problema a ser considerado é quando existem múltiplos pontos a serem entregues e um único ponto de chegada e partida (problema do caixeiro viajante). Existe ainda o problema de roteamento de veículos, onde o objetivo é definir qual veículo vai atender a qual rota, e ainda estabelecer roteiros que minimizem o custo total de atendimento. 
Dado um conjunto de pontos a serem visitados (clientes) e um ponto de partida, o problema do caixeiro viajante tem como objetivo determinar a sequencia ótima, que minimizará o custo total da rota, na qual os clientes são visitados uma única vez.
O problema do caixeiro tem diversas aplicações, tais como reabastecimento de alimentos ou de drogarias a partir de um ponto de distribuição central; otimização do trajeto de caminhões de entregas das lojas de varejo aos clientes (entrega domiciliar de mercadorias); caminhões de entrega de jornal, etc..
Numerosos métodos foram propostos para resolvê-lo. Encontrar a rota ótima para um problema particular não tem sido prático para problemas que contém muitos pontos, na prática acima de 20 clientes. O tempo computacional de solução é demasiadamente alto para problemas reais. Os procedimentos heurísticos de solução têm sido boas alternativas, entre eles o 2-opt e heurística de inserção mais distante. Esses procedimentos apresentam bons resultados com um tempo computacional bastante reduzido.
Roteamento de veículos (PRV) ou roteirização consiste em definir roteiros que minimizem o custo total de atendimento, cada um iniciando e terminando no depósito ou base de veículos, assegurando que cada ponto seja visitado exatamente uma vez e nenhuma restrição seja violada. Uma condição básica a ser considerada é que a demanda em qualquer rota não exceda a capacidade do veículo que a atende.
Existem extensões para o problema de roteamento. Dentre elas pode-se citar o problema de roteamento com janela de tempo, onde se deve respeitar um horário específico de entrega. Existe também o problema de coleta e entrega, onde existem pontos onde se deve fazer coleta de alguma mercadoria, e outros onde se devem fazer entregas. Em vez de considerar um único ponto de partida (depósito), existe a alternativa de partir de vários depósitos, logo o algoritmo deve estabelecer de qual depósito cada veículo deve partir, a fim de minimizar o custo total das rotas. Há uma tendência das empresas de transporte em utilizar veículos com multi-compartimentos, logo a restrição de cubagem de cada compartimento, bem como o tipo de produto que pode ser alocado, deve ser respeitada.
O problema de roteirização de veículos é bastante aplicado em empresas de distribuição e transporte de cargas. Algumas dessas empresas chegam a ter que roteirizar milhares de clientes por dia, e possuem uma frota considerável de veículos de diversas capacidades e custos. Encontrar a solução exata para esses problemas é praticamente impossível para problemas reais, mas com a metodologia do Caixeiro Viajante podemos achar a melhor rota em pouco tempo, assim otimizando o trabalho da Logística. 
É inegável a contribuição e a importância da geoinformação para a logística, seja para auxiliar a localização de centros de distribuição, roteirização ou no monitoramento de frotas.
Exercício: 
	x
	A
	B
	C
	D
	E
	A
	-
	80
	160
	110
	10
	B
	80
	-
	240
	150
	30
	C
	160
	240
	-
	60
	250
	D
	110
	150
	60
	-
	140
	E
	10
	30
	250
	140
	-
Etapa 5
	x\x5
	X5
	F5
	X5
	B
	80
	80
	A
	C
	160
	160
	A
	D
	110
	110
	A
	E
	10
	10
	A
Etapa 4
	x\x4
	B
	C
	D
	E
	F4
	X4
	B
	
	240+160=400
	150+110=260
	30+10=40
	40
	E
	C
	240+80=320
	
	60+110=170
	250+10=260
	170
	D
	D
	150+80=230
	60+160=220
	
	140+10=150
	150
	E
	E
	30+80=110
	250+160=410
	140+110=250
	
	110
	B
Etapa 3
	x\x3
	B
	C
	D
	E
	F3
	X3
	B
	
	240+170=410
	150+150=300
	Ciclo B,E,B
	300
	D
	C
	240+40=280
	
	60+150=210
	250+110=360
	210
	D
	D
	150+40=190
	Ciclo D,C,D
	
	140+110=250
	190
	B
	E
	Ciclo E,B,E
	250+170=420
	Ciclo E,D,E
	
	420
	C
Etapa 2
	x\x2
	B
	C
	D
	E
	F2
	X2
	B
	
	240+210=450
	Ciclo B,D,B
	30+420=450
	450
	C
	C
	240+300=540
	
	60+190=240
	Ciclo C,E,C
	250
	D
	D
	Ciclo D,B,D
	Ciclo D,C,D
	
	Ciclo D,E,C,D
	-
	-
	E
	Ciclo E,B,D,E
	Ciclo E,C,D,E
	Ciclo E,D,B,E
	
	-
	-
Etapa 1 
	x\x1
	B
	C
	D
	E
	F1
	X1
	A
	80+450=530
	160+250=410
	-
	-
	410
	C
 Concluindo que passa por, A – C - D – B – E e chega no A. 
Fazendo 410km.