BRPI0614492A2 - método e dispositivo de navegação para planejar rota dependente no tempo - Google Patents

Abstract

MéTODO E DISPOSITIVO DE NAVEGAçãO PARA PLANEJAR ROTA DEPENDENTE NO TEMPO A presente invenção combina a cobertura geográfica possível com custos de segmento de rota pré-definidos fixos (por exemplo, o limite de velocidade legal) com, sempre que possível, custos dependentes no tempo maiores. Um usuário, por exemplo, de um dispositivo de navegação portátil, pode então continuar a planejar a rota como antes para virtualmente qualquer destino em um país coberto pelo banco de dados do mapa armazenado, mas, sempre que possível, pode tam-bém usar os dados de tráfego com os custos dependentes no tempo, tal que o efeito de congestionamento com qualquer previsibilidade de tempo possa ser precisamente recebido levando em conta como um processo base automático. Ele deixa o usuário para simplesmente continuar a dirigir, seguindo o guia oferecido pelo dispositivo de navegação, sem a necessidade de se preocupar com o congestionamento que existe agora, e se ele terá impacto em sua viagem.

Description

"MÉTODO E DISPOSITIVO DE NAVEGAÇÃO PARA PLANEJARROTA DEPENDENTE NO TEMPO"

Campo da Invenção

Esta invenção refere-se a um método de planejamen-to de uma rota até um destino; ele encontra aplicação emsistemas implementados por computador que habilitam uma rotade direção ótima a ser planejada.

Fundamentos da Invenção

A viagem viária é uma parte principal da vida co-tidiana para negócios e outras organizações, e para indiví-duos privados. Os custos de atrasos no tráfego podem sermuito grandes. 0 custo puramente financeiro tem sido estima-do em bilhões de libras somente no Reino Unido [CFIT]. Dadosestes custos, sistemas que podem auxiliar os motoristas aotimizarem suas viagens, por exemplo, selecionando a melhorrota e evitando atrasos por congestionamento, são de grandevalia. De fato, um arranjo diverso de sistemas de informaçãoao motorista tem crescido:

- Relatório de tráfego via transmissão por rádiosão há muito estabelecidos, os quais agregam dados a partirde um número de fontes (polícia, de olho no céu, e mais re-centemente chamadas de telefone móvel a partir de motoristaspresos em congestionamento) para fornecer aviso subjetivo deincidentes e atrasos. Os rádios RDS tornam estes sistemasmais eficazes cortando automaticamente de programas de rádionormais para relatórios de tráfego.

- Sistemas estáticos de planejamento de rotas sãofornecidos na rede através das principais organizações demotoristas (AA, RAC). Esses sistemas permitem a um motoristainserir os pontos de uma viagem e fornecem a ele uma rota einstruções de direção para esta rota.

- Sistemas de navegação pessoal (PNS) em veículoscom base em GPS têm sido introduzidos. Estes sistemas usam aposição do veículo e uma rota calculada usando uma função decusto estático tradicional para emitir instruções para guiaro motorista para seu destino. Tais sistemas têm começado aincorporar informação de tráfego em seus serviços, mas essanão está integrada na seleção de rota; o usuário pode obser-var atrasos onde eles afetam a rota selecionada, e manual-mente guia o sistema para re-planejar uma rota evitando asseções atrasadas na estrada se eles consideram isso necessá-rio.

- Sistemas de monitoramento de tráfego em temporeal, baseados em várias tecnologias (por exemplo, telefonesmóveis, câmeras fixas, rastreamento de frota por GPS) estãosendo usados para identificar os atrasos no tráfego e parasuprir a informação em sistemas de notificação.

À medida que o congestionamento de estradas aumen-ta, sistemas de fornecimento de planejamento de rotas tor-nam-se mais susceptíveis a erros. Um motorista não estarásatisfeito em perguntar qual a rota mais rápida de A até B,e então se encontra preso em um congestionamento por 50 mi-nutos. Similarmente, eles suspeitariam de um sistema que osorienta ao longo de uma estrada A movimentada onde eles via-jam em comboio atrás dos HGVs a 80,46 Km/h (50 mph), enquan-to eles poderiam estar viajando muito mais rápido em uma ro-ta da estrada ligeiramente mais longa.

Técnicas conhecidas para melhorar o planejamentode rotas exigem a determinação de velocidades individuais emestrada e seções de estrada que mais verdadeiramente refle-tem a velocidade na qual o tráfego pode esperar para viajarpor elas. Esta determinação é geralmente estática, ou seja,a uma seção da estrada é determinada um custo fixo depois dolevantamento e análise, e esse custo é sempre mais tarde u-sado como o custo da seção da estrada no algoritmo de traça-do de rota. O custo pode ser revisto, mas isso é tão caroquanto a determinação de custo original. Portanto, algorit-mos de planejamento de rotas em dispositivos de navegaçãotrabalham elaboram tempos de trânsito de segmento de rotausando os tipos de estrada definidos no banco de dados domapa armazenado no dispositivo; uma hipótese pode ser feitaa fim de que os veículos em média viajem no limite de velo-cidade legal para aquele tipo de estrada ou em alguma velo-cidade consistente com a classe da estrada. Estes bancos dedados de mapa, de companhias como TeleAtlas e NavTech, são oresultado de levantamento de estradas altamente dispendiosoe completo, geralmente por todo o país. Então a força dessaaproximação é que tempos de trânsito podem ser estimados pa-ra cada estrada no banco de dados do mapa. Mas sua fraquezareside no fato de que a hipótese de viajem no limite de ve-locidade legal claramente falha para áreas congestionadasporque os dispositivos não têm informação de tráfego confiá-vel. A aproximação geral para calcular uma rota de customais baixo (por exemplo, mais rápida) pode ser pensada comoabrangente, mas imprecisa se o congestionamento ocorre.

Os dispositivos de navegação portáteis por satéli-te GPS com algoritmos de planejamento rotas sofisticados,tal como o GO™ da TomTom International BV têm se tornadofreqüentes nos últimos anos e são usados por um grande núme-ro de motoristas normais: os benefícios da integração dosdados de tráfego efetivos nestes sistemas são consideráveis.

Sistemas de monitoramento de tráfego da técnicaanterior têm focado em fornecer dados de fluxo de tráfegotal que o congestionamento possa ser evitado. Porém estessistemas têm sido limitados principalmente às estradas prin-cipais por causa dos custos de infra-estrutura de desenvol-vimento do equipamento de monitoramento (por exemplo, senso-res cíclicos fixados em estradas; sistemas baseados em câme-ras, tal como sistemas de reconhecimento do número da placa)ou porque eles contam com sistemas de veículos instáveis nosquais uma proporção relativamente pequena de todos os veícu-los (equipados com hardware dedicado) é rastreada, tipica-mente aqueles em movimento nas estradas principais e não nasáreas urbanas. Para companhias de transporte comercial, essalimitação pode ser aceitável porque seus caminhões usamprincipalmente as estradas principais de qualquer maneira.

Geralmente, os serviços de monitoramento de tráfe-go não são de todo abrangentes, mas úteis quando o congesti-onamento ocorre em uma estrada que é monitorada. Porém a u-tilidade é limitada por duas razões. Primeiro, um usuário émeramente informado do congestionamento; ele está então ti-picamente abaixo do usuário para solicitar uma ação apropri-ada, tal como para planejar uma nova rota, levando o conges-tionamento em conta. Segundo, o congestionamento pode ter sedissipado através do tempo tal que o veiculo chega nos lo-cais que estão indicados como estando congestionados só ago-ra. Onde o congestionamento é previsível (isto é, ele seguealgum tipo de regularidade ou previsibilidade no tempo, talcomo a hora de rush matutina, ou o congestionamento em tornode um estádio quando um jogo principal está sendo realizado,ou um acidente que fecha uma faixa da estrada principal) en-tão é possível estimar o congestionamento possível que o ve-ículo experimentará uma vez que ele alcança a estrada queestá atualmente congestionada. O fluxo de tráfego dependenteno tempo ou os dados de tempo do trânsito (por exemplo, às8:00 em cada manhã de segunda-feira, o tempo de trânsito pa-ra um segmento de rota particular é de 20 minutos; ele caipara 15 minutos às 13:00 e para 5 minutos às 23:00, etc.)pode abordar isso. Referência pode ser feita para US 6356836e depois WO 2004/021306. Mas até agora, como notado acima,este tipo de dados tem tipicamente somente sido aplicado pa-ra sistemas de monitoramento de tráfego para fornecer dadosa uma proporção relativamente pequena de estradas em um pa-ís.

