BRPI0708099A2 - método implementado por computador para gerar uma programação para uma operação de transporte, sistema de programação para uma operação de transporte, sistema de transporte, e, elemento de programação para um computador - Google Patents

Abstract

MéTODO IMPLEMENTADO POR COMPUTADOR PARA GERAR UMA PROGRAMAçãO PARA UMA OPERAçãO DE TRANSPORTE, SISTEMA DE PROGRAMAçãO PARA UMA OPERAçãO DE TRANSPORTE, SISTEMA DE TRANSPORTE, E, ELEMENTO DE PROGRAMAçAO PARA UM COMPUTADOR. Métodos para programar uma operação de transporte tal como a operação de uma companhia de linha aérea. O método seleciona de forma desejável uma demanda (100) para transporte especificando uma origem, um destino, e tempo de chegada ou de partida e seleciona recursos de um banco de dados de recursos disponíveis tal como aeronave (508), tripulação, e portões de embarque. A seleção de recursos é conduzida de forma desejável a fim de otimizar uma função de resultado tal como contribuição à margens ou outro resultado financeiro da operação particular especificada na demanda. Quando do desenvolvimento de um fragmento de programação (108), os recursos especificados são compromissados, e o banco de dados de recursos disponíveis é modificado (110) para indicar que os recursos não estão mais disponíveis nos tempos relevantes. O sistema então trata outra demanda e repete o processo a fim de desenvolver uma programação completa.

Description

"MÉTODO IMPLEMENTADO POR COMPUTADOR PARA GERARUMA PROGRAMAÇÃO PARA UMA OPERAÇÃO DE TRANSPORTE,SISTEMA DE PROGRAMAÇÃO PARA UMA OPERAÇÃO DETRANSPORTE, SISTEMA DE TRANSPORTE, E, ELEMENTO DEPROGRAMAÇÃO PARA UM COMPUTADOR"

REFERÊNCIA CRUZADA PARA APLICAÇÕES RELACIONADAS:

Esta aplicação reivindica os benefícios de datas de depósito dopedidos de patente provisórios U.S. Nos. 60/774.623, depositado em 21 defevereiro de 2006; 60/797.413, depositado em 3 de maio de 2006; e60/879.831, depositado em 11 de janeiro de 2007, as divulgações que são comisto incorporadas aqui para referência.

CAMPO DA INVENÇÃO

A presente aplicação se relaciona aos métodos e sistemas paraprogramar operações de transporte.

CONHECIMENTO DA INVENÇÃO

Companhias de transporte tal como companhia de linhasaéreas que enfrentam problemas em configurar programações. Umaprogramação que especifica quais veículos e tripulação estão para fazerviagens em tempos específicos precisa levar em conta da disponibilidade deveículos a serem usados na operação e as tripulações para operar os veículos,assim como a disponibilidade de recursos fixos tal como portões de aeroporto.Cada um desses recursos tipicamente é governado por configuraçõescomplexas de regras que levam em conta fatores tal como a necessidade deconfigurar tempos a parte para manutenção de aeronave; as qualificações dediferenciação dos diferentes pilotos e as limitações de tempo de trabalho dosmembros da tripulação configuradas por regulamentações governamentais ouacordos com o sindicato dos trabalhadores.

O sistema de programação pode iniciar com uma lista deoperações, tal como uma lista de vôos á acontecerem em horas específicasentre aeroportos específicos, e tentar encontrar uma programação que vai teraeronave apropriada disponível para todas as operações, então tentarprogramar as tripulações necessárias, e assim por diante. O processo deconfigurar a programação efetiva é de forma geral, separada do processo dedeterminar que rotas voar em que horas. Isto tipicamente conduz ao uso nãoótimo dos recursos. Por exemplo, tipicamente não há realimentação quepoderia levar a companhia de linha aérea a reconhecer que uma pequenamudança em uma hora de partida de um vôo poderia permitir a companhia delinha aérea usar um avião para um outro vôo, tal que um avião fique ocioso aum custo de milhares de dólares por hora.

Seria desejável derivar uma programação otimizada para umacompanhia de linha aérea ou outra operação de transporte, levando em contaambas variáveis financeiras tal como os receita esperados de cada vôo erestrições impostas pelos recursos tal como aeronave disponível. Em umaprimeira consideração, poderia ser visto que alguém poderia derivar umaprogramação ótima aplicando técnicas de programação linear convencionaispara tratar todas as variáveis na programação e encontrar a programação quefornece o retorno financeiro líquido máximo. Contudo, é impossíveldeterminar uma programação ótima para uma companhia de linha aérea ououtra companhia de transporte de qualquer tamanho através de técnicasmatemáticas convencionais. Para uma companhia de linha aérea com 100aviões atendendo à 200 vôos por dia, mesmo assumindo que as horas de vôosão fixas e ignorando os diferentes arranjos de tripulação possíveis, existem20.000 possibilidades de voar em aeronave particular em vôos particulares noprimeiro dia. Por causa da reposição de aeronave do primeiro dia emdiferentes aeroportos, cada possibilidade para o primeiro dia conduz a umadiferente configuração de 20.000 possibilidades para o segundo dia, tal queuma programação de dois dias iria incluir (20.000)2 ou 400.000.000possibilidades, e uma programação de três dias iria incluir (20.000) ou8.000.000.000 de possibilidades e assim por diante. Para selecionar umaprogramação ótima para um mês ou dois requer exame de um numeroessencialmente infinito de possibilidades, e está além da capacidade demesmo dos mais poderosos computadores. Colocado de uma forma, oproblema de derivar uma programação ótima pertence a uma classe deproblemas matemáticos referido como "NP-hard", tal que a cargacomputacional aumenta exponencialmente com o número da aeronave,tripulação e outro elementos a serem contabilizados pela programação.

Independente do esforço considerável devotado ao problemade programar para a companhia de linha aéreas e outras companhias detransporte, nenhum sistema satisfatório de verdade tem sido doravantedesenvolvido. Em particular, é estimado que usando as melhores técnicascorrentes, as companhias de linha aéreas gastam aproximadamente por centode seus receita devido à ineficiências resultante de programação pobre. Assimsendo, antes da presente invenção, tem havido umas necessidades nãosatisfeitas substanciais para melhoras em programar.

SUMÁRIO DA INVENÇÃO

Um aspecto da invenção fornece métodos implementados porcomputador de gerar programações para a operação de transporte. Método deacordo com este aspecto da invenção usa, de forma desejável, uma listaordenada de uma grande quantidade de demandas para transporte entre umagrande quantidade de origens e uma grande quantidade de destinações, cadademanda sendo associada com uma origem, uma destinação e uma hora departida ou de chegada. O método usa, de forma desejável, um computadorpara configurar um fragmento de programação para satisfazer uma dasdemandas na lista ordenada. O estágio de configurar o fragmento deprogramação incluindo atribuir recursos de uma ou mais listas de recursosdisponíveis, por exemplo, no caso de uma companhia de linha aérea, o estágiode configuração um fragmento de programação mais comumente incluidesignar a particular aeronave, tripulação e aeroporto portão. O método deacordo com este aspecto da invenção inclui, de forma desejável, modificar auma ou mais listas de recursos disponíveis para indicar um estado revisadocom base no uso de recursos no estágio de configuração da programação. Ométodo mais preferencialmente também inclui o estágio de repetir as etapasde configuração de um fragmento de programação e modificar as listas derecursos disponíveis que essas etapas são efetuadas para a grande quantidadede demandas de acordo com a ordem das demandas na lista e tal que o estágiode configurar um fragmento de programação para cada demanda é efetuadousando o estado resultante do estágio de modificar para a próxima demandaprévia.

Um outro aspecto da invenção fornece métodos adicionais degerar programações para operações de transporte. O método de acordo comeste aspecto da invenção usa, de forma desejável, uma lista de uma grandequantidade de demandas para transporte entre uma grande quantidade deorigens e uma grande quantidade de destinações, cada demanda sendoassociada com uma origem, uma destinação e uma hora de partida e dechegada, e também usa uma ou mais listas de veículos incluindo identidadesde grande quantidade de veículos e informação especificando localização decada veículo versus hora. O método de acordo com este aspecto da invençãousa, de forma desejável, um computador para selecionar um veículo a partirde um ou mais veículos identificados na lista de veículos, selecionar uma dasdemandas de uma lista das demandas e configurar um fragmento deprogramação para satisfazer as demandas selecionadas designando o veículoselecionado para a demanda selecionada. Aqui de novo, o método inclui, deforma desejável, modificar a uma ou mais listas de veículos e a lista dedemandas para indicar um estado revisado com base no uso de veículos edemandas no estágio de configuração de um fragmento de programação. Ométodo de acordo com este aspecto da invenção inclui, de forma desejável,repetir essas etapas tal que as etapas de seleção e de configuração defragmentos de programação são efetuadas para uma grande quantidade dedemandas e tal que essas etapas são efetuadas para cada repetição usando oestado resultante do estágio de modificação da próxima repetição prévia.

Como ainda discutido abaixo, modalidades preferidas demétodos de acordo com esses aspectos da invenção podem rapidamenteproduzir programações realísticas usáveis, mesmo para uma operação detransporte complexa tal como uma grande companhia de linha aérea.

Ainda aspectos da invenção fornecem sistemas de computadore elementos de programa de computador para implementar métodos deprogramação, como discutido acima, e sistema de transportes usando taismétodos de programação.

DESCRIÇÃO BREVE DOS DESENHOS

FIG. 1 é um fluxograma, de forma esquemática, descrevendocertos elementos no método de acordo com uma modalidade da invenção.

FIG. 2 é um fluxograma parcial descrevendo outros elementosno método da FIG. 1.

FIG. 3 é um apresentação gráfica de dados de carga depassageiros históricos.

FIG. 4 é uma representação em diagrama de certos dados decarga de passageiros prognosticados abstraídos a partir dos dados da FIG. 3.

FIG. 5 é um fluxograma parcial ainda descrevendo etapas dométodo mostrado nas FIGS. 1 e 2.

FIG. 6 é um outro fluxograma parcial descrevendo uma dasetapas da FIG. 5 em maiores detalhes.

FIG. 7 é ainda um fluxograma parcial descrevendo uma outroestágio mostrado na FIG. 5 em maiores detalhes.

FIG. 8 é ainda um outro fluxograma parcial descrevendo umestágio adicional mostrada na FIG. 5 em maiores detalhes.FIG. 9 é um gráfico em diagrama de carga de passageirosesperada versus tempo de partida.

FIG. 10 é uma vista, em forma de diagrama, de um processo

usados no método das FIGS. 1-9.FIG. 11 é ainda um fluxograma parcial descrevendo certasetapas usadas no método das FIGS. 1-10.

FIG. 12 é ainda um outro fluxograma parcial descrevendo umadas etapas mostradas na FIG. 11.

FIG. 13 é um fluxograma, em forma de diagrama, descrevendoum processo de acordo com uma modalidade adicional da invenção.

FIG. 14 é uma representação esquemática de um sistema decomputador e sistema de transporte, usados em uma modalidade da invenção.

DESCRIÇÃO DETALHADA

Um processo de acordo com uma modalidade da presenteinvenção é mostrado em forma geral na FIG. 1. O processo começaformulando um conjunto de nós de demanda, i. e., demandas para operaçõesde transporte associadas com datas e horas particulares no futuro. No exemplodiscutido aqui, um nó de demanda representa demandas para passageiros devôos de companhia de linha aérea, mas outras operações de transporte podemser tratadas de forma similar. Em adição para a data, hora de partida, origem,destinação, e número de passageiros esperados em cada classe, os dadosdefinindo maioria de cada nó demanda inclui, de forma desejável, dadosadicionais associados com os resultados a serem alcançados encontrando umademanda, como por exemplo, uma contribuição ideal para margem deoperação ("CTM") ou outro resultado financeiro da companhia de linha aéreade uma operação coincidindo com a demanda usando a melhor aeronavepossível na hora exata especificada na demanda; receita esperada porpassageiros em cada classe de serviço; uma indicação como para se aoperação denotada pelo nó de demanda serve como um alimentador paraencaminhar tráfego para outras operações no sistema; e outro fatores discutidoabaixo. O sistema pode fornecer resultados usáveis com os nós de demandaformulados de acordo com qualquer esquema razoável. Contudo, é altamentedesejável formular as demandas de acordo com um processo tal como umprocesso de formulação de nó de demanda ainda discutido abaixo.

No próximo estágio 102 do processo, as demandas sãocolocadas em uma ordem, referida aqui como uma ordem "topológica ". Estaordem define a ordem na qual as demandas serão tratadas pelo sistema naoperação de programação. O estágio de ordenar etapa é efetuadaprincipalmente ordenando as demandas de acordo com uma ou mais chavesde ordenação, cada tal chave de ordenação sendo com base em um ou maiselementos dos dados associados com um nó de demanda. Por exemplo, um nóde demanda pode ser ordenado por data e hora de partida, com ou sem outrosfatores tal como contribuição esperada para CTM. De forma alternativa, aorigem e destinação de um nós de demanda podem ser usados como chavesde ordenação, tal que vôos entre cidades particulares são colocados na ordemmais alta.

