AULA 6 PPT - OTIM DE SISTEMAS DE TRANS GST0311

Prévia do material em texto

OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Aula 6 – Problemas de transportes
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Problemas de Transportes
Objetivos:
Identificar os problemas clássicos de transportes;
Verificar as possibilidades de uso de cada método de solução.
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Um problema bastante comum que muitas vezes pode ser modelado como um problema de programação linear é o problema de transporte. Este problema pode envolver o transporte de alguma carga de diversas fontes a diversos pontos de destino. Dados o custo da distribuição entre cada fonte e destino, as produções das fontes e as capacidades dos destinos, dessa forma podemos minimizar o custo total do transporte.
O PROBLEMA DE TRANSPORTE
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Segundo Campos (1998), Problema de cobertura de arcos
Problemas de ROTEAMENTO de VEÍCULOS (PRV)
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Segundo Campos (1998), Problema de cobertura de nós
Problemas de ROTEAMENTO de VEÍCULOS (PRV)
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Segundo Campos (1998), Problema de cobertura de nós (Cont...)
Problemas de ROTEAMENTO de VEÍCULOS (PRV)
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Os problemas de roteamento de veículos de uma forma geral consistem em determinar percursos ótimos para uma frota de veículos estacionada em um ou mais domicílios de forma a atender um conjunto de clientes geograficamente dispersos. Um exemplo clássico aparece nos problemas de distribuição/coleta de mercadorias, onde cada cliente possui uma demanda específica e os veículos apresentam capacidade limitada. Busca-se a configuração das rotas dos veículos de modo que cada cliente seja servido por um e somente um veículo, minimizando-se o custo/comprimento do percurso total.
Dado um conjunto de cidades e conhecidas as distâncias entre cada uma delas, pretende-se determinar o circuito de menor comprimento que passa por todas as cidades, exatamente uma vez, e que termina na cidade de onde partiu.
Problemas de ROTEAMENTO de VEÍCULOS (PRV)
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Segundo Lucchesi (1979),
A estrutura matemática do problema do caixeiro viajante é um grafo em que cada cidade é um nó e as linhas que unem todos os nós são denominadas por arcos. Associada a cada linha está uma distância ou custo.
Uma viagem, que passe por todas as cidades uma única vez, corresponde a qualquer subconjunto de linhas do grafo e é designado por circuito Hamiltoniano, na teoria de grafos. O comprimento de um circuito é a soma do comprimento das linhas que fazem parte da viagem.
Problema do caixeiro viajante
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Segundo Lucchesi (1979),
Problema do caixeiro viajante
Circuito ótimo
A + D + E + C + B + A
Comprimento do circuito
2 + 4 + 5 + 6 + 3 = 20
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Segundo Lucchesi (1979),
Aplicações:
Determinação de percursos ótimos em transporte de pessoas ou mercadorias
Ex: ônibus de transportes urbanos
Subproblema de problemas de distribuição e planejamento de rotas de veículos
Ex: determinar, para um dado conjunto de veículos, qual o percurso que cada veículo deve efetuar, de modo a, no seu conjunto, servir a todos os clientes.
Problema do caixeiro viajante
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Um problema bastante comum que muitas vezes pode ser modelado como um problema de programação linear é o problema de transporte.
Carteiro chinês – Problema de cobertura de arcos, onde deve-se encontrar a rota de menor custo, passando por todos os arcos pelo menos uma vez.
Carteiro chinês capacitado – Generalização do “Carteiro chinês”, onde leva-se em consideração a capacidade dos veículos.
Caixeiro viajante – Problema de cobertura de nós, onde deve-se encontrar a rota de menor custo, visitando por todos os nós apenas uma vez.
Síntese da aula 6 (Continuação)
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Múltiplos caixeiros viajantes – Generalização do “Caixeiro viajante”, onde são considerados mais de um “caixeiro viajante”.
Roteirização com um único depósito e vários veículos – Generalização do “Caixeiro viajante”, onde os veículos saem da central de distribuição e atendem a todos os nós, buscando diminuir a distância total.
Roteirização com vários depósitos e vários veículos – Generalização do problema anterior, só que com múltiplos depósitos.
Roteirização com depósito único, vários veículos e demanda estocástica – Generalização do problema anterior, só que a demanda é desconhecida.
Síntese da aula 6
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Circuito ótimo
A – E - B - C - D - A
Comprimento do circuito
3 + 3 + 3 + 3 + 2 = 15
Circuito ótimo
A – C - B - E - D – A 
Comprimento do circuito
2 + 3 + 3 + 5 + 2 = 15
Circuito ótimo
A – C - D - B - E - A
Comprimento do circuito
2 + 3 + 4 + 3 + 3 = 15
Partindo de “A”, qual é o circuito ótimo?
Neste caso específico encontramos 3 (três) circuitos ótimos.
Síntese da aula 6
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
É correto afirmar sobre o Carteiro Chinês que:
Consiste em determinar uma rota de custo mínimo que passe por todos os arcos pelo menos uma vez.
Consiste em determinar uma rota de custo mínimo que visite todos os nós uma única vez. 
Consiste em determinar uma rota de custo mínimo que visite todos os arcos uma única vez.
Consiste em determinar uma rota de custo mínimo que passe por todos os nós pelo menos uma vez.
Consiste em determinar uma rota de custo mínimo que passe por todos os arcos mais de uma vez.
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
É correto afirmar sobre o Carteiro Chinês que:
Consiste em determinar uma rota de custo mínimo que passe por todos os arcos pelo menos uma vez.
Consiste em determinar uma rota de custo mínimo que visite todos os nós uma única vez. 
Consiste em determinar uma rota de custo mínimo que visite todos os arcos uma única vez.
Consiste em determinar uma rota de custo mínimo que passe por todos os nós pelo menos uma vez.
Consiste em determinar uma rota de custo mínimo que passe por todos os arcos mais de uma vez.
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
É correto afirmar sobre o Caixeiro Viajante que:
Consiste em determinar uma rota de custo mínimo que passe por todos os arcos pelo menos uma vez.
Consiste em determinar uma rota de custo mínimo que visite todos os arcos uma única vez.
Consiste em determinar uma rota de custo mínimo que visite todos os nós uma única vez. 
Consiste em determinar uma rota de custo mínimo que passe por todos os nós pelo menos uma vez
Consiste em determinar uma rota de custo mínimo que passe por todos os arcos mais de uma vez.
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
É correto afirmar sobre o Caixeiro Viajante que:
Consiste em determinar uma rota de custo mínimo que passe por todos os arcos pelo menos uma vez.
Consiste em determinar uma rota de custo mínimo que visite todos os arcos uma única vez.
Consiste em determinar uma rota de custo mínimo que visite todos os nós uma única vez. 
Consiste em determinar uma rota de custo mínimo que passe por todos os nós pelo menos uma vez
Consiste em determinar uma rota de custo mínimo que passe por todos os arcos mais de uma vez.
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Ao aplicar qualquer método de problemas de roteamento de veículos, desejamos:
Sempre minimizar a distância percorrida.
Minimizar a distânciapercorrida, com o menor custo.
Minimizar a distância percorrida, com o maior custo.
Sempre chegar mais rápido.
Sempre gastar menos.
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Ao aplicar qualquer método de problemas de roteamento de veículos, desejamos:
Sempre minimizar a distância percorrida.
Minimizar a distância percorrida, com o menor custo.
Minimizar a distância percorrida, com o maior custo.
Sempre chegar mais rápido.
Sempre gastar menos.
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Uma empresa contrata uma consultoria para determinar uma rota de mínimo custo. Para isso ela passa algumas diretrizes exigidas pela direção: As rotas deverão ser cumpridas por um único veículo e que todos os caminhos (arcos) deverão ser percorridos pelo menos uma vez, sem limitar a capacidade do veículo. Que método pode ser utilizado para atender essas diretrizes.
Caixeiro viajante
Caixeiro viajante Capacitado
Carteiro chinês Capacitado
Múltiplos caixeiros viajantes
Carteiro Chinês
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Uma empresa contrata uma consultoria para determinar uma rota de mínimo custo. Para isso ela passa algumas diretrizes exigidas pela direção: As rotas deverão ser cumpridas por um único veículo e que todos os caminhos (arcos) deverão ser percorridos pelo menos uma vez, sem limitar a capacidade do veículo. Que método pode ser utilizado para atender essas diretrizes.
Caixeiro viajante
Caixeiro viajante Capacitado
Carteiro chinês Capacitado
Múltiplos caixeiros viajantes
Carteiro Chinês
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Uma empresa contrata uma consultoria para determinar uma rota de mínimo custo. Para isso ela passa algumas diretrizes exigidas pela direção: As rotas deverão ser cumpridas por um único veículo e que todos os caminhos (arcos) deverão ser percorridos pelo menos uma vez, com limitação para a capacidade do veículo. Que método pode ser utilizado para atender essas diretrizes.
Carteiro Chinês
Caixeiro viajante
Múltiplos caixeiros viajantes
Carteiro chinês Capacitado
Caixeiro viajante Capacitado
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Uma empresa contrata uma consultoria para determinar uma rota de mínimo custo. Para isso ela passa algumas diretrizes exigidas pela direção: As rotas deverão ser cumpridas por um único veículo e que todos os caminhos (arcos) deverão ser percorridos pelo menos uma vez, com limitação para a capacidade do veículo. Que método pode ser utilizado para atender essas diretrizes.
Carteiro Chinês
Caixeiro viajante
Múltiplos caixeiros viajantes
Carteiro chinês Capacitado
Caixeiro viajante Capacitado
AULA 6 – PROBLEMAS DE TRANSPORTES
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
BONS ESTUDOS E ATÉ A PRÓXIMA