O efeito geral é que o usuário pode usar algorit-mos de planejamento de rota com custos de segmento de rotadependente no tempo, porém está limitado a planejamento derota para a proporção relativamente pequena de estradas queé coberta pelo sistema de monitoramento de tráfego. A preci-são é fornecida nos custos de cobertura geográfica. Alterna-tivamente, um usuário pode usar algoritmos de planejamentode rota baseados em custos de segmento de rota pré-definidosfixos (por exemplo, limite de velocidade legal). A coberturageográfica está disponível, mas no custo de precisão.

Sumário da Invenção

A invenção envolve um método de planejar uma rotaa um destino. Ele compreende as seguintes etapas:

(a) usar um banco de dados do mapa que define asestradas em termos dos segmentos de rota e inclui um custoindependente no tempo, pré-definido, fixo associado com cadasegmento de rota diferente no banco de dados do mapa;

(b) usar software que habilita uma rota a ser pla-nejada a um destino e que calcula um custo estimado de al-cançar esse destino usando um ou mais segmentos de rota;

onde usar.o software envolve planejar uma rota u-sando automaticamente uma combinação de (i) custos dependen-tes no tempo para um ou mais segmentos de rota na rota, talque um custo é aplicado para cruzar um segmento de rota par-ticular que é apropriado para o tempo específico quando eleé planejado para ser cruzado e (ii) os custos independentesno tempo, pré-definidos e fixos para aqueles segmentos derota na rota que não são definidos pelos custos dependentesno tempo.

A presente invenção combina a cobertura geográficapossível com custos de segmento de rota pré-definidos, fixos(por exemplo, limite de velocidade legal), sempre que possí-vel, com custos dependentes no tempo aumentados. Um usuário,por exemplo, de um dispositivo de navegação portátil, podeentão continuar o planejamento de rota como antes para vir-tualmente qualquer destino em um pais coberto pelo banco dedados do mapa, porém sempre que possível, pode também usardados de tráfeqo com custos dependentes no tempo, tal que oefeito de conqestionamento com qualquer previsibilidade detempo pode ser precisamente levado em consideração como umprocesso base automático. Ele deixa o usuário para simples-mente continuar a dirigir, seguindo o guia oferecido pelodispositivo de navegação, sem a necessidade de estar preocu-pado com o congestionamento que existe agora, e se ele teráimpacto na sua jornada.

Os detalhes adicionais de implementação incluem oseguinte:

O custo dependente no tempo associado com um seg-mento de rota particular refere-se à velocidade do veículoou tempos de trânsito de segmento de rota que foram medidosou deduzidos e não são pré-definidos e fixos. A medição podetomar uma variedade de formas e será descrita depois. Poroutro lado, o custo independente no tempo, pré-definido efixo associado com um segmento de rota particular não foimedido ou deduzido a partir do fluxo de tráfego ou movimentodo veículo real, mas, ao invés, é uma função de (i) o tipode estrada associado com esse segmento de rota ou (ii) o li-mite de velocidade aplicável a esse segmento de rota. Oscustos independentes no tempo são usados em combinação comos custos dependentes no tempo, para aqueles segmentos derota que são definidos por ambos os custos dependentes e in-dependentes no tempo. A combinação pode tomar muitas formasdiferentes: a essência, entretanto, é que existe ainda algumvalor nos dados independentes no tempo no estabelecimento docusto mais preciso para um segmento de rota, mesmo que osdados dependentes no tempo possam estar disponíveis. Por e-xemplo, a qualidade dos dados dependentes no tempo pode sermuito baixa para ser inteiramente confiável; combinando es-ses dados com os dados independentes no tempo fixos com opeso relativo adequado pode-se fornecer a estimativa maisrazoável. Provavelmente, os dados dependentes no tempo podemnão estar disponíveis para um segmento de rota específico,porém podem ser conhecidos por segmentos de rota próximos ousimilares e, portanto, deduzir uma dependência no tempo podeser possível: mas, como antes, algum peso com os dados inde-pendentes no tempo fixos pode ser desejado.

Geralmente, o custo associado com uma rota particular será o tempo estimado obtido para alcançar o destino,desde que a maior parte dos usuários está mais interessada.Porém qualquer outro custo também pode ser usado. O custo équalquer custo percebido ou real que o motorista ou algumaoutra pessoa pode escolher para solicitar ou fornecer que serefere aos segmentos de rota. Por exemplo, o custo associadocom uma rota particular poderia ser o uso de combustível as-sociado com essa rota. Ou o custo financeiro creditável as-sociado com essa rota - especialmente útil onde o pedágioestá no lugar ou existem outras formas de pagamento direto,tal como zonas de congestionamento. O custo associado comuma rota particular pode ser de um tipo que um usuário finalpode selecionar a partir de uma lista de opções exibida emum dispositivo de computação. Nos exemplos acima, a lista deopções incluiria uma ou mais dos itens seguintes: tempo detrânsito para a rota, custo financeiro para a rota, uso decombustível na rota, tráfego estacionário. Em todos casos, osoftware calcula o custo da rota como parte de um algoritmode minimização de custo.

Uma característica é que um custo estimado de al-cançar um destino para um motorista particular de um veículoé uma função de um perfil de condução associado com esse mo-torista. Portanto, o estilo de condução (por exemplo, rápi-da/agressiva/esportiva/; normal; lenta/cautelosa) pode terum impacto significativo nos custos (especialmente nos tem-pos de trânsito e no uso de combustível) . 0 método habilitadiferentes perfis a serem selecionados (por exemplo, pelopróprio motorista, manualmente a partir de uma lista de op-ções exibida em um dispositivo de navegação; ou automatica-mente por esse dispositivo monitorando a condução atual);estes são então usados para selecionar um conjunto apropria-do de custos ou fatores de peso a serem aplicados aos cus-tos. Por exemplo, um motorista em modo esporte pode ter tem-pos de trânsito reduzidos em 5%, a não ser em áreas muitocongestionadas.

Como notado acima, existem muitas formas de medi- ção do fluxo real de tráfego de veículos ou dados de circu-lação. Por exemplo, isso pode ser feito usando o rastreiopor GPS (tipicamente uma gravação dos dados da posição GPSno tempo regular ou nos intervalos de distância) . Os ras-treios por GPS podem ser armazenados por um dispositivo denavegação baseado em GPS em um veículo viajando ao longo dossegmentos de rota. Os rastreios por GPS podem ser enviadospor uma rede sem fio celular diretamente pelo dispositivo aum sistema de monitoramento de tráfego, ou enviados pelodispositivo a um sistema de monitoramento de tráfego. Osrastreios por GPS poderiam ser enviados por um telefone mó-vel conectado ao dispositivo por uma rede de computadorescom.dispositivo de tecnologia bluetooth ("piconet") ou outraforma de conexão, ou enviados pelo dispositivo quando eleestá acoplado com um PC a um sistema de monitoramento detráfego.

A medição dos fluxos reais de tráfego de veículosou circulação também poderia ser alcançada pela medição dalocalização de telefones móveis; isso pode ser feito monito-rando passivamente tráfego de sinalização a partir dos tele-fones móveis às estações base. A medição dos fluxos reais detráfego de veículos ou circulação pode também ser alcançadausando sensores cíclicos em estradas, ou usando sistemas ba-seados em câmeras (por exemplo, sistemas de reconhecimentode número de placa) Oou usando veículos equipados com rádiosinalizador.

Os custos dependentes no tempo podem ser dinamicamente atualizáveis: portanto, à medida que as condições detráfego mudam, essas mudanças podem ser detectadas pelo sis-tema de monitoramento de tráfego e os custos mudados usadospelo software de planejamento de rota. Isso também cobre asituação onde um acidente ou outro evento não previsível o-corre; a atualização dinâmica em tempo real é então muitodesejável.

Os custos dependentes no tempo associados com umsegmento de rota podem ser uma função de um ou mais de mui-tos diferentes parâmetros relacionados com o tempo. Por e-xemplo, eles podem ser uma função de:

- a hora do dia ou da noite.

- os dias da semana.

- feriados públicos.

- feriados escolares.

- Mais geralmente, qualquer evento que provavel-mente terá impacto nos custos de segmento de rota; ou qual-quer situação futura sobre a qual é possível inferir um im-pacto provavelmente no custo de segmento de rota.