Uma vez que as demandas forem colocadas na ordem noestágio 102, o sistema começa com um estado de sistema inicial assumido.Este estado de sistema inclui dados definindo disponibilidade de recursos quesão requeridos para efetuar as operações de transporte. Esses recursos incluemrecursos móveis tais como aeronave ou outros veículos usado na operação; emembros de tripulação, assim como recursos fixos que podem ser associadoscomo pontos de origem ou pontos de destinação, como por exemplo, portõesde aeroportos. O sistema então trata as demandas em ordem de acordo com aordenação topológica designada no estágio 102. Assim sendo, no estágio 106,o sistema simplesmente pega a primeira demanda no topo da lista ordenada, etrabalha com aquela demanda no estágio 108 para calcular um fragmento deprogramação para aquela particular demanda. O processo de calcular ofragmento de programação envolve, seleção de recursos a ser aplicada parcoincidir com a demanda in tal uma maneira como para produzir um resultadofactível, e, de forma desejável, o melhor resultado obtido dado o estado dosistema. Por exemplo, o sistema pode procurar selecionar uma particularaeronave e tripulação que irá conduzir ao melhor resultado da operação, talcomo a melhor CTM, para o particular segmento. Deve ser apreciado queotimização do fragmento de programação para uma operação particular é umproblema relativamente simples; o número de possibilidades para um dado nóde demanda é delimitado pelo número de recursos disponíveis no sistema, enão cresce com o número de nós de demanda. O processo de calcular ofragmento de programações pode incluir adaptação. Como discutido abaixo, otermo "adaptação "como usado aqui se refere ao ajuste das suposições iniciaisaplicadas em uma seleção ou processo de otimização. Por exemplo, enquantoa demanda pode especificar um vôo saindo de Cleveland às 6:00 p.m. comcapacidade para 150 passageiros, o processo de configurar um fragmento deprogramação inclui examinar os resultados que poderiam ser alcançadospartindo em horas um pouco mais tarde, ou com aeronave menor, ou ambos.

Uma vez que o sistema selecionou um factível e, maispreferencialmente, ótimo conjunto de recursos a ser aplicado para a particulardemanda sob consideração, os recursos são compromissados para a particulardemanda sendo tratada. Isto resulta em configurar um novo estado de sistemano estágio 110. Assim sendo, uma lista de que aeronave está disponível emque horas é modificada para indicar que a aeronave designada para umademanda tratada no estágio 108 pode não mais ser considerada disponível nadata e hora considerados no estágio 108. De forma similar, os membros datripulação designados para a particular demanda tratada no estágio 108 nãoirão estar mais disponível, e assim por diante. O sistema então cicla de voltapara o estágio 106, onde quando o sistema trata a próxima demanda agora notopo da lista. Assim sendo, em cada ciclo, o sistema considera uma demanda etenta encontrar uma configuração factível de recursos para aquela demanda, emais, de forma desejável, um conjunto ótimo de recursos. Este processocontinua até todos os nós de demanda terem sido processados, no estágio 112.

Como colocado acima, durante calculo do fragmento deprogramação para cada demanda, o sistema avalia uma função de resultado,mais freqüentemente um resultado financeiro tal como CTM associado com oconjunto de recursos designado para ir de encontro com o nó de demanda. Osistema também grava este resultado como o resultado esperado para ofragmento de programação e agrega este resultado com os resultadosassociados com todos os outros fragmento de programações calculadosanteriormente para conduzir a um resultado esperado agregado, tal comoCTM agregado para a programação como um todo.O resultado esperado talcomo CTM neste estágio da operação é mais preciso do que o CTM ideal donó de demanda original. O resultado esperado após cálculo do fragmento deprogramação reflete resultados que podem ser alcançados com os recursosdisponíveis. Em alguns casos, o sistema pode não ser capaz de encontrar umaconfiguração factível de recursos, e naquele caso, pode retornar um resultadoindicando que a demanda não será atendida. O sistema também pode manteracompanhamento desses recursos.

Quando o sistema processou a última demanda no estágio 112,o sistema desenvolveu uma programação completa definindo alocações derecursos para todas das demandas, ou pelo menos aquele conjunto secundárioque pode ser servido pelos recursos disponíveis e que não são excluídos poroutros critérios discutidos abaixo. O número de cálculo a ser efetuado em umciclo completo através das etapas 106-112 para produzir uma programaçãocompleta é limitada e não aumenta de forma exponencial, com o tamanho daoperação a ser programada. Todos os cálculos requeridos para completar umaprogramação completa podem ser efetuados em uns poucos minutos ou menosem um computador pessoal convencional programado para efetuar asoperações discutidas aqui. Porque a operação de programação pode serefetuada de forma rápida, as suposições usadas ao desenvolver a programaçãopodem ser mudadas,e o processo de programar pode ser repetido. Comoindicado no estágio 114, o sistema de computador ou um operador manualpode observar o resultado agregado da operação de programação, porexemplo, através da avaliação do CTM agregado, dos números de demandasque não são atendidas ou o similar, e tomar uma decisão de repetir o processode programação. Aquela decisão pode incluir uma decisão no estágio 116 paraajustar o nível de recursos tornados disponível para a operação deprogramação, Como por exemplo, o número de aeronave ou tripulações, erepetir a operação de programação começando no estágio 104 e continuandoaté a programação adicional total ter sido completada.

Porque é factível calcular programações de forma rápida, esteciclo pode ser repetido mais e mais de novo, até um nível ótimo recursos queretorna o melhor resultado, tal como a mais alta CTM ou o menor número dedemandas não atendidas, é encontrado. De forma alternativa ou adicional, osistema ou um operador manual pode instruir o sistema para mudar, ou ospressupostos usados na formulação como demandas no estágio 100, ou aordem de ordenação aplicada no estágio de ordenação topológica 102. Porexemplo, o sistema de programação pode ser usado em conjunto com ummódulo de prognóstico de receita que aplica uma teoria de jogo para testarvários níveis de tarifa, serviços de níveis ou auxiliares (e. g., uma permissãode bagagem ou serviço de refeição associada com um vôo) ou outros fatoresversus informação conhecida considerando competição. Diferentes suposiçõesaplicadas na teoria de jogo conduzem a diferentes estimativas decompartilhamento de mercado e então diferentes números de passageirosesperados e diferente receita esperada por passageiro nos nós de demanda. Noestágio de estratégia de mudança 118, o sistema de teoria de jogo (nãomostrado) pode ser instruído para tentar uma suposição diferenteconsiderando tarifas a serem mudadas ou serviços a serem oferecidos pelacompanhia de linha aérea usando o sistema de programação e as respostas decompetidores para aquelas tarifas, e que resulta em prognósticos diferentes decarga de passageiros, e então diferentes demandas no estágio 100. Diferentesestimativas de compartilhamento de mercado podem ser aplicadas para váriasporções do cálculo de demanda como por exemplo, para compartilhamento demercado diferentes, junto com as rotas atendidas por diferentes competidores.

As chaves de ordenação e ordem de ordenação aplicadas, no estágio deordenação topológica 102, também podem ser variadas. Assim sendo,essencialmente qualquer elemento da estratégia usada pela companhia delinha aérea pode ser mudado. Aqui de novo, porque o sistema de programaçãopode gerar uma programação completa para meses de operação em unspoucos minutos, é factível calcular programações para inúmeros pressupostosde estratégia, e assim sendo achar os melhores pressupostos de estratégia.

Um processo para formular as demandas (etapa 100 da FIG. 1)é mostrado em maiores detalhes na FIGS. 2-9. O processo começa carregandoos dados histórico descrevendo as vendas de bilhetes por todas astransportadoras atendendo as cidades a serem servidas pela companhia delinha aérea. Estes dados de passageiros tipicamente são fornecidos na formade registros de nomes de passageiros ou "PNRs", cada um dos quais reflete aviagem por um passageiro individual. Cada PNR tipicamente reflete a origeme destinação do passageiro; o preço pago para transporte entre a origem edestinação; a classe de serviço como definida pela transportadora quetransporta o passageiro. Dados de PNR estão comercialmente disponíveisdentro da indústria de companhia de linha aérea. De forma desejável, pelomenos, um ano de dados histórico é usado.

No próximo estágio 152 do processo, o sistema compila osdados históricos para cada par de cidades de origem e destino. O sistema podefazer compilações separadas para diferentes configurações de dias durante operíodo tratado. Por exemplo, o sistema pode compilar um conjunto de dadospara cada origem e destinação, com respeito a todos os dias da semana; oualternativamente, um conjunto de dados para todas as Segundas-feiras duranteo período histórico em questão, uma outra configuração de dados para todasas Terças-feiras durante o mesmo período, e assim por diante. Cada períodohistórico de forma desejável e menos do que um ano completo como, porexemplo, um mês, tal que conjuntos de dados compilados para diferentesperíodos tal como diferentes meses podem ser comparados um com o outropara detectar padrões de variação periódica. Também, conjuntos de dadoscompilados para diferentes períodos históricos podem ser comparados umcom o outro para detectar tendências de crescimento na viagem em cidadesparticulares de origem e de destino, Por exemplo, se mais do que um valor dedados do ano está disponível, o número de passageiros transportados entre acidade particular de origem e cidade de destino em dias da semana emFevereiro do último ano pode se comparada com o número comparável paraFevereiro do ano anterior para derivar uma estimativa de crescimento ano aano. A compilação para cada conjunto de dias durante o período históricoinclui dados considerando o número de passageiros partindo a cada particularhora de hora de partida em cada classe de serviço oferecido através de váriastransportadoras servindo as cidades durante o período histórico em questão, etambém inclui dados sobre a tarifa média paga pelos passageiros para cada talclasse de serviço.

Os dados de hora de partida dados reflete o comportamento dopassageiro com as programações oferecidas pela companhia de linha aéreasservindo a origem e destinação durante o período histórico em questão. Estesdados são representados de forma gráfica na FIG. 3. Por exemplo, a barra 154representa o número de passageiros viajando em classe econômica em um vôoda companhia de linha aérea A partindo às 8:30 a.m., o estágio que a barra156 representa o número médio de passageiros transportados na primeiraclasse no mesmo vôo da companhia de linha aérea A, o estágio que a barra158 representa o número médio de passageiros transportados em um vôo declasse única da companhia de linha aérea B partindo às 8:45 a.m.

Em um estágio 160 adicional do processo, uma informaçãohistórica é resumida misturando junto os passageiros partindo durante umintervalo de tempo definido referido aqui como uma janela, como porexemplo, a janela particular de uma hora ou duas horas durante o dia, e asclasses de serviço oferecidas pelas várias companhias de linha aéreas sãomapeadas para a sistema mais próximas classes de serviço comparadas aserem oferecidas pela companhia de linha aérea sendo programada. O sistemaassim sendo forma uma demografia de par de cidades histórica para cadaclasse da companhia de linha aérea sendo programada para cada janela. Porexemplo, como mostrado de forma gráfica na FIG. 4, a barra 162 representa onúmero médio de passageiros que partiram da particular origem para aparticular destinação em um dia de semana meio e adquiriram bilhetes emclasses de serviço em todas as transportadoras correspondendo à grosso modoà classe econômica da transportadora sendo programada. De forma similar, abarra 164 representa o número médio de passageiros para a primeira classedurante a mesma janela em um dia de semana médio. Embora um processo decompilação e abstração 152 e 160 são mostrados como processos separadospara clareza da ilustração, esses processos podem se sobrepor. Por exemplo,como cada registro de PNR é examinado, a classe de serviço pode sertransladada da classe de serviço da transportadora usada de forma efetiva,para a classe de serviço média da transportadora sendo programada.

Em efeito, cada janela representa um mercado de passageirosem potencial que é distinto, em certa extensão, do mercado representado poroutras janelas durante o dia. Os tamanhos das janelas podem ser variados parapares de cidade diferentes através de seleção manual ou automáticadependendo de fatores tais como o número de vôos servindo o par de cidade.Por exemplo, onde duas cidades são conectadas através de somente dois vôospor dia, o tamanho da janela pode ser de 12 horas,- onde cidades sãoconectadas através de dúzias de vôos por dia (tal como New York e Chicago),o tamanho da janela pode ser menos do que uma hora.

O sistema pode designar uma hora de partida arbitrária dentroda janela usada no processo de abstração, como por exemplo, o centro dajanela. Mais preferencialmente, o sistema computa a hora de partida médiados passageiros incluídos na demografia com base nas horas de partidahistóricas incorporados na demografia, e atribui aquela hora média como ahora de partida do demografia de par de cidades. O sistema pode tambémobter uma medida da variância da hora na demografia, i. e., a medida darelação entre a hora dentro da janela e número de passageiros.

O sistema também computa uma tarifa histórica média emtermos das classes de serviço a serem oferecidas pela transportadora sendoprogramada. Assim sendo, como a classe de viagem para cada registro denome de passageiro é coincido com uma classe comparável na transportadorasendo programada, uma tarifa histórica paga pelo passageiro em questão éconsiderada como uma tarifa que o mesmo passageiro teria pago para viajarna classe comparável na transportadora sendo programada. Essas tarifas sãomédias sobre todos os passageiros incluídos na demografia para conduzir auma tarifa histórica média associada com a classe e janela.

