Mutualisation de taxis avec partage de coût : modélisation, complexité et linéarisation du problème

Session : LTSS1-1 / LTSS1 : Mobilités urbaines
Mercredi 10 février 11:00 - 12:20 Salle : Apollo
Dimitri Watel et Alain Faye

On se propose dans cette présentation d’étudier une variante du problème Dial-A-Ride (DARP). Dans, le problème original, on cherche à optimiser les routes de véhicules chargés de transporter des personnes depuis leurs origines respectives vers leurs destinations respectives, tout en respectant des contraintes de fenêtre de temps et des contraintes de capacités (nombre de places dans le véhicule). Ce modèle est généralement utilisé pour optimiser des chemins pour des taxis. Nous nous penchons sur une variante de ce problème dans laquelle les clients partagent le coût des trajets (ou des parties de trajets) qu'ils effectuent avec d'autres clients. Nous étudions dans un premier temps la complexité de ce problème. Puis, nous présentons un modèle linéaire en variable mixte et des règles de réduction de l'instance. La présentation se termine par une présentation des résultats de tests numériques.

Mots clés : Transports mutualisés, Dial-A-Ride Problem, Complexité, Programmation non linéaire en variables mixtes, Linéarisation