Usando o método acima, uma rota pode ser planejadaa um destino, ou dois ou mais destinos, e o tempo de chegadaem cada destino será significativamente mais preciso que asaproximações baseadas no limite de velocidade atual.

Outro aspecto da invenção é um dispositivo de na-vegação programado com:

(a) um banco de dados do mapa que define as estra-das em termos dos segmentos de rota e inclui um custo inde-pendente no tempo pré-definido, fixo associado com cada seg-mento de rota diferente no banco de dados do mapa; e

(b) software que habilita uma rota a ser planejadaa um destino e que calcula um custo estimado de alcançar es-se destino usando um ou mais segmentos de rota;

Onde o dispositivo pode planejar uma rota usandoautomaticamente uma combinação de (i) custos dependentes notempo para um ou mais segmentos de rota na rota, tal que umcusto é aplicado para cruzar um segmento de rota particularque é apropriado para o tempo especifico quando ele é plane-jado a ser cruzado e (ii) os custos independentes no tempo,pré-definidos, fixos para aqueles segmentos de rota na rotaque não são definidos pelos custos dependentes no tempo.

É o dispositivo que calcula a rota de menor custo ao destino; por exemplo, a rota mais rápida, a rota com me-nor gasto de combustível, a rota com as menores despesas fi-nanceiras, etc. Os custos dependentes no tempo podem ser em-purrados para o dispositivo ou enviados ao dispositivo emsolicitação pelo dispositivo. Para a eficiência de largurade banda, os custos dependentes no tempo recebidos pelo dis-positivo podem ser restritos à classe de tipos de estrada.

0 dispositivo pode incluir custos dependentes notempo em uma mesma memória que inclui o banco de dados domapa. Portanto, uma aproximação é para distribuir cartões dememória ou outros formatos físicos de memória não somentecom o banco de dados completo, mas também com os custos de-pendentes no tempo associados com muitos dos segmentos derota no banco de dados. Alternativamente, os custos depen-dentes no tempo poderiam estar disponíveis ao dispositivoquando ele se acopla com um PC conectado à internet que podedescarregar os dados de um servidor, ou pelo ar, e entãoarmazenar na memória (tipicamente um disco rígido ou memóriaem estado sólido) do próprio dispositivo.

Uma outra aproximação é para o servidor remoto en-viar ao dispositivo um custo associado com circulação de uminício até o destino; o servidor recebe o conteúdo de tráfe-go em tempo real que o habilita a atualizar os dados de trá-fego com dados recentes. Quando o dispositivo recebe dadosem tempo real ou dados de tráfego recentes ou informação decongestionamento a partir de um servidor, ele usa automati-camente esses dados ou informações para recalcular a rotaótima.

É também possível para:

(a) ambos o dispositivo e o servidor usarem cadaum separadamente os custos dependentes no tempo;

(b) para o dispositivo informar ao servidor dosmenores custos de rota que ele calculou;

(c) para o servidor enviar uma notificação ao dis-positivo se a rota de menor custo que ele calculou é dife-rente da rota que o dispositivo calculou.

Δ largura de banda pode ser economizada se o ser-vidor enviar uma notificação ao dispositivo que define uni-camente a diferença entre as rotas.

Outra aproximação é:

(a) ambos o dispositivo e o servidor usam cada umseparadamente os custos dependentes no tempo;

(b) o dispositivo identifica os segmentos de es-trada para os quais dados recentes são valiosos e solicitaos dados recentes do servidor.

Em qualquer evento, o dispositivo pode sugerir umtempo de início ótimo para uma jornada, se o usuário definirquando ele deseja chegar.

O próprio dispositivo pode ser um dispositivo denavegação baseado em GPS. Ele pode ser um telefone móvel comum sistema de procura de localização, tal com GPS. Ele podeser um dispositivo de navegação portátil, tal como um GO doTomTom, ou ele pode estar permanentemente embutido em um ve-iculo a motor.

Outros aspectos são:

Um sistema de monitoramento de tráfego que mede avelocidade do tráfego ou os dados de tempo de trânsito comouma função do tempo e gera um banco de dados de históricodas velocidades do tráfego dependentes no tempo ou tempos detrânsito para segmentos de estradas; e compartilha no mínimoalgum deste banco de dados ou de seus conteúdos para habili-tar o método definido acima a ser executado.

Um mapa digital de uma região, mapa que inclui da-dos que definem segmentos de estradas, junto com dados quedefinem os custos dependentes no tempo associados no mínimocom alguns dos segmentos de estrada, adaptado para habilitaro método definido acima a ser executado quando usado pelosoftware de planejamento de rota.

Um veículo a motor incluindo um sistema de navega-ção embutido operável para planejar uma rota usando o métododefinido acima.

Breve Descrição dos Desenhos

A Figura 1 é uma representação esquemática de umsistema de planejamento de rota de acordo com uma modalidadeda presente invenção;

A Figura 2 é um mapa que ilustra o uso de uma fun-ção de custo dinâmica para selecionar uma rota otimizada pa-ra uma jornada;

A Figura 3 é uma representação esquemática da ope-ração de um sistema de rota dinâmico distribuído.

Descrição Detalhada da Invenção

Existem vários aparelhos para propor uma rota emuma rede de estradas a um motorista que deseja fazer uma vi-agem específica. A viagem pode ser simples especificada en-tre dois pontos, ou pode ser uma viagem mais complexa envol-vendo múltiplas localidades que podem ser visitadas, não ne-cessariamente em uma ordem particular. Esse é o tipo de via-gem que o motorista entregador faria. Não importa a forma daviagem, o objetivo é minimizar um custo associado com a via-gem. Os custo mais óbvio é o tempo de duração, porém qual-quer outro custo pode ser relevante, por exemplo, o combus-tível usado durante a viagem. Os usuários podem restringir aescolha das estradas usadas, por exemplo, algumas classes deveículos comerciais são proibidas de usar todas as rotas,exceto as rotas de caminhão quando fora das conurbações. Es-ses aparelhos são usualmente mais incorporados como algorit-mos encapsulados em sistemas computacionais que determinamum custo a uma seção de rota, e que aplicam um algoritmo deminimização de custo [Dijkstra] ao gráfico das junções e ro-tas. No caso simples, o custo é fixo para cada rota, e é otempo de viagem ao longo da rota quando viajando na veloci-dade normal da rota (tipicamente essa figura é o limite develocidade para a estrada em questão, ou um valor simples-mente derivado do limite de velocidade). Esse pode ser cha-mado de uma função de custo estática.Isso não leva em consideração as variações na ve-locidade potencial ao longo da rota, tal como aquelas causa-das pelos períodos de pico e de não pico. Nenhuma das duasleva em consideração o fato de que o limite de velocidade naestrada é um indicador muito pobre da velocidade utilizávelsegura de uma estrada.

Para resolver o problema da variação no custo deuma estrada ao longo do tempo, o algoritmo pode ser modifi-cado para anexar um custo a uma rota que é dependente medi-ante a hora do dia. Então a entrada para o algoritmo de rotainclui um tempo para o qual a melhor rota é exigida, e ocusto apropriado no tempo relevante é aplicado a cada seçãode rota. O problema com tais sistemas é o fornecimento deuma boa função de custo para uma rota; um pode gerar umafunção de custo sintética determinando um custo mais altonos horários de pico, porém estradas individuais tendem ater padrões de congestionamento individuais, então embora umcusto variável no tempo possa ser uma estimativa melhoradado custo verdadeiro, ele está longe da perfeição.

A presente invenção aborda o problema de forneceruma estimativa de melhor custo para estradas para resultarem um sistema de rota para motoristas mais preciso. Um sis-tema de monitoramento de tráfego (ou a saída de histórico deum sistema de monitoramento de tráfego) é incorporado nosistema de rota. A informação de tráfego de histórico emiti-da pelo sistema de monitoramento é processada para fornecerprevisões de custo para a rota e o tempo de interesse, e umalgoritmo de minimização de custo é então aplicado para oscustos previstos de segmentos de rota para gerar a rota proposta ou rotas e seu custo(s) total previsto.

Como o novo sistema fornece estimativas de custovariáveis no tempo e sugestões de rota, pode-se também des-crever uma estrutura para garantir que um motorista que usao que foi originalmente proposto como a rota ótima para umaviagem continue a seguir a rota mais ótima à medida que ascondições da estrada mudam dinamicamente.

Em adição, o novo sistema fornece a oportunidadede refinamentos adicionais ao serviço de rota. Ele pode, porexemplo, ser adaptado para sugerir um tempo de viagem prefe-rencial dentro de uma janela de tempo selecionada, quandoesta resultará no custo mais baixo de viagem.

