Le 13/12/2018 par Laetitia :

Contexte

Cette étude s'inscrit dans un projet de recherche entre l’équipe ORKAD du laboratoire CRIStAL de l'Université de Lille et l'Université de Metz Ce projet a pour objectif d'améliorer les algorithmes de résolution de problèmes d'optimisation combinatoire NP*complet grâce à des techniques d'apprentissage [1,5] et notamment sur les méthodes de résolution de programmation mathématique.

Encadrant : Pr. Laetitia Jourdan,  Dr. Marie-Eléonore Kessaci, Pr. Nicolas Jozefowiez

E-mail : laetitia.jourdan@univ-lille1.fr, mkessaci@univ-lille.fr, nicolas.jozefowiez@univ-lorraine.fr

Laboratoire : CRIStAL – UMR 9189 et LCOMS

Equipe : ORKAD +  IDESS /DO

Rémunération : Indemnité de Stage

Objectif du projet

Les algorithmes de résolution de problèmes d'optimisation sont pour la plupart conçus de manière à être spécifiques au problème voire même à une instance particulière de ce problème. Dès lors que de nouvelles données apparaissent, la conception doit être reconsidérée. Notre objectif est d'utiliser des mécanismes génériques d'apprentissage pour concevoir un algorithme qui s'adapte au mieux à ses données d'entrée et accélère le processus de résolution. Nous nous intéressons ici à la famille des problèmes de tournées de véhicule et notamment la prise en charge de l’équité dans les tournées. Un intérêt particulier sera porté au problème « multiple Traveling Salesman Problem with Lower and Upper Bounds » où la seule méthode de résolution connue est [6].

Les méthodes de résolutions considérées seront la programmation mathématique et notamment la génération de colonnes.

Travail à effectuer

L’objectif de ce projet est d’étudier

• Prise en main des problèmes de tournée de véhicules [6] et de résolution de méthode par programmation mathématique
• Etude des caractéristiques [3, 4] pouvant être apprises dans les problèmes de tournées de véhicules
• Choix d’algorithmes d’apprentissage permettant de trouver automatiquement les caractéristiques
• De concevoir une méthode de programmation dynamique (par génération de colonneà se servant des caractéristiques apprises afin d’améliorer ses résultats (une Learnheuristic)

Compétences :

• Optimisation Combinatoire
• Apprentissage
• Tests statistiques
• C/C++/Python

Poursuite possible :

Une poursuite en thèse dans l’équipe de Metz est envisagée.

Bibliographie

1. Lucien Mousin, Laetitia Jourdan, Marie-Éléonore Kessaci-Marmion, Clarisse Dhaenens: Feature Selection Using Tabu Search with Learning Memory: Learning Tabu Search. LION2016: 141-156
2. Marie-Eléonore Marmion, Hernán E. Aguirre, Clarisse Dhaenens, Laetitia Jourdan, Kiyoshi Tanaka: Multi-objective Neutral Neighbors': What could be the definition(s)? GECCO 2016: 349-356
3. Marie-Eléonore Marmion, Laetitia Jourdan, Clarisse Dhaenens: Fitness Landscape Analysis and Metaheuristics Efficiency. J. Math. Model. Algorithms 12(1): 3-26 (2013)
4. Florian Arnold & Kenneth Sörensen  A simple, deterministic, and efficient knowledge-driven heuristic for the vehicle routing problem RESEARCH PAPER 2017-012 DECEMBER 2017
5. David Corne, Clarisse Dhaenens, Laetitia Jourdan: Synergies between operations research and data mining: The emerging use of multi-objective approaches. European Journal of Operational Research 221(3): 469-479 (2012)

[6]  T. Bekta?. and J. Lysgaard (2015), Optimal vehicle routing with lower and upper bounds on route durations. Networks, 65: 166-179. doi:10.1002/net.21592