Assim sendo, na conclusão do processo de compilação e deabstração, o sistema tem um conjunto de demografias de pares de cidadeshistóricas para cada par de cidades de origem e de destino. Cada demografiade par de cidades histórica inclui uma hora de partida, um número depassageiros, e um tarifa média para cada classe de serviço da transportadorasendo programada, e pode incluir dados adicionais tal como um medida devariância na hora de partida.

Estas demografias de pares de cidades históricas são entãoconvertidas para demografias de par de cidades previstas em um estágioadicional 168 do processo. Como discutido acima, uma demografia históricapara cada par de cidades representa passageiros transportados por todas astransportadoras. O número de passageiros em cada demografia de par decidades histórica é multiplicado por um compartilhamento de mercadoprognosticado para a companhia de linha aérea sendo programada noparticular mercado representado pela demografia. Por exemplo, se umdemografia de par de cidades histórica indica que 600 passageiros da classeeconômica e 100 passageiros da primeira classe partem de Seattle para NewYork em um dia de semana médio entre 6:00 p.m. e 8:00 p.m., e ocompartilhamento estimado de mercado alcançado pela transportadora sendoprogramada é 20%, então a demografia de par de cidades prevista vai indicarque a companhia de linha aérea pode esperar 120 passageiros de classeeconômica e 20 passageiros de primeira classe. De forma similar, um fator decrescimento pode ser aplicado para levar em conta o crescimento de ano a ano(ou diminuição) no tráfego entre as cidades de origem e de destino. Ainda, umtarifa média prevista para cada classe de serviço que a companhia de linhaaérea vai realizar é incluída em cada demografia prevista de par de cidades. Oprognóstico de compartilhamento de mercado como uma função de tarifamédia pode ser feito de modo intuitiva, mas preferencialmente é feitoaplicando técnicas tal como teoria de jogo que leva em conta ocomportamentos competitivos no mercado. Em um modo alternativo,alternativamente, compartilhamento histórico de mercado e dados históricosde tarifa podem ser usados, com base na suposição que nenhuma dascompanhias de linha aéreas servindo o mercado vai mudar sua estratégia depreço.

As demografia de par de cidades previstas resultantes doestágio 168 são convertidas para nós de demanda, i. e., demandas individuaispara transporte entre origens e destinações ao longo das rotas servidas pelacompanhia de linha aérea sendo programada através do processo mostrado navisão geral da FIG. 5. No primeiro estágio 180 deste processo, cadademografia de par de cidades é convertida para uma demografia de rotaatravés das etapas mostradas em maiores detalhes na FIG. 6. O processo daFIG. 6 assume que a companhia de linha aérea determinou quais os pares decidades que serão servido por vôos direto, sem escala, entre as cidades, eentão tem uma lista de cidades conectadas diretamente. Cada par de cidadesconectadas diretamente é referida aqui como uma "rota ". O sistema pega umalista de demografias de pares de cidades e então trata cada demografia de parde cidades em ordem. No estágio 185, o sistema seleciona o caminho maiscurto de todas as rotas disponíveis que conecta a cidade de origem dademografia de par de cidades com a cidade de destino. Por exemplo, osistema pode examinar todas as rotar que tem origem na cidade de origem dademografia de par de cidades e determina se qualquer dessas rotas tem suasdestinações na cidade de destino da demografia de par de cidades. Se sim,aquela rota é direta, rota sem escala, e então, é mais curta. Se não, o sistemapode examinar a cidade de destino de cada rota tendo sua origem na cidade deorigem da demografia de par de cidades e selecionar um conjunto de cidadesque constituem as cidades de destino daquelas rotas. O sistema pode entãoconsiderar cada tal destinação por sua vez, e ver se há uma rota tendo suaorigem em tal cidade de destino e sua destinação na destinação da demografiade par de cidades. Se sim, o sistema grava a combinação de comprimentoagregado de duas rotas e continua tal verificação até tais combinações de duasrotas terem sido encontradas. O sistema então considera as combinaçõesdisponíveis de duas rotas e seleciona a combinação que tem o menorcomprimento total. Se nenhuma combinação de duas rotas é encontrada, osistema pode então procurar por uma combinação de três rotas em umamaneira análoga de forma direta.

Em uma variante desta abordagem, o sistema pode tratar certascidades como cidades de interconexão, tal que se não há caminho de rotaúnico, direto, o sistema irá procurar construir caminhos de duas rotas e de trêsrotas usando vôos passando através das cidades de interconexão. Isto reduzgrandemente o número de possibilidades a serem consideradas na formulaçãode caminhos de duas rotas e de três rotas.

Em uma ainda variante, o sistema pode excluir rotas, indo nadireção errada, da cidade de origem ou de uma cidade de interconexão, i. e.,rotas para as quais a cidade de destino da rota é ainda mais a partir da cidadede destino da demografia de par de cidades do que a cidade de origem da rota.

Isto ainda limita o número de rotas a ser considerada na procura de caminhosde duas rotas e três rotas. O comprimento de cada rota considerada nesteprocesso pode ser a milhagem geográfica efetiva entre as cidades, ou pode seruma pontuação com base em milhagem geográfica e outros fatores tais comotaxas de desembarque ou congestionamento em particulares aeroportos.

Uma vez que o sistema encontrou o caminho de rota maiscurto para uma particular demografia de par de cidades, o sistema cria umademografia de rota para cada rota neste caminho mais curto no estágio 187.

Se a rota mais curta acontece ser um caminho de rota única, i. e., uma rotadireta, sem escala, então a demografia de rota é idêntica à demografia de parde cidades original. Contudo, se o caminho é um caminho de múltiplas rotas,o sistema constrói uma primeira demografia de rota tendo sua origem nacidade de origem da demografia de par de cidades, tendo a destinação como adestinação da primeiro rota, e tendo a hora de partida como a hora de partidada demografia de par de cidades. A receita esperada por passageiro para aprimeira demografia de rota é uma porção da receita esperada por passageiro.

A proporção da receita esperada pode ser feita com base no comprimento darota, i. e., a receita esperada para a primeira rota pode ser a receita esperadapara a demografia de par de cidades dividida pelo comprimento total de todasas rotas no caminho e multiplicado pelo comprimento da própria primeirarota. O sistema também cria uma demografia de rota para a segunda rota nocaminho. Esta demografia de rota tem, sua cidade de partida como a cidade dedestino da primeira rota, sua cidade de destino como a cidade de destino dasegunda rota, e sua hora de partida igual à hora de partida da demografia depar de cidades mais a hora de vôo esperada junto com a primeira rota e umapermissão de hora de transferência. Aqui de novo, a receita esperada para asegunda rota é a porção da receita esperada por passageiro para a demografiade par de cidades como um todo, calculada através do comprimento comodiscutido acima para a primeira rota. No caso de um caminho de múltiplasrotas, a demografia de rota para cada rota no caminho pode ser anotada paraindicar que a rota é ou uma rota alimentadora (onde há uma rota subseqüenteno caminho), ou uma rota receptora (onde há uma rota anterior no caminho),ou ambas.

Uma vez que demografias de rota foram configuradas paratodas as rotas no caminho, o sistema retorna ao 181 e repete o processo dasetapas 185 e 187 para a próxima demografia de par de cidades, até todas asdemografia de pares de cidades tenham sido tratadas e convertidas emdemografia de rota. Cada demografia de rota identifica suas datas deaplicabilidade na mesma maneira como uma demografia de par de cidades.Por exemplo, a demografia de rota derivada de uma demografia de par decidades aplicável somente para as Segundas-Feiras em Fevereiro seria, damesma forma, também aplicável somente as Segundas-Feiras em Fevereiro.

Após as demografias de rota terem sido formadas, elas sãousadas no próximo estágio 190 do processo mostrado na FIG. 5 para criaruma lista de nós de demanda. Cada rota é tomada por vez. Para cada rota, umalista de demografias de rota tendo origem e destinação correspondendo para arota em questão é compilada a partir das demografias de rota formadas noestágio 180. A lista de demografias de rota para cada rota é convertida em umconjunto de nós de nós de demanda para cada dia de aplicabilidade dademografia de rota em questão. Por exemplo, a demografia de rota aplicávelpara as Segundas-Feiras em Fevereiro seria convertida em um nó de demandapara a data correspondendo à primeira Segunda-Feira em Fevereiro, um outronó de nó de demanda para a data correspondendo à segunda Segunda-Feiraem Fevereiro, e assim por diante. O sistema pode também levar em conta umconhecimento intuitivo ou anterior disponível para o operador. Por exemplo,se dados históricos são compilados para vôos de dias de semana, e o operadorestá ciente que uma particular data será um feriado religioso na origem ou nadestinação, o sistema pode reduzir o número de passageiros esperados paraaquela particular data. Após todas as demografia de rota, correspondendo auma particular rota, terem sido processadas, o sistema pega a próxima rota, eprocessa as demografias de rota para aquela rota na mesma maneira. Esteprocesso continua até todas as demografias de rota para todas as rotas teremsido processadas. Neste ponto, há uma lista inicial de nós de demanda paracada rota. Cada tal nó de demanda inclui todas as características dademografia de rota, tal como a origem, a destinação, uma data e hora departida, uma receita esperada por passageiro para cada classe, e um número depassageiros esperados em cada classe.

No próximo estágio 200 do processo, o sistema verifica os nósde demanda na lista inicial como mostrado em maiores detalhes na FIG. 7.

Esta verificação começa com uma lista de rotas no estágio 202, e pega cadarota por vez no estágio 204. Para cada rota, o sistema obtém a lista de nós dedemanda para a rota no estágio 206. Esta lista não necessita estar em qualquerordem particular. Uma vez que a lista de nós de demanda para uma particularrota foi recuperada, o sistema começa com um primeiro nó de demanda nalista. O sistema pega o primeiro nó de demanda na lista no estágio 208 eprocessa o nó de demanda para selecionar a melhor aeronave para uso em umvôo de encontro aquele nó de demanda, i. e., um vôo da origem para adestinação com o número esperado de passageiros. O sistema verifica todosos tipos de aeronave usados pela companhia aérea sendo programada, eseleciona o tipo de aeronave que, se fluindo da origem para a cidade dedestino com o número de passageiros especificado no nó de demanda, iráconduzir à maior contribuição para a margem. Neste estágio do processo, aseleção de um "melhor" tipo de aeronave é feita sem a consideração de seuma aeronave deste tipo estará disponível de modo efetivo na data e horaespecificadas por um nó de demanda, e sem consideração de custos quepoderiam incorrer em tornar a aeronave disponível em tal data e hora, comopor exemplo, transbordando a aeronave a partir de uma localização distante.

Assim sendo, a contribuição para margem caracterizada neste estágio doprocesso apresenta um limite superior no retorno a ser esperado ao atender umnó de demanda.

No próximo estágio 212 do processo, o sistema compara onúmero de passageiros especificado no nó de demanda contra o número depassageiros que podem ser transportados pela melhor aeronave selecionada noestágio 210. Se o número de passageiros especificado no nó de demanda émenos do que ou igual à capacidade da melhor aeronave selecionada, osistema marca um nó de demanda como processado, anota um nó de demandacom uma contribuição esperada para margem, e retorna à etapa 208 paraprocessar o próximo nó de demanda. Contudo, se o número de passageirosespecificado no nó de demanda é maior do que a capacidade de transporte damelhor aeronave selecionada, o sistema apaga o nó de demanda original dalista e divide um nó de demanda em dois menores nós de demanda no estágio214 e adiciona esses nós de demanda menores para uma lista de nós dedemanda para a rota, onde quando o sistema de novo retorna à etapa 208 parapegar o próximo nó de demanda não processado. Um dos novos menores nósde demanda pode constituir o próximo nó de demanda a ser processado. Omenor dos nós de demanda criado a partir de um grande nó de demanda éidêntico ao nó de demanda original, mas cada um dos novos menores nós dedemanda tem uma metade do número de passageiros especificado no nó dedemanda original. Os nós de demandas adicionais têm a mesma hora departida que o nó de demanda original. Os nós de demandas adicionais sãoprocessados na mesma maneira que os outros nós de demanda em uma lista.

Assim sendo, um bem grande nó de demanda pode ser dividido em dois nósde demanda na primeiro estágio através do estágio 212. Quando cada umdesses nós de demanda menores é processado, um ou mais pode ser divididode novo em ainda nós de demanda menores. Também, quando tal umadivisão, nó de demanda menor é processado no estágio 210, a melhoraeronave selecionada para aquele nó de demanda pode ser diferente da melhoraeronave selecionada para o grande nó de demanda original.

O processo continua desta maneira até todos os nós dedemanda para a rota (incluindo qualquer nó de demanda menor resultante dadivisão no estágio 214) foram processados, onde quando o sistema pega apróxima rota no estágio 204 e a lista de nós de demanda associada com a novarota, e repete o mesmo processo. Isto continua até todas as rotas terem sidoprocessadas na mesma maneira.