A presente invenção fornece um método e um sistemapara gerar planos de rota otimizados e estimativas de tempode viagem para uma viagem particular e tempo de partida echegada, e podem também ser usados por propor um tempo departida ótimo. Eles usam os dados e previsões geradas por umsistema de monitoramento de tráfego para fornecer previsõesde tempo de viagem precisas para horários particulares emsegmentos de rota. Combinado com um algoritmo de rota tradi-cional, isso permite que a melhor rota seja selecionada parauma viagem levando em conta as condições de tráfego que se-rão provavelmente encontradas. Em particular, e como notadoacima, uma implementação combina a cobertura geográfica pos-sível com custos de segmento de rota pré-definidos, fixados(por exemplo, limite de velocidade legal), sempre que possí-vel, com custos dependentes no tempo maiores. Um usuário,por exemplo, de um dispositivo de navegação portátil, podeentão continuar a planejar a rota como antes para virtual-mente qualquer destino em um pais coberto pelo banco de da-dos do mapa armazenado, mas, sempre que possível, pode tam-bém usar dados de tráfego com os custos dependentes no tem-po, tal que o efeito de congestionamento com qualquer previ-sibilidade de tempo possa ser precisamente levado em contacomo um processo base automático. Ele deixa o usuário sim-plesmente continuar a dirigir, seguindo o guia oferecido pe-lo dispositivo de navegação, sem a necessidade de estar pre-ocupado com o congestionamento que existe agora, e se eleterá impacto em sua viagem.

0 sistema é mostrado na Figura 1 e compreende:

•Um sistema de monitoramento de tráfego 1

•Um sistema de rota 2

Esses dois sistemas são integrados tal que o sis-tema de monitoramento 1 fornece um aparelho de previsão detempo de trânsito 3 que é usado pela função de custo 7 dosistema de rota 2 para fornecer os custos de segmento de ro-ta dependentes no tempo precisos.

1. Sistema de Monitoramento de Tráfego (TMS)

Um sistema de monitoramento de tráfego 1, tal comoRoDIN24 da Applied Generics [RoDIN24], contém um núcleo demonitoramento e de coleta 4 que observa, via algum mecanis-mo, o tráfego em uma determinada área geográfica.

Dentro da área geográfica, a rede de estradas estásegmentada em segmentos curtos e discretos; tipicamente ossegmentos terminam em junções, apesar de que pode haver múl-tiplos segmentos entre junções amplamente espaçadas. Um mó-dulo de processamento interno ao núcleo gera um ou outro ouambos de:

-Informação de tempo de trânsito de histórico pa-ra segmentos de estrada, armazenada no banco de dados 5. Emuma freqüência definida, a estimativa do sistema para o tem-po atual para cruzar o segmento de estrada é gravada no ban-co de dados, junto com quaisquer outros parâmetros que osistema gera relacionados com o tráfego no segmento de es-trada. 0 método para calcular a estimativa de tempo de trân-sito é dependente do sistema de monitoramento de tráfego; emRoDIN24 ele é derivado dos movimentos de telefones móveisque o sistema acredita ter cruzado o segmento em questão comum alto grau de probabilidade. Referência pode ser feita aoWO 0245046, os conteúdos do qual são incorporados como refe-rência .

-Informação e notificação de congestionamento 6.0 sistema 6 identifica aqueles segmentos de estrada que es-tão com congestionamentos significativos (viajando em velo-cidade na estrada muito abaixo que a esperada) e emite noti-ficações ao clientes interessados usando um protocolo combi-nado.

1.1 Previsão do Tempo de Trânsito

O sistema de monitoramento de tráfego 1 é aumenta-do com um módulo de previsão de tempo de trânsito 3. Esse édesignado para fornecer um estimativa do tempo de trânsitoesperado em qualquer segmento de estrada dentro do âmbito doTMS 1, em qualquer tempo futuro solicitado. Observa-se queum módulo de previsão de tempo de trânsito 3 que sempre for-nece o tempo de trânsito na velocidade limite da estrada éum exemplo degenerado deste sistema, e quando integrado comum sistema de rota serve para implementar as previsões derota da maneira estática tradicional. Portanto, onde o bancode dados histórico 5 ou sistemas de notificação/informaçãode congestionamento podem fornecer dados não significativos,então a posição padrão é que o tempo de trânsito é simples-mente uma função do limite de velocidade - ou seja, dadosindependentes no tempo fixados, convencionais.

Na modalidade preferencial, a previsão de tempo detrânsito é baseada em uma análise automática da informaçãode tempo de trânsito de histórico 5, e em uma integração coma informação de congestionamento atual 6. A previsão podeser executada continuamente para todos os segmentos em umfuturo próximo, ou pode executada em demanda quando a soli-citação por um cálculo da rota solicita um tempo de trânsitoprevisto do segmento de estrada particular.

É comum em pesquisa de transporte categorizar ocalendário em tipo de dia, e em dias de um tipo particular,categorizar o horário em horário de pico, horário de não-pico, hora do dia, noite, etc.

Os tipos de dias podem ser

•Dia da semana.

•Sexta-feira, que tende a um padrão diferente dosoutros dias da semana.

•Sábado.

•Domingo.•Feriado público.

As fases do ano quando as escolas estão em sessãoou em feriado adicionalmente servem para dividir o tempo.

Definindo tal calendário como a entrada para o TMS1, dados históricos podem ser alocados em uma categoria a-propriada. Dentro de cada categoria, as estimativas de tempode trânsito em uma janela de tempo curto podem ser agrupa-das; 15 minutos é um tamanho realista de janela. Então a in-formação histórica torna-se estruturada na forma:

- Dia da semana, sessão de escola, 08:00-08:15,tempo de trânsito estimado médio de 43 minutos.

- Sexta-feira, feriado escolar, 08:30-08:45, tempode trânsito estimado médio de 27 minutos.

Um mecanismo para executar a previsão do tempo detrânsito 3 é usar as categorias de informação histórica, talcomo aquelas descritas. Então o tempo de trânsito previstopara uma viagem em um horário particular é dado como um va-lor médio de tempo de trânsito da categoria que contém o ho-rário.

O refinamento do mesmo mecanismo leva em conta in-cidentes raros e congestionamento atualmente sendo observa-dos pelo sistema de informação de congestionamento 6. Ostempos de trânsito mais recentemente observados são compara-dos com as previsões para suas categorias, e a previsão fu-tura é escalada na proporção à razão recentemente observadados tempos de trânsito recentemente previstos. Para previ-sões de tempo de trânsito em um longo tempo no futuro, o es-calonamento não deve ser aplicado. Mais geralmente, a previ-são observada deve decair para o valor histórico médio à me-dida que a distância da previsão no futuro cresce.

Claramente, o mecanismo de previsão pode ser feitomais sofisticado. O aperfeiçoamento central é que a informa-ção histórica está disponível e pode ser usada para produziruma previsão muito mais precisa dos tempos de trânsito paraas seções de rota na área geográfica em consideração.

2. Descobridor de rota

A descoberta da rota pode ser implementada em umsistema 2 usando qualquer algoritmo de descoberta de rotaque determina os custos às ligações na rede. A função decusto dinâmica é simplesmente integrada no algoritmo de rota.

2.1 Função de Custo Dinâmica

Uma função de custo dinâmica é uma função do seg-mento de estrada e do tempo de interesse (futuro previsí-vel) . Essa contrasta com uma função de custo estática que éuma função somente do segmento de estrada. A função de custoestática mais comum é o tempô de trânsito no limite de velo-cidade 7, porém outras funções de custo podem ser seleciona-das 8 ao invés. Uma boa função de custo dinâmica pode serimplementada usando o mecanismo de previsão de tempo detrânsito do TMS 1. Quando o algoritmo de minimização de cus-to é aplicado 9 para um tempo de viagem particular, estafunção de custo dinâmica resulta em um tempo de viagem pre-visto mais preciso e uma seleção de rota que está mais pró-xima da ótima.

2.2 Rota com DijkstraExiste um algoritmo bem conhecido [Dijkstra] quepermite que o caminho mais curto seja calculado 9 entre osnós de um gráfico. Esse é o algoritmo padrão empregado paradescobrir a rota mais curta em uma rede de estradas. No al-goritmo Dijkstra, um peso fixado é anexado em cada margem dográfico; o custo para a rota de estrada normal é o tempo detrânsito para a seção de estrada na velocidade limite fixadana seção de estrada.

