Le séminaire OCAD recevra le 20 avril Thierry Garaix (chercheur, Politecnico di Torino).

Cette présentation met en avant trois problèmes de tournées de véhicules originaux issus de la considération de réseau routiers réels et de critères de qualité de service pour le transport de personnes. Les méthodes proposées sont basées sur des approches de génération de colonnes.

Au cours des dernières décennies, en partant du problème de Voyageur de Commerce, les problèmes de tournées de véhicules académiques ont été enrichis par des contraintes ou des extensions de natures différentes : flotte de véhicules, capacités, fenêtres de temps et ramassage et livraison pour les plus étudiées. Nous disposons ainsi aujourd’hui de méthodes heuristiques ou exactes efficaces sur ces problèmes. Deux enjeux majeurs actuels en terme d’optimisation, sont le passage à des problèmes de grande taille et/ou la prise en compte de nouvelles contraintes (possiblement multicritères). Le transport de personnes et en particulier les transports à la demande s’apparentent directement à ces enjeux en intégrant notamment des contraintes fortes liées à la qualité de service.

Un réseau de transport propose généralement des chemins alternatifs privilégiant tel ou tel critère (coût, temps, sécurité;...). Considérer ces alternatives, génère une forte augmentation de la taille des données définissant l’espace des solutions. Il est donc nécessaire de valider des approches pertinentes sur des réseaux ainsi définis. Un critère usuel d’évaluation de la performance générale d’un système de transport, est le taux moyen de remplissage des véhicules. Cependant, ce critère fractionnaire est rarement (jamais) utilisé comme objectif dans les outils de calcul des tournées. Dans le un cas de transport à la demande, il se révèle peu coûteux en temps de calcul d’y adapter une méthode de génération de colonnes standard.

Dans le cadre de transport de personnes handicapées, la régularité des horaires de ramassage d’un jour sur l’autre, est un critère de qualité de service primordial. C’est aussi une valeur ajoutée à des tournées de livraison pour des clients réguliers. La modélisation de cette contrainte donne un problème original pour lequel est proposé une heuristique basée sur la résolution exacte d’un problème de tournées à fenêtres de temps dures (sans temps d’attentes) et multiples.