A lista de nós de demanda de saída resultante é passada paraum estágio adicional 220 (FIGS. 5 e 8). Neste estágio, o sistema examina alista de nós de demanda para cada rota e determina se um CTM esperado podeser encontrado combinando nós de demanda um como o outro. Este estágioseleciona uma rota particular da lista de rotas e ordena todos os nós dedemanda a partir do estágio 200 (FIG. 5), por hora de partida. No estágio 224do estágio 220 (FIG. 8), o sistema seleciona um conjunto dos três maisrecentes nós de demanda na lista ordenada. O sistema então tenta no estágio226 criar um nó combinada dos primeiros dois dos três nós selecionados.

Este processo computa um intervalo de tempo para cada umdos dois nós de demanda. Este intervalo de tempo para cada nó de demanda écom base em uma estimativa da maneira na qual a carga de passageiro vaivariar com o tempo se um vôo é deslocado no tempo a partir da horaespecificada no nó de demanda. Como representado de forma gráfica na FIG.9, a variância na carga de passageiro com hora de partida para um nó dedemanda 250 pode ser representada por uma função de etapa mostrada pelasbarras listradas. A função de etapa tem um valor máximo de N25O igual aonúmero de passageiros no nó de demanda, na hora de partida original T25o donó de demanda, e tendo de forma progressiva, valores mais baixos para horasde partida mais cedo e mais tarde. Este intervalo significante para um nó dedemanda pode ser tomado como entre a hora mais cedo e mais tarde para quea função de etapa tenha um valor maior do que algum número arbitrário depassageiros. A função de etapa pode ser com base em uma suposição globalpara o sistema como um todo, ou alternativamente, pode ser selecionada combase em um conhecimento anterior associado com rotas particulares. Porexemplo, nós de demanda servindo destinações de negócios conhecidas talcomo New York City ou Washington, D. C. podem ser designados a umafunção do estágio de declínio estreito, para refletir uma suposição queviajantes á negócios de forma geral, estão em uma programação restritaamarrada, o estágio que nós de demanda tendo uma destinação ou origem emuma localização de local de veraneio tal como Orlando, Florida, podem serdesignados à amplas variâncias de forma considerável com base na suposiçãoque viajantes de férias são relativamente não sensitivas à programação.

Em ainda uma outra modalidade, uma estimativa da variânciada carga de passageiro com a hora de partida pode ser obtida dos dadoshistóricos usados para gerar os dados históricos de passageiros e demografiade pares de cidades. Por exemplo, se os dados históricos de passageirosmostram substancialmente igual números de passageiros partindo em muitashoras diferentes, amplamente espaçadas em torno do ponto médio da janelausada no processo de abstração (etapa 150), à demografia de par de cidadespode ser designado uma grande variância, e a esta variância pode serdesignada para cada demografia de rota derivada de tal demografia de par decidades no estágio 180 e transportados à frente em cada nó de demanda criadaa partir da demografia de rota. Adicionalmente, a variância para um particularnó de demanda pode ser lateral simples ou assimétrica sobre a hora de partidade um nó de demanda. Por exemplo, se um particular nó de demanda édenotado com uma indicação que este nó de demanda é derivado dademografia de rota que representa o segundo ou subseqüente demografia derota em um rota de múltiplo caminho (etapa 180), a variância ou função deetapa pode ser arrumada para declinar gradualmente para horas de partidaapós a hora de partida original do nó de demanda, mas pode cairabruptamente para zero passageiros para todas as horas de partida antes dahora de partida original do nó de demanda, refletindo a realidade que se umvôo de conexão passa mais cedo, os passageiros do vôo mais cedo nocaminho não estarão disponíveis.

Uma função relacionando o número de passageiros por horapara cada nó de demanda tem um intervalo de significância limitado pelashoras mais cedo e mais tarde no qual qualquer número apreciável dospassageiros representados através de um nó de demanda seria desejoso paraviajar ao longo da rota. Por exemplo, a função de etapa para nó de demanda250 tem um intervalo de significância a partir da hora T2Soe para a hora T259l.Um outro nó de demanda 252 tendo hora de partida T25o tem uma função devariância representada pela barras sem sombras na FIG. 9, com um intervalode significância de T252E para T252l- O sistema examines o intervalo designificâncias dos dois nós de demanda e determina se o intervalo designificâncias se sobrepõem. Se eles não se sobrepõem, a tentativa decombinar esses dois nós de demanda é abandonada, e o estágio 226 écompletado. Contudo, se esses intervalos de significâncias se sobrepõem, osistema seleciona um conjunto de possíveis horas de partida para um nó dedemanda combinado. A hora de partida mais cedo possível é ou a hora maiscedo no intervalo de horas englobadas pelo intervalo de significâncias sesobrepondo, ou a hora de partida original do nó de demanda mais recente,prevalecendo a que for mais tarde. A hora de partida mais tarde possível é ahora mais tarde englobada pelos intervalos de significâncias se sobrepondodos dois nós de demanda, ou a hora de partida do último nó de demanda,prevalecendo a que for mais cedo. Por exemplo, o intervalo de significânciasde nós de demanda 250 e 252 se sobrepõem a partir da hora T252E para a horatempo T250L- Assim sendo, a hora de partida mais cedo possível para um nócombinado seria T252e e a hora de partida mais tarde possível seria T250l- Narealidade, sobrepondo o intervalo de significâncias para dois nós de demandana mesma rota e mesmo dia indica que um vôo ao longo da rota partindodurante o intervalo de sobreposição atrairia alguns passageiros associadoscom o nó de demanda anterior e alguns passageiros associados com o últimonó de demanda. O sistema também calcula uma ou mais horas de partidaintermediárias possíveis entre as horas de partida mais cedo e mais tarde, Porexemplo, o sistema pode calcular uma tal hora de partida intermediária comoo ponto médio entre as horas de partida mais cedo e mais tarde.

Para cada hora de partida possível, o sistema determina onúmero de passageiros esperado para tal hora de partida. O sistema avalia afunção de etapa para cada nó de demanda na hora de partida possível eadiciona o valor das funções de etapa para ambos nós de demanda paraparticular hora de partida para conduzir a um número de passageirosesperados para um nó combinado operando naquela hora de partida possível.Por exemplo, o número de passageiros esperados para um vôo partindo nahora T252e é a soma de Na e Nb (FIG. 9).

O sistema então calcula a melhor aeronave para um nó dedemanda em cada hora de partida possível e calcula a CTM para aquela horade partida possível. No estágio de combinação, se o número de passageirosesperados excede a capacidade da melhor aeronave, o número de passageirosesperados é configurado igual à capacidade da aeronave. O sistema comparaas CTMs para as horas de partida possíveis e seleciona a melhor como oresultado de combinar o primeiros dois nós de demanda, onde quando oestágio 226 termina. O sistema então tenta combinar os segundos dois nós dedemanda no estágio 240 exatamente na mesma maneira e tenta combinartodos os três dos nós de demanda selecionados no estágio 242. O processo decombinar três nós de demanda pode assumir que esses nós de demanda sãopara serem combinados em dois nós de demanda tendo duas horas de partidadiferentes, e usa uma grande quantidade de horas de partida possíveis dentrodo intervalo da hora de partida do mais cedo ou do primeiro nó de demandapara a hora de partida do mais tarde ou do terceiro nó de demanda e calcula acarga de passageiro combinada em cada hora de partida possível com base nasfunções de etapa das três demandas selecionadas, e uma vez mais seleciona amelhor aeronave e computa CTMs para a melhor aeronave para cada hora departida possível. O melhor CTM agregado para os dois nós de demanda éemitido como o resultado do estágio 242.

No estágio 244, o sistema compara as CTMs resultantes apartir das combinações de dois nós das etapas 226 e 240 e da combinação detrês nós do estágio 242, e pega a melhor dessas CTMs e emite um resultadoincluindo a hora de partida possível, a CTM esperada para os nóscombinados, e a identidade dos nós que irão combinar para conduzir aos nóscombinados, i. e., os primeiros dois, os segundos dois, ou todos os três dosnós considerados. No estágio 246, o sistema compara a CTM com o nócombinado emitido pelo estágio 244 com a soma das CTMs para os nósindividuais que foram usados para formar o nó combinado. Se os nóscombinados conduzem a CTM maior do que a soma das CTMs para os nósindividuais, o sistema vai para o estágio 248 e substitui os nós individuaisusados para formar o nó de saída combinado com o nó ou nós combinados, eentão retorna à etapa 224. Se não, o sistema retorna diretamente à etapa 244sem substituir os nós individuais. No estágio 224, o sistema pega um outroconjunto de três nós de demanda, incluindo o último nó de demanda noconjunto processado anteriormente e os dois nós de demanda que sucedem. Osistema então trata este novo conjunto de nós de demanda na mesma maneira.

Isto continua até não haver mais nós de demanda para serem processados,onde quando o sistema vai de volta à etapa 221 e seleciona a próxima rota,que é processada na mesma maneira. Isto continua até todas as rotas teremsido processadas.

Neste processo de combinação, o sistema pode reverter algumadas divisões feitas no estágio secundário 214 (FIG. 7) da residual demandaprocesso de demanda residual 200. Por exemplo, se um bem grande nó dedemanda foi dividido em dois nós de demanda, os dois nós de demandapodem ser combinados de volta de novo em um maior nó de demanda noestágio 226 ou etapa 240.

Neste ponto no processo, o estágio de formular demandas(etapa 100 na FIG. 1) está completo. O sistema então coloca uns nós dedemanda em uma ordem, referida aqui como ordem topológica. Isto é feitoordenando as demandas de acordo com uma ou mais chaves de ordenação.

Uma chave de ordenação pode incluir qualquer característica das demandas.

Uma simples chave de ordenação consiste da data e hora de partidaespecificados na demandas, tal que as demandas são colocadas em ordemcronológica. Contudo, outras chaves de ordenação podem ser usadas, comopor exemplo, ordenando por CTMs esperadas, tal que os vôos mais rentáveissão os primeiros na ordem topológica, ou ordenando por comprimento derotas, tal que as demandas de percurso longo são programadas primeiro ou talque demandas de percurso curto são programadas primeiro. Também, umacompanhia de linha aérea pode desejar dar prioridade aos vôos entre cidadesde conexão designadas tal que nós de demanda tendo cidades de conexãocomo cidades de origem e de destino são tratadas primeiro. Como notadoacima, a demanda de rota pode ser marcada como uma demanda de rotaalimentadora de um caminho de múltipla rota, e os nós de demandaresultantes da demanda de rota alimentadora são da mesma forma marcadas.Esta marca pode ser usada como uma chave de ordenação tal que nós dedemanda alimentadores são tratados primeiro. Em uma variante adicional, aessa e outras características dos nós de demanda podem ser designados fatoresde peso, e um chave de ordenação composta pode ser calculada com base nasvárias características de cada nó de demanda, ponderada por tais fatores. Aescolha da chave de ordenação vai influenciar os resultados alcançados naprogramação em alguns graus. Contudo, na prática, tem sido encontrado quesimplesmente ordenando por data e hora de partida funciona da mesma formaou aproximadamente assim como esquemas mais complexos.

O sistema mantém um banco de dados dos recursosnecessários para efetuar as operações a serem programadas. Para umacompanhia de linha aérea, esses recursos incluem aviões e membro detripulação, ambos do quais são móveis, assim como portões de embarque depassageiros em particulares aeroportos. O banco de dados inclui informaçãosobre as características de cada recurso, e também contém informaçãoenvolvendo o estado de cada recurso em cada hora no futuro durante aduração da programação sendo gerada. Para um avião, as característicastipicamente vão incluir o tipo de avião; sua capacidade de assento em cadaclasse de serviço; seu intervalo máximo (que pode ser colocado como umbloco de tempo máximo); e o custo de usar o avião, tipicamente colocadocomo um custo por hora de vôo. A informação de estado de um avião paracada hora na programação incluiria a localização, como por exemplo,estacionado em um particular aeroporto ou na rota; uma indicação se o aviãoestá fora de serviço para manutenção; e informação sobre o histórico deoperação do avião, tal como o número de horas e dias do calendário deoperação desde a última verificação de manutenção programada e desdeúltimo principal percurso. Para um membro de tripulação, característicasincluiriam qualificações para servir em tipos particulares de aeronave e basede origem. A informação de estado para cada hora incluiria informação talcomo se o membro de tripulação está de serviço ou fora de serviço, alocalização do membro da tripulação em sua base de origem, ou em algumoutro aeroporto, ou na rota, e o número de horas ou vôos desde que o membroda tripulação ficou em serviço, o número de horas do tempo de serviçoacumuladas em cada mês e ano, e qualquer outro dado pertinente para cálculoda disponibilidade de membro da tripulação para vôos sob regulamentaçõesgovernamentais pertinentes, contratos de sindicado, ou políticas de pessoal dacompanhia aérea. As características de um portão incluem identificação deum aeroporto onde o portão está localizado, e pode também incluir tipos deaeronave que podem ser acomodados em particulares portões. Um portãotambém pode ter associada com ele um custo de ocupação tal como pode serimposto para partida atrasada de um avião. O estado para um portãotipicamente é simplesmente uma indicação de se o portão está ocupado ou nãoocupado em cada intervalo durante a programação.