Usando a função de custo dinâmica, o custo de umamargem do gráfico não é um valor constante, porém varia aolongo do tempo. Entretanto, pode ser mostrado que a extensãoleve necessária para o algoritmo ainda resultará no calculode pelo menos caminho de custo a partir de um local e tempode inicio particulares; de fato, somente um custo é sempreaplicado a uma margem/seção de estrada particular, (durantea fase de relaxamento do algoritmo) , e à medida que essecusto está disponível a partir da função de custo dinâmica,a prova da correção do algoritmo em nossa aplicação é imedi-ata.

Nessa implementação, usam-se custos de segmento derota pré-definidos fixados (por exemplo, o limite de veloci-dade legal) para alguns segmentos de rota, mas, sempre quepossível, os custos dependentes no tempo maiores para outrossegmentos de rota. Um usuário, por exemplo, de um dispositi-vo de navegação portátil, pode, portanto, continuar a plane-jar a rota como antes para virtualmente qualquer destino emum país coberto pelo banco de dados de mapa armazenado, mas,sempre que possível, pode também usar dados de tráfego comcustos dependentes no tempo, tal que o efeito do congestio-namento com qualquer previsibilidade no tempo pode ser pre-cisamente levado em conta como um processo base automático.Ele deixa o usuário simplesmente continuar a dirigir, se-guindo o guia oferecido pelo dispositivo de navegação, sem anecessidade de se preocupar com congestionamento que existeagora, e se ele terá impacto em sua viagem.

2.3 Figura 2 - Exemplo

Demonstra-se como o sistema de rota dinâmico re-sulta em uma grande economia concreta de tempo para uma via-gem exemplificada. Considera-se o seguinte mapa de estradaesquemático. Um motorista deseja viajar de Lilliput a Brod-bingnag. Qual rota ele deveria tomar, e em quanto tempo elechegaria lá? 0 mapa é rotulado com as distâncias ao longodas estradas, e as velocidades, respectivamente, na hora doalmoço e na hora do rush. Por exemplo, 30 km (60 kph/30 kph)indica que o segmento de estrada é de 30 km, e de acordo coma melhor informação disponível para o preditor de tempo detransito, na hora do almoço (12:00), ele viajará em 60 kph,enquanto na hora do rush (16:00), ele viajará a 30 kph.

Consideram-se as opções do motorista. Ela(ele) po-de viajar via ou Blefuscu, ou via Laputa. Assumindo que to-dos os limites de velocidade de estrada são 90 kph, a viagemvia Blefuscu é mais curta, e o sistema de rota convencionalsempre proporá essa rota. Agora, deixe-nos examinar a rotacom uma função de custo dinâmica:

Hora do Almoço:

1. Às 12:00, Lilliput para Blefuscu leva 3 min a60 kph. Às 12:30 (quando o motorista chega em Blefuscu), aviagem para Brobdingnag leva 20 min a 60 kph para outros 20min. A duração total da viagem é 50 min.

2. Às 12:00, Lilliput para Laputa leva 20 min a 60kph. Às 12:20 (chegando em Laputa), a viagem para Brobding-nag leva 40 min a 60 kph para outros 20 min, uma duração to-tal de 60 min. Então na hora do almoço, é claramente melhorviajar via Blefuscu.

Hora do Rush

1. Às 16:00, Lilliput para Blefuscu leva 60 min a30 kph. O motorista chega em Blefuscu às 17:00, e leva mais60 min para viajar os 20 km até Brobdingnag a 20 kph. A via-gem leva um total de 120 min.

2. Às 16:00, Lilliput para Laputa leva 40 min a 30kph. O motorista chega em Laputa às 16:30, hora na qual elelevará mais 60 min para viajar os 40 km para Brobdingnag a40 kph. A viagem leva um total de 100 min.

Então, durante a hora do rush, a escolha de viajarvia Laputa economizou 20 minutos do motorista.

3. Atualização/Monitoramento de Rotas Escolhidas

Quando o sistema de rota calculou uma rota para ummotorista, o estado das estradas pode mudar inesperadamenteenquanto o motorista ainda está atravessando a rota. Uma im-plementação de sistema de rota pode ser construída, que emtempo real, assegura que o motorista está ainda tomando amelhor rota. Isso exige que:

- O motorista deveria estar em contato com o sis-tema de rota para indicar a posição alcançada na rota; comoum dispositivo de emergência, o sistema pode estimar a posi-ção do motorista baseada na velocidade da rota proposta.

- O sistema de rota periodicamente re-calcula arota do motorista a partir de sua posição atual até o desti-no .

- O sistema de rota usa um mecanismo de comunica-ção para informar ao motorista quando a rota calculada foialcançada.

3.1 Sistema Eficiente de Rota Dinâmico Distribuído

Uma implementação comum de um sistema que fornecerota dinâmica localiza um sistema de navegação pessoal (PNS)no veículo do usuário, ou em alguma forma de situação móvelcom o usuário. 0 PNS está em comunicação (intermitente) comum sistema de navegação central (CNS) que é um sistema in-terconectado de rede fixa contendo o sistema de monitoramen-to de tráfego. Pode-se ver o sistema como distribuído entreo PNS e o CNS.

O mais moderno em sistemas de comunicação entrePNS e CNS (por exemplo, GPRS) não fornece alta largura debanda, baixa latência ou comunicação contínua em geral, talque os problemas de comunicação devem ser lidados na arqui-tetura de uma implementação.

Em adição, onde o sistema contém um grande númerode PNSs, os custos de executar significante s computações noCNS, em particular fazendo rota podem ser proibitivos. Simi-larmente, mantendo estado em benefício de todos os PNSs noCNS adiciona significativamente à complexidade e recursoscomputacionais que devem ser desenvolvidos no CNS.Em um sistema de rota dinâmico distribuído, a in-teligência de rota pode estar localizada:

- No PNS sozinho

- O PNS contém um instantâneo recente do banco dedados histórico;

- O PNS recebe informação de congestionamento apartir do CNS;

- O PNS implementa previsão de tempo de transito eum sistema de rota baseado em sua aproximação.

- Compartilhada entre PNS e CNS

- PNS e CNS ambos calculam uma rota para o usuá-rio;

- CNS e PNS tentam assegurar que o PNS fornece umarota sempre boa o suficiente (ou melhor) com mínimas surpre-sas para o usuário.

Um sistema de rotas no CNS sozinho sofre da ausên-cia de conectividade garantida entre CNS e PNS, e em qual-quer caso, os PNSs mais modernos usam rotas estáticas noPNS; então é sempre possível fornecer o que pode ser vistocomo simplesmente um caso degenerado de rota de PNS.

As várias alternativas têm vantagens diferentes, eexaminou-se como cada uma pode ser implementada com os obje-tivos de fornecer seleção de rota rápida e precisa com bai-xos custos de comunicação. Finalmente, descreve-se um siste-ma de rotas que tem a vantagem de ser sem estado para o CNSe de baixo custo em largura de banda.

3.2 Rota de PNS

Quando o PNS faz a rota, ele deve indicar ao CNS aárea geográfica gue é de interesse dele. Esta é uma área ro-deando a fonte e destino de uma rota, com folga suficientegue gualguer rota sensível estará sempre dentro da área.Chama-se essa a área direcionável. Então o CNS necessita as-segurar gue:

1. O PNS recebe atualizações guando os segmentosde estrada na área direcionável estão viajando em uma velo-cidade (portanto, tem um custo) significativamente diferentedaguela prevista pela informação no PNS; usualmente issosignifica gue há um retardo inesperado (congestionamento) nosegmento de estrada.

2. O PNS tem uma vista de histórico atualizada daárea direcionável. O banco de dados de histórico tende a mu-dar lentamente, e o CNS pode fornecer ao PNS atualizaçõesdinâmicas de informação de histórico na área direcionávelgue está desatualizada.

Em soma, o CNS assegura gue o PNS tenha uma vistaboa o suficiente da área direcionável para produzir uma rotague está muito próxima da rota ótima gue o próprio CNS gera-ria. A rota de PNS tem vantagens em tempo real. Se o PNS es-tá em contato com o CNS ou não, uma melhor rota conhecidapode ser calculada e usada pelo motorista até gue atualiza-ções são recebidas a partir do CNS para re-calcular a rota e(possivelmente) re-direcionar o motorista.

