Le 30/11/2022 par simonc :

Bonjour à tous,

Le laboratoire Lineact du Cesi de Strasbourg, sur l'équipe "Aide à la décision" propose un stage en recherche niveau M2/ingénieur. Le stage aura une durée de 6 mois et débutera seconde quinzaine de janvier au plus tard. La rémnunération sera d'environ 550 euros par moi.

Ci dessous, le détail de l'offre.

Sujet : Optimisation des flux physique finals de la supply chain : la planification de tournées de véhicules à l’aide de l’IA.

Mots clefs : Supply chain ; Exploration de données ; Optimisation ; Planification ; IA

Domaine scientifique : Informatique

1 Description

Une entreprise a besoin de s’approvisionner en matières premières pour produire des marchandises. La chaîne de fabrication inclut également des éléments d’assemblage, ainsi que des pièces détachées. C’est l’ensemble de toutes les tâches relatives à l’approvisionnement qui est désigné sous le terme supply chain. Elle représente donc la chaîne d’approvisionnement qui permet à une entreprise de livrer un produit à un client au travers des étapes d’approvisionnement, de processus productif et de distribution de la marchandise. C’est un service clé incluant les achats, les relations avec les fournisseurs, la gestion des stocks, le transport et la manutention. Elle est généralement
représenté à l’aide de différents flux nommés flux physiques (matière brut, marchandises, produits finis...), flux d’informations (relation clients, big data...), et flux financiers/administratifs (transactions financières...). Son enjeu principal est donc l’optimisation de ces flux afin d’obtenir un juste équilibre entre le coût d’approvisionnement, les frais de transport et les délais de livraison pour ainsi profiter d’un ascendant compétitif sur la concurrence.
Le problème de planification de tournée de véhicules, Véhicule Routing problem (VRP) en anglais, est une activité logistique qui fait partie intégrante de la supply chain. De manière générale, cela consiste à déterminer les tournées d’une flotte de véhicules afin de livrer des biens à une liste de clients, tout en respectant un ensemble de contraintes structurelles et opérationnelles, afin d’optimiser la gestion des coûts liés au transport au travers de différents objectifs : minimiser les quantités de camions utilisés, la distance et le temps de trajet, etc. Au fil des années, et avec la prise de conscience écologique, des objectifs secondaires plus vertueux se sont ajoutés, comme par exemple la diminution des émissions de CO2 liées aux tournées de véhicules [4].
Au delà des activités de supply chain, de nombreuses applications réelles existent pour ce pro- blème, par exemple réaliser des tournées d’interventions (maintenance, réparation, contrôles), de visites (visites médicales, commerciales), de transport scolaire, etc. Ainsi, il existe de nombreuses variations [5] du VRP faisant intervenir de nouvelles contraintes. De plus, en raison de l’augmentation des coûts de transport, des ressources limitées et des attentes croissantes des clients, gouvernements, et de la société de manière générale, les méthodes et techniques qui permettent l’optimisation des planifications de tournées de véhicules jouent un rôle essentiel pour fournir des solutions pratiques à la gestion et à l’exploitation des systèmes de distribution de biens ou services, et sont toujours en constante évolution [1, 6, 7].
Dans le cadre de ce stage, nous allons nous intéresser à une variante spécifique du problème de tournée de véhicule, qui se nomme Time-Dependent Vehicule Routing Problem with Time Windows (TD-VRP-TW) [2] dans lequel (1) les clients doivent être livrés durant des périodes spécifiques et (2), les temps de trajets entre deux clients donnés varies en fonction du moment de la journée. Une partie des clients à livrer sera connu en début d’instance, les autres arriveront au fur et à mesure de manière dynamique.

Concrètement, le travail demandé durant ce stage vise à développer une méthode qui combine des techniques de l’IA, avec d’autres, plus traditionnelles et issues de la recherche opérationnelle [3]. Le domaine d’application sera la mobilité, avec un problème de tournée de véhicules fortement contraint. Néanmoins, la méthode fournie devra d’être modulable afin de pouvoir intégrer de nouvelles contraintes et objectifs. L’enjeu de ce projet est donc de concevoir, implémenter et de valider une méthode novatrice en terme de stratégie d’exploration, et qui sera couplé a un système d’apprentissage afin de s’approprier dynamiquement les caractéristiques des problèmes de tournées de véhicules.

