Procedimiento y sistema de construcción de tarifas de viaje reales, actuales.

Un sistema para proporcionar una pluralidad de opciones de destino que comprende:

- un componente (110, 210) de aprendizaje de tarifas conectable a al menos un sistema de reservas informatizado;

- un par de estructuras (220, 230) de datos actualizables a partir del componente (110) de aprendizaje de tarifas, y almacenar una pluralidad de datos de viaje, comprendiendo los datos de viaje mencionados al menos un origen (221), un destino (225), un precio reservable y unas fechas reservables; comprendiendo el par de estructuras de datos, por un lado, una gráfica de nodos con nodos y aristas en los que los nodos son los destinos de viaje y en los que cada una de las aristas hace referencia a una tarifa de viaje más baja entre los dos nodos que conectan, y por otro lado, un árbol de tarifas construidas para cada arista de gráfica y que comprende una raíz que mantiene la tarifa del viaje más baja de la arista;

- un motor (105) de comprador para aceptar al menos un origen (610) y un intervalo (630, 640) de fechas e interrogar a la estructura (220, 230) de datos para generar la pluralidad de opciones de destino correspondientes al origen (610) y a las fechas reservables dentro del intervalo (630, 640) de fechas;

- un motor (200) de extracción de ruta de tarifa, configurado para extraer rutas de tarifa a partir del par de estructuras de datos con el fin de determinar las rutas de tarifa menos costosas, dicho motor de extracción de rutas de tarifa configurado para construir, para cada par de origen y destino, una pila mantenida organizada como un árbol binario y configurada para acumular un número (k) máximo predeterminado de rutas de tarifa menos costosas entre el origen y el destino durante la extracción.

Procedimiento y sistema de construcción de tarifas de viaje reales, actuales Campo de la invención La presente invención se refiere, en general, a sistemas de planificación de viajes informatizados y se refiere más específicamente a un procedimiento y a un sistema que permiten extraer eficientemente las tarifas de viaje reales, actuales, de manera que pueden proponerse un gran número de oportunidades de reservas posibles a un cliente.

Antecedentes de la invención La planificación de un viaje, especialmente un viaje aéreo, se hace en general en base a la selección de los aeropuertos de la ciudad de origen y de destino y del establecimiento de las fechas de salida y regreso. Este es el caso de cualquier planificación que se haga por una agencia de viajes o directamente por el cliente. En cuyo caso, este último solo tiene que acceder a cualquiera de los sitios web especializados, en los que muchos operadores turísticos y las compañías aéreas se han juntado en Internet para anunciar sus ofertas de viajes y estancias de vacaciones, en un intento de venderlos sin terceros involucrados. De hecho, la mayoría de las compañías aéreas ofrecen ahora la posibilidad de reservar y comprar un billete de avión desde su servidor web. En cuyo caso, el billete a menudo se "desmaterializa" ya que no se emite ningún billete real y el cliente solo tiene que mostrar en el mostrador de la aerolínea del aeropuerto un ID, por ejemplo, un pasaporte, para obtener su tarjeta de embarque.

Si bien es así de fácil reservar un viaje o unas vacaciones, el cliente no puede tener la certeza, sin embargo, de que haya obtenido la mejor oferta posible o la que mejor se ajuste a sus preferencias. Si la mayoría de la gente, si no toda, que viaja por negocios, se compromete a llegar y salir en fechas precisas que conoce, a menudo con mucha antelación, exactamente dónde y cuándo tienen que estar para sus citas profesionales, reuniones corporativas, conferencias o seminarios de todo tipo, lo cierto es que una buena parte de la clientela de las agencias de viajes no tienen esas limitaciones. De hecho, muchos de sus clientes ven como un inconveniente tener que establecer fechas precisas para sus viajes e incluso a veces no están seguros sobre el destino.