Um problema com essa forma de rota de PNS é gue oPNS deve pesguisar no CNS por atualizações para a função deprevisão na área direcionável, ou o CNS deve manter estadogravando a área direcionável do PNS, tal gue ele pode empur-rar atualizações ao PNS.

3.3 Rota Compartilhada

Ambos PNS e CNS podem participar em guiar o moto-rista em uma rota. Quando eles estão em contato, o PNS e oCNS podem ambos calcular a rota, então eles podem negociarsobre diferenças em suas rotas selecionadas, ou ficarem des-cansados já que ambos escolheram a mesma rota.

Por exemplo:

1. Motorista pergunta ao PNS para (rota A B)

2. PNS calcular (A r s t B)

3. PNS envia ao CNS (rota selecionada A B(r s) )

- qual rota é perguntada a tomar

- o primeiro ponto(s) (equivalentemente aos pri-meiros segmentos de rota) que ele selecionou

4. O CNS calcula a (rota A B) usando seu sistemade rota, que por definição resulta na melhor rota possívelque sua tecnologia pode gerar. (A χ y ζ B)

5. 0 CNS compara a rota que ele gerou com a rotagerada pelo PNS. Nesse exemplo, o CNS fez a rota via x, y ez, uma rota completamente diferente do PNS, assim parecerianecessário deixar o PNS conhecer.

6. Onde há diferenças, o CNS transmite essas devolta ao motorista. Em particular, ele necessita somentetransmitir imediatamente se há diferença no início da rota.E é necessário somente transmitir a primeira diferença; emrecebimento de uma diferença, o PNS pode calcular uma rotarestante a partir do próximo ponto no mapa na rota fornecidapelo PNS. Então o CNS diz ao PNS (rota selecionada AB (x) )e ο PNS calcula (rota A via χ Β) que, felizmente, o PNS cal-cula como (A χ y ζ B).

- Se uma diferença existe mais tarde na rota, oPNS pode até escolher não transmitir a rota até que o moto-rista está mais próximo à divergência de rotas, em razão deque a divergência pode ser causada pelo congestionamentotemporário que terá desaparecido quando o motorista o alcan-ça .

7. O CNS continua a monitorar a rota do motorista,enviando notificações se ele re-calcular uma rota diferenteem um tempo futuro.

Rota compartilhada dessa forma e de formas rela-cionadas é extremamente eficiente em largura de banda. Estátambém muito próxima da ótima para procura de rota, dada pe-la função de custo dinâmica correta. O problema principalcom rota compartilhada é que ela localiza significante com-putação e custos de estado no CNS.

-3.4 Figura 3 - Rota de PNS com Baixa Carga de RedeQuando o sistema usa rota de PNS, constata-se queuma rota boa o suficiente pode ser feita usando a função derota dinâmica no PNS que codifica a informação de histórico,mais uma quantidade muito pequena de informação de retardosolicitada a partir do CNS. A chave é fazer a rota no PNSpara identificar os poucos segmentos de estrada que devemter seus custos atualizados no PNS com os valores mais atua-lizados calculados pelo CNS. Esse então permite que o PNSrefine sua rota para aproximar a rota ótima como teria sidocalculado pelo CNS usando a função de custo dinâmica.Aqui está o mecanismo:

1. O PNS constrói a área direcionável para a rotaA a B, e pergunta ao CNS pelos valores de custo do CNS pelostempo nos quais a rota será usada para quaisquer segmentosde estrada na área direcionável que são de custo menor deacordo com a função de custo do CNS do que de acordo com afunção de custo do PNS. O CNS conhece quais funções de custoo PNS está usando porque o PNS pode dizer ao CNS a versão dobanco de dados de histórico que ele mantém. O CNS mantém umacodificação de todos os bancos de dados de histórico que es-tão presentes na população de PNSs, tal que ele pode deter-minar para qualquer segmento de estrada se qualquer dos va-lores de custo do segmento deve ser retornado ao PNS. Umadiferença de custo mínima por segmento é definida, ds, talque o CNSD somente envia ao PNS os segmentos de estrada e osvalores de custo de CNS (segment, Costcns (segment)) que sa-tisfaz Costcns (segment) + ds < coStpns (segment) , que é aquelecom um valor de custo de CNS menor por pelo menos ds. Prati-camente, o número de tais segmentos de estrada selecionados,e, portanto, o tamanho de mensagem e custo, será pequeno.

2. Agora, o PNS constrói uma função de custo modi-ficada, routecostpus, que determina os valores de custo re-tornados pelo PNS para os segmentos de estrada com customais baixo retornados no estágio anterior, e determina osvalores históricos mantidos pelo PNS para todos os outrossegmentos de estrada. O PNS executa um cálculo de rota de Aaté B usando routecostPNS. A rota selecionada por esse cálcu-lo é chamado a rota candidata bestroutePNS· A função de custodo CNS, routecostcNSr pode anexar um custo mais alto a essarota do que routecostPNS, porque a função de custo do PNS mo-dificada não conhece os custos raramente altos (equacionandopara segmentos de estrada retardados) que a função de custode CNS conhece. Mas por causa da modificação da função decusto do PNS no estágio anterior, bestroutePNS terá um custode acordo com PNS que não é muito maior do que a rota decusto mais baixo de acordo com routecostCNSr que chama-sebestrouteCNs De fato:

routecostPNS (bestroutePNS) < route-costcNs (bestrouteCNs) + segmentcount (hestrouteCNs) *ds- 0 valorde ds usado no sistema é escolhido de modo a compensar quãopróximo routecostPNS (bestroutePNS) deve ser para route-costcNs (bestroutePNS) contra o tempo e largura de banda de re-de exigidos para transmitir segmentos de estrada e custo noestágio 1.

3. Agora resta verificar que o custo que o CNS de-termina à rota candidata escolhida pelo PNS, route-costcNs (bestroutePNS) , não é muito pior do que o custo que oPNS determina a ela. Para fazer isso, o PNS solicita os va-lores de custo do CNS para os segmentos de estrada em bes-troutePNS. 0 CNS fornece os valores de custo para esses seg-mentos de estrada ao PNS, e o PNS atualiza sua função decusto para incorporar esses valores de custo de segmento deestrada a partir do CNS. Se o CNS retém o número de versãode banco de dados histórico de PNS, ou o PNS envia o númerode versão novamente nessa solicitação, o CNS necessita so-mente responder com aqueles valores de custo de segmento deestrada que diferem daqueles que o PNS mantém em seu bancode dados. A função de custo do PNS é agora routecostPNSupdated.

4. O PNS agora calcula routecostPNSupda~ted (bestroutePNS) r o custo da rota candidata que ele anterior-mente selecionou, esse tempo usando os valores de custo for-necidos para os segmentos de estrada nessa rota. Nota-se queroutecostPNSupdated (bestroutePNS) = routecostcm (bestroutePNS).

Uma diferença de custo aceitável máxima dextraroute é defini-da para testar se bestroutePNS é para ser aceitável como arota a oferecer ao cliente nesse estágio. bestroutePNS é a-ceito somente no caso em que routecostPNSupdated (bestroutePNS) ^routecostPNS (bestroutePNS) + dextraroute· 0 valor de dextrar0uteusado pelo sistema é escolhido para compensar quão próximoroutecostPNSupdated (bestroutePNS) está de routecostcm (bestrou-teCNs) contra o tempo e largura de banda da rede que o meca-nismo consome.

5. Se bestroutePNS foi aceita, o processo de sele-ção de rota está completo e bestroutePNS é emitido ao usuáriodo PNS.

6. Se bestroutePNS não foi aceita, o mecanismo re-torna ao estágio 2, exceto que esse tempo routecostPNSupdated êusado para selecionar uma nova rota candidata bestroute'PWS.Se bestroute'PNS = bestroutePNS (ou, em iterações adicionais,qualquer rota candidata previamente selecionada) então bes-troute'PNS é aceita imediatamente. De outra forma, o sistemaexecuta o mesmo processo novamente, solicitando os valoresde custo do CNS para bestroute' PNS (estágio 3) atualizandoroutecostPNSupdated, e calculando route-cost'pNsupdated (bestroute'PNS) (estágio 4).

7. Eventualmente, e usualmente muito rapidamentedada uma escolha razoável de dextraroater uma das rotas can-didatas que o sistema gera é aceita. Pode ser mostrado que oPNS deve eventualmente aceitar uma rota candidata porque afunção de custo routecostPNSupdated estabilizará eventualmenteigual a routecostCNSr ponto no qual routecostPNSupdated = route-costpns e a condição de aceitação para a rota candidata atualroutecostPNSupdated (bestroutePNS) ≤ routecostPNS (bestroutePNS) +dextraroute se manterá imediatamente.

