Note: Descriptions are shown in the official language in which they were submitted.
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
1
Procédé pour la mise en place d'une séquence de données
permettant la génération d'un voyage
La présente invention concerne un procédé pour la mise en
place à l'aide d'un ordinateur d'une séquence de données permettant la
génération d'un voyage, lequel procédé comporte l'usage d'une première
table dans laquelle est stocké un premier ensemble de N données,
chaque donnée (POI; ; 1 < i <_ N) identifiant un point d'intérêt pouvant
faire partie de voyages, lequel procédé comporte également la réception
de données d'utilisateur introduites par un utilisateur et qui se rapportent
audit voyage à mettre en place.
Un tel procédé est connu de l'article de Jean-Marc Godart
intitulé Combinatorial optimisation, based decision support system for
trip planning et publié dans International conference on information and
communication technologies in tourism, Innsbruck 1999, Springer Verlag
Austria 1999, pages 318-327. Suivant le procédé connu l'utilisateur
introduit des données d'utilisateur se rapportant au voyage qu'il envisage
de faire. Ces données d'utilisateur ainsi que les données stockées dans
la première table sont utilisées pour composer un voyage.
Un inconvénient du procédé connu est qu'il n'est pas
évident de produire de façon efficace un voyage à partir de ce premier
ensemble de données.
L'invention a pour but de réaliser un procédé pour la mise
en place à l'aide d'un ordinateur d'une séquence de données permettant
la génération d'un voyage, lequel procédé permet de structurer les
données de façon à obtenir un traitement rapide du procédé n'entraînant
pas une longue attente pour l'utilisateur.
A cette fin un procédé suivant l'invention est caractérisé en
ce que les données d'utilisateur sont corrélées aux points d'intérêt afin
de prélever dans la première table un premier sous-ensemble de F (F <
N) données identifiant des points d'intérêt corrélées aux données
d'utilisateur, et en ce qu'à chaque donnée (POI;) dudit premier ensemble
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
2
de données est associé un premier identificateur (Lp ; 1 < p < P ; P <_ N)
identifiant un lieu géographique où est situé le point d'intérêt identifié par
la donnée (POI;), lequel procédé comporte également l'usage d'une base
de données indiquant entre chaque fois un premier couple ((Lr,Lj) ; 1 _< r
<_ P ; 1 <_ j < P) de lieux géographiques une distance (Odra) et une durée
( trj) pour se rendre du lieu géographique Lr au lieu géographique Lj,
lequel usage de la base de données est réalisé en formant à partir du
premier sous-ensemble de F données un deuxième sous-ensemble de G
(G < F ; G <_ P) premiers identificateurs reprenant les premiers
identificateurs associés aux données reprises dans le premier sous-
ensemble, et en formant chaque fois un deuxième couple ((Lp)k, (Lp)m ; 1
<_ k <_ G ; 1 < m <_ G) de premiers identificateurs à l'aide des premiers
identificateurs repris dans le deuxième sous-ensemble, lesquels couples
((Lp)k, (Lp)m) de premiers identificateurs étant alors utilisés pour prélever
dans la base de données chaque fois la distance (A(dp)km) et la durée
(A(tp)km) pour se rendre du lieu géographique (Lp)k au lieu géographique
(Lp)m, une première matrice GxG étant construite en mettant en chaque
endroit (k,m) la distance (A(dp)km) et la durée (A(tp)km) prélevées dans la
base de données, les données du premier sous-ensemble de données
étant ensuite utilisées pour former des troisièmes couples de données
(POIp)q, (POlp)s (1 <_ q < F ; 1 <_ s <_ F) et pour former une deuxième
matrice FxF en prélevant dans la première matrice pour chaque couple
de données (POIp)q, (POlp)s à l'aide de leur premier identificateur ((Lp)k,
(Lp)m) associé chaque fois à la donnée (POIp)q, (POlp)s la distance
(A(dp)km) et la durée ( (tp)km) et en mettant en chaque endroit (q,s) la
distance (A(dp)km) et la durée (A(tp)km) prélevées dans la première
matrice, ladite séquence de données étant ensuite construite à l'aide de
la distance (L(dp)km) et la durée (A(tp)km) présentes dans la deuxième
matrice FxF pour chacun des couples (POIp)q, (POlp)S. En associant à
chaque donnée un premier identificateur on parvient à établir un lien
entre le point d'intérêt et le lieu géographique où se trouve ce point
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
3
d'intérêt. Comme, de plus, différents points d'intérêt peuvent se trouver
au même endroit, l'usage des premiers identificateurs permet de limiter
le nombre d'éléments à traiter ultérieurement. L'usage de la base de
données permet de stocker les distances et les durées de façon efficace,
puisqu'elles sont stockées en faisant usage d'une structure basée sur les
premiers identificateurs. En n'utilisant que les premiers identificateurs
faisant partie du deuxième sous-ensemble pour accéder à la base de
données lors de la formation du voyage le temps pour exécuter le
procédé est considérablement réduit, ce qui contribue sensiblement à
l'efficacité du procédé. A partir de la première matrice, la deuxième
matrice peut rapidement être formée, ce qui permet de revenir à ces
points d'intérêt sélectionnés sur base des données utilisateur et donc de
former la séquence de données pour générer le voyage.
Une première forme de réalisation préférentielle d'un
procédé suivant l'invention est caractérisée en ce que chaque premier
identificateur (Lp) est formé par une valeur numérique distincte (LoclDp),
à chacun des premiers identificateurs (Lp) une valeur d'index (index-w)
est associée, laquelle valeur d'index indique la position de chaque
premier identificateur dans un rangement des premiers identificateurs
réalisé sur base de ladite valeur numérique, ladite base de données
comprend une troisième matrice qui est structurée et adressée à l'aide
de cette valeur d'index et qui contient la distance et la durée de chacun
des premiers couples. Ainsi la base de données peut être adressée à
l'aide des valeurs d'index, ce qui permet une gestion plus structurée et
donc plus rapide.
Une deuxième forme de réalisation préférentielle d'un
procédé suivant l'invention est caractérisée en ce que sur base des
valeurs numériques formant les premiers identificateurs un deuxième
identificateur (MaxLoclD) est formé indiquant la valeur numérique la plus
élevée attribuée à un premier identificateur, une deuxième table
comprenant un nombre d'emplacements au moins égal à la valeur
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
4
numérique dudit deuxième identificateur étant ensuite formée,
l'ensemble des premiers identificateurs étant ensuite parcouru et pour
chacun des premiers identificateurs il est mis à l'endroit dont la position
dans la deuxième table correspond à la valeur numérique attribuée au
premier identificateur considéré une valeur prédéterminée, le nombre
d'endroits dans la deuxième table où une telle valeur prédéterminée est
reprise étant ensuite compté pour former un troisième identificateur
(NumL). Ceci permet de structurer l'ensemble des premiers
identificateurs.
Une troisième forme de réalisation préférentielle d'un
procédé suivant l'invention est caractérisée en ce qu'une troisième table
est formée dont le nombre d'emplacements correspond au nombre
indiqué par le troisième identificateur, ladite valeur d'index (index-w)
étant associée aux premiers identificateurs en plaçant les premiers
identificateurs dans la troisième table suivant l'ordre dans lequel ils sont
repris dans la deuxième table, la valeur d'index attribuée correspondant
à l'ordre de succession suivant lequel les premiers identificateurs sont
repris dans la troisième table. Ceci permet d'attribuer par une simple
logique les valeurs d'index.
Une quatrième forme de réalisation préférentielle d'un
procédé suivant l'invention est caractérisée en ce pour le deuxième
sous-ensemble ladite valeur d'index est également reprise dans ce
deuxième sous-ensemble, et en ce que lesdits deuxièmes couples sont
formés par les valeurs d'index attribuées aux premiers identificateurs
formant lesdits deuxièmes couples. Ainsi il devient possible d'adresser la
base de données à l'aide de la valeur d'index également pour les
premiers identificateurs repris dans le deuxième sous-ensemble.
Une cinquième forme de réalisation préférentielle d'un
procédé suivant l'invention est caractérisée en ce qu'une quatrième table
ayant un nombre d'emplacements égal au deuxième identificateur est
formée, chacun des premiers identificateurs repris dans le deuxième
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
sous-ensemble étant ensuite repris dans la quatrième table à
l'emplacement dont la position correspond à la valeur numérique
attribuée au premier indicateur considéré, lesdits premiers identificateurs
repris dans la quatrième table étant ensuite substitués par leur valeur
5 d'index. Ceci permet de logiquement grouper les premiers identificateurs
du deuxième sous-ensemble.
Une sixième forme de réalisation préférentielle d'un
procédé suivant l'invention est caractérisée en ce que la base de
données comporte un troisième ensemble comprenant des premiers
facteurs d'adaptation permettant d'introduire dans ladite séquence une
adaptation en fonction du moyen de locomotion utilisé pour parcourir
ladite distance. Ainsi la séquence de voyage peut être modulée en
fonction du moyen de locomotion utilisé pour parcourir ladite distance.
L'invention sera maintenant décrite plus en détails à l'aide
des dessins qui illustrent une forme préférentielle d'un procédé suivant
l'invention. Dans les dessins :
la Figure 1 illustre les différentes phases de construction de la
base de données ;
la Figure 2 illustre les différentes phases de construction de la
deuxième matrice utilisée pour évaluer la séquence de données ; et
la Figure 3 illustre les différentes étapes du procédé suivant
l'invention.
Dans les dessins une même référence a été attribuée à un même
élément ou à un élément analogue.
Planifier le voyage d'un touriste ou d'un utilisateur consiste
à sélectionner et combiner, dans un voyage, les produits touristiques les
plus appropriés en prenant en compte les centres d'intérêts, les
desiderata et les contraintes du touriste. A titre illustratif, envisageons
différents produits touristiques, à savoir les logements (hôtels, chambres
d'hôtes, camping, ...) et les activités (musées, parcs d'attractions,
randonnées, ... ). Ainsi, un voyage sera entre autre composé d'un point
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
6
d'origine, d'activités, de logements et d'un point de destination. Ces
différents types d'éléments seront désignés par le terme points d'intérêt
(POI). Bien entendu, les trajets entre les points d'intérêt composant un
voyage sont également gérés dans le procédé suivant l'invention. Il va de
soi que l'invention n'est pas limitée aux points d'intérêt cités en tant
qu'exemple, et que bien entendu d'autres formes de réalisation peuvent
être envisagées.
Pour produire un voyage le procédé suivant l'invention fait
appel à une base de données dont la structure sera décrite à l'aide de la
Figure 1. Comme décrit au préalable la génération d'un voyage nécessite
des points d'intérêt (POI) pouvant faire partie du voyage. Il est donc
nécessaire de grouper et de mémoriser ces points d'intérêt. A cette fin le
procédé suivant l'invention fait appel à une première table 1 dans
laquelle est stockée un premier ensemble de N données (POI;), chaque
donnée (POI; ; 1 <_ i <_ N) identifiant un point d'intérêt. Chaque point
d'intérêt est lié à un lieu géographique indiquant où il est situé
géographiquement. La localisation d'un point d'intérêt est, par exemple,
défini par sa longitude et sa latitude. Cette information concernant le lieu
géographique est nécessaire pour construire le voyage afin de pouvoir
prendre en compte le déplacement d'un point d'intérêt POIX vers un
autre point d'intérêt POIy. A cette fin il est associé à chaque donnée
(POI;) dudit premier ensemble de données un premier identificateur (Lp ;
1 <_ p <_ P ; P <_ N) identifiant le lieu géographique où est situé le point
d'intérêt identifié par la donnée (POI;). Que P <_ N s'explique par le fait
qu'en un même lieu géographique Lp il peut y avoir plus d'un point
d'intérêt. Ainsi par exemple dans un parc d'attraction situé au lieu
géographique L5 on peut avoir un hôtel P013, un théâtre P019 et une
attraction P0111. Après avoir attribué à chaque lieu géographique un
premier identificateur on obtient un deuxième ensemble de P premiers
identificateurs.
Suivant l'invention les informations relatives aux trajets lors
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
7
d'un voyage sont calculées à partir d'une base de données 4 de trajets
structurés de façon adaptée et généralement gigantesque qui peut par
exemple prendre la forme d'un ou plusieurs fichiers informatiques à
accès direct. Cette base de données structurée contient les distances Ad
et durées At de trajet pour l'ensemble des trajets possibles entre tous les
couples de lieux géographiques 2 se trouvant dans la première table des
points d'intérêt. Il faut noter qu'ici ce sont des informations relatives aux
trajets entre deux lieux géographiques, et non entre deux points d'intérêt.
La base de données 4 est construite en indiquant entre chaque fois un
premier couple ((Lr,Lj) ; 1 <_ r <_ P ; 1 <_ j <_ P) de lieux géographiques du
deuxième sous-ensemble une distance (,~,drj) et une durée (Atrj) pour se
rendre du lieu géographique Lr au lieu géographique Lj.
Pour toutefois permettre un accès facile à cette base de
données il est important de mettre une structure logique dans la façon
d'y stocker la distance et la durée pour chacun des premiers couples.
Cette technique permet évidemment de réduire les dimensions de la
base de données des trajets. Le volume requis pour ces données reste
cependant important et nécessite une grande place mémoire. De plus,
seulement une petite partie de ces données sera réellement utilisée lors
de la construction d'un voyage demandé par l'utilisateur. Il faut toutefois
souligner que plusieurs bases de données des trajets pourraient être
utilisées simultanément, par exemple pour différents pays ou régions,
afin de limiter la taille de chacune d'entre-elles.
Le premier identificateur est par exemple chaque fois formé
par une valeur numérique distincte (LocID). Cette valeur numérique
distincte est de préférence une valeur positive. L'ensemble de ces lieux
géographiques constitue le deuxième ensemble de P (P s N) lieux
géographiques. Pour chaque premier couple de premiers identificateurs
((Lr,Lj) ; 1 : r P, 1 _< j s P ), la distance et la durée d'un trajet entre ce
couple de localisations sont alors calculées.
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
8
Pour des raisons de clarté, il a été choisi de calculer un seul
trajet pour chaque couple de premiers identificateurs. Ceci n'est bien
évidemment pas restrictif et moyennant quelques modifications plusieurs
trajets (ou aucun trajet) entre un couple de premiers identificateurs (Lr,Lj)
pourraient être envisagés, comme par exemple pas de moyen d'accès
de Lr vers Lj, trajet le plus court et trajet le plus rapide de Lr vers Lj,,
etc.
La base de données peut le cas échéant comporter pour un nombre
prédéterminé de points d'intérêt un coefficient d'évaluation permettant
d'évaluer l'intérêt du point d'intérêt considéré. Ces coefficients
d'évaluation peuvent être un coût et/ou une mesure d'attractivité
associée au point d'intérêt considéré. Si par exemple le point d'intérêt
concerne une attraction le coût sera le prix d'entrée, si le point d'intérêt
concerne un logement le coût sera le tarif par nuit. Ce coefficient d'intérêt
sera pris en considération lors de la génération de la séquence servant à
produire le voyage. Une adaptation de la séquence en fonction du moyen
de locomotion (voiture, avion, train, etc..) utilisé pour parcourir ladite
distance est également possible.
La base de données temporaire 3 contient donc les
informations de distance (Adrj) et de durée (Otrj) pour se rendre du lieu
géographique Lr au lieu géographique Lj. Cette base de données des
distances et de durées des trajets peut par exemple prendre la forme
d'un fichier informatique. La structure de ce fichier est la suivante
L1 [T] L2 [T] d(1,2) [T] At(1,2) [LB]
L1 [T] L3[T] Ad(1,3) [T] At(1,3) [LB]
L1 [T] L4 [T] dd(1,4) [T] At(1,4) [LB]
... et ainsi de suite pour tous les trajets du L1 vers tous les autres L,
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
9
L2 [T] L1[T] Ad(2,1) [T] nt(2,1) [LB]
L2[T] L3[T] Ad(2,3) [T] t(2,3) [LB]
L2 [T] L4[T] Ad(2,4) [T] At(2,4) [LB]
... et ainsi de suite pour tous les trajets du L2 vers tous les autres L,
ainsi
que pour toutes les combinaisons de L.
Dans l'exemple ci-dessus, [T] symbolise une tabulation,
[LB] le retour à la ligne, Od(r,j) la distance du lieu géographique Lr au
lieu géographique Lj et At(r,j) la durée pour se déplacer du lieu
géographique Lr au lieu géographique Lj. Il faut noter que l'ordre des
lignes dans ce fichier n'a pas d'importance.
Pour construire la base de données temporaire on calcule
pour chaque couple de points d'intérêt la distance (Ad) et la durée (At) de
trajet entre leur lieu géographique respectif. Pour ce faire il a été choisi
d'utiliser par exemple un outil commercial spécifique, proposé par la
société GeoSolutions (Opti-Time), pour le transport par route (voiture,
marche, vélo, etc.). Toutefois d'autres outils pourraient parfaitement être
utilisés pour ce faire. En particulier, tout outil qui inclut une base de
données routière (type TeleAtlas ou NavTech) et un algorithme de plus
court chemin (bien connus) peut se substituer à celui retenu. On peut
aussi y substituer le calcul d'une distance et d'une durée de trajet
approximatives, par exemple calculées "à vol d'oiseau".
A partir de cette structure de données des trajets
temporaire, la base de données des trajets dans un format structuré 4
sera construite. Cette base de données structurée contiendra les
éléments suivants :
un deuxième identificateur appelé MaxLoclD et dont
la valeur numérique est égale à la valeur numérique maximale,
c'est-à-dire celle qui est la valeur numérique (LoclDp) la plus élevée
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
attribuée à un premier identificateur présent dans le deuxième
ensemble;
= un troisième identificateur appelé NumL et dont la
valeur numérique est égale à P, qui indique le nombre total de
5 premiers identificateurs utilisés présents dans la base de données
en construction;
= une valeur d'index (index-w), qui indexe les premiers
identificateurs présents dans la base de données en construction;
= une troisième matrice PxP qui contient les distances
10 et durées des trajets entre les premiers identificateurs pris deux à
deux présents dans la base de données temporaire.
Pour former ce deuxième et troisième identificateurs la
base de données temporaire, à savoir le fichier informatique, est
parcourue une première fois afin de vérifier la cohérence des données,
c'est-à-dire que chacune des valeurs numériques (LocID) attribuées aux
premiers identificateurs soient positives et que les distances et durées
soient cohérentes. Le deuxième identificateur (MaxLoclD) est déterminé
en recherchant parmi les premiers identificateurs celui qui possède la
plus grande valeur numérique. Cette plus grande valeur numérique est
ensuite mémorisée.
L'étape suivante est la détermination du troisième
identificateur (NumL), qui est déterminé en comptant dans le deuxième
ensemble le nombre de premiers identificateurs différents effectivement
présents dans la base de données temporaire. En effet, si par exemple
le deuxième identificateur vaut MaxLoclD= 7, il se peut très bien que
certaines valeurs numériques n'aient pas été utilisées pour les premiers
identificateurs. Ainsi, par exemple, il se pourrait qu'il n'y ait aucun
premier identificateur ayant la valeur numérique L=3. Il serait alors inutile
de stocker des données concernant ce premier identificateur L=3.
Pour calculer le troisième identificateur (NumL), une
deuxième table comprenant un nombre d'emplacement au moins égal à
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
11
la valeur numérique dudit deuxième identificateur est formée. Les
emplacements étant numérotés en ordre croissant. La base de données
temporaire 3 est ensuite parcourue et pour chacun des premiers
identificateurs présents dans cette base de données temporaire il est mis
à l'emplacement dont la position dans la deuxième table correspond à la
valeur numérique attribuée au premier identificateur considéré une valeur
prédéterminée. Ceci est par exemple réalisé en stockant lors de la
formation de la deuxième table, une valeur initiale (par exemple 0) dans
chacun des emplacements de la deuxième table. Lors du prochain
parcours de la base de données temporaire, lorsqu'un trajet allant du
premier identificateur Lr vers le premier identificateur Lj est lu, une valeur
numérique prédéterminée (par exemple 1) est inscrite dans ces
emplacements de la deuxième table dont les numéros d'ordre
correspondent aux valeurs numériques attribuées aux premiers
identificateurs Lr et Lj. Le nombre d'endroits dans la deuxième table où
une telle valeur prédéterminée (1) est reprise étant ensuite compté pour
former le troisième identificateur (NumL). Ce troisième identificateur sera
de préférence stockée dans la base de données.
Par exemple, si MaxLoclD = 7 et si les valeurs numériques
des premiers identificateurs présents dans la base de données
temporaire sont 1, 4, 5, 6 et 7, alors la deuxième table aura sept
emplacements tous initialisés à la valeur 0 comme repris dans l'exemple
ci-dessous :
0 0 0 0 0 0 0
1 2 3 4 5 6 7
Puisque les valeurs numériques 2 et 3 ne sont pas présentes dans
l'exemple considéré, le parcours de la base de données temporaire
donnera ensuite :
1 0 0 1 1 1 1
1 2 3 4 5 6 7
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
12
Compter le nombre d'emplacements dans la deuxième
table contenant la valeur numérique prédéterminée 1 fournit la valeur P=
NumL du troisième identificateur. Dans l'exemple, P=5.
Une valeur d'index (index-w) sera associée aux premiers
identificateurs présents dans la deuxième table, laquelle valeur d'index
indique la position de chaque premier identificateur dans un rangement
des premiers identificateurs réalisé sur base de ladite valeur numérique,
en particulier l'ordre de rangement dans la troisième table sera utilisé à
cette fin. La valeur d'index du premier identificateur sera la place ou la
position qu'il occupe dans le rangement des premiers identificateurs
présents dans le fichier informatique. Pour créer cette valeur d'index, la
troisième table sera formée comprenant P emplacements, les
emplacements de la troisième table étant numérotés en ordre croissant.
Le nombre d'emplacements de la troisième table correspond au nombre
indiqué par le troisième identificateur NumL. Ladite valeur d'index (index-
w) étant associée aux premiers identificateurs en plaçant les premiers
identificateurs dans la troisième table suivant l'ordre dans lequel ils sont
repris dans la deuxième table, la valeur d'index attribuée correspondant
à l'ordre de succession suivant lequel les premiers identificateurs sont
repris dans la troisième table. La troisième table sera de préférence
intégrée dans la base de données.
Pour chacun (p ; 1 <_ p <_ P) des emplacements de la
troisième table, le numéro d'ordre correspondant à la p-ième valeur
numérique prédéterminée présente dans la deuxième table est inscrit à
l'emplacement p dans la troisième table. Dans l'exemple décrit ci-dessus,
la troisième table est :
1 4 5 6 7
1 2 3 4 5
et, ainsi par exemple, le premier identificateur dont l'index est 4 vaut 6.
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
13
Une troisième matrice PxP est ensuite construite en mettant
en chaque endroit (r,j) la distance ( drj) et la durée ( tr), prélevées dans
la base de données temporaire, pour se rendre du lieu géographique Lr
au lieu géographique Lj, c'est-à-dire pour se rendre du lieu géographique
d'index r au lieu géographique d'index j. Par exemple, l'endroit (3,5) de
cette troisième matrice contient la distance et la durée pour se rendre du
lieu géographique identifié par la valeur numérique 5 = valeur du
troisième emplacement de la troisième table) au lieu géographique
identifié par la valeur numérique 7 (= valeur du cinquième emplacement
de la troisième table).
Une vérification de la consistance des données est
effectuée lors de la phase de construction de cette troisième matrice ;
c'est-à-dire une vérification qu'il n'existe pas deux trajets concernant un
même couple de lieux géographiques avec des distances et durées
différentes et que l'on dispose des informations de trajet pour chaque
couple de premiers identificateurs présents dans la base de données
temporaire.
Il faut remarquer que la construction de cette base de
données structurée 4 pourrait être adapté dans le cas de données
symétriques, c'est-à-dire si le trajet pour aller de Lr à Lj est le même que
le trajet pour aller de Lj à Lr.
Soulignons que cette troisième matrice PxP ne devra être
modifiée que lorsque l'ensemble des N points d'intérêt est modifié, ou
que la distance ou la durée entre deux lieux géographique change. Elle
est indépendante des voyages calculés.
Pour construire un voyage, l'utilisateur va faire appel à une
interface utilisateur, qui a notamment pour rôle d'obtenir de l'utilisateur
les informations essentielles à la construction d'un voyage adapté à ses
attentes. Cette interface est de préférence un site internet destiné au
grand public. Bien évidemment, d'autres technologies peuvent être
envisagées (interface mobile, ...), à destination du grand public ou de
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
14
professionnels. A l'aide de cette interface, l'utilisateur va introduire des
données d'utilisateur 9 qui se rapportent au voyage à mettre en place.
Avant d'obtenir une première proposition de voyage, l'utilisateur devra
simplement répondre à quelques questions, ou introduire des données
comme la ou les destinations, le ou les logement(s) et la ou les
attraction(s) pour lesquel(le)s il souhaite qu'ils fassent partie du voyage.
Ces questions posées à l'utilisateur sont bien entendu un choix parmi
d'autres.
Par exemple, l'utilisateur pourra entre autres déterminer :
1. la (ou les) région(s) qu'il souhaite visiter ;
2. le point de départ de son voyage. Ce point de
départ peut être fixé ou non ;
3. les dates de son voyage. Ces dates peuvent
être définies de manière fixe (à savoir une période de voyage
précise), ou ces dates peuvent être flexibles (à savoir un nombre
de jours de voyage minimum, un nombre de jours de voyage
maximum et une période de voyage plus ou moins large);
4. la forme de son voyage :
un voyage circulaire, à savoir un
voyage commençant et terminant au même endroit,
un voyage linéaire, à savoir un voyage
ne se finissant pas forcément là ou il a commencé ;
5. si le voyage est linéaire, le point d'arrivée du
voyage peut être fixé ou non.
Il va de soi que l'invention n'est pas limitée à l'ensemble de
ces critères et qu'ils sont mentionnés à titre d'exemple, mais bien
entendu d'autres formes de réalisation peuvent être utilisées.
Sur base des réponses ou des données introduites, à
savoir les données utilisateur, l'interface utilisateur va les corréler aux
points d'intérêt POI stockés dans la première table 1 et va sélectionner et
prélever, parmi l'ensemble des N points d'intérêt POI stockés dans la
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
première table, un premier sous-ensemble de F (F <_ N) points d'intérêt 5
POli, qui seront utilisés dans la construction d'un voyage adapté aux
desiderata de l'utilisateur, comme illustré à la Figure 2. Comme à chacun
des points d'intérêt est associé un premier identificateur Lp, il sera
5 également sélectionné. Ainsi par exemple les points d'intérêt suivants
sont sélectionnés-
0 les origines potentielles du voyage, soit une
ville (ou village) ou un aéroport fixé par l'utilisateur, soit une partie
des villes (ou villages) ou aéroports présents dans la première
10 table 1;
= les activités pouvant être réalisées lors du
voyage, à savoir les activités présentes dans la première table 1,
se situant dans les régions à visiter et ouvertes aux dates du
voyage ;
15 = les logements où l'on peut séjourner lors du
voyage, à savoir les logements présents dans la première table 1,
qui se situent dans les régions à visiter et qui sont disponibles aux
dates du voyage ;
= les destinations potentielles du voyage, soit
une ville (ou village) ou un aéroport fixé par l'utilisateur, soit une
partie des villes (ou villages) ou aéroports présents dans la
première table 1.
L'ensemble des N points d'intérêt stockés dans la première
table peuvent être stockés dans différentes sous-tables. Certaines de
ces sous-tables peuvent être des sous-tables internes (locales à
l'interface utilisateur) et d'autres des bases de données externes. La
consultation des bases de données externes peut par exemple se faire
au travers de web services (par exemple en XML).
En particulier, en ce qui concerne le logement, une
connexion par web service à une base de données externe d'hôtels
gérée et tenue à jour en temps réel permet de connaître et d'exploiter les
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
16
disponibilités et coûts effectifs des logements possibles. Ceci est utile
pour construire des voyages réalistes. En effet, ces informations évoluent
de minute en minute.
Un moteur de calcul reçoit les données utilisateur, ainsi que
le premier sous-ensemble des F données. Ce moteur se chargera de la
construction de la séquence de données.
Ainsi il est transmis au moteur de calcul, entre autres, les
informations suivantes :
= les paramètres relatifs aux contraintes et objectifs à
prendre en compte dans l'optimisation,
= les informations relatives aux origines,
= les informations relatives aux activités et à leurs
heures d'ouverture,
= les informations relatives aux logements et à leurs
disponibilités et coûts,
= les informations relatives aux destinations.
Il est évident que certaines de ces informations pourraient
être supprimées et d'autres pourraient être ajoutées.
Les paramètres relatifs aux contraintes et objectifs à
prendre en compte dans l'optimisation incluent entre autres, par
exemple :
= une valeur indiquant si le voyage est circulaire ou
linéaire
= le nombre minimum de jours dans le voyage ;
= le nombre maximum de jours dans le voyage ;
= la période durant laquelle l'utilisateur veut voyager ;
= le montant à ne pas dépasser pour le coût total du
voyage ;
= le coût de transport par kilomètre.
Les informations relatives aux origines incluent, entre
autres, par exemple, pour chaque origine :
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
17
= un identifiant (ou un ensemble d'identifiants) de cette
origine;
= le premier identificateur.
Les informations relatives aux activités incluent, entre
autres, par exemple, pour chaque activité :
= un identifiant (ou un ensemble d'identifiants) de cette
activité;
= le premier identificateur ;
= ses heures d'ouverture ;
= son coût.
Les informations relatives aux logements incluent, entre
autres, par exemple, pour chaque logement :
= un identifiant (ou un ensemble d'identifiants) de ce
logement;
le premier identificateur ;
= ses disponibilités
= ses prix.
Les informations relatives aux destinations incluent, entre
autres, par exemple, pour chaque destination :
= un identifiant (ou un ensemble d'identifiants) de cette
destination
= le premier identificateur.
Il va de soi que l'invention n'est pas limitée à l'ensemble de
ces informations et qu'elles sont mentionnés à titre d'exemple, mais bien
entendu d'autres formes de réalisation peuvent être utilisées.
Avantageusement, la première table comporte pour un
nombre prédéterminé de points d'intérêt un coefficient d'évaluation
permettant d'évaluer l'intérêt du point d'intérêt considéré. Ceci permet,
lors de la construction de la séquence, d'utiliser le coefficient d'évaluation
pour construire ladite séquence et tenir ainsi compte de l'intérêt du point
d'intérêt considéré. Ce coefficient d'évaluation peut ainsi indiquer la
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
18
catégorie d'un hôtel, l'environnement (centre ville, campagne), la
présence de sites touristiques, etc. Le coefficient d'évaluation peut
également comporter un coût associé au point d'intérêt considéré,
comme par exemple le tarif pour passer la nuit. Le coefficient
d'évaluation peut également comporter une mesure d'attractivité
associée au point d'intérêt considéré. Ainsi, la séquence peut non
seulement comprendre ce coefficient d'évaluation, mais il est également
possible de l'utiliser lors de la mise en place de la séquence.
Dans le procédé suivant l'invention le moteur de calcul va
ensuite structurer les informations liées aux différents trajets entre les F
points d'intérêt du premier ensemble qui ont été sélectionnés sur base
des données de l'utilisateur, afin de construire une deuxième matrice des
trajets 8 entre ces F différents points d'intérêt pris deux à deux.
Pour construire la deuxième matrice ayant une dimension
dépendante des caractéristiques du voyage, le moteur de calcul passera
en revue l'ensemble des F points d'intérêt du premier sous-ensemble. Le
moteur de calcul référenciera leur lieu géographique et ne retiendra que
les informations liées aux trajets susceptibles d'être parcourus durant le
voyage, ignorant les autres.
Pour rendre le volume de travail à effectuer par le moteur
de calcul plus facile et ainsi obtenir une meilleure efficacité, le procédé
suivant l'invention comprend la formation, à partir du premier sous-
ensemble 5 de F données, d'un deuxième sous-ensemble 6 de G (G s F)
premiers identificateurs reprenant les premiers identificateurs Lp associés
aux données reprises dans le premier sous-ensemble. Que G s F
s'explique par le fait que dans le premier sous-ensemble il peut y avoir
des points d'intérêt situés à un même lieu géographique. La formation du
deuxième sous-ensemble 6 a également pour but d'utiliser pour les
points d'intérêt repris dans le premier sous-ensemble 5, c'est-à-dire ceux
qui ont été sélectionné sur base des données d'utilisateur, le premier
identificateur qui leur a été associé. Ainsi grâce aux premiers
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
19
identificateurs repris dans le deuxième sous-ensemble il devient possible
d'adresser la base de données 4, qui a été structurée à l'aide des
premiers identificateurs comme décrit ci-dessus. A partir des premiers
identificateurs Lp repris dans le deuxième sous-ensemble, le moteur de
calcul va former chaque fois un deuxième couple (((Lp)k, (Lp)m) ; 1 <_ k s
G ; 1 <_ m <_ G ) de premiers identificateurs.
Supposons, comme par exemple repris à la Figure 2, que le
premier sous-ensemble des points d'intérêt susceptibles de faire partie
du voyage est de taille 5 (F = 5) et que les premiers identificateurs
associés à ces points sont L1 (= 1), L2 (= 4) et L4 (= 6) (G = 3) :
Li L2 L2 L4 Li
(PO/i),/PO/1 (POI,)2/PO13 (PO1)3/PO14 (POI,)4/PO16 (POI,)5/PO16
Le moteur de calcul va lire la valeur NumL du troisième
identificateur et la valeur MaxLocID du deuxième identificateur dans la
base de données 4. Supposons que ces valeurs soient NumL = 5 et
MaxLoclD = 7. Il sera alors créée une quatrième table ayant un nombre
d'emplacements égal au deuxième identificateur MaxLoclD. Chacun des
premiers identificateurs repris dans le deuxième sous-ensemble sera
ensuite repris dans la quatrième table à l'emplacement dont la position
correspond à la valeur numérique attribuée au premier identificateur Lp
considéré. Lesdits premiers identificateurs repris dans la quatrième table
seront ensuite substitués par leur valeur d'index.
En pratique la quatrième table est d'abord remplie d'une
première valeur constante, par exemple -2.
2 2 2 -2 -2 -2 -2
1 2 3 4 5 6 7
Ladite première valeur constante sera ensuite remplacée
par une deuxième valeur constante -1 à ces emplacements de la
quatrième table où doivent être repris les premiers identificateurs du
deuxième sous-ensemble. Pour réaliser ce remplacement le moteur de
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
calcul va parcourir le premier sous-ensemble des points d'intérêt et
prélever à l'aide de la première table à chaque fois le premier
identificateur associé aux points d'intérêt repris dans le premier sous-
ensemble. Ensuite pour chaque premier identificateur ainsi prélevé le
5 moteur de calcul va substituer la première valeur constante par la
deuxième valeur constante -1 à tous les emplacements dont le numéro
d'ordre de l'emplacement correspond à la valeur numérique attribuée aux
premiers identificateurs prélevés.
j -1 -2 -2 -1 -2 -1 -2
1 2 3 4 5 6 7
G=3
10 Lors du parcours des premiers identificateurs associés aux
points d'intérêt du premier sous-ensemble, le moteur de calcul vérifie
également que ceux-ci sont inférieurs ou égaux au deuxième
identificateur MaxLoclD. Si tel n'est pas le cas un signal d'erreur est
produit. En totalisant le nombre de deuxièmes valeurs constantes dans la
15 quatrième table, on obtient le nombre G (G <_ F) égal au nombre de lieux
géographique différents que l'on devra récupérer dans la base de
données 4. Ce nombre G forme un quatrième identificateur.
Le moteur de calcul lit ensuite dans la troisième table pour
chacun des premiers identificateurs repris dans la quatrième table les
20 valeurs d'index (index-w) associées à ces premiers identificateurs. La
quatrième table sera complétée en y introduisant les valeurs d'index des
premiers identificateurs repris dans le deuxième sous-ensemble.
Pour réaliser ceci, pour chacun des premiers identificateurs
(Lp)k (k ; 1 <_ k <_ G) lu dans la quatrième table, si à l'emplacement ayant
le numéro d'ordre (Lp)k la deuxième valeur constante -1 est présente, on
la remplace par la valeur d'index attribuée au premier identificateur (Lp)k.
1 -2 -2 2 -2 4 -2
1 2 3 4 5 6 7
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
21
A l'aide de la quatrième table reprenant les valeurs d'index
des lieux géographiques différents qui sont susceptibles de faire partie
du voyage, le moteur de calcul est en mesure de prélever de la base de
données 4 toutes les distances (A(dp)km) et les durées (L (tp)km) pour se
rendre du lieu géographique (Lp)k au lieu géographique (Lp)m ((Lp)k,
(Lp)m ; (1 <_ k <_ G ; 1 <_ m <_ G ). Après ce prélèvement une première
matrice 7 GxG sera construite en mettant en chaque endroit (k,m) la
distance (A(dp)km) et la durée (A(tp)km) prélevées dans la base de
données 4. Ainsi, cette première matrice contient la distance et la durée
entre tous les couples de lieux géographique différents correspondant
aux points d'intérêt susceptibles d'être dans le voyage. Les données
(POI;) du premier sous-ensemble de données seront ensuite utilisées
pour former des troisièmes couples de données ((POli)q, (POl;)s) (1 <_ q s
F ; 1 < s <_ F) où q et s représentent une numérotation dans le premier
sous-ensemble. Le point d'intérêt (POI;)q représentant celui ayant le
numéro d'ordre q dans le premier sous-ensemble. Dans l'exemple repris
ci-dessus, (Ad(3,2)) est la distance pour aller du lieu géographique L4 au
lieu géographique L2.
La première matrice, qui est structurée à l'aide des
premiers identificateurs du deuxième sous-ensemble, sera alors utilisée
pour former une deuxième matrice FxF. En effet, puisque à chaque
premier identificateur est associé au moins un point d'intérêt, il suffit de
prélever pour chaque couple de données ((POl;)q, (POli)S) du premier
sous-ensemble à l'aide de leur premiers identificateurs ((Lp)k, (Lp)m) la
distance ((Adp)km) et la durée (A(tp)km). La première matrice est alors
formée en mettant en chaque endroit (q,s) la distance ((Adp)km) et la
durée (A(tp)km) qui viennent d'être prélevées.
Ainsi, par exemple, la durée du trajet entre le quatrième
point d'intérêt P016 et le deuxième point d'intérêt P013 dans l'ensemble
des points d'intérêt susceptibles de faire partie du voyage est stockée
dans la composante (3,2) de la deuxième matrice GxG.
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
22
La séquence de données permettant la génération du
voyage sera ensuite construite à l'aide de la distance ((Adp)km) et de la
durée (A(tp)km) présentes dans la deuxième matrice FxF pour chacun
des couples ((POlj)q, (POl;)S). Maintenant, le moteur de calcul pourra très
rapidement trouver les informations relatives à un trajet à réaliser lors du
voyage.
Un voyage est essentiellement caractérisé par sa séquence
(ordonnée) de points d'intérêt et éventuellement par d'autres variables
nécessaires à l'optimisation. Il doit satisfaire un certain nombre de
contraintes et est évalué selon un ou plusieurs objectifs. Clairement, pour
caractériser entièrement un voyage, il suffit de connaître la séquence
(ordonnée) des points d'intérêt qui le constituent et sont repris dans le
premier sous-ensemble, ainsi que les moments auxquels commencent et
terminent la visite de ces points d'intérêt. Ainsi, pour chaque voyage
construit, on enregistre les éléments suivants qui caractérisent ce
voyage, à savoir la séquence des points d'intérêt qui constituent le
voyage et le moment du début de la visite à chacun des points d'intérêt,
qui constituent ce voyage ainsi que le temps nécessaire pour cette visite.
La première composante dans la séquence des points
d'intérêt fait référence au point d'intérêt, appartenant au premier sous-
ensemble de données, qui a été choisi comme origine du voyage. Les
composantes suivantes contiennent, dans leur ordre d'apparition dans le
voyage, les références aux points d'intérêt (activités et/ou logements),
appartenant au premier sous-ensemble de données, qui constituent le
voyage. La dernière composante dans la séquence des points d'intérêt
fait référence au point d'intérêt, appartenant au premier sous-ensemble
de données, qui a été choisi comme destination du voyage.
Un voyage doit satisfaire un certain nombre de contraintes.
En effet, les paramètres globaux et certaines informations fournies au
moteur de calcul (horaires d'ouverture, disponibilité, ...) se traduisent en
contraintes que doit respecter chaque voyage. Ainsi par exemple on peut
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
23
avoir une contrainte liée au budget maximum : la somme des coûts du
voyage ne doit pas dépasser le budget maximum fournit par l'utilisateur.
A titre d'exemple on présente maintenant des éléments sur
lesquels on peut se baser pour évaluer un voyage. On peut évaluer la
qualité d'un voyage selon différents critères (objectifs). Deux objectifs
principaux sont, par exemple, pris en compte : minimiser les coûts des
différentes composantes du voyage et maximiser l'attractivité (c'est-à-
dire l'intérêt) des différentes composantes du voyage. L'attractivité est
une mesure de l'intérêt d'un point d'intérêt. Les mesures de compromis
définies par l'utilisateur sont utilisées pour définir des pondérations
relatives à chacun des objectifs.
Le moteur de calcul construit un voyage adapté aux
attentes de l'utilisateur en partant d'un voyage initial simple construit sur
base de la séquence de données 10 obtenue comme décrit ci-dessus,
puis l'améliore par un processus d'optimisation.
Il faut observer que le mode de raisonnement appliqué par
la technologie s'oppose au raisonnement qu'aurait un homme du métier
s'il devait construire un voyage par lui-même, ou donc concevoir un
système informatique qui permettrait d'automatiser ce processus. En
effet, il aurait sans doute tendance à choisir quelques activités et
logements qui lui plaisent, puis à essayer de les organiser pour les
répartir en différentes journées, afin d'obtenir directement un voyage plus
ou moins adapté, qu'il pourrait ensuite essayer d'améliorer en visitant
quelques activités supplémentaires, en décidant d'en supprimer d'autres,
en remplaçant un logement par un autre, ..., le tout par tâtonnements.
Toutefois, le voyage obtenu sera alors fortement
conditionné par ses premiers choix. Par ailleurs, ce processus peut
difficilement être automatisé. A l'opposé, partir d'un projet de voyage très
simple, on laisse plus de libertés pour explorer des pistes plus variées, et
la réalisation d'un grand nombre d'améliorations itératives est facilement
automatisable. La technologie suivant l'invention évalue en quelques
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
24
secondes des millions de voyages différents. Un voyageur ne pourrait
pas comparer autant de voyages en une vie entière.
Ce voyage 11 est présenté, par exemple jour par jour, à
l'utilisateur, accompagné d'informations utiles (descriptions, photos, etc.).
L'utilisateur peut également visualiser chaque journée du voyage, ainsi
que le voyage complet, sur une carte. Si le voyage proposé ne convient
pas parfaitement à l'utilisateur, ce dernier a la possibilité de préciser ou
revoir ses souhaits 12 et de construire un nouveau voyage. Ces choix
seront pris en compte lors de la construction d'un nouveau voyage, car
ils correspondent à des paramètres ou données précises envoyés au
moteur de calcul.
Par exemple, avant de construire un nouveau voyage,
l'utilisateur peut exprimer ses préférences vis-à vis des activités
proposées dans le voyage actuel. Si une activité ne l'intéresse pas, il lui
suffira de l'exclure des prochains voyages (activité non envoyée au
moteur de calcul). Au contraire, si une activité l'intéresse, il pourra
demander qu'elle soit absolument placée dans le prochain voyage.
L'utilisateur peut également exclure des prochaines propositions un
logement qui ne lui convient pas (logement non envoyé au moteur de
calcul). A l'inverse, il peut demander de placer un logement qui lui
convient dans les prochaines propositions de voyage. De même, le
nombre de fois (nuits) durant lesquelles l'utilisateur souhaite séjourner
dans ce logement peut être précisé. L'utilisateur peut indiquer ses
centres d'intérêt, ce qui conditionnera la sélection des activités.
L'utilisateur a également la possibilité de parcourir les données de la
première table correspondant à des activités dans le but d'inclure dans
son prochain voyage quelques unes de ces activités. La même chose est
possible pour les logements.
D'un point de vue technique, de nombreux tests sont
réalisés afin de ne pas permettre à un utilisateur de faire des choix
incohérents. Lorsque l'utilisateur a affiné ses demandes, il demande de
CA 02744171 2011-05-17
WO 2010/055173 PCT/EP2009/065342
reconstruire un nouveau voyage. Le système envoie alors les
informations mises à jour au moteur de calcul, qui génère un nouveau
voyage adapté. Le nouveau voyage est alors proposé à l'utilisateur. Ce
voyage pourra être affiné jusqu'à ce que l'utilisateur soit satisfait du
5 voyage proposé.
