Problema do menor caminho

Disponível somente no TrabalhosFeitos
  • Páginas : 12 (2756 palavras )
  • Download(s) : 0
  • Publicado : 14 de março de 2013
Ler documento completo
Amostra do texto
PROBLEMA DO MENOR CAMINHO
Consiste em encontrar o menor caminho entre uma origem e um destino, dentro de uma rede, minimizando o custo de travessia de um grafo, entre dois nós (ou vértices), custo este dado pela soma dos pesos de cada aresta percorrida.

Origem – Ponto de ônibus de partida
Destino – Ponto de ônibus de chegada
Rede – Itinerários disponíveis das diversas linhas de ônibus queabastecem determinada área geográfica.
Pesos de cada aresta – Distância, trânsito em determinado horário de pico, problemas viários.

1 - Determinada região da cidade possui diversas linhas de ônibus que a alimentam.

2 - O conjunto das linhas de ônibus de determinada região da cidade perfazem uma rede complexa de itinerários.

3 – Cada itinerário passa por vários pontos e conforme a ocasiãoleva a pontos diferentes ou iguais aos outros.

4 – Cada Ponto pode ser alimentado por várias linhas.

5 – Cada Itinerário pode possuir pontos em comum com outros.

6 – Os pontos estão localizados nos logradouros, cujos nomes são conhecidos pelos usuários das linhas e serão usados como locais de origem e destino.

Observação: Em um mesmo logradouro o itinerário de uma linha pode passarduas vezes, uma na ida outra na volta.

Descrição das formas de escolha das melhores rotas pelos passageiros:

O comportamento dos usuários do transporte coletivo na hora de fazer a escolha da rota pode ser classificado em dois tipos segundo a literatura existente: no tipo I o passageiro espera um ônibus de uma linha determinada, e no tipo II o passageiro espera o primeiro ônibus a aparecer noponto de parada, de um subconjunto de linhas consideradas atrativas.

No primeiro grupo estão aqueles que se baseiam no conceito de rota mínima, ou seja, o usuário do sistema de transporte coletivo utilizará a rota que minimize seu custo generalizado. O usuário já sabe qual é a linha que tem o menor custo generalizado para chegar até seu destino, e somente espera um ônibus daquela linha, o quecorresponderia a uma alocação do tipo “tudo ou nada”. No segundo grupo, estão aqueles modelos que se fundamentam na idéia de estratégia ótima, conceito formulado por Spiess (1983), que basicamente consiste em escolher um subconjunto de linhas de modo a minimizar o valor esperado do custo total de viagem. Bouzaïene-Ayari et al. (1995) indicam que o que determina uma estratégia de viagem são oconjunto de linhas atrativas escolhidas pelo passageiro em diferentes paradas e os pontos de desembarque daquelas linhas, para transbordo ou para caminhada até o destino. Knoppers (1995) ressalta que os transbordos reduzem a atratividade do transporte público como uma alternativa ao carro. A resistência ao transbordo pode ser expressa como o tempo necessário para o transbordo e uma probabilidade deperder a conexão. Conexões perdidas implicam em tempos de espera longos.

De Cea et al. (1990) salientam que se bem os modelos baseados no conceito de estratégia permitem obter uma maior dispersão de fluxos na rede de transporte público, a abordagem da alocação a rotas mínimas é mais eficiente em termos de tempo de cálculo computacional.

A existência de seções do caminho que podem ser atendidaspor mais de uma linha de
ônibus, origina várias opções para escolha dos passageiros, e esta escolha freqüentemente não é simples de ser modelada. Um passageiro, para viajar de um ponto a outro da rede, pode escolher de um conjunto de linhas disponíveis. Umas linhas dentro deste conjunto podem ser muito mais lentas que outras. Chriqui (1974) apresenta um método de determinação do subconjunto daslinhas atrativas. Ele parte da idéia de que o subconjunto de linhas é escolhido de modo a minimizar o valor esperado do custo total de viagem, incluindo tempo de espera e tempo em veículo.

A linha mais rápida está sempre nesse subconjunto. As outras linhas são ordenadas em forma crescente com respeito ao tempo de viagem em veículo, e somente são incluídas aquelas que diminuem o valor esperado...
tracking img