8. O sistema emite a rota aceita ao usuário doPNS.

9. Se em qualquer conectividade de estágio é per-dida entre PNS e CNS, o PNS pode emitir a rota candidata a-tual ao usuário. Ao invés, é freqüentemente melhor emitir oprimeiro estágio de uma rota imediatamente, e então à rota apartir da próxima junção que o motorista se aproximará. Ainteração com o sistema parece muito mais natural ao usuáriose ele não necessitar esperar mais do que uma fração de umsegundo por uma resposta inicial a partir do sistema depoisde solicitar uma rota.

10. À medida que o motorista viaja em direção aodestino, o sistema pode periodicamente solicitar (como noestágio 3) os custos para os segmentos de estrada restantesda rota aceita. Se um retardo se constrói pela rota, o PNSpode automaticamente re-direcionar a partir da posição atualreiniciando o algoritmo no estágio 4.

A rota de PNS de baixo custo executa todos os seuscálculos de rota no PNS (portanto, a rota de PNS), mas aomesmo tempo ela exige estado mínimo no CNS, e faz mínimasdemandas de largura de banda. Ela tem a vantagem de rota dePNS de ser capaz de continuar sendo útil quando ela está emcontato com o CNS. Em adição, a rota de PNS de baixo custoproduz rotas que são praticamente suficientemente próximasem custo às rotas produzidas usando rota dinâmica no CNS,tal que quase todas as economias de custo associadas com arota dinâmica podem ser realizadas na prática.

3.5 Reduzindo Custos de Comunicação

Entretanto, as responsabilidades para seleção derota são divididas, o custo de transmissão de dados pode sermantido baixo usando um número de técnicas:

Numeração de Segmento Relativa à Localização

Quando o PNS e o CNS estão em comunicação, a loca-lização precisa do motorista e o PNS é quase sempre exigidapelo CNS. Como a maior parte dos segmentos de estrada de in-teresse são locais ao motorista (ou a uma rota selecionadapara o motorista), um sistema de numeração de rota alterna-tivo pode ser colocado no local temporariamente entre o PNSe o CNS, onde somente um pequeno número de bits é necessáriopara identificar os segmentos de estrada mais usualmentetransmitidos.

Numeração de Segmento Relativa à Rota

Uma rota de Ά até B pode ser inteiramente descritacontando saídas em junção atravessada na rota. Onde cadasegmento de estrada é de comprimento significativo, isso re-sulta em uma representação muito compacta de uma rota.Onde, como é típico, uma grande seção de uma rotapode dar na mesma estrada, uma forma de executar codificaçãode comprimento pode ser usada. Então uma rota pode ser re-presentada como (3, 13, 2, 28, 2, 15), significando

- 3a salda de uma próxima junção

- reto através das próximas 13 junções

- 2a saída na 14a junção

- reto através das próximas 28 junções

- 2a saída na 29a junção

- reto através das 15 junções

- chegada.

Claims (56)

1. Método de planejar uma rota até um destino,CARACTERIZADO pelo fato de que compreende as etapas de:(a) usar um banco de dados do mapa que define asestradas em termos dos segmentos de rota e inclui um custoindependente no tempo, pré-definido, fixo associado com cadasegmento de rota diferente no banco de dados do mapa;(b) usar software que habilita uma rota a ser pla-nejada a um destino e que calcula um custo estimado de al-cançar esse destino usando um ou mais segmentos de rota;onde usar o software envolve planejar uma rota u-sando automaticamente uma combinação de (i) custos dependen-tes no tempo para um ou mais dos segmentos de rota na rota,tal que um custo é aplicado para cruzar um segmento de rotaparticular que é apropriado para o tempo especifico quandoele é planejado para ser cruzado e (ii) os custos indepen-dentes no tempo, pré-definidos e fixos para aqueles segmen-tos de rota na rota que não são definidos pelos custos de-pendentes no tempo.

2. Método, de acordo com a reivindicação 1,CARACTERIZADO pelo fato de que o custo dependente no tempoassociado com um segmento de rota particular refere-se à ve-locidade do veiculo ou tempos de transito de segmento de ro-ta que foram medidos ou inferidos e não são fixos e pré-def inidos .

3. Método, de acordo com a reivindicação 1 ou 2,CARACTERIZADO pelo fato de que o custo independente no tem-po, pré-definido fixo associado com um segmento de rota par-ticular não foi medido ou inferido a partir do fluxo ou mo-vimento de tráfego de veiculo atual, mas, ao invés, é umafunção de (i) o tipo de estrada associada com esse segmentode estrada ou (ii) o limite de velocidade aplicável a essesegmento de estrada.

4. Método, de acordo com a reivindicação 3,CARACTERIZADO pelo fato de que os custos independentes notempo são usados em combinação com os custos dependentes notempo, para aqueles segmentos de rota que são definidos porambos os custos independentes no tempo e os custos dependen-tes no tempo.

5. Método, de acordo com qualquer uma das reivin-dicações anteriores, CARACTERIZADO pelo fato de que o custoassociado com uma rota particular é o tempo estimado obtidopara alcançar o destino.

6. Método, de acordo com qualquer uma das reivin-dicações anteriores, CARACTERIZADO pelo fato de que o custoassociado com uma rota particular é o uso de combustível as-sociado com essa rota.

7. Método, de acordo com qualquer uma das reivin-dicações anteriores, CARACTERIZADO pelo fato de que o custoassociado com uma rota particular é o custo financeiro cre-ditável associado com essa rota.

8. Método, de acordo com qualquer uma das reivin-dicações anteriores, CARACTERIZADO pelo fato de que o custoassociado com uma rota particular é de um tipo que um usuá-rio final pode selecionar a partir de uma lista de opçõesexibida em um dispositivo de computação.

9. Método, de acordo com a reivindicação 8,CARACTERIZADO pelo fato de que a lista de opções inclui umaou mais dos seguintes itens: tempo de trânsito para a rota;custo financeiro para a rota; uso de combustível pela rota;tráfego estacionário.

10. Método, de acordo com qualquer uma das reivin-dicações anteriores, CARACTERIZADO pelo fato de que o soft-ware calcula o custo da rota como parte de um algoritmo deminimização de custo.

11. Método, de acordo com qualquer uma das reivin-dicações anteriores, CARACTERIZADO pelo fato de que um custoestimado de alcançar um destino para um motorista particularde um veículo é uma função de um perfil de condução associa-do com esse motorista.

12. Método, de acordo com a reivindicação 11,CARACTERIZADO pelo fato de que os fluxos de tráfego atuaisou dados de movimento são derivados de rastreios por GPS ar-mazenados por um dispositivo de navegação baseado em GPS emum veículo viajando ao longo dos segmentos de rota.

13. Método, de acordo com a reivindicação 12,CARACTERIZADO pelo fato de que os rastreios por GPS são en-viados por uma rede sem fio celular diretamente pelo dispo-sitivo a um sistema de monitoramento de tráfego.

14. Método, de acordo com a reivindicação 11 ou 12, CARACTERIZADO pelo fato de que os rastreios por GPS sãoenviados diretamente pelo dispositivo a um sistema de moni-toramento de tráfego.

15. Método, de acordo com a reivindicação 12,CARACTERIZADO pelo fato de que os rastreios por GPS são en-viados pelo telefone móvel conectado ao dispositivo por umarede de computadores com dispositivo de tecnologia bluetooth("piconet") ou outra forma de conexão.

16. Método, de acordo com a reivindicação 12,CARACTERIZADO pelo fato de que os rastreios por GPS são en-viados pelo dispositivo quando ele está acoplado a um PC aum sistema de monitoramento de tráfego.

17. Método, de acordo com a reivindicação 11,CARACTERIZADO pelo fato de que a medição dos fluxos de trá-fego de veiculo atuais ou movimentos é alcançada medindo-sea localização de telefones móveis.

18. Método, de acordo com a reivindicação 17,CARACTERIZADO pelo fato de que a localização de telefonesmóveis é obtida passivamente monitorando-se tráfego de sina-lização de telefones móveis a estações base.

19. Método, de acordo com a reivindicação 11,CARACTERIZADO pelo fato de que a medição dos fluxos de trá-fego de veiculo atuais ou movimento é alcançada usando-sesensores cíclicos em estradas.

