Transport multimodal incluant le covoiturage dynamique

Première approche : Approche directe

Nous présentons un exemple qui illustre les différentes étapes de notre approche. Cet exemple représente la situation suivante : un utilisateur r souhaite se déplacer d’une origine Or vers une destination Dr à l’instant tr = 9 : 00. Les transports publics lui permettent d’aller d’un point x2 à un autre point xnbs, respectivement à proximité de son point de départ Or et de sa destination Dr . On notera x2, x3, . . ., xnbs1 les points de correspondance constituant son chemin multimodal classique. Pour simplifier l’exemple, on considère que l’origine du passager Or correspond à un arrêt de bus, donc Or = x1. On considère également un seul conducteur (voir les figures : 6.4 à 6.9).

Étape d’initialisation

Lorsqu’une requête Or Dr arrive dans le système à l’instant tr , un plus court chemin multimodal classique ainsi que les chemins possibles en covoiturage entre les différents arrêts de correspondance sont déterminés. L’algorithme 23 détaille cette étape.
En utilisant L’API, l’étape 1 détermine un chemin multimodal classique P avec les temps de chaque arrivée et de départ sur chacun des nœuds se situant entre la position de départ Or et la destination Dr . L’étape 2 calcule les chemins possibles de substitution en voiture sur le long des arrêts du chemin P. Seuls ceux dont le temps d’arrivée en voiture à l’arrêt concerné est plus tôt que le temps d’arrivée en utilisant les transports publics sont conservés. Plus spécifiquement, l’heure d’arrivée au lieu de prise en charge plus le temps de changement nécessaire en incluant la durée du trajet jusqu’à l’arrêt de dépose y est comparé avec l’heure d’arrivée à y en transport public. Si le gain en temps pour l’utilisateur n’est pas positif, alors le trajet en covoiturage (x, y) ne sera pas conservé. Les trajets potentiels en covoiturage sont stockés dans l’ensemble P Dr i ve.
La figure 6.1 illustre un exemple où un passager r se déplace à l’instant tr =9h00 à partir de son point de départ Or (qui est considéré comme le premier arrêt) vers sa destination Dr . Plus spécifiquement, cette dernière représente le résultat retourné par l’étape 1 de l’algorithme 23. Pour chaque arrêt x i 2 P, nous associons une fenêtre de temps [tar(xi , p), tdr (xi , p)] qui est composée respectivement de l’heure d’arrivée à l’arrêt xi et l’heure à laquelle le passager quitte l’arrêt xi . Dans cet exemple, le chemin déterminé par l’API est composé de trois modes différents. Le passager attend à son point de départ trois minutes avant de monter dans le bus à 9h03, puis il est déposé à l’arrêt x2. Il marche pendant 5 minutes depuis l’arrêt x2 vers l’arrêt x3 puis il attend 5 minutes avant de prendre finalement le train pour rejoindre sa destination finale Dr (voir la figure 6.1).
Dans la figure 6.3, nous présentons les chemins potentiels de substitution retournés par l’algo-rithme 23. Le chemin (x2, x3) se traduit par une arrivée à x3 plus tard que si on utilisait les transports publics, car il nécessite 6 minutes de x2 à x3, au lieu de 5 minutes. Une situation similaire se produit pour le chemin (x3, Dr ) : 31 minutes en covoiturage contre 26 minutes avec les transports publics. Donc les deux chemins (x2, x3) et (x3, Dr ) sont annulés.

Conducteurs potentiels

A ce niveau, nous définissons une estimation sur la proximité des chemins potentiels de substi-tution par rapport aux conducteurs. Cette estimation est définie comme une somme minimale de la distance estimée à partir de la position d’un conducteur vers un arrêt du chemin classique P, et inversement à partir de P vers la destination du conducteur. Quatre points différents sont utilisés de sorte que seules les substitutions potentielles sont autorisées. Pour ce faire, nous estimons la distance entre deux points donnés par leur latitude/longitude avec la formule de Haversine. L’algorithme 24 restreint la liste des conducteurs potentiels à ceux dont la position de départ et d’arrivée sont assez proche des arrêts de P et dont le temps de détour est inférieur à une valeur fixée pour les conducteurs correspondants. L’étape 7 vérifie l’admissibilité de la contrainte du temps de détour en déviant leur trajet via x ! y. Cette dernière est basée sur des estimations pour les durées manquantes de Ok vers x (étape 5) et de y vers Dk (étape 6). Pour chaque arrêt potentiel x pour une prise en charge, nous gardons seulement dans l’ensemble L Px# les conducteurs qui respectent la borne supérieure sur la contrainte du temps de détour. La même méthode s’applique pour le lieu de dépose dans l’ensemble L Py ». Le détour maximal d’un conducteur ne doit pas dépasser 20% 27 de sa durée initiale (c’est à dire k = 1.2). L’étape 2 parcourt l’ensemble des conducteurs dans le système ayant une même date de départ que l’utilisateur r et qui se situent également dans une même zone géographique.
La figure 6.6 représente les tests effectués sur chaque chemin potentiel de substitution depuis la position de départ du conducteur jusqu’à sa destination. Les chiffres sur les arcs en pointillé repré-sentent les durées estimées, tandis que les chiffres sur les arcs en lignes continues représentent les durées réelles (calculées par l’algorithme 23).
La figure 6.7 détaille le résultat de l’algorithme 24, où l’arc (Or , x2) a été supprimé car la nouvelle durée 16 + 15 + 26 = 57 minutes, dépasse le détour maximal fixé par le conducteur (1, 2 47 = 56, 4 minutes). Ce dernier sera retiré de la liste des chemins potentiels de substitution L Dk pour le conducteur k. Cela permet également de restreindre la liste des lieux potentiels de prise en charge et de dépose.

Calcul de plus courts chemins et de la meilleure substitution en covoiturage

Une fois que la liste des conducteurs potentiels est déterminée, l’algorithme 25 calcule l’ensemble des plus courts chemins afin de vérifier l’admissibilité des trois contraintes, à savoir : le temps de détour du conducteur, le temps d’attente à l’emplacement de prise en charge et le temps d’arrivée du passager. Deux types de calculs de plus courts chemins sont effectués. Le premier depuis la position actuelle de chaque conducteur vers chaque arrêt potentiel de prise en charge (étape 4). Le second, depuis chaque arrêt potentiel de dépose vers la destination de chaque conducteur (étape 10) (voir la figure 6.8).
Ces calculs seront effectués en deux phases. La première phase détermine les durées depuis leur lieu de départ vers les lieux potentiels de prise en charge. En se basant sur ces premières durées calculées, nous mettons à jour l’ensemble L Py » en enlevant les conducteurs qui ne respectent pas une des contraintes : la contrainte du temps d’attente du conducteur, la contrainte du temps de détour ou la contrainte du temps d’arrivée du passager. Une fois que l’ensemble de dépose L Py » est mis à jour, la deuxième phase calcule les durées exactes depuis chaque lieu de dépose y vers la destination de chaque conducteur contenue dans la liste L Py ». Dans la seconde phase, à chaque fois qu’une durée d’un conducteur k est calculée, nous parcourons l’ensemble de ses trajets potentiels L Dk en vérifiant l’admissibilité exacte de la contrainte du temps de détour du conducteur. Enfin, parmi tous les trajets admissibles, nous sélectionnons celui qui génère le plus d’économies en temps d’arrivée.
L’objectif est donc de trouver un moyen de se rendre à des points de correspondance en utilisant le covoiturage comme mode de transport. Autrement dit, nous sélectionnons le meilleur chemin de substitution (x?, y?) qui génère un gain en temps d’arrivée le plus élevé au passager si ce dernier partage son trajet avec le conducteur k? depuis x? jusqu’à l’arrêt y? plutôt que les transports publics (voir la figure 6.9). Pour chaque gain positif généré autour de chaque arrêt potentiel de dépose, un itinéraire multimodal classique est lancé en prenant en compte la nouvelle heure d’arrivée du passa-ger à l’arrêt concerné. Ceci permet de garantir au passager une arrivée plus tôt que celle annoncée par l’API (étapes 17 à 23 de l’algorithme 25).