Thèse Camille GRAS

Auteur : Camille GRAS
Directeur de Thèse : Van Dat CUNG
Encadrante : Alantha NEWMAN
Encadrante : Nathalie HERR
Encadrant : Nicolas TEYPAZ
Date : 14 octobre 2021
 

Problème de transport long-courrier de colis :
modèles orientés chemins et algorithmes diviser-pour-régner

 

Avec l’essor du e-commerce, de nombreuses études ont été menées sur la logistique urbaine et la livraison du dernier kilomètre. Nous optimisons ici une autre étape de la livraison des colis : le transport long-courrier. Il a lieu entre les centres de tri de collecte et les dépôts de livraison. Ni la manière dont les colis sont acheminés de leur bureau de poste de départ à leur centre de tri de collecte, ni comment ils sont transportés vers les bureaux de poste puis aux particuliers ne sont pris en considération. Le problème du transport long-courrier de colis (PTLCC), défini formellement, est un problème de conception de réseau de services avec gestion des actifs. Il intègre l'opération de tri permettant une meilleure mutualisation des colis dans les conteneurs. C’est un problème tactique d'optimisation qui consiste à définir un plan de transport annuel composé de liaisons fixes, basé sur des prévisions de volumes à moyen terme, dont on minimise le coût total. Ce coût est composé du coût logistique et du coût de transport. Le transport de colis se fait avec deux types de véhicules (camions à un ou deux conteneurs) qui sont équilibrés chaque jour sur le réseau grâce à la gestion des conteneurs vides. Le transport est optimisé sur un réseau hybride hub-and-spoke biniveau à l'échelle d'un pays. En effet, ce problème industriel provient d'une entreprise postale et leurs ensembles de données sont de taille réaliste (environ 225 sites avec 2500 demandes). Une même demande (origine, destination, nombre de colis) peut être acheminée sur plusieurs chemins simultanément ce qui augmente la complexité du problème. Ainsi, le nombre de plans de transport possibles explose.

Nous proposons un programme linéaire mixte (PLM) orienté chemin pour le PTLCC et deux algorithmes divise-pour-régner exploitant ce modèle pour créer de meilleurs plans de transport. Le premier algorithme, l'algorithme k-Clusters, optimise le PTLCC après avoir regroupé les sites du réseau en clusters. Nous testons des techniques classiques de clustering (clustering spectral, clustering hiérarchique, k-means et aléatoire) en utilisant des fonctions de similarité appropriées (basées sur les demandes et sur les distances) pour étudier l’impact sur les résultats.

Le problème d'origine est divisé en sous-problèmes intercluster et intracluster résolus avec le PLM. Les solutions des sous-problèmes sont ensuite fusionnées. Les résultats obtenus sont comparés à ceux obtenus avec une utilisation directe du PLM sans clustering. Ces tests montrent que le respect de la hiérarchisation des sites du réseau postal est la propriété qui a le plus d'impact sur les résultats.

Ainsi, nous concevons un deuxième algorithme, l'algorithme hiérarchique avec agrégation de demandes qui exploite la structure à deux niveaux du réseau. Ses performances sont liées à un seuil du taux de remplissage des camions. Les demandes au-dessus de ce seuil peuvent être acheminées directement. Celles en dessous de ce seuil doivent suivre la structure hiérarchique du réseau. L’acheminement des deux types de demandes est optimisé, d'abord séparément puis conjointement via plusieurs étapes dans lesquelles les sous-problèmes sont résolus avec le PLM. Différents seuils sont testés pour déterminer lequel donne les meilleurs solutions et temps de calcul. Ces tests montrent qu’un meilleur taux de remplissage n’aboutit pas à un plan de transport moins cher dans notre cas.

De plus, l'algorithme hiérarchique permet d'avoir des plans de transport nettement meilleurs que ceux appliquées sur le terrain, ceux obtenus via une utilisation directe du PLM et même ceux obtenus avec l'algorithme k-Clusters. Enfin, nous implémentons ces algorithmes et présentons les résultats numériques. Cela montre que le paradigme diviser-pour-régner est efficace pour la conception de réseau de services lorsqu'il s'applique à un problème industriel de grande taille.