Como ejemplo de lo anterior, un cliente de un agente de viajes puede expresar su deseo de visitar la parte noreste del continente americano en otoño, es decir, durante el llamado veranillo de San Martín, que es famoso por el color cambiante de las hojas de los árboles o el follaje de otoño. Puede ser también interesante para un cliente llegar a Boston, Nueva Inglaterra, en Nueva York o incluso a Montreal, Quebec, siempre que el agente de viajes pueda conseguir una reserva a un precio interesante en un intervalo flexible de fechas que el cliente está dispuesto a aceptar.

Otros pueden incluso expresar requisitos más flexibles y les gustaría solo especificar un tema para sus destinos de viaje o de vacaciones. Los que gustan de, digamos, las civilizaciones antiguas puede que quieran considerar en su solicitud destinos tan diferentes como Egipto y sus pirámides, México y las civilizaciones precolombinas o los templos de Angkor, Camboya.

Si se han propuesto soluciones parciales para manejar este tipo de consultas, algunas se discuten más adelante en el presente documento; esto no es posible con los productos de software con los que están equipadas actualmente las agencias de viaje. Esto exige una gran flexibilidad en la especificación de las fechas y de los destinos que los productos actuales simplemente no soportan. En este punto debe quedar claro, que se entiende que el objetivo es reservar en realidad un viaje y no solo considerar las posibles oportunidades de viaje que pueden revelarse más tarde de no estar disponibles, por ejemplo, debido a que ya están completamente reservados para el período considerado, o porque se han cancelado.

Ya existen productos para ayudar a un cliente a tomar una decisión. Por ejemplo uno puede referirse a una solicitud de patente a la USPTO (Oficina de Patentes y Marcas de Estados Unidos) , número de publicación US20020091535, que describe un procedimiento y un sistema para ayudar en la selección de un destino de vacaciones y donde no se ha especificado ningún destino en un primer lugar. Sin embargo, esto no proporciona ninguna forma de garantía de que las opciones de destino y de estancia realizadas por el cliente se puedan reservar en realidad.

Con el fin de que el cliente pueda reunir suficiente información sobre la disponibilidad real de vuelos para múltiples destinos, y en un cierto intervalo de fechas, será necesario emitir tantas consultas diferentes al sistema de reservas como destinos y días haya que considerar. Toda la información devuelta debe registrarse cuidadosamente para una comparación manual. A pesar de que algunos sistemas han introducido un cierto nivel de flexibilidad, especialmente, al proponer fechas cerradas automáticamente a las especificados en caso de no disponibilidad en el día específico solicitado, la búsqueda de la mejor solución es siempre consumidora de mucho tiempo, aburrida y requiere una gran cantidad de dedicación por parte del agente de viajes. Además, la habilidad de este último no puede ser tal que sea capaz de encontrar realmente todas las soluciones que son susceptibles de satisfacer una solicitud del cliente.

Una manera de fuerza bruta de moverse por estas dificultades sería la de precalcular todas las combinaciones de tarifas de orígenes y destinos. Debido al número de combinaciones, enumerar y almacenar todas las posibilidades necesitaría sin embargo de una enorme cantidad de recursos que no pueden implementarse de manera realista. En

efecto, si se tiene en cuenta solo el caso de las líneas aéreas, hay cerca de 3.600 ciudades en el mundo que tienen al menos un aeropuerto y los vuelos comerciales asociados. Doscientos operadores más o menos se hacen referencia en las bases de datos de reservas. Existen al menos diez tarifas por cada par de aeropuertos de origen y de destino. Además, pueden definirse diez tipos de pasajeros (niño, adulto, personas mayores, etc.) Por lo tanto, tendrían que grabarse billones de combinaciones. Si no es una tarea imposible esto no sería económicamente realista.

Sin ir tan lejos, se han propuesto sistemas, sin embargo, que tratan de calcular un gran número de combinaciones. Esto es, por ejemplo, lo que se describe en la patente de Estados Unidos 6.336.097 que enseña un procedimiento para construir un gran número de tarifas de viaje entre grupos de ciudades, orígenes y destinos. El procedimiento informático se basa en el uso de matrices de tarifas, algunas estructuras de datos multidimensionales y sofisticadas que exigen realizar una importante potencia de cálculo y los correspondientes recursos de memoria activos. Cuando en cientos de períodos pico, si no miles de usuarios remotos pueden querer acceder a un sistema de reservas de forma simultánea, el riesgo de agotar su capacidad de cómputo, hasta que se colapse, está llegando a ser alta a menos que se implementen unos recursos enormes y costosos que serán, en general, infrautilizados.

