Dynamic Dial-a-ride Problem: application aux taxis-partagés dans un milieu urbain

Session : LTSS1-1 / LTSS1 : Mobilités urbaines
Mercredi 10 février 11:00 - 12:20 Salle : Apollo
Kamel Aissat, Sacha Varone et Ammar Oulamara

Dans ce travail, nous présentons une heuristique d'insertion pour un problème dynamique de type Dial-a-Ride, conçu pour une application réelle de partage de taxis. L'application s'appuie sur des cartes géographiques avec les coordonnées GPS en temps réel des taxis et des clients. Un client envoie une demande de trajet à une centrale de taxis, qui lui attribue en (quasi) temps réel le taxi le plus approprié, tout en tenant compte de la capacité de ce dernier, contrainte des coûts ainsi que des contraintes temporelles: le temps d'attente maximum avant la prise en charge du client et la durée maximale du trajet pour chaque passager. Les passagers peuvent partager leur taxi pour une partie ou la totalité de leur voyage. Dans un second temps, nous présentons quelques extensions de notre modèle, à savoir: la prise en compte des lieux intermédiaires de prise en charge et du dépose des clients ainsi que la prise en compte des offres de covoiturage. La méthodologie repose sur le calcul de plus courts chemins en temps-réel, sur la détermination des bornes inférieures valides, suivi d'un algorithme d'insertion avec contrôle de validité. Chaque nouvelle demande est donc insérée dans un itinéraire. Des expériences sur des données réelles montrent la viabilité de nos méthodes.

Mots clés : Transport, Mobilité partagée, Problème du plus court chemin, Temps réel.