20. Método, de acordo com a reivindicação 11,CARACTERIZADO pelo fato de que a medição dos fluxos de trá-fego de veículo atuais ou movimento é alcançada usando-sesistemas baseados em câmeras.

21. Método, de acordo com a reivindicação 11,CARACTERIZADO pelo fato de que a medição dos fluxos de trá-fego de veículo atuais ou movimento é alcançada usando-seveículos equipados com rádio sinalizadores.

22. Método, de acordo com qualquer reivindicaçãoanterior, CARACTERIZADO pelo fato de que os custos dependen-tes no tempo são dinamicamente atualizáveis.

23. Método, de acordo com a reivindicação 22,CARACTERIZADO pelo fato de que os custos dependentes no tem-po são dinamicamente atualizáveis em tempo real.

24. Método, de acordo com qualquer reivindicaçãoanterior, CARACTERIZADO pelo fato de que os custos dependen-tes no tempo associados com um segmento de rota são uma fun-ção da hora do dia ou da noite.

25. Método, de acordo com qualquer reivindicaçãoanterior, CARACTERIZADO pelo fato de que os custos dependen-tes no tempo associados com um segmento de rota são uma fun-ção dos dias da semana.

26. Método, de acordo com qualquer reivindicaçãoanterior, CARACTERIZADO pelo fato de que os custos dependen-tes no tempo associados com um segmento de rota são uma fun-ção de feriados públicos.

27. Método, de acordo com qualquer reivindicaçãoanterior, CARACTERIZADO pelo fato de que os custos dependen-tes no tempo associados com um segmento de rota são uma fun-ção de feriados escolares.

28. Método, de acordo com qualquer reivindicaçãoanterior, CARACTERIZADO pelo fato de que os custos dependen-tes no tempo associados com um segmento de rota são uma fun-ção de qualquer evento que provavelmente causará impacto emcustos de segmento de rota.

29. Método, de acordo com qualquer reivindicaçãoanterior, CARACTERIZADO pelo fato de que os custos dependen-tes no tempo associados com um segmento de rota são uma fun-ção de qualquer situação futura sobre a qual é possível in-ferir um impacto provavelmente em custo de segmento de rota.

30. Método, de acordo com qualquer reivindicaçãoanterior, CARACTERIZADO pelo fato de que o destino incluidois ou mais destinos.

31. Método, de acordo com qualquer reivindicaçãoanterior, CARACTERIZADO pelo fato de que o método é executa-do por um dispositivo de navegação baseado em GPS.

32. Dispositivo de navegação, CARACTERIZADO pelofato de que é programado com:(a) um banco de dados do mapa que define as estra-das em termos dos segmentos de rota e inclui um custo inde-pendente no tempo pré-definido, fixo associado com cada seg-mento de rota diferente no banco de dados do mapa; e(b) software que habilita uma rota a ser planejadaaté um destino e que calcula um custo estimado de alcançaresse destino usando um ou mais segmentos de rota;onde o dispositivo pode planejar uma rota usandoautomaticamente uma combinação de (i) custos dependentes notempo para um ou mais dos segmentos de rota na rota, tal queum custo é aplicado para cruzar um segmento de rota particu-lar que é apropriado para o tempo específico quando ele éplanejado a ser cruzado e (ii) os custos independentes notempo, pré-definidos, fixos para aqueles segmentos de rotana rota que não são definidos pelos custos dependentes notempo.

33. Dispositivo, de acordo com a reivindicação 32,CARACTERIZADO pelo fato de que o dispositivo calcula a rotade menor custo até o destino.

34. Dispositivo, de acordo com a reivindicação 32ou 33, CARACTERIZADO pelo fato de que o dispositivo planejarotas mais rápidas.

35. Dispositivo, de acordo com a reivindicação 32ou 33, CARACTERIZADO pelo fato de que o dispositivo planejauma rota com o uso de combustível mais baixo.

36. Dispositivo, de acordo com a reivindicação 32ou 33, CARACTERIZADO pelo fato de que o dispositivo planejauma rota com os encargos financeiros mais baixos.

37. Dispositivo, de acordo com a reivindicação 32- 36, CARACTERIZADO pelo fato de que os custos dependentesno tempo são empurrados para o dispositivo.

38. Dispositivo, de acordo com a reivindicação 32- 36, CARACTERIZADO pelo fato de que os custos dependentesno tempo são enviados ao dispositivo em solicitação pelodispositivo.

39. Dispositivo, de acordo com a reivindicação 37ou 38, CARACTERIZADO pelo fato de que os custos dependentesno tempo recebidos pelo dispositivo são restritos a umaclasse de tipos de estradas.

40. Dispositivo, de acordo com a reivindicação 32,CARACTERIZADO pelo fato de que inclui custos dependentes notempo na mesma memória que inclui o banco de dados do mapa.

41. Dispositivo, de acordo com a reivindicação 32,CARACTERIZADO pelo fato de que acessa os custos dependentesno tempo, os quais são mantidos em um servidor remoto.

42. Dispositivo, de acordo com a reivindicação 41,CARACTERIZADO pelo fato de que pode ser acoplado com um com-putador conectado à internet e recebe os custos dependentesno tempo a partir do servidor remoto via o computador conec-tado à internet.

43. Dispositivo, de acordo com a reivindicação 41,CARACTERIZADO pelo fato de que o servidor remoto envia aodispositivo um custo associado com movimento a partir de uminicio até o destino.

44. Dispositivo, de acordo com a reivindicação 41,CARACTERIZADO pelo fato de que o servidor recebe um conteúdode tráfego em tempo real que o habilita a suplementar oscustos dependentes no tempo com dados recentes.

45. Dispositivo, de acordo com a reivindicação 41,CARACTERIZADO pelo fato de que recebe dados de tráfego re-cente ou em tempo real ou informação de congestionamento apartir do servidor e automaticamente usa esses dados ou in-formação para re-calcular a rota ótima.

46. Dispositivo, de acordo com a reivindicação 41,CARACTERIZADO pelo fato de que:(a) ambos o dispositivo e o servidor usam cada umseparadamente os custos dependentes no tempo;(b) o dispositivo informa ao servidor da rota demenores custos de que ele calculou; e(c) o servidor envia uma notificação ao dispositi-vo se a rota de menor custo que ele calculou é diferente darota que o dispositivo calculou.

47. Dispositivo, de acordo com a reivindicação 46,CARACTERIZADO pelo fato de que o servidor envia uma notifi-cação ao dispositivo que define unicamente a diferença entreas rotas.

48. Dispositivo, de acordo com a reivindicação 41,CARACTERIZADO pelo fato de que:(a) ambos o dispositivo e o servidor usam cada umseparadamente os custos dependentes no tempo;(b) o dispositivo identifica os segmentos de es-trada para os quais dados recentes são valiosos e solicitaos dados recentes a partir do servidor.

49. Dispositivo, de acordo com a reivindicação 32-48, CARACTERIZADO pelo fato de que o dispositivo pode su-gerir uma hora de inicio ótima para uma viagem.

50. Dispositivo, de acordo com a reivindicação 32-48, CARACTERIZADO pelo fato de que é um dispositivo de na-vegação baseado em GPS.

51.Dispositivo, de acordo com a reivindicação 32-48, CARACTERIZADO pelo fato de que é um dispositivo móvelcom sistema de procura de localização.

52. Dispositivo, de acordo com a reivindicação 32-48, CARACTERIZADO pelo fato de que o sistema de procura delocalização é GPS.

53. Dispositivo, de acordo com a reivindicação 32- 48, CARACTERIZADO pelo fato de que é permanentemente embu-tido em um veiculo a motor.

54. Sistema de monitoramento de tráfego,CARACTERIZADO pelo fato de que mede velocidade de tráfego oudados de tempo de trânsito como uma função do tempo e geraum banco de dados de histórico de velocidades de tráfego de-pendente no tempo ou tempos de trânsito para segmentos deestradas; e compartilha pelo menos algum desse banco de da-dos ou seus conteúdos para habilitar o método da reivindica-ção 1 a ser executado.

55. Mapa digital de uma região, CARACTERIZADO pelofato de que o mapa inclui dados que definem segmentos de es-trada, junto com dados que definem custos dependentes notempo associados com pelo menos alguns dos segmentos de es-trada, adaptados para habilitar o método das reivindicações-1 - 31 a ser executado quando usado pelo software de plane-jamento de rota.

56. Veiculo a motor, CARACTERIZADO pelo fato deque inclui um sistema de navegação embutido operável paraplanejar uma rota usando o método da reivindicação 1- 31.