Objeto de la invención Por lo tanto, un objeto general de la invención es acelerar la construcción actual de tarifas de viaje reservables, es decir, en ordenadores del estado de la técnica convencionales.

Es otro objeto de la invención permitir que puedan manejarse muchos destinos en el tiempo transcurrido de una única solicitud del usuario final.

Es otro objeto más de la invención permitir que el sistema de planificación de viajes ofrezca opciones de viaje temáticas a sus usuarios finales que no tienen un destino específico para elegir del que comenzar a planificar un viaje.

Es otro objeto más de la invención que las rutas de tarifa seleccionadas sean las menos costosas entre el conjunto de posibles rutas de tarifa.

Otros objetos, características y ventajas de la presente invención serán evidentes para los expertos en la materia tras el examen de la siguiente descripción en referencia a los dibujos adjuntos. Se pretende que cualquiera de las ventajas adicionales se incorpore en el presente documento.

Sumario de la invención Se desvela la construcción de tarifas de viaje reales, actuales, en un ordenador, a partir de las bases de datos de tarifas. Se construye una primera estructura de datos que forma una gráfica en la que los nodos son destinos de viaje. Las aristas de la gráfica conectan pares de nodos. Cada arista hace referencia a una tarifa de viaje más baja. Se construye también una segunda estructura de datos, un árbol de tarifas, para cada arista de gráfica. Los arboles comprenden al menos un nodo raíz que mantiene la tarifa de... [Seguir leyendo]

1. Un sistema para proporcionar una pluralidad de opciones de destino que comprende:

- un componente (110, 210) de aprendizaje de tarifas conectable a al menos un sistema de reservas informatizado; -un par de estructuras (220, 230) de datos actualizables a partir del componente (110) de aprendizaje de tarifas, y almacenar una pluralidad de datos de viaje, comprendiendo los datos de viaje mencionados al menos un origen (221) , un destino (225) , un precio reservable y unas fechas reservables; comprendiendo el par de estructuras de datos, por un lado, una gráfica de nodos con nodos y aristas en los que los nodos son los destinos de viaje y en los que cada una de las aristas hace referencia a una tarifa de viaje más baja entre los dos nodos que conectan, y por otro lado, un árbol de tarifas construidas para cada arista de gráfica y que comprende una raíz que mantiene la tarifa del viaje más baja de la arista; -un motor (105) de comprador para aceptar al menos un origen (610) y un intervalo (630, 640) de fechas e interrogar a la estructura (220, 230) de datos para generar la pluralidad de opciones de destino correspondientes al origen (610) y a las fechas reservables dentro del intervalo (630, 640) de fechas; -un motor (200) de extracción de ruta de tarifa, configurado para extraer rutas de tarifa a partir del par de estructuras de datos con el fin de determinar las rutas de tarifa menos costosas, dicho motor de extracción de rutas de tarifa configurado para construir, para cada par de origen y destino, una pila mantenida organizada como un árbol binario y configurada para acumular un número (k) máximo predeterminado de rutas de tarifa menos costosas entre el origen y el destino durante la extracción.

2. El sistema de la reivindicación 1, en el que el árbol binario de la pila comprende un nodo padre cuya clave del mismo es una ruta de tarifa más grande que las rutas de tarifa de dos nodos hijo correspondientes a dicho nodo padre y en el que un nodo raíz mantiene una ruta de tarifa más costosa.

3. El sistema de la reivindicación anterior, en el que el motor de extracción de ruta de tarifa comprende medios configurados para construir la pila implantando las siguientes etapas:

