|
Choose your language |
|
|
Recherche
Domaine
de recherche
Recherche Opérationnelle - Optimisation
Combinatoire –
Méthodes exactes et heuristiques
Logistique de transport - Tournées de
véhicules - Gestion des opérations
Problématiques
abordées
Ma recherche aborde différents
types de problèmes, mais se dirige essentiellement autour des tournées de
véhicules ou plus généralement de l'optimisation du transport.
Le problème de tournées de véhicules (vehicle
routing problem - VRP) consiste à déterminer les itinéraires pour une flotte
de véhicules de capacité limitée afin de visiter un ensemble de clients. Le but
est de minimiser le coût de transport. Il s'agit d'une extension classique du problème
du voyageur de commerce, qui fait partie de la classe des problèmes NP-difficiles.
Des extensions de ce problème sont fréquentes afin de s'approcher des réalités
du monde industriel.
Le premier problème étudié est
celui concernant la considération simultanée de la localisation et du routage
(LRP - Location-Routing Problem).
Dans ce problème, il faut déterminer le nombre et la localisation des dépôts
qui serviront de point de départ pour les tournées de véhicules qui visiteront
les clients. Contrairement au multi-dépôt VRP, il ne s'agit pas seulement de
partitionner les clients sur des tournées pouvant débuter de divers endroits.
L'utilisation d'un site engendre ici un coût d'ouverture qui contre-balance une
potentielle économie dans le cheminement des véhicules. De plus, la variante
étudiée comprend des contraintes de capacité limitée à la fois sur les
véhicules et les dépôts, ce qui engendre un double problème de Bin-packing lié
à l'affectation des clients aux tournées et dépôts. En extension, une partie
des travaux porte sur un cas multi-période du problème de localisation-routage.
J’ai développé pour le LRP une
des meilleures méthodes publiées à ce jour.
Ensuite, un autre type de restriction
de ressources est initiateur de recherche : la limitation de la flotte de
véhicules, en particulier quand celle-ci est hétérogène (Heterogeneous VRP - HVRP). Au problème classique de tournées
s'ajoute alors aussi un problème de partitionnement et d'affectation des
clients sur des ressources (type de véhicules) présentes en quantité limitée.
L'étude du problème de tournées avec remorques
permet de combiner l'idée de flotte hétérogène et de localisation. Il ajoute de
plus la notion de tournées multi-niveaux. C'est donc tout naturellement que la
poursuite des recherches porte sur les problèmes
de localisation-routage à deux niveaux.
Dans la continuité des
extensions, après avoir étudié le LRP et sa version périodique, ainsi que le
HVRP, des travaux portent sur leurs variantes incorporant une autre gestion de
ressources : le stockage (inventory
routing), avec la possibilité de servir les clients en avance à condition
de respecter les disponibilités d'entreposage. En parallèle, d’autre types de
variantes ont été explorée, en particulier en changeant de fonction-objectif.
C’est l’objet de mes travaux sur le problème de transport de matières dangereuses.
Mixant des contraintes et une
fonction-objectif originales, je me suis intéressée aux tournées de véhicules électriques en centre-ville qui doivent se
recharger régulièrement à des bornes.
Une autre extension qui a
attiré mon attention consiste à intégrer différents problèmes, comme dans le
problème d’ordonnancement et de transport. Sur ce sujet, j’aime
particulièrement regarder une supply chain comme un problème de Job-shop avec transport (puisque le
temps de transfert devient loin d’être négligeable). Mais au lieu de considérer
un transport direct entre unité, on peut penser à résoudre des problèmes de
type VRP, et pourquoi pas VRP avec contrainte de stockage.
Depuis peu, j’ai intégré un projet
ANR incluant des questions autour du routage
dans les réseaux télécom, où l’on retrouve des décisions de localisation de
services, du chainage, de l’ordonnancement, et où les compétences en
modélisation et résolution par la recherche opérationnelle s’avèrent
intéressantes.
Enfin, quelques travaux
concernent d'autres problématiques, comme les tournées de soins à domicile,
comportant des critères antagonistes à optimiser et menant à des études multi-objectifs.
Approches
de résolution
La résolution des problèmes de
tournées fait appel aux techniques de recherche opérationnelle et
d'optimisation combinatoire. Les variantes étudiées peuvent toutes se ramener au
VRP classique en cas particulier. Ce sont donc des problèmes NP-difficiles qui ne
peuvent être résolus optimalement en des temps de calcul raisonnables, du moins
pour les instances de grande taille.
L'optimisation linéaire en nombres entiers permet tout de même de
résoudre de façon exacte certains problèmes de tournées de véhicules de taille
relativement réduite. De plus, il est intéressant d'utiliser des approches
exactes pour développer des bornes et ainsi mieux évaluer la qualité des
solutions obtenues heuristiquement. J'ai proposé différentes modélisations mathématiques,
sous forme de programmes linéaires en nombres entiers. Les formulations se différencient
par le nombre d'indices des variables utilisées, chacune ayant un intérêt selon
le type de résolution envisagé. J'ai en particulier développé des méthodes de branchement et coupes résolvant
optimalement des petites instances et fournissant des bornes inférieures pour
les cas de plus grandes tailles.
Cependant, mes recherches sont
plutôt basées sur des méthodes approchées. En premier lieu, il s'agit
d'heuristiques constructives spécifiques aux problématiques traitées, et
permettant d'élaborer des solutions réalisables. En particulier, une version généralisée de l'algorithme de
Clarke & Wright est proposée afin de résoudre le cas multi-dépôts. Des adaptations algorithmiques de
l'utilisation de l'algorithme Split
sont également présentées. Les solutions obtenues sont améliorées à l'aide de
recherches locales dédiées aux problèmes étudiés.
Pour échapper aux optima
locaux obtenus par les heuristiques suivies de recherches locales, de
nombreuses métaheuristiques sont appliquées, comme des algorithmes génétiques, recherches
à voisinages variables, etc. Cependant, une autre option concerne des versions
plus pertinentes hybridant plusieurs métaheuristiques ou combinant une
résolution exacte et heuristique à travers des matheuristiques.
Enfin, il est intéressant de
tirer parti de l'architecture des ordinateurs récents, équipés de processeurs
multi-cœurs. Ainsi, une implémentation de métaheuristique est développée de façon
à exploiter de manière coopérative des explorations
parallèles de l'espace des solutions.
Une autre piste qui me semble pertinente
et à laquelle je commence à m’intéresser, est la résolution sur ordinateurs quantiques. En effet, ces
derniers promettent depuis quelques années de résoudre efficacement les
problèmes NP-difficiles en offrant un nouveau paradigme de résolution.
Le fil conducteur des
approches de résolution proposées est une volonté de garder une vision globale
et de proposer une exploration judicieuse de l'espace de recherche, en passant
par exemple par des problèmes simplifiés ou relaxés, mais tout en garantissant
une certaine coopération pour préserver une efficacité de résolution, et des
techniques d’apprentissage.
De plus, soulignons que pour
tester l'ensemble des méthodes et fournir les résultats proposés, un travail
considérable et non trivial d'informaticien a été nécessaire, pour l'implémentation
des approches (incluant parfois l’utilisation d'un solveur commercial de
programmation linéaire comme CPLEX), ainsi que des analyses statistiques pour l'évaluation de performances.