Le covoiturage est un moyen qui fournit plusieurs avantages, comme la réduction des frais de déplacement, la congestion du trafic routier et les émissions de CO2 . De nos jours, il existe plusieurs services Internet qui fournissent les correspondances nécessaires entre un passager et un conducteur. Malheureusement, ces systèmes offrent souvent des solutions qui se concentrent sur une fonctionnalité plutôt simple de covoiturage i.e. dans le cas où l'emplacement de ramassage ne diffère pas de l'origine du passager, la même chose est vraie pour le lieu de dépôt et sa destination.

Des travaux de recherche ont étudié la possibilité d'avoir un seul point intermédiaire entre le conducteur et le passager qui peut correspondre soit au point de rencontre soit au point de séparation. Plus précisément, ils ajustent la route du conducteur pour ramasser ou déposer le passager sur ce point de rencontre en permettant au conducteur un détour acceptable. Néanmoins ces travaux ne se focalisent que sur le confort du conducteur.

Dans cet article, nous nous intéressons à une approche générale de covoiturage dynamique dans laquelle le conducteur et le passager acceptent de se rencontrer dans un lieu de départ intermédiaire et de se séparer dans un autre lieu intermédiaire. Ces deux points intermédiaires seront déterminés de façon à minimiser la distance totale parcourue par ces derniers, tout en respectant les contraintes de détour à la fois du passager et du conducteur.

L'approche exacte de type force brut est de complexité O(n².log n), cette dernière n'est pas adaptée aux grandes instances, ainsi nous développons une heuristique de complexité O(n.long n). Afin de déterminer les deux points intermédiaires, l'heuristique est basée sur la détermination de deux classes, la première (respectivement la deuxième) regroupe les points de rencontre (respectivement de séparation ).

Cette approche est testée sur des réseaux routiers atteignant 3,5 millions de nœuds et 8,7 millions d'arcs et fournit des solutions très proches de l'optimum avec un temps de calcul de quelques secondes.