2 Missions

Ce sujet de stage se décomposera en deux parties principales. La première concernera l’analyse des données relatives au problème du "Time-Dependent Vehicule Routing Problem with Time Windows" (TD-VRP-TW). Puis, à partir des analyses réalisées, la seconde partie se focalisera sur la mise en place d’une méthode pouvant résoudre ce problème. A ce stade, l’apport scientifique se fera sur l’adjonction de mécanismes variés afin de s’approprier les caractéristiques du problème via un processus d’apprentissage, mais aussi d’améliorer la stratégie d’exploration de l’espace des solutions.
 

Ces phases donneront lieu aux contributions suivantes :

• Conception d’un entrepôt de données pour recueillir les informations relatives aux instances et solutions existantes au TD-VRP-TW. Analyse des données afin de classifier les instances et caractériser les bonnes solutions.
• Développer une métaheuristique afin de résoudre le problème du TD-VRP-TW, en s’appuyant sur les analyses effectuées précédemment, qui permettront de déduire des indicateurs de qualité pouvant guider la recherche de solutions.
• Adjoindre des mécanismes supplémentaires à la métaheuristique développée afin de diversifier la recherche, mais aussi améliorer la qualité de l’apprentissage : stratégie decay ε-greedy, liste tabou, hybridation, apprentissage par renforcement, multi-agent, etc.

3 Compétences requises

Ce stage est proposé aux élèves de niveau Master 2 ou dernière année d’école d’ingénieur, et qui
correspondent au profil suivant :

• Filière informatique.
• Bon niveau en programmation et en base de données.
• Des connaissances en recherche opérationnelle et optimisation combinatoire, dont notamment
• des connaissances sur les heuristiques, métaheuristiques et techniques de l’IA.
• Autonomie et rigueur.

4 Organisation du stage

Le stage durera six mois et se déroulera à CESI Strasbourg sous l’encadrement de M. Caillard. Pour candidater, merci d’envoyer les documents suivants à Simon Caillard (scaillard@cesi.fr) : CV complet, lettre de motivation, relevés de notes, lettres de recommandation (optionnel). L’objet du mail devra être sous la forme suivante : [candidature] titre du stage. 
 

Références

[1] Hsiang Chen, Aldy Gunawan, Vanny Minanda, and Yun-Chia Liang. Metaheuristics for time-
dependent vehicle routing problem with time windows. International Journal of Operational
Research, 1 :1, 01 2022.
[2] Huey-Kuo Chen, Che-Fu Hsueh, and Mei-Shiang Chang. The real-time time-dependent ve-
hicle routing problem. Transportation Research Part E : Logistics and Transportation Review,
42(5) :383–408, 2006.
[3] Robert Faure, Bernard Lemaire, and Christophe Picouleau. Précis de recherche opérationnelle.
Dunod, 2014.
[4] Yongbo Li, Hamed Soleimani, and Mostafa Zohal. An improved ant colony optimization algo-
rithm for the multi-depot green vehicle routing problem with multiple objectives. Journal of
cleaner production, 227 :1161–1172, 2019.
[5] Suresh Nanda Kumar and Ramasamy Panneerselvam. A survey on the vehicle routing problem
and its variants. Intelligent Information Management, 04, 01 2012.
[6] Binbin Pan, Zhenzhen Zhang, and Andrew Lim. A hybrid algorithm for time-dependent vehicle
routing problem with time windows. Computers & Operations Research, 128 :105193, 2021.
[7] Deng Ye, Zhu Wanhong, Li Hongwei, and Zheng Yonghui. Multi-type ant system algorithm for
the time dependent vehicle routing problem with time windows. Journal of Systems Engineering
and Electronics, 29(3) :625–638, 2018