Aula4

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Tecnologia e novas mídias
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTE
Aula 04
AULA 02
Um problema de transporte é definido como transportar itens de centros de origens a centros de destinos, ou seja, disponibilizar o produto no local onde o mercado o exige. Do ponto de vista do mercado, é inútil que o fornecedor disponha de um bom produto que não é encontrado pelo cliente no momento em que deseja.
Problemas de transporte
© Teriyaki999 | Dreamstime.com - © Teriyaki999 | Dreamstime.com
2
ID 33253750
ID 33099563 
o transporte representa o elemento logístico mais custoso e consequentemente, o candidato preponderante para otimização, uma vez que os custos com transporte por parte das empresas correspondem a 6,9% do PIB. De acordo com Andrade (2004), problemas de transporte em empresas são resolvidos por meio de modelos de pesquisa operacional de fácil resolução.
2
© Teriyaki999 | Dreamstime.com
São dados conhecidos do problema de transporte:
 O custo de transporte de cada item;
 As quantidades dos itens disponíveis em cada centro;
 E as demandas de cada consumidor.
3
Problemas de transporte
o transporte representa o elemento logístico mais custoso e consequentemente, o candidato preponderante para otimização, uma vez que os custos com transporte por parte das empresas correspondem a 6,9% do PIB. De acordo com Andrade (2004), problemas de transporte em empresas são resolvidos por meio de modelos de pesquisa operacional de fácil resolução.
3
© Teriyaki999 | Dreamstime.com
O transporte deve ser efetuado de modo que as limitações de oferta em cada centro seja respeitada e a demanda de cada mercado atendida e o custo total de transporte seja mínimo.
4
Problemas de transporte
o transporte representa o elemento logístico mais custoso e consequentemente, o candidato preponderante para otimização, uma vez que os custos com transporte por parte das empresas correspondem a 6,9% do PIB. De acordo com Andrade (2004), problemas de transporte em empresas são resolvidos por meio de modelos de pesquisa operacional de fácil resolução.
4
Uma indústria de bebidas possui: Dois centros de produção (Queimados e Resende): vamos nomear total de centros de produção m=2. Três mercados consumidores São Paulo, Belo Horizonte e Rio de Janeiro assim, total de mercados consumidores n =3. 
Problema clássico de transporte
© Teriyaki999 | Dreamstime.com
5
o transporte representa o elemento logístico mais custoso e consequentemente, o candidato preponderante para otimização, uma vez que os custos com transporte por parte das empresas correspondem a 6,9% do PIB. De acordo com Andrade (2004), problemas de transporte em empresas são resolvidos por meio de modelos de pesquisa operacional de fácil resolução.
5
Sejam: xij a quantidade do produto cij o custo unitário do transporte de uma unidade de produto do centro de produção i ao mercado consumidor j. Como atender a demanda de todos os mercados consumidores, minimizando o custo de transporte? Os custos são dados na tabela abaixo: 
Problema clássico de transporte
6
Centro de Suprimento
São Paulo (1)
Belo Horizonte (2)
Rio de Janeiro (3)
Suprimento Dispoinível ai
Queimados (1)
4
2
5
800
Resende (2)
11
7
4
1000
Demanda dos Mercados (bj)
500
400
900
1800
o transporte representa o elemento logístico mais custoso e consequentemente, o candidato preponderante para otimização, uma vez que os custos com transporte por parte das empresas correspondem a 6,9% do PIB. De acordo com Andrade (2004), problemas de transporte em empresas são resolvidos por meio de modelos de pesquisa operacional de fácil resolução.
6
Problema clássico de transporte - representação
7
7
Modelagem do exemplo
Min
Sujeito a:
8
Modelo clássico de transportes genérico
Minimizar Z =
Sujeito a: 
9
Para que o problema tenha solução:
10
Modelo clássico de transportes genérico
Caso a demanda seja maior que o fornecimento é necessário acrescentar uma variável auxiliar (estoque, atraso, terceirização). Por outro lado, caso o fornecimento seja maior que a demanda devemos acrescentar um destino auxiliar (estoque, por exemplo)
ATENÇÃO
Em caso de necessidade de criação de variáveis de atraso ou estoque, é necessário considerar o custo de manter estoque e o custo de perda de vendas ou de entregar depois da data (combinada), que nem sempre é possível mensurar.
10
11
Vídeo
https://www.youtube.com/watch?v=_yc7puzMJjM
VRP (fácil) - Roteamento de Veículos - Modelagem PARTE 1
VRP (fácil) - Roteamento de Veículos - Modelagem PARTE 2
https://www.youtube.com/watch?v=U_9i7-TsNso&t=130s
11
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. 
Problemas de Roteamento de Veículos (PRV)
© Salavan | Dreamstime.com
12
ID 14065395
12
Problemas de Roteamento de Veículos (PRV)
© Salavan | Dreamstime.com
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.
13
ID 14065395
13
Problema de cobertura de arcos
Problema
Carteiro chinês
Carteiro chinês capacitado
Descrição
Consiste em determinar uma rota de custo mínimo que passe por todos os arcos pelo menos uma vez. É um problema de cobertura de arcos.
É uma generalização do carteiro chinês, onde há restriçãodecapacidade dos veículos.
Problemas de Roteamento de Veículos (PRV)
14
Problema de cobertura de nós
Problema
Descrição
Caixeiro viajante
Consiste em determinar uma rota de custo mínimo que visite todos os nós uma única vez. Pode ser classificado como um problema de cobertura de nós.
Múltiplos caixeiros viajantes
É uma generalização do caixeiro viajante na qual se considera mais de um caixeiro viajante, que iniciam e terminam suas rotas em um local comum. Não há restrições sobre o número de nós que cada um pode visitar, exceto que cada caixeiro visite no mínimo um nó.
Roteirização com um único depósito e vários veículos
É o problema clássico de roteirização de veículos (PRV). É uma generalização do problema do caixeiro viajante, onde a frota de veículos parte de um depósito central e atende todos os nós, com o objetivo de minimizar a distância total percorrida pela frota.
Problemas de Roteamento de Veículos (PRV)
15
Problema
Descrição
Roteirização com vários depósitos e vários veículos
É uma generalização do problema anterior, com múltiplos depósitos ao invés de apenas um. Neste problema, cada veículo é alocado a um único depósito, originando e terminando a viajem no mesmo local.
Roteirização com depósito único, vários veículos e demanda estocástica
É idêntico ao PRV, exceto pela demanda não ser conhecida com certeza, podendo ser originada de uma distribuição de probabilidades específica.
Problemas de Roteamento de Veículos (PRV)
Problema de cobertura de nós
16
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.
Problema do caixeiro viajante
© Sergey Khakimullin | Dreamstime.com
17
https://www.youtube.com/watch?v=_vKMyRj855A
ID 21190344 
17
Problema do caixeiro viajante
© Sergey Khakimullin | Dreamstime.com
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.
18
ID 21190344 
18
Problema do caixeiro viajante
© Sergey Khakimullin | Dreamstime.com
O problema do Caixeiro Viajante é um problema de otimização associado ao da determinação dos caminhos hamiltonianos em um grafo qualquer.
Nesta disciplina, apresentaremos três métodos de resolução: 
vértice adjacente mais próximo, da inserção com menor encargo e da inserção com maior afastamento.
19
ID 21190344 
19
Método do Vértice Adjacente mais Próximo
 
Este método baseia-se nos seguintes passos para identificar a solução aproximada seguindo seguintes passos:
Seleciona-se arbitrariamente um nó Ni para o início do ciclo. 
Dentre os nós não selecionados, seleciona-se o nó Nk que está a menor distância de Ni, ficando a cadeia Ni,Nk. Repetem-se esses passos até que todos os vértices possam ser utilizados.
Problema do caixeiro viajante
20
20
O método da Inserção com menor encargo baseia-se nos seguintes passos para identificar a solução aproximada:
Seleciona-se um subciclo {i,j,i} associado a Minimizar {Cij + Cji} Obs.: se houver empate deve-se escolher arbitrariamente um subciclo.
No subciclo corrente, calcular para cada ligação do tipo (u,v), a inserção do nó "k" (não selecionado) a que corresponda ao aumento mínimo da distância dado por Min {Cuk + Ckv - Cuv}. Esse processo deve ser repetido até que todos os nós do grafo sejam selecionados. 
Problema do caixeiro viajante
21
21
Método da Inserção com maior afastamento.
Este método baseia-se nos seguintes passos para identificar a solução aproximada:
Seleciona-se o subciclo "i,j,i" associado a Max {Cij + Cji} (se houver empate deve-se escolher arbitrariamente um subciclo).
Seleciona-se um nó "k" dos não inseridos de acordo com os subpassos a seguir:
Avalia-se a menor distância entre os nós já pertencentes ao subciclo atual, ao nó "k" a inserir.
Escolhe-se para inserção o nó "k" onde seja maior à distância registrada (máximo dos mínimos).
Problema do caixeiro viajante
22
22
Método da Inserção com maior afastamento.
 No subciclo atual, calcular para cada ligação do tipo (u,v) a inserção do nó "k", selecionado anteriormente, a que corresponda o aumento mínimo de distância dado por Min {Cuk+Ckv-Cuv}.
 Selecionar novo nó até que todos estejam na solução inicial.
Problema do caixeiro viajante
23
23
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
© Sergey Khakimullin | Dreamstime.com
24
O que é necessário para que um problema de transporte tenha solução factível? O que temos que levar em conta?
Atividade
© Teriyaki999 | Dreamstime.com - © Teriyaki999 | Dreamstime.com
25
ID 33253750
ID 33099563 
o transporte representa o elemento logístico mais custoso e consequentemente, o candidato preponderante para otimização, uma vez que os custos com transporte por parte das empresas correspondem a 6,9% do PIB. De acordo com Andrade (2004), problemas de transporte em empresas são resolvidos por meio de modelos de pesquisa operacional de fácil resolução.
25
Equilíbrio demanda x oferta
Estoque
Ruptura
Atraso
Atividade
© Teriyaki999 | Dreamstime.com - © Teriyaki999 | Dreamstime.com
26
ID 33253750
ID 33099563 
26
Tecnologia e novas mídias
VAMOS AOS PRÓXIMOS PASSOS?
AVANCE PARA FINALIZAR
A APRESENTAÇÃO.
AULA 03