O banco de dados é configurado para um estado inicial querepresenta o estado esperado dos vários recursos no começo da programação.

O sistema pega os nós de demanda na ordem estabelecida peloestágio de ordenação topológica e procura calcular um fragmento deprogramação para cada nó de demanda. Cada fragmento de programaçãoinclui a origem e destinação de um nó de demanda, e condições especificadaspara a operação de vôo que vai satisfazer um nó de demanda. Essas condiçõesincluem uma particular aeronave, uns particulares membros de tripulação, eum particular portão. As condições especificadas são selecionadas tal que elassão factíveis, i. e., tal que a aeronave existe e por outro lado não está ocupado;tal que o espaço ou portão está disponível; e os membros da tripulação sãoqualificados e estão disponíveis. O sistema também procura especificarcondições para o fragmento de programação tal que uma função de resultadorepresentando um resultado esperado para voar o vôo de acordo com ascondições, coincide com um critério. A função mais comum de resultado é acontribuição para margem esperada da operação, e o sistema procuramaximizar a contribuição esperada para a margem da operação.

O problema de selecionar condições a serem especificadas emum fragmento de programação pode ser entendido com referência à FIG. 10.A distância Di entre a aeronave e as condições especificadas representa umacontribuição negativa para a margem ou para o custo associado a voar aaeronave da origem especificada na demanda para a destinação especificadana demanda, e também inclui um custo, se aplicável, para reposicionamentoda aeronave de um outro aeroporto se necessário. A distância D2 representa ocusto de fornecer a tripulação, incluindo ambos custos diretos por hora ecustos extraordinários tal como relocação dos membros da tripulação, tempoextra pago aos membros da tripulação, e o similar. A distância D3 entre ascondições especificadas e as demografias incorporadas no nó de demandarepresenta efeitos negativos na receita resultante da especificação de hora departida diferente da hora de partida especificada no nó de demanda, como porexemplo, onde a aeronave especificada não está disponível no portão deembarque na hora especificado no nó de demanda. Distância D3 tambéminclui qualquer perda de receita resultante da especificação de uma aeronaveque é muito pequena para acomodar a carga de passageiro especificada.Distância D4 representa um custo associado com o espaço ou portão usado noaeroporto de origem e no aeroporto de destino. O sistema procura selecionarcondições tal que a soma de D1 - D4 é em um mínimo dado as restriçõesimposta pelo estado corrente do banco de dados de recursos, i. e.,disponibilidade de recursos como indicado no banco de dados. Aminimização ou maximização não necessita ser uma minimização oumaximização matemática estrita. Colocada de outra maneira, o sistema nãonecessita considerar cada alternativa possível, mas pode de fato considerarsomente algumas alternativas consistentes com os recursos disponíveis a fimde alcançar um mínimo ou máximo local. Contudo, é de forma geral, factívelconsiderar mais ou todos os recursos disponíveis.

Uma implementação do processo usado para selecionarcondições para fragmento de programações é mostrado de forma de diagramana FIG. 11. O processo inicia entrando a lista ordenada de nós de demandaresultante do estágio de ordem topológica discutido acima no estágio 300. Noestágio 302, o sistema verifica para ver se todos os nós de demanda foramtratados. Assumindo que há nós de demanda não tratados, o sistema pega oprimeiro nó de demanda não tratado na lista ordenada no estágio 304. Nasetapas 306 e 308, o sistema tenta selecionar o melhor avião entre os aviõesque estão disponíveis para voar o vôo especificado através da origem,destinação, e hora de partida da demanda. Nessas etapas, o sistema procuraencontrar um avião que, dado o estado corrente do banco de dados derecursos, está indicado como disponível no aeroporto onde o vôo é para seoriginar, ou que pode voar para o aeroporto de origem e tornado disponívelpara o vôo. Dentre essas aeronaves, o sistema procura uma particularaeronave que terá o impacto menos negativo na CTM. Porque é quase sempremelhor usar uma aeronave que já está estacionado no aeroporto de origem, osistema primeiro verifica os aviões que estarão no aeroporto de origem nahora da partida, no estágio 306. Se um avião satisfatório é encontrado, osistema pula o estágio 308, e então, não verifica a possibilidade de usar aviõesque estará localizados em outro lugar na hora da operação.

Um processo de seleção que pode ser usado no estágio 306 émostrado, de forma esquemática, na FIG. 12. No estágio 309, o processoseleciona uma aeronave da frota. Se o banco de dados de recursos indica quea aeronave estará estacionada no aeroporto de origem indicado no nó dedemanda, ou na hora de partida indicado no nó de demanda ou dentro dealguma janela pré-determinada, tal como uma hora após a hora de partida, osistema prossegue para a próximo estágio 312. Ao contrário, o sistemadescarta a aeronave e retorna à etapa de seleção de aeronave 309. No estágio312, o sistema verifica o banco de dados de recursos para determinar se aaeronave foi comprometida com um outro vôo ou com manutenção durante ahora requerida para o vôo especificado no nó de demanda. Se a aeronave nãoestá disponível, de novo, o sistema descarta a aeronave e retorna à etapa 309.Se a aeronave está disponível, o sistema também verifica se a aeronave é umaaeronave factível para uso no vôo especificado no nó de demanda. Porexemplo, o sistema verifica a autonomia de vôo do tipo de aeronave contra ocomprimento do vôo entre os aeroportos de origem e destino. Se a aeronavenão tem suficiente autonomia de vôo, não é uma aeronave factível para o vôo.Outros fatores podem ser considerados ao determinar a possibilidade de serfactível. Por exemplo, se o aeroporto de destino não tem suficientecomprimento de pista para acomodar uma aeronave de um tipo particular,qualquer aeronave daquele tipo pode ser excluído. Assumindo que umaaeronave não é excluído, o sistema no estágio 316 determina a diferença ou"delta "entre a hora que a aeronave se tornará disponível no portão, de acordocom o banco de dados de recursos, versus a hora de partida especificada no nóde demanda. É claro que, se o banco de dados indica que a aeronave estarádisponível na hora de partida requerida, delta seria 0.

Em um estágio adicional 318, um sistema computa fatores depontuação para uso da aeronave selecionada no nó de demanda. Um fator depontuação é baseado na disponibilidade da diferença de hora computada noestágio 316. Este fator de pontuação pode ser baseado em um valor arbitráriopor minuto configurado pela companhia de linha aérea. De forma alternativa,este fator de pontuação pode ser computado com base em uma medida devariância nos nós de demanda, tal como uma função de etapa relacionado onúmero de passageiros na hora de partida discutida acima com referência àFIG. 9. Assim sendo, se um nó de demanda inclui uma função relacionando onúmero de passageiros na hora de partida tal como uma função de etapa daFIG. 9, o sistema pode calcular o número de passageiros esperados com basenaquela função a fim de refletir o efeito da mudança da hora de partida paracoincidir com a hora quando a aeronave estará disponível. A diferença entre onúmero de passageiros no nó de demanda e o número de passageirosresultante da avaliação da variância com a hora, pode ser multiplicada pelareceita esperada por passageiro para obter uma pontuação ou custo associadocom disponibilidade em atraso.

Adicionalmente, o sistema computa uma pontuação ou custocom base no custo por hora de vôo do avião selecionado correntemente. Osistema também computa um delta de assento, i. e., a quantidade através daqual o número de passageiros esperado excede o número de assentos naaeronave. Este custo é simplesmente o produto da diferença entre número deassentos e o número de passageiros multiplicado pela receita esperada porpassageiro na particular classe. O sistema adiciona as várias pontuações ecomputa uma pontuação total. Esta pontuação total representa o efeitonegativo na CTM de voar com a particular aeronave, e assim sendo representaDi da FIG. 10, e também representa o efeito negativo na CTM de qualqueratraso na hora do vôo causado pela seleção da particular aeronave ou qualquerfalta de capacidade, e assim sendo representa D3 na FIG. 10. O sistemaadiciona a aeronave a uma lista de aeronave factível. A posição da aeronavena lista é com base na pontuação. Por conseguinte, a lista é ordenadatopologicamente de acordo com as pontuações das várias aeronaves. Osistema retorna á etapa 309 para processar a próxima aeronave. Se não hámais aeronave a ser processada, o sistema vai para o estágio 322 e pega aaeronave com a mais baixa pontuação na lista e vai para o estágio de seleçãode tripulação 324, FIG. 11. Se nenhuma aeronave é encontrada em uma lista,isto indica que não há aeronave factível disponível no aeroporto de origemespecificado no nó de demanda, e o sistema vai para o estágio 308.

Substancialmente, o estágio 308 é idêntica à etapa 306, excetoque o estágio 308 somente considera as aeronaves que não estão indicadascomo estacionados no aeroporto de origem e inclui etapas secundáriosadicionais para determinar, com base na informação do banco de dados derecursos, se a aeronave pode ser deslocada para o aeroporto de origem àtempo de coincidir com a hora de partida, ou com uma janela especificada, talcomo uma hora, após a hora de partida. Também, no estágio 308, a pontuaçãopara cada aeronave inclui um custo para o vôo a partir do aeroporto onde oavião está localizado na hora relevante para o aeroporto de origem. Senenhum avião é encontrado no estágio 308, isto indica que um nó de demandanão pode se atendido com os recursos no estado indicado pelo banco dedados. Assim sendo, nenhum fragmento de programação é gerado para um nóde demanda. Em vez isso, um nó de demanda é simplesmente marcado noestágio 326 para indicar que este particular nó de demanda foi pulado comoum resultado de não ter nenhum avião factível.

Quando um avião foi selecionado no estágio 306 ou 308, ahora de partida da operação de vôo servindo um nó de demanda é ajustadapara a hora quando a aeronave está disponível, se tal hora é diferente da horaespecificada no nó de demanda. Colocado de outro modo, o sistema adapta ofragmento de programação para ir de encontro aos recursos de aeronavedisponíveis.

Se um avião é selecionado no estágio 306 ou 308, o sistemapassa para o estágio de seleção de tripulação 324. O estágio de seleção detripulação é efetuado em uma maneira similar às etapas de seleção de avião306 e 308. Assim sendo, o sistema verifica tripulações disponíveis, selecionaaquelas que são factíveis, e encontra a tripulação factível de mais baixo custo.O sistema, de forma desejável, também considera o balanceamento de horasdevidas de serviço da tripulação, tal que membros da tripulação não excedamo máximo de horas devidas de serviço por me ou por ano. Por exemplo, umcusto adicional pode ser atribuído a qualquer membro de tripulaçãodiretamente relacionado ao número de horas devidas de serviço anteriormenteprogramado para tal membro de tripulação durante o mês sendo considerado.

O estágio de seleção de tripulação usa a hora de partida e aeronave tipo deaeronave encontrado nas etapas de seleção de avião. Assim sendo, para serfactível, a tripulação precisa ser qualificada a voar a bordo do tipo de aviãoselecionado no estágio 306 ou 308, e precisa estar disponível no aeroporto deorigem na hora de partida estabelecida no estágio 306 ou 308. Também, atripulação precisa ter suficiente horas de serviço devidas remanescentes nahora de partida para permitir a tripulação completar o vôo. O estágio deseleção de tripulação pode primeiro endereçar tripulações que, de acordo como banco de dados de recursos, estarão à disposição no aeroporto de origem, eentão endereçar tripulações que podem ser re-alocadas para o aeroporto deorigem. Também, o estágio de seleção de tripulação pode processartripulações completas para o tipo de aeronave, e então, se nenhuma tripulaçãocompleta podem ser encontrada, o estágio de seleção de tripulação podeprocurar encontrar membros de tripulação individuais para forma umatripulação completa. De forma alternativa ou adicional, o estágio de seleçãode tripulação pode tratar membros da tripulação não tendo nenhum históricode serviço primeiro, e então tratar aqueles membros da tripulação que tenhamtido histórico de serviço desde seu último dia de folga. Isto pode ser útil jáque os cálculos requeridos, para determinar se um particular membro detripulação tem suficientes horas de serviço devido remanescentes dadas todasas restrições em horas de serviço devidas, podem consumir tempo.

Se nenhuma tripulação pode ser encontrada, o sistema nãoforma um fragmento de programação, mas em vez disso vai para o estágio328 e marca o nó como pulado porque nenhuma tripulação estava disponível.Em uma variante, se a falha para encontrar tripulação foi causada pela falta deum membro de tripulação tendo certas qualificações específicas, como porexemplo, a falha para encontrar um piloto qualificado para os Boeing 747s, osistema pode marcar o nó com aquela indicação específica.

Assumindo que a tripulação é encontrada, o sistema computa apontuação refletindo o custo da tripulação como por exemplo, uma pontuaçãoque reflete ambos o salário básico da tripulação e qualquer pagamento deprêmio, como extraordinário, custos de demissão, e vôos de re-alocação detripulação, que estão associados com a tripulação. Esta pontuação representaD2 na FIG. 10. Se a tripulação é encontrada, o sistema vai para o estágio 330 eprocura por portões factíveis na origem e na destinação. Aqui de novo, senenhum portão é encontrado, o sistema não forma um fragmento deprogramação, mas em vez disso marca o nó pulado devido a indisponibilidadede um portão em um particular aeroporto.

