Covoiturage Dynamique et Incrémental, avec fenêtres de temps, livraisons et chargements partiels, flottes à capacités variables, et itinéraires avec vias.

Session : LTSS4-1 / LTSS4 : Transport vert
Vendredi 12 février 10:30 - 11:50 Salle : Apollo
Philippe Canalda et Idriss Hassine

Le problème classique du covoiturage consiste à savoir affecter la demande de nouveau(x) passager(s) à un ou plusieurs véhicules dont leur(s) propriétaire(s) propose(nt) des itinéraires flexibles. Cette mission d'affectation doit être effectuée le plus réactivement possible. La plupart des études restent encore au stade embryonnaire en ce qui concerne l'automatisation et l'aspect temps réel. La majorité des solutions commerciales leaders se cantonnent à des systèmes de mises en contact basées sur l'origine et la destination qui doivent être communes; mises à part les solutions Covivo et ShareAndMove, car celles-ci proposent des itinéraires distribués appariant les offres et les demandes à la volées : la première apparie dynamiquement toujours une demande dont l'origine et la destination correspondent, lorsque la seconde propose des appariements et génère des itinéraires distribués dont les détours des offres et des demandes restent compatibles avec des fenêtres de temps spécifiées. Les approches algorithmiques opérationnelles des industriels leaders ou des académies, sous-jacentes à un traitement temps-réel souhaité, se basent sur des heuristiques de proximité et de disponibilité, ou bien sur la détermination du détour le plus faible, ou encore sur un calcul incrémental des appariements et de la génération des itinéraires relâchés des offres et des demandes. Les documentations ne sont pas disponibles, les communications gardées. Il en découle que la formalisation des solutions, aujourd'hui pourtant opérationnelles, ne peuvent être confrontées aux travaux académiques. Dans cette étude, nous présentons la première formulation du covoiturage dynamique et incrémental. Cette formulation spécifie les contraintes multiples d'un transport organisé mettant en oeuvre les offres (Véhicule, Chauffeur, Itinéraire et sa relaxation), et les demandes (comparables à l'offre). Les objectifs sont également multiples et complexes, de part la nature même d'un système opérationnel sur le terrain. Toutes les décisions d'un système de covoiturage doivent être maîtrisés et opposables. Il s'agit donc de tenir compte des priorités déclaratives (temporalité, sécurité), et satisfaire le mieux possible à ces contraintes parfois paradoxales, devient l'objectif primordial. D'autres objectifs plus classiques demeurent, mais toujours pas si aisés à mettre en oeuvre, comme minimiser l'usage du véhicule (nombre, kilométrage, temps, énergie, nuisances écologiques), et maximiser le taux de remplissage des véhicules. Une approche incrémentale du problème se traduit par une contrainte contractualisée de l'organisation du transport jusqu'alors. Toutes les organisations calculées éligibles (satisfaisant les contraintes, et triées suivant les objectifs), tiennent compte des appariements (offres et demandes), et des itinéraires distribués des offres et demandes associées. Le calcul du covoiturage incrémental peut se faire sans tenir compte d'un antécédent, ou bien en tenant compte du dernier antécédent. L'aspect dynamique du covoiturage se traduit dans les conditions d'appel : la contractualisation précédente des offres et demandes contraintes, et les propositions d'itinéraires adaptés, peuvent comporter des modifications, les nouvelles offres de transport et les nouvelles demandes viennent compléter la demande contextuelle de covoiturage (spatial et temporel). Notre formulation du covoiturage tient compte des fenêtres de temps associables à l'ensemble des itinéraires proposés (de l'offre) ou demandés, ainsi que des itinéraires calculés, dérivés des appariements. Des fenêtres de temps sont également associées à chaque arrêt déclaré. La formulation tient également compte des chargements partiels et des livraisons partielles des covoiturés et covoitureurs. La flotte de véhicules est bien évidemment hétérogène. Un élément nouveau est que les itinéraires considérés sont composés de vias. Cette formulation associant les vias et les fenêtres de temps locales (par arrêt) et globales, permet la modélisation généralisée d'une organisation d'un transport où toutes les étapes d'un voyage se spécifient (aller-retour, vias), pour un déroulement sur une même journée ou sur plusieurs jours. Pour compléter cette étude, un algorithme de résolution exacte de ce problème de covoiturage dynamique et incrémental est proposé. Il se base sur la technique de programmation dynamique {it "Cut and Price and Share"}. Deux fonctionnalités complètent cet algorithme, l'une de clonage et d'insertion d'une nouvelle organisation partiellement éligible, et l'autre de vérification et de propagation des fenêtres de temps dynamiques. Ces algorithmes sont illustrés par des exemples réalistes pédagogiques. Une implémentation de cet algorithme a été réalisée en C++. Quelques tests sont présentés dans l'étude proposée qui valident fonctionnellement cette formulation du covoiturage dynamique pour une applicabilité incrémentale à l'échelle d'une métropole de la taille de Rennes ou encore de Belfort-Montébliard-Héricourt. Des tests de montée en charge sont aussi évalués. Ils sont issus du fonctionnement réels de transport déclenchés sur la ville de Rennes (projet ANR Modulobuc). Les résultats des tests font la démonstration de l'usage immédiat, même malgré une résolution "exacte" toujours plus coûteuse (en temps de réactivité à l'exécution), d'un système qui se baserait sur les éléments de cette étude. Les perspectives sont, tout d'abord l'intégration réelle dans un système de covoiturage dynamique, ensuite l'évaluation sur un territoire dynamique pour étudier la robustesse associable à l'élasticité des fenêtres de temps, et enfin l'intégration de ce covoiturage dans une politique globale de transport publique.

Mots clés : Covoiturage dynamique, optimisation incrémentale, fenêtres de temps, chargement et livraison partiels, Itinéraires avec Vias, génération feuilles de routes