a-inicializar la pila con una primera ruta de tarifa de longitud uno correspondiente a una conexión directa entre el origen y el destino de un par de origen y destino, b-determinar una primera arista de gráfica de la gráfica de un nodo que sale desde el origen, manteniendo dicha primera arista de gráfica la ruta de tarifa más baja desde el origen; c-determinar una segunda arista de gráfica de la gráfica de un nodo que sale desde el destino, manteniendo dicha segunda arista de gráfica la ruta de tarifa más baja desde el destino, d-construir una nueva ruta de tarifa con la primera arista de gráfica y la segunda arista de gráfica, e-comprobar si el número (k) máximo predeterminado de rutas de tarifa menos costosas ha sido añadido ya a la pila, f-si se ha acumulado más que el número (k) máximo predeterminado de rutas de tarifa menos costosas en la pila, eliminar la ruta de tarifa más costosa de dicha pila, g-determinar una segunda arista de gráfica adicional de la gráfica del nodo que sale desde el destino, manteniendo dicha segunda arista de gráfica una ruta de tarifa más baja adicional desde el destino, h-si se ha acumulado menos que el número (k) máximo predeterminado de rutas de tarifa menos costosas en la pila y si la suma de los valores de la primera arista de gráfica y de la segunda arista de gráfica adicional es menor o igual que el valor más alto de las rutas de tarifa acumuladas en la pila, construir una nueva ruta de tarifa con la primera arista de gráfica y la segunda arista de gráfica adicional, i-repetir las etapas c a h hasta que se haya acumulado más de, o un número igual a, el número (k) máximo predeterminado de rutas de tarifa menos costosas en la pila y si la suma de los valores de la primera arista de gráfica y de la segunda arista de gráfica adicional es mayor que el valor más alto de las rutas de tarifa acumuladas en la pila; j-seleccionar una primera arista de gráfica adicional de la gráfica del nodo que sale desde el origen, manteniendo dicha primera arista de gráfica adicional una ruta de tarifa más baja adicional desde el origen; k-repetir las etapas c a j hasta que: se haya acumulado no más que un número igual al número (k) máximo predeterminado de rutas de tarifa menos costosas en la pila y el valor de la primera arista de gráfica adicional sea mayor que el valor más alto de las rutas de tarifa acumulado en la pila.

4. El sistema de cualquiera de las reivindicaciones 1 a 3, en el que los datos de viaje comprenden además al menos uno de entre un tipo de pasajero o un límite presupuestario y en el que la pluralidad generada de opciones de destino se genera usando al menos uno de entre el tipo de pasajero o el límite presupuestario.

5. El sistema de la reivindicación 1 a 4, en el que el motor (105) de comprador está adaptado además para aceptar una o más solicitudes (615) temáticas y en el que la solicitud (615) temática se usa, además, para generar la lista de la pluralidad de opciones de destino.

6. El sistema de cualquiera de las reivindicaciones anteriores, en el que el motor (105) de comprador está adaptado además para validar al menos una opción de tarifas para al menos una de la pluralidad de opciones de destino.

7. El sistema de una cualquiera de las reivindicaciones 1 a 6, en el que un ordenador (150) personal está conectado a través de una red (130) a dicho sistema.

8. Un procedimiento de producción de una pluralidad de opciones de destino que comprende:

- recibir al menos un origen (610) y un intervalo (630, 640) de fechas; -enviar una solicitud a un par de estructuras (220, 230) de datos, pudiendo las estructuras (220, 230) de datos actualizarse con datos de viaje que comprenden al menos un origen (221) , un destino (225) , un precio reservable y unas fechas reservables, comprendiendo el par de estructuras de datos, por un lado, una gráfica de nodos con nodos y aristas en la que los nodos son los destinos de viaje y en la que cada una de las aristas hace referencia a una tarifa de viaje más baja entre los dos nodos que conectan, y por otro lado, un árbol de tarifas construidas para cada arista de gráfica y que comprende una raíz que mantiene la tarifa de viaje más baja de la arista; -extraer rutas de tarifa a partir del par de estructuras de datos, con el fin de determinar las rutas de tarifa menos costosas, comprendiendo dicha extracción de ruta de tarifa construir, para cada par de origen y destino, una pila mantenida organizada como un árbol binario y configurada para acumular un número (k) máximo predeterminado de rutas de tarifa menos costosas entre el origen y el destino durante la extracción; -devolver una pluralidad de resultados de la estructura (220, 230) de datos que corresponde a una lista de opciones de destino accesible desde el origen (610) y las fechas reservables dentro del intervalo (630, 640) de fechas.

