segunda-feira, maio 08, 2006

 

Caminho mais curto


Suponha-se que para fazer uma entrega de mercadoria se pretende determinar a rota de menor custo entre um centro de distribuição (O) e um hipermercado (T) na rede da Figura 1. Os valores dos arcos tanto podem representar distâncias, como tempos de deslocação e quaisquer deles são usados como medida indirecta do custo de fazer a entrega. Todas as vias são de dois sentidos.

Figura 1. Rede de estradas.
Fonte: Hillier e Lieberman (2005)

Trata-se, então, de determinar o caminho mais curto de uma origem (O) a um destino (T). Este problema pode ser resolvido aplicando vários algoritmos e programas. Um desses algoritmos é descrito por Hillier e Lieberman (2005) e aplicado na resolução do problema da Figura 1.

O resultado são duas soluções óptimas, ambas com o valor de 13:

O → A → B → E → D → T

ou

O → A → B → D → T

HILLIER, Frederick S.; Lieberman, Gerald J. - Introduction to Operations Research, 8.ª ed. Nova Iorque, McGraw-Hill, 2005.

Comments: Enviar um comentário

Links to this post:

Criar uma hiperligação



<< Home

This page is powered by Blogger. Isn't yours?