Assumindo que um portão é encontrado, o sistema forma umfragmento de programação e implementa este fragmento de programaçãomarcando o banco de dados de recursos para comprometer o avião, atripulação, e os portões encontrados nas etapas precedentes. Assim sendo, osrecursos são indicados como ocupados durante o tempo requerido paracompletar o vôo. Também, o sistema marca o banco de dados para indicarquais os recursos móveis, incluindo o avião e a tripulação, serão posicionadosno aeroporto de destino correspondendo ao final do vôo. O sistema tambématualiza o estado da aeronave para indicar tempo de vôo adicional desde aúltima manutenção, e atualiza o estado dos membros da tripulação paraindicar o tempo de serviço devido adicional que eles terão de dedicar ao vôo.

Neste ponto, o fragmento individual de programação estácompleto. O sistema pode também gravar a contribuição esperada para amargem do vôo se voado de acordo com o fragmento de programação noestágio 336.

Em uma variante, o sistema pode testar o fragmento deprogramação proposto contra um ou mais critérios de descarte antescomprometendo as fontes no estágio 334. Por exemplo, se o fragmento deprogramação proposto resulta em uma contribuição negativa para a margem,o sistema não pode comprometer os recursos, mas em vez disso pode marcarum nó de demanda como pulado devido a CTM negativa e retorna à etapa302. Em uma outra variante adicional, o sistema pode sobrepor o critério dedescarte se um ou mais critérios de retenção são encontrados. Por exemplo, osistema pode ser arrumado para reter o fragmento de programação se um nóde demanda é marcado como um alimentador para uma outra demanda. Emuma variante adicional, os critérios de retenção podem incluir serviço paraparticulares cidades de importância particular para a companhia de linhaaérea. Em uma outra variante adicional, o sistema pode re-examinar algumalocalizações prévias de recursos. Por exemplo, se os resultados das etapas deseleção de aeronave 306 e 308 indicam que nenhuma aeronave está disponívelpara ir de encontro a demanda, ou que a única aeronave disponível para ir deencontro a demanda, levaria à resultados pobres porque eles são muitomenores do que ou muito maiores do que o número de passageiros esperado,o sistema pode examinar a aeronave anteriormente designada para os vôosque vai chegar no aeroporto de origem dentro de poucas horas após a hora departida da demanda sendo tratada e determinar se ele é factível parâmetro re-programação daqueles vôos tal que a aeronave chega mais cedo e, se assim,qual seria o efeito na CTM ou outro resultado. O sistema pode tambémprocurar re-programar um vôo programado anteriormente se o primeiroestágio indica que a aeronave selecionada estará disponível após a hora departida na demanda sendo considerada, e que tal atraso vai reduzir a CTM dademanda sendo considerada. Em uma variante adicional, o sistema pode testaro efeito da divisão ou combinação das demandas neste estágio. Por exemplo,se há uma primeira demanda com uma primeira hora de partida e 100passageiros esperados, e a melhor aeronave disponível tem 200 assentos, osistema pode procurar uma demanda com uma outra hora de partida edeterminar se seria mais rentável combinar as duas demandas. Este estágiopode usar processo similar àquele discutido acima com referência à FIGS. 7 e8. Contudo, neste caso a verificação de combinação possível, uma divisão éefetuada com base naquela aeronave que de modo efetivo estará disponívelnas horas de partida das demandas combinadas ou divididas em questão, maispropriamente do que na melhor aeronave possível.

Após um fragmento de programação ter sido completado paraum nó de demanda ou um nó de demanda ter sido pulado, o sistema verificase há mais nós de demanda a serem tratados no estágio 302. Se assim, osistema pega o próximo nó de demanda no estágio 304 e repete as etapasdiscutidas acima. Se não há nós de demanda adicionais, a programação écompletada. O sistema pode emitir uma CTM total esperada resultante daadição de todas as CTMs individuais associadas aos fragmentos deprogramação.

Como indicado acima com referência à FIG. 1, o sistema podeajustar os recursos e repetir ou o processo de programação inteiro ou umaporção do processo de programação. O ajuste dos recursos pode ser com basena informação sobre as causas das demandas puladas adquiridas quando asdemandas são marcadas nas etapas 324, 328, e 332. Por exemplo, se asmarcas indicam que numerosas demandas estão sendo puladas para umaescassez de atendentes de vôo qualificados nos aviões da Embraer, e que essaescassez ocorre primeiramente em 31 de Março e mais tarde, o sistema podeajustar o banco de dados de recursos para indicar que há atendentes de vôoadicionais assim qualificados e emite uma indicação que tais atendentes devôo adicionais devem ser contratados e treinado para estarem disponíveis apartir de 31 de Março. O sistema pode re-calcular a inteira programação combase na suposição que um certo número de atendentes de vôo adicionaisestará disponível a partir de 31 de Março em diante. De forma alternativa, seas demandas foram ordenadas de acordo com a data e hora de partida, osistema pode re-calcular somente a porção de uma programação a partir de 31de Março em diante, e concatenar a programação re-calculada com aprogramação calculada anterior antes de 31 de Março para formar umaprogramação composta. A CTM total para a programação re-calculada podeser comparada com a CTM para a programação original, para determinar se amudança sugerida nos recursos é desejável do ponto de vista econômico. Damesma forma, se as indicações de nós pulados sugerem que aviões adicionaisde um tipo particular devem se tornar disponíveis, o sistema pode alterar obanco de dados de recursos para indicar que tais aviões adicionais estãodisponíveis, re-calcular a programação ou uma porção da programação comtais indicações, e comparar a CTM da programação com a CTM daprogramação original para determinar a vantagem que pode ser obtida atravésda aquisição ou leasing de mais aviões.

Um processo de acordo com uma outra modalidade dainvenção,, de forma esquemática, ilustrado na FIG. 13, utiliza demandassimilares àquelas discutidas acima. As demandas podem ser formuladas noestágio 400 essencialmente pelo mesmo processo como discutido acima comreferência às FIGS. 2 - 9. Aqui de novo, cada demanda pode incluir umaorigem, uma destinação, e uma hora de partida ou uma hora de chegadadesejadas, e também de forma desejável inclui informação especificando umacarga estimada tal com uma carga de passageiros em cada classe de tarifa nocaso de uma companhia de linha aérea. Aqui de novo, cada demanda podeincluir informação relacionando carga (tal como carga de passageiro ou cargade passageiro em cada classe de tarifa) para a hora de partida ou uma hora dechegada. Aqui de novo, o sistema mantém um banco de dados de recursos queinclui pelo menos, uma lista de veículos, e inclui, de forma desejável, umalista de veículos tendo informação como discutido acima tal como o estado decada veículo, como por exemplo, dispostos em um particular terminal talcomo um aeroporto ou em uma rota, para cada hora durante o intervalo futuroque é para ser englobado pela programação. O banco de dados, de formadesejável, também inclui outros recursos, como por exemplo, portões etripulações do terminal, e inclui, de forma desejável, a mesma informaçãocomo discutido acima. Aqui de novo, no início do procedimento deprogramação, o banco de dados está em um estado inicial.

O sistema seleciona um particular veículo a parti do banco dedados no estágio 404. Esta seleção pode ser com base em uma ordenação dosveículos por tipo ou mesmo por identidade do veículo. Por exemplo, umacompanhia de linha aérea pode escolher programar seus mais caros aviõesprimeiro, a fim de fazer o melhor uso desses particulares aviões, no qual caso,os mais caros aviões seriam os primeiros na ordem dos veículos, e então, umdesses mais caros aviões seria selecionado primeiro. Tendo selecionado umparticular veículo, o sistema no estágio 406 avalia o estado do veículo,encontra a próxima hora quando o veículo estará disponível, e seleciona umconjunto de demandas factíveis que poderia ser encontradas de formaconcebível através do uso do veículo selecionado. Por exemplo, se o veículoselecionado está listado no banco de dados como estando ocupado emmanutenção ou em operações previamente programadas através de umparticular date e hora, o sistema pode selecionar um conjunto de demandasfactíveis excluindo aquelas demandas tendo horas de partida antes daparticular data e hora quando o veículo se tornará disponível. Também, osistema neste estágio pode excluir demandas que não são factíveis para oparticular veículo, como por exemplo, aquelas demandas procurando por umaeroporto de destino tendo luzes de pista menores do que as requeridas poruma aeronave em questão, ou tendo uma distância de vôo maior do que aautonomia de vôo da aeronave em questão. O sistema pode também excluirdemandas que podem ser factíveis tecnicamente mas altamente improváveisde conduzir a um resultado rentável ser servido com este particular veículo,como por exemplo, demandas com origens localizadas mais do que uma certadistância da localização do veículo como indicado pelo banco de dados. Épossível omitir este estágio e usar como o conjunto de demandas todas asdemandas no e banco de dados; as demandas não factíveis podem serexcluídas durante estágios posteriores. Contudo, selecionar um conjunto dedemandas factíveis reduz o número de cálculos.

No estágio 408, o sistema seleciona uma das demandas noconjunto a partir do estágio 406, e então, no estágio 410, calcula umfragmento de programação para a demanda com base na suposição que oparticular veículo selecionado no estágio 404 será usado para atender aquelademanda. O estágio de calcular um fragmento de programação pode serefetuado usando etapas similares àquelas discutidas acima a fim de selecionaros melhores recursos, tais como tripulação e portões, para completar ofragmento de programação e ajustar a hora de partida, se necessário, para umahora de partida ou após a hora de disponibilidade da aeronave. Aqui de novo,o sistema calcula uma função de resultado no estágio 412 para o possívelfragmento de programação resultante do estágio 410. Como discutido acima,uma função de resultado pode incluir a resultado financeiro tal como CTMpara o possível fragmento de programação. Uma função de resultado podeincluir, de modo opcional, uma penalidade o tempo ocioso passado pelaaeronave a partir de sua hora de disponibilidade para a hora de partida. Noestágio 414, o sistema determina se todas as demandas no conjunto dedemandas do estágio 406 foram processadas. Se não, o sistema retorna à etapa408, seleciona uma outra demanda a partir do conjunto, e repete etapas 410 e412 para aquela demanda, a fim de fornecer um possível fragmento deprogramação e a função de resultado associada, para a próxima demanda. Esteprocesso continua até todas as demandas factíveis terem sido processadas paraconduzir a possíveis fragmentos de programações e funções de resultadoassociadas. O sistema então vai para o estágio 416, onde ele seleciona aparticular demanda que conduziu a melhor função de resultando, como porexemplo, a mais alta CTM de todas as demandas no conjunto do estágio 406.A esse respeito, se o estágio 406 foi omitido, ou usado critérios bem amplostal que o conjunto inclui demandas não factíveis, o sistema irá determinar apossibilidade de ser factível durante o estágio de calcular um fragmento deprogramação possível (etapa 410), e irá excluir qualquer demanda queresultou da não possibilidade de ser factível da seleção no estágio 416.

Uma vez que o melhor resultado foi selecionado, umfragmento de programação é configurado considerando as condiçõesespecificadas no possível fragmento de programação associado com o melhore comprometendo os recursos, incluindo o veículo selecionado e outrorecursos, para aquele fragmento de programação. Assim sendo, o banco dedados é atualizado no estágio 418 para um novo estado, indicando que oveículo selecionado e qualquer outro recurso usado no conjunto do fragmentode programação estão comprometidos. Uma vez que o novo estado foiconfigurado, o sistema retorna de novo ao estágio 406 e seleciona um novoconjunto de demandas factíveis para a aeronave selecionada com base nonovo estado. Por exemplo, se o última anterior passagem através das etapas406 - 416 resultados na configuração de um fragmento de programação quetoma o veículo para San Francisco como sua destinação, e que torna o veículodisponível para ainda uso em 3:00 p.m. em uma data particular, a próximapassagem através das etapas 406 - 416 vai resultar na seleção de umademanda que melhor utiliza a aeronave com base na sua posição em SanFrancisco e sua hora de disponibilidade de 3:00 p.m. naquela data. Esteprocesso continua até que, no estágio 420, o sistema determina que o veículoestá completamente programado através do intervalo de tempo a ser cobertopela programação sendo gerada. Se o veículo foi programado completamente,o sistema verifica no estágio 424 para determinar se este é o último veículo aser programado. Se não, o sistema vai de volta à etapa 404, seleciona opróximo veículo e repete as etapas 406 - 420 com aquele veículo, a fim dedesenvolver um programação completa para o próximo veículo na mesmamaneira; e o processo se repete até todos os veículos terem sido programados,onde quando a programação está completa.

Programar nesta maneira usa, a mesma abordagem geral comodiscutido acima com referência à FIG. 10, i. e., pegando condições queminimizem o custo ou maximizem algum outro resultado para uma particularoperação de vôo. Nesta modalidade, contudo, as demandas são endereçadasna ordem em que elas se tornam factíveis para um particular aeronave.Colocado de outro modo, esta modalidade segue uma aeronave através daprogramação e encontra o melhor uso para aquela aeronave a qualquer horadurante a programação, repete o processo até a aeronave ter sido totalmenteprogramado para os intervalos de tempo requeridos. Em uma variante desteprocesso, o sistema pode não computar a programação inteira para cadaveículo antes de selecionar o próximo veículo. Por exemplo, após configurarum novo estado gravando um fragmento de programação para um particularveículo, o sistema pode ir de volta à etapa 404 e selecionar um outro veículo.O estágio de selecionar um veículo pode ser configurado nesta modalidadepara selecionar um veículo de entre todos os veículos de um tipo particularcom base no número de vezes que o veículo foi selecionado, tal que o veículoque foi selecionado previamente o menor numero de vezes será pego. Nestamaneira, o sistema essencialmente encontra o melhor uso para cada veículoem uma primeira operação começando a partir do estado inicial. Então,quando o estado do sistema indica que cada veículo foi programado para umaprimeira operação, o sistema procura o melhor uso de cada veículo uma vezmais para uma segunda operação. Este processo continua até todos osveículos terem sido programados do começo ao fim do intervalo de tempointeiro a ser coberto pela programação.

Em cada uma dessas modalidades, após a programaçãocompleta ter sido formulada, ou um operador humano ou o sistema podedecidir ajustar os recursos como indicado, de forma esquemática, no estágio428, ou mudar a estratégia, através das quais as demandas são formuladascomo indicado, de forma esquemática, no estágio 430 e repetir o processopara gerar uma outra programação. Aqui de novo, programaçõesdesenvolvidas com vários conjuntos de recursos, e estratégias diferentespodem ser geradas de forma rápida e podem ser comparadas uma com a outra.

Em ainda uma outra variante, o sistema pode usar a abordagemde programação de veículos ordenados como discutida acima com referênciaà FIG. 13 para configurar uma porção da programação, e pode usar aabordagem de demanda ordenada discutida com referência à FIG. 11 paraconfigurar a outra porção da programação. Nestas modalidades discutidasacima, o processo de programação inclui recursos outros do que veículos, i.e., tripulação e portões de aeroporto. Em uma mais limitada variante, osprocessos de programação discutidos aqui podem ser usados para programarsomente veículos, e processos externos podem ser usados para programaroutros recursos. Nesta mais limitada, o banco de dados pode incluir somenteinformação pertinente aos veículos.

Os sistemas discutidos acima, de forma desejável, fornecemhoras para manutenção dos veículos. Por exemplo, a aeronave tipicamenteprecisa ser revisada ao final de cada vôo. A manutenção deste tipotipicamente requer um intervalo fixo e pode ser efetuada em qualquerlocalização. Por conseguinte, o sistema, de forma desejável, simplesmenteadiciona um intervalo para manutenção ao final de cada vôo. Outramanutenção, comumente referida como manutenção "11C" e "D ", precisa serefetuada em centros de manutenção específicos, que pode ou pode não estarem terminais servido pela companhia de linha aérea. A manutenção desse tipoprecisa ser efetuada em intervalos estabelecidos por regras que podem incluir,por exemplo, número especificado de horas de vôo, subidas ou aterrissagens,ou dias de serviço, ou alguma combinação desses. Como estabelecido acima,os banco de dados de recursos mantidos pelo sistema contém informação deestado para cada aeronave, que inclui esses fatores. O sistema pode rever obanco de dados ou a porção do banco de dados pertencente a um particularaeronave cada vez que a aeronave é incorporada em um fragmento deprogramação. Se o estado da aeronave ao final do novo fragmento deprogramação for tal que a aeronave requer manutenção, o sistema podesimplesmente programar a aeronave a priori para a particular manutençãorequerida, marcar o banco de dados de recursos para indicar que a aeronaveestará fora de serviço para o intervalo requerido (tipicamente dias ousemanas), e passa um sinal para um sistema de controle de manutenção oupara um operador humano indicando quando a aeronave se tornará disponívelpara manutenção e o tipo de manutenção requerida. Em uma varianteadicional, se a informação de estado para um particular aeronave indica que otempo limite para manutenção está se aproximando, o sistema podeconfigurar um custo baixo artificialmente para a aeronave voar para umadestinação na ou próxima da base de manutenção apropriada, assim sendoaumentando a probabilidade que a próxima demanda programada tomará aaeronave para ou próximo a base de manutenção. A habilidade de interagircomo os sistemas de manutenção e programar a aeronave de modo realísticocom conhecimento total da manutenção requerida fornece uma vantagemsignificativa.

Cada um dos sistemas discutido acima começa o processo deprogramação com base no estado inicial da aeronave e outro recursos, econstrói o banco de dados de estados futuros que as aeronaves são esperadasde estarem nas horas futuras gerando os fragmentos de programações. Maistipicamente, o estado inicial é um estado prognosticado em alguma hora apósa operação de programação ser efetuada. Por exemplo, uma companhia delinha aérea pode usar o sistema durante o mês de Janeiro para gerar aprogramação para operações durante os meses de Julho e Agosto, talprogramação sendo com base em um estado inicial assumido de 1 de Julho.Contudo, porque o processo de programação é extremamente rápido, ele podeser usado como uma ferramenta de programação em tempo real, com o estadoinicial sendo um estado observado na data da programação. Assim sendo, oprocesso de programação pode permitir à companhia de linha aérea reagir aeventos efetivos tais como perturbações atmosféricas pegando a maiseficiente programação para voar daquela data em diante.

Na discussão acima, uma função de resultado foi colocada emtermos de resultados financeiros, tal como CTM. Contudo, resultado nãofinanceiros também podem ser avaliados. Por exemplo, uma função deresultado para uma particular demanda pode incluir tempo de espera parapassageiros se transferindo de vôos alimentadores. O tempo de espera podeser avaliado de forma independente, ou pode ser transladado em um custofinanceiro refletindo a expectativa da companhia de linha aérea que umpassageiro incomodado por um grande tempo de espera se torne um clientemenos leal. Tal um custo pode ser subtraído da CTM para acarretar umafunção de resultado final.

A computação discutida acima pode ser efetuada usando umcomputador de propósito geral convencional 500 (FIG. 14) que inclui oselementos normais de um computador, tal como um processador, e umamemória para manter o banco de dados de recursos e fragmentos deprogramação. O computador também inclui um elemento de programação queinclui um meio legível de computador 501 e um programa armazenado em talmeio, o programa sendo operacional para forçar o computador a efetuar asetapas discutidas acima. O meio 501 pode ser separado da memória usadapara armazenar o banco de dados de recursos e os fragmentos deprogramação, ou pode ser integrado com ela, Por exemplo, o meio 501 podeser um disco, uma fita ou memória em estado sólido incorporado nocomputador. Como mostrado de forma simbólica na FIG. 14, um sistema paraefetuar esses cálculos inclui um computador 500 programado para efetuar asoperações discutidas acima; e também inclui um ou mais nós de entrada 502para fornecer informação de entrada que pelo menos, de forma parcial, defineos serviços a serem fornecidos na operação de transporte a ser programada.Na modalidade representada, os nós de entrada 502 são mostrados comoterminais de entrada, e esses nós podem ser usados para fornecer qualquer doselementos de informação a serem processados nos métodos como discutidoacima. O sistema ainda inclui pelo menos, um nó de saída 506 arrumado parareceber informação representando pelo menos, algum dos recursos designadopara o fragmento de programações a partir do computador 500. De formadesejável, cada nó de saída 506 é arrumado para mostrar ou emitir estainformação em forma legível para o ser humano, como por exemplo, em umatela de exibição ou impressora. Embora os nós de entrada 502 e os nós desaída 506 são mostrados separadamente, esses nós podem ser combinados umcom o outro. Os nós de entrada e saída podem ser conectadas ao computador500 diretamente se os nós estão na mesma localização que o computador. Osnós 502 e 506 podem ser dispostos em localizações distantes do computador500, e podem ser conectados ao computador através de qualquer meioadequado de comunicação, como por exemplo, através de uma conexão localatravés de uma rede tal como a Internet 504, de forma esquemática,representado na FIG. 14. Embora um computador 500 seja mostrado comoum único elemento na FIG. 14, os elementos de computador 500 podem serdistribuídos em várias localizações conectados um com o outro através dequalquer meio adequado de comunicação. Também, embora os nós de entradae de saída, de forma desejável estejam ligados ao computador 500 através deuma rede ou outra forma de comunicação instantânea, isto não é essencial; osnós de entrada e saída podem ser arrumados para fornecer a informação deentrada e receber a informação de saída em cópia em papel ou em mídiaeletrônica adequada que possa ser fisicamente transportada entre os nós e ocomputador.

Os nós de entrada e nós de saída do computador formam partede um grande sistema de sistema de transporte que inclui veículos tal comouma aeronave 508, e terminais 510 tal como aeroportos. Como discutidoacima, a programação define rotas entre terminais 510, que correspondem arotas físicas 512. Os nós de entrada e saída podem ser localizadas em um oumais dos terminais 510, ou em uma outra localização.

Embora a invenção aqui tenha sido descrita com referência amodalidades particulares, é para ser entendido que essas modalidades são,meramente ilustrativas dos princípios e aplicações da presente invenção. E,por conseguinte, para ser entendido que numerosas modificações podem serfeitas para as modalidades ilustrativas e que outros arranjos podem serconcebidos sem fugir do espírito e escopo da presente invenção comodefinida pelas reivindicações anexas.

Claims (50)

1. Método implementado por computador para gerar umaprogramação para uma operação de transporte, caracterizado pelo fato decompreender:a) fornecer uma lista ordenada de uma grande quantidade dedemandas para transporte entre uma grande quantidade de origens e umagrande quantidade de destinos, cada demanda sendo associada com umaorigem, uma destino e um tempo de partida ou um tempo de chegada;usando um computador para:b) estabelecer um fragmento de programação para satisfazeruma das demandas na lista ordenada, o estágio de estabelecimento dofragmento de programação incluindo recursos designados de uma ou maislistas de recursos disponíveis, ec) modificar a uma ou mais listas de recursos disponíveis paraindicar um estado revisado com base no uso dos recursos no estágio (b); ed) repetir os estágios (b) e (c) tal que os estágios (b) e (c)sejam efetuados para uma grande quantidade de demandas de acordo com aordem das demandas na lista e tal que o estágio (b) para cada demanda éefetuado usando o estado resultante proveniente do estágio (c) para a próximademanda prévia.

2. Método de acordo com a reivindicação 1, caracterizado pelofato de que o estágio de estabelecimento de um fragmento de programaçãopara a demanda inclui ajustar um tempo de partida dentro de um intervalo detempos adjacente a um tempo de partida na demanda.

3. Método de acordo com a reivindicação 2, caracterizado pelofato de que o estágio de estabelecimento de um fragmento de programaçãoinclui determinar pelo menos, um resultado com base na informaçãorelacionando o tempo de partida a carregar para a demanda.

4. Método de acordo com a reivindicação 2, caracterizado pelofato de que o intervalo de tempos é selecionado com base pelo menos, emparte quando dos fragmentos de programação determinados anteriormentepara outras demandas.

5. Método de acordo com a reivindicação 1, caracterizado pelofato de que o estágio de estabelecimento de um fragmento de programação éefetuado tal que uma função de resultado para o fragmento de programaçãocoincide com um ou mais critérios.

6. Método de acordo com a reivindicação 5, caracterizado pelofato de que o um ou mais critérios incluem maximização ou minimização dafunção de resultado para o fragmento de programação.

7. Método de acordo com a reivindicação 5, caracterizado pelofato de que uma função de resultado inclui um ou mais valores financeirospara o fragmento de programação.

8. Método de acordo com a reivindicação 7, caracterizado pelofato de compreender adicionalmente agregar os valores financeiros para osfragmentos de programação para derivar um valor financeiro de agregaçãopara a programação.

9. Método de acordo com a reivindicação 7, caracterizado pelofato de que cada demanda inclui uma carga prevista, ainda inclui o estágio dederivar as cargas previstas para as demandas com base pelo menos, em parteem uma um ou mais estimativas do comportamento do mercado.

10. Método de acordo com a reivindicação 9 caracterizadopelo fato de compreender adicionalmente os estágios de ajustar a uma ou maisestimativa do comportamento do mercado, e repetir os estágios antesmencionados usando as estimativas ajustadas do comportamento do mercado.

11. Método de acordo com a reivindicação 10, caracterizadopelo fato de que o estágio de ajustar a uma ou mais estimativas docomportamento do mercado, inclui ajustar pelo menos, um aspecto de umpreço a ser cobrado para o transporte e do valor a ser oferecido em taltransporte e aplicar uma relação estimada entre o pelo menos, um aspecto dopreço e do valor e da demanda para o transporte.

12. Método de acordo com a reivindicação 11, caracterizadopelo fato de que o pelo menos, um aspecto do preço e do valor inclui aquantidade a ser paga por um cliente para o transporte.

13. Método de acordo com a reivindicação 11, caracterizadopelo fato de que o pelo menos, um aspecto do preço e do valor inclui um nívelde um serviço auxiliar fornecido a um cliente em troca da aquisição dotransporte.

14. Método de acordo com a reivindicação 8, caracterizadopelo fato de compreender adicionalmente os estágios de modificar osrecursos, repetir os estágios antes mencionados para pelo menos, algumas dasdemandas usando os recursos modificados.

15. Método de acordo com a reivindicação 14, caracterizadopelo fato de compreender adicionalmente o estágio de comparar os valoresfinanceiros de agregação alcançados com diferentes conjuntos de recursos.

16. Método de acordo com a reivindicação 1, caracterizadopelo fato de que o estágio de estabelecimento de um fragmento deprogramação para a demanda inclui avaliar uma função de resultado para ademanda e não programar nenhum serviço para a demanda se uma função deresultado coincide com um ou mais critérios de eliminação.

17. Método de acordo com a reivindicação 16, caracterizadopelo fato de que um ou mais critérios de eliminação incluem a ausência de umou mais critérios de retenção.

18. Método de acordo com a reivindicação 1 caracterizadopelo fato de que o estágio de fornecer uma lista ordenada inclui estabeleceruma grande quantidade de chaves de ordenação e ordenar as demandas deacordo com uma grande quantidade de chaves de ordenação.

19. Método de acordo com a reivindicação 18, caracterizadopelo fato de que as chaves de ordenação incluem um valor de continuidadeindicativo de se uma demanda particular é uma de uma série de demandas aserem atendidas com sucesso através de um único veículo.

20. Método de acordo com a reivindicação 18, caracterizadopelo fato de que as chaves de ordenação incluem pelo menos, um valorfinanceiro para a demanda.

21. Método de acordo com a reivindicação 18, caracterizadopelo fato de que as chaves de ordenação incluem pelo menos, um de tempo departida e do tempo de chegada.

22. Método de acordo com a reivindicação 18, caracterizadopelo fato de que o estágio de fornecer uma lista ordenada ainda inclui umestágio de modificar uma lista ordenada de acordo com uma grandequantidade de chaves de ordenação com base em uma ou mais relações decontinuidade entre demandas.

23. Método de acordo com a reivindicação 18, caracterizadopelo fato de compreender um estágio de modificar pelo menos, uma dasdemandas ou das chaves de ordenação e repetir os estágios antesmencionados.

24. Método de acordo com a reivindicação 1, caracterizadopelo fato de que a lista de recursos inclui um banco de dados de recursosdisponíveis em localizações e tempos particulares e que o estágio deestabelecimento de um fragmento de programação para a demanda particularinclui deduzir recursos dos recursos disponíveis na origem.

25. Método de acordo com a reivindicação 24, caracterizadopelo fato de que o estágio de estabelecimento de um fragmento deprogramação para uma demanda particular ainda inclui o estágio de adicionarrecursos móveis para o banco de dados de recursos disponíveis no destinoassociado com uma demanda para um tempo seguindo um tempo decompletar a operação associada com a demanda.

26. Método de acordo com a reivindicação 24, caracterizadopelo fato de compreender adicionalmente o estágio de determinar se osrecursos disponíveis na origem associada com a demanda para um tempo departida desejada associado com a demanda são insuficientes para permitir aoperação associada com a demanda e, se assim, determinar a partir do bancode dados se existem recursos móveis em uma outra localização e se podem serrealocados para a origem em tempo para uma operação com o tempo departida desejado.

27. Método de acordo com a reivindicação 26, caracterizadopelo fato de compreender adicionalmente o estágio, se recursos móveis nãopodem ser realocados para a origem em tempo para uma operação com otempo de partida desejado, de determinar o tempo de partida mais cedofactível após o tempo de partida desejado quando todos os recursos podem serfeitos disponíveis e de estabelecer um tempo de partida no tempo de partidamais cedo factível.

28. Método de acordo com a reivindicação 27, caracterizadopelo fato de compreender adicionalmente retornar uma mensagem de erroindicando que indisponibilidade de um particular recurso impede oestabelecimento de um fragmento de programação para uma demandaparticular se nenhum tempo de partida mais cedo factível dentro de umintervalo de tempos de partida aceitáveis podem ser encontrados.

29. Método de acordo com a reivindicação 28, caracterizadopelo fato de compreender acumular informação de uma grande quantidade dasmensagens de erro indicativas de que os recursos restringem a operação dosistema de transporte.

30. Método de acordo com a reivindicação 29, caracterizadopelo fato de compreender adicionalmente ajustar os recursos responsivos paraa informação acumulada e repetir os estágios antes mencionados usando osrecursos ajustados para pelo menos, algumas de umas demandas.

31. Método de acordo com a reivindicação 25, caracterizadopelo fato de que os recursos móveis incluem veículos.

32. Método de acordo com a reivindicação 28 caracterizadopelo fato de que os recursos móveis incluem tripulações.

33. Método de acordo com a reivindicação 1, caracterizadopelo fato de que compreender adicionalmente compilar os fragmentos deprogramações para formar uma programação e operar o sistema de transportede acordo com a programação.

34. Método de acordo com a reivindicação 33, caracterizadopelo fato de que o sistema de transporte é uma companhia aérea.

35. Método implementado por computador para gerar umaprogramação para uma operação de transporte, caracterizado pelo fato decompreender:a) fornecer uma lista de uma grande quantidade de demandaspara transporte entre uma grande quantidade de origens e uma grandequantidade de destinos, cada demanda sendo associada com uma origem, comuma destino e com pelo menos, um de um tempo de partida e um tempo dechegada, e uma lista de recursos incluindo uma grande quantidade de veículose informação especificando a localização de cada veículo versus o tempo;usando um computador para:b) selecionar um veículo a partir dos veículos identificados emuma lista de recursos;c) selecionar um das demandas a partir de uma lista dasdemandas e estabelecer um fragmento de programação para satisfazer ademanda selecionada designando o veículo selecionado para a demandaselecionada, ed) modificar a lista de recursos e a lista de demandas paraindicar um estado revisado com base no uso dos veículos e das demandas noestágio (c); ee) repetir estágios (b) através de (d) tal que os estágios (b) atéde (d) são efetuados para uma grande quantidade de demandas e tal que oestágio (c) para cada repetição é efetuado usando o estado resultante doestágio (d) para a próxima repetição prévia.

36. Método de acordo com a reivindicação 35, caracterizadopelo fato de que o estágio de selecionar um das demandas inclui avaliar umafunção de resultado para cada uma de um conjunto de demandas com base nouso do veículo selecionado para coincidir com aquela demanda.

37. Método de acordo com a reivindicação 36, caracterizadopelo fato de que, para cada demanda do conjunto de demandas, o estágio deavaliar uma função de resultado inclui ajustar um tempo de partida dentro deum intervalo de tempos adjacente a um tempo de partida na demanda combase pelo menos, em parte em um tempo de disponibilidade do veículoselecionado e em que o estágio de avaliar uma função de resultado é com basepelo menos, em parte na informação relacionando o tempo de partida acarregar para a demanda.

38. Método de acordo com a reivindicação 36, caracterizadopelo fato de que o estágio de selecionar uma demanda inclui selecionar ademanda a partir do conjunto que conduz a uma melhor função de resultado.

39. Método de acordo com a reivindicação 36, caracterizadopelo fato de que uma função de resultado inclui um ou mais valoresfuncionais.

40. Método de acordo com a reivindicação 39, caracterizadopelo fato de compreender adicionalmente agregar os valores financeiros paraos fragmentos de programação para derivar um valor financeiro de agregaçãopara a programação.

41. Método de acordo com a reivindicação 39, caracterizadopelo fato de que cada demanda inclui a carga prevista, o método aindaincluindo o estágio de derivar as cargas previstas para as demandas com basepelo menos, em parte em uma ou mais estimativas do comportamento domercado.

42. Método de acordo com a reivindicação 41, caracterizadopelo fato de compreender adicionalmente os estágios de ajustar a uma ou maisestimativas do comportamento do mercado, e repetir os estágios antesmencionados usando a estimativa ajustada do comportamento do mercado.

43. Método de acordo com a reivindicação 42, caracterizadopelo fato de que o estágio de ajustar a uma ou mais estimativas docomportamento do mercado, inclui ajustar pelo menos, um aspecto de umpreço a ser cobrado para o transporte e de um valor a ser oferecido em taltransporte e aplicar uma relação estimada entre o pelo menos, um aspecto dopreço e do valor e da demanda para o transporte.

44. Sistema de programação para uma operação de transporte,caracterizado pelo fato de compreender:a) pelo menos, um nó de entrada possível de ser operado parareceber informação de entrada pelo menos, de forma parcial, definindoserviços a serem fornecidos na operação de transporte;b) um computador conectado ao pelo menos, um nó de entradatal que a informação de entrada recebida através do nó de entrada seráfornecida ao computador, o computador sendo possível de ser operado emresposta à informação de entrada para:(1) manter uma lista ordenada de uma grande quantidade dedemandas para transporte entre uma grande quantidade de origens e umagrande quantidade de destinos, cada demanda especificando uma particularorigem, uma particular destino e pelo menos, um de um tempo para partida daparticular origem e um tempo para chegada na particular destino;(2) estabelecer um fragmento de programação para satisfazeruma das demandas na lista ordenada, o estágio de estabelecimento dofragmento de programação incluindo designar recursos de uma ou mais listasde recursos disponíveis, o estágio de estabelecimento do fragmento deprogramação sendo efetuado tal que uma função de resultado para ofragmento de programação coincide com um ou mais critérios;(3) modificar a uma ou mais listas de recursos disponíveis paraindicar um estado revisado com base no uso dos recursos no estágio (2); e(4) repetir estágios (2) e (3) tal que estágios (2) e (3) sãoefetuados para uma grande quantidade de demandas de acordo com a ordemdas demandas na lista e tal que estágio (2) para cada demanda é efetuadousando o estado resultante do estágio (3) para a próxima demanda prévia; ec) pelo menos, um nó de saída conectado ao computador talque informação de saída representando pelo menos, algum dos recursosdesignados para programar fragmentos serão fornecidos ao pelo menos, umnó de saída.

45. Sistema de acordo com a reivindicação 44, caracterizadopelo fato de que o computador é conectado com pelo menos, um nó de saída ecom o pelo menos, um nó de entrada através de uma rede de comunicaçõeseletrônicas.

46. Sistema de programação para uma operação de transporte,caracterizado pelo fato de compreender:a) pelo menos, um nó de entrada possível de ser operado parareceber informação de entrada pelo menos, de forma parcial, definindoserviços a serem fornecidos na operação de transporte;b) um computador conectado ao pelo menos, um nó de entradatal que a informação de entrada recebida através do nó de entrada seráfornecida ao computador, o computador sendo possível de ser operado emresposta à informação de entrada para:(1) manter uma lista de uma grande quantidade de demandaspara o transporte entre uma grande quantidade de origens e uma grandequantidade de destinos, cada demanda sendo associada com uma origem, comuma destino e com um tempo de partida ou tempo de chegada, e uma ou maislistas de recursos, incluindo uma grande quantidade de veículos e informaçãoespecificando a localização de cada veículo versus o tempo;(2) selecionar a veículo a partir de um ou mais veículosidentificados na lista de veículos;(3) selecionar uma das demandas a partir de uma lista dasdemandas e estabelecer um fragmento de programação para satisfazerdemanda selecionada designando o veículo selecionado para a demandaselecionada;(4) modificar a uma ou mais listas de veículos e a lista dedemandas para indicar um estado revisado com base no uso de veículos edemandas no estágio (3); e(5) repetir estágios (2) até (4) tal que estágios (2) até (4) sãoefetuados para uma grande quantidade de demandas e tal que o estágio (3)para cada repetição é efetuado usando o estado resultante do estágio (4) para arepetição anterior.

47. Sistema de acordo com a reivindicação 44, caracterizadopelo fato de que o computador é conectado com pelo menos, um nó de saída ecom o pelo menos, um nó de entrada através de uma rede de comunicaçõeseletrônicas.

48. Sistema de transporte, caracterizado pelo fato decompreender:a) uma grande quantidade de veículos;b) uma grande quantidade de localizações de terminal;c) pelo menos, um nó de entrada possível de ser operado parareceber informação de entrada pelo menos, de forma parcial, definindoserviços a serem fornecidos na operação de transporte;d) um computador conectado ao pelo menos, um nó de entradatal que a informação de entrada recebida através do nó de entrada seráfornecida ao computador, o computador sendo possível de ser operado emresposta à informação de entrada para efetuar um processo de acordo com areivindicação 1 ou reivindicação 36 ee) pelo menos, um nó de saída disposto em uma ou mais daslocalizações de terminais e conectado ao computador tal que a informação desaída representando os recursos designados para programar fragmentosatravés do processo serão fornecidos para o pelo menos, um nó de saída.

49. Sistema de transporte de acordo com a reivindicação 46,caracterizado pelo fato de que os veículos incluem aviões e as localizações determinais incluem os aeroportos.

50. Elemento de programação para um computador,caracterizado pelo fato de compreender um meio legível por computadortendo nele um programa armazenado nele, o programa sendo operativo paraforçar um computador a efetuar um método como definido na reivindicação 1ou reivindicação 36.