9. El procedimiento de la reivindicación anterior, en el que el árbol binario de la pila comprende un nodo padre cuya clave del mismo es una ruta de tarifa más grande que las rutas de tarifa de dos nodos hijo correspondientes a dicho nodo padre y en el que un nodo raíz mantiene una ruta de tarifa más costosa.

10. El procedimiento de la reivindicación anterior, en el que la construcción de la pila comprende:

a-inicializar la pila con una primera ruta de tarifa de longitud uno correspondiente a una conexión directa entre el origen y el destino de un par de origen y destino, b-determinar una primera arista de gráfica de la gráfica de un nodo que sale desde el origen, manteniendo dicha primera arista de gráfica la ruta de tarifa más baja desde el origen; c-determinar una segunda arista de gráfica de la gráfica de un nodo que sale desde el destino, manteniendo dicha segunda arista de gráfica la ruta de tarifa más baja desde el destino, d-construir una nueva ruta de tarifa con la primera arista de gráfica y la segunda arista de gráfica, e-comprobar si el número (k) máximo predeterminado de rutas de tarifa menos costosas ha sido añadido ya a la pila, f-si se ha acumulado más que el número (k) máximo predeterminado de rutas de tarifa menos costosas en la pila, eliminar la ruta de tarifa más costosa de dicha pila, g-determinar una segunda arista de gráfica adicional de la gráfica del nodo que sale desde el destino, manteniendo dicha segunda arista de gráfica una ruta de tarifa más baja adicional desde el destino, h-si se ha acumulado menos que el número (k) máximo predeterminado de rutas de tarifa menos costosas en la pila y si la suma de los valores de la primera arista de gráfica y de la segunda arista de gráfica adicional es menor o igual que el valor más alto de las rutas de tarifa acumuladas en la pila, construir una nueva ruta de tarifa con la primera arista de gráfica y la segunda arista de gráfica adicional, i-repetir las etapas c a h hasta que se haya acumulado más de o un número igual al número (k) máximo predeterminado de rutas de tarifa menos costosas en la pila y si la suma de los valores de la primera arista de gráfica y de la segunda arista de gráfica adicional es mayor que el valor más alto de las rutas de tarifa acumuladas en la pila; j-seleccionar una primera arista de gráfica adicional de la gráfica del nodo que sale desde el origen, manteniendo dicha primera arista de gráfica adicional una ruta de tarifa más baja adicional desde el origen; k-repetir las etapas c a j hasta que: se haya acumulado no más que un número igual al número (k) máximo predeterminado de rutas de tarifa menos costosas en la pila y el valor de la primera arista de gráfica adicional sea mayor que el valor más alto de las rutas de tarifa acumulado en la pila.

11. El procedimiento de cualquiera de las reivindicaciones 8 a 10, en el que la solicitud incluye además al menos uno de entre un límite presupuestario y un tipo de pasajero y la lista devuelta de resultados corresponde además al menos al límite presupuestario o al tipo de pasajero.

12. El procedimiento de cualquiera de las reivindicaciones 8 a 11, que comprende además enviar una o más solicitudes (615) temáticas a la estructura (220, 230) de datos y devolver una pluralidad de resultados correspondientes además a las una o más solicitudes (615) temáticas.

13. El procedimiento de una cualquiera de las reivindicaciones 8 a 12, que comprende además validar al menos una opción de tarifas entre un origen y al menos una de las opciones de destino.

14. Un producto de programa de ordenador almacenado en un medio de almacenamiento legible por ordenador no transitorio que comprende un código legible por ordenador para hacer que al menos un ordenador haga funcionar el procedimiento de una de las reivindicaciones 8 a 13.