07-Transporte e transbordo



Otimização em transporte

O Problema do Caixeiro Viajante (TSP – Travelling Salesman Problem) é um problema complexo de otimização combinatória. Dada uma lista de cidades e suas distancias entre si, a tarefa é encontrar a menor rota que passe por cada cidade exatamente uma vez e retorne à cidade de origem. O problema foi formulado pela primeira vez em 1930 e é um dos problemas mais intensivamente estudado em otimização. Embora seja na classe dos problemas computacionalmente difícil de ser resolvido, um número grande de heurísticas e métodos exatos foram desenvolvidos de forma que instâncias de dezenas de milhares de cidades podem ser resolvidas. O TSP possui muitas aplicações em sua mais pura formulação, como em planejamento e logística e manufatura de microchip. Levemente modificado, o problema aparece na área de seqüenciamento de DNA. Na teoria de complexidade computacional esse problema está na classe dos problemas não polinomiais (NP). Assim, no pior caso, o tempo do algoritmo para resolvê-lo cresce exponencialmente com o número de cidades.


Problema do caminho mínimo: Um dos problemas encontrados na teoria de grafos é o problema de caminho mínimo, que determina a menor distância entre dois nós escolhidos em um grafo.





Exercício: 

1) Em uma parceria com a IBM, empresa SIX pretende fazer uma fábrica de chips em Contagem – MG. Nessa mesma região temos empresas de manufatura de computadores, de manufatura de placas de circuito impresso, de impressoras e de terminais de cartão de crédito, configurando um sistema integrado de tecnologia. O planejamento estratégico da cadeia de suprimentos integrada estuda como será o transporte de lotes desses componentes para centros de distribuição e para centros consumidores.


Sejam 3 centros de produção de chips que transportam lotes do produto a 2 centros de distribuição, que por sua vez possui caminhões que entregam esses lotes a 4 indústrias de eletroeletrônicos. O plano diário de produção das indústrias determina a quantidade total de lotes a ser transportada dos centros de distribuição pelos caminhões, no entanto, o estoque diário dos 3 centros de produção é limitado.


As tabelas abaixo apresentam os dados (fictícios, claro) de custos unitários de transporte dos lotes de chips das fábricas aos centros de distribuição e destes às indústrias de eletroeletrônicos, a capacidade diária de oferta de produtos por parte das fábricas de chips, as demandas diárias das indústrias de eletroeletrônicos e as capacidades logísticas inbound e outbound dos centros de distribuição.


Formule um problema de programação linear, programe em MathProg (GLPK) e encontre a estratégia logística de custo mínimo para esse sistema.


 

 

Custo Unitário de Transporte (R$/km)

Fábricas de Chips

Oferta Diária (lotes)

CD1

CD2

1

697

27

37

2

421

15

25

3

612

35

19


 

 

Custo Unitário de Transporte (R$/km)

Indústrias de Eletroeletrônicos

Demanda Diária (lotes)

CD1

CD2

1

433

30

13

2

215

12

40

3

782

27

15

4

300

37

25



CD1

CD2

Capacidade Inbound (lotes)

1000

750

Capacidade Outbound (lotes)

1000

1000


FONTE:

Arenales, M. Armentano, V. Morabito, R. Yanasse, H. Pesquisa Operacional para cursos de engenharia, Ed. Campus, 2007

Wikipedia: http://en.wikipedia.org/wiki/Travelling_salesman_problem