Covoiturage dynamique avec des emplacements intermédiaires de rencontre et de séparation

Covoiturage dynamique avec des emplacements intermédiaires de rencontre et de séparation

déterminons un meilleur conducteur ainsi qu’un meilleur emplacement de prise en charge et de dé- pose qui minimisent le coût du trajet total du passager et du conducteur sous certaines contraintes. Une méthode exacte et plusieurs heuristiques sont proposées afin d’identifier un meilleur conducteur, de meilleurs emplacements de prise en charge et de dépose ainsi que le taux de partage des coûts. Ensuite, nous procédons à une évaluation comparative en utilisant un vrai réseau routier de la région Lorraine en France et un vrai jeu de données fourni par une entreprise de covoiturage CovivoNous traitons dans ce chapitre le problème où les passagers ont la possibilité de se déplacer versdes lieux intermédiaires de prise en charge et de dépose autre que leurs lieux de départ et de desti- nation. Cela évite d’obliger le conducteur d’aller chercher le passager depuis son point départ pour le transporter jusqu’à sa destination. La prise en compte de ces emplacements intermédiaires permet de réduire considérablement le détour pour le conducteur ainsi que le coût total du trajet (voir la figure 3.1). Deux études récentes qui proposent des emplacements intermédiaires de prise en charge et de dépose sont présentées dans [Bit-Monnot et al., 2013] et [Stiglic et al., 2015]. L’approche propo-de maximiser le nombre d’appariements dans le système. Cependant, les hypothèses fixées par les auteurs réduisent considérablement la difficulté du problème car aucun calcul de plus court chemin ne s’effectue lors d’une arrivée d’une requête.

Le principal objectif de leur étude est de montrer l’in- térêt de considérer des points de rencontre et de séparation pour le service de covoiturage. Contrairement à leur approche, nous utilisons des durées exactes qui seront calculées dynamique- ment lors d’une demande de covoiturage. Le passager sera également en mesure de choisir son mode de transport pour atteindre le lieu de prise en charge depuis son point de départ ainsi qu’un second mode de transport pour atteindre sa destination depuis le lieu de dépose. Dans ce chapitre, les modes de transport possibles pour le passager concernent uniquement les transports individuels, à savoir : le vélo privé, la voiture personnelle, la marche à pied. A l’inverse des transports en commun, leurs disponibilités ne dépendent pas du temps. La figure (a) représente le plus court chemin du passager (de couleur verte) et du conducteur (de couleur rouge) avant l’appariement. La figure (b) représente les nouveaux chemins du conducteur et du passager après l’appariement. Les deux nouveaux emplacements intermédiaires de prise en charge et de dépose sont représentés par deux flêches noires, tandis que le chemin com- mun est représenté en bleu (le chemin se trouvant entre les deux emplacements intermédiaires). L’approche classique de covoiturage ne détecte pas cet appariement dû au long détour du conduc- teur pour transporter le passager directement depuis sa position de départ à sa destination.

Le reste de ce chapitre est constitué comme suit : la section 3.2 décrit le modèle de covoitu- rage dynamique avec des emplacements intermédiaires de rencontre et de séparation. La section 3.3 présente les différentes approches de résolution du problème présenté dans la section 3.2. Dans la section 3.4 nous traiterons le problème de sélection du meilleur conducteur lorsqu’une demande de covoiturage entre dans le système. En effet, les approches développées dans la section 3.3 corres- pondent au cas où une offre et une demande de covoiturage sont déjà fixées à l’avance. Une analyse comparative entre notre modèle de covoiturage avec emplacements intermédiaires et le modèle clas- sique sur différents réseaux routiers et différentes données (réelles et simulées) est présentée dans la section 3.5. Enfin, nos conclusions du chapitre sont présentées dans la section 3.6.lonnée qui permet de sélectionner les meilleures offres avec les plus petits détours pour une demande de covoiturage donnée. Ainsi, une offre apparie parfaitement une demande de covoiturage si et seule- ment si le conducteur et le passager ont le même le lieu de départ et de destination. L’appariement dans lequel le conducteur fait un petit détour pour transporter un passager est dit “appariement raisonnable”voyage seul. Dans un tel cas, aucun détour n’est effectué par le conducteur et le coût du nouveau trajet reste inchangé. Cette approche est inflexible et les possibilités d’appariement des conducteurs et des passagers diminuent lorsque les itinéraires des passagers et des conducteurs sont légèrement différents. Cependant, afin d’obtenir plus de possibilités de covoiturage, le passager peut accepter deux emplacements intermédiaires.