LUCAS Flavien

Soutenance de thèse de doctorat - Flavien LUCASFlavien LUCAS, en vue de l’obtention du grade de docteur, en « INFORMATIQUE », présentera ses travaux intitulés : "Données ouvertes, simulation et optimisation pour le transport urbain" le 19 novembre.

Résumé

Dans le domaine de la recherche opérationnelle, la résolution des problèmes de tournées constitue un défi emblématique depuis les années 1960.

Initialement développées sur des problèmes simples, de nombreuses variantes ont permis d'améliorer le réalisme des instances étudiées, en particulier en milieu urbain où la congestion dépend du véhicule utilisé.

Cependant, encore peu de méthodes sont compatibles avec l'ensemble des variantes existantes, celles-ci perdant de l'efficacité avec l'augmentation du nombre de clients.

C’est dans ce contexte que nous avons développé un solveur robuste et adaptatif, obtenant de bonnes solutions dans un très bref délai sur un nombre élevé d’instances aussi difficiles que variées (plusieurs milliers de clients, véhicules hétérogènes, milieu urbain, etc).

Ce nouveau solveur permet de générer des solutions issues de multiples instances, caractérisées par un ensemble de variables, dont l'étude permet de mieux comprendre ce que constitue une bonne solution.

Dans un contexte où les travaux interdisciplinaires croisant recherche opérationnelle et apprentissage automatique sont de plus en plus fréquents, nous nous sommes intéressés à l’utilisation d’arbres de décision pour cartographier les aires contenant a priori l’ensemble des solutions de bonne qualité. La combinaison entre les arbres de décision et ce nouveau solveur restreint la recherche de bonnes solutions aux zones prometteuses, afin d’augmenter les chances d’obtenir de bons résultats et de réduire la durée de cette exploration.

Les résultats expérimentaux indiquent que ces travaux interdisciplinaires sont prometteurs pour générer un ensemble de méthodes hybrides performantes.

 

Mots clés : Optimisation, analyse statistique, apprentissage automatique, métaheuristique,

tournées de véhicules

Abstract

Solving realistic vehicle routing problems with heterogeneous fleet in urban environments: towards an adaptive solver combining operations research and machine learning

In the field of operations research, solving vehicle routing problem has been an emblematic challenge since the 1960s. Initially developed on simple problems, many variants have improved the realism of the studied instances, especially in urban areas where congestion depends on the vehicle used. However, there are still few methods consistent with all the existing variants, which are becoming less effective as the number of clients increases.

It is in this context that we have developed a robust and adaptive solver, obtaining good solutions in a very short period of time on a high number of instances as difficult as varied (several thousand customers, heterogeneous vehicles, urban environment, etc).

This new solver makes it possible to generate solutions from multiple instances, characterized by a set of variables, which allows a better understanding of what constitutes a good solution.

In a context where interdisciplinary work combining operational research and machine learning is becoming more and more frequent, we were interested in the use of decision trees to map areas containing a priori all good quality solutions. The combination between decision trees and this new solver restricts the search for good solutions to promising areas, in order to increase the probability of obtaining good results and to reduce the duration of this exploration.

Experimental results indicate that this interdisciplinary work is promising to generate a set of efficient hybrid methods.

 

Keywords: Optimisation, statistical analysis, machine learning, metaheuristic, vehicle routing

 

Membres du jury

  • DR Latifa OUKHELLOU, Directrice de Recherche, IFSTTAR – Marnes-La-Vallée
  • Prof. Daniele VIGO, Université de Bologne – Italie
  • Prof. Christine SOLNON, INSA Lyon
  • Prof. Christian PRINS, Université de Technologie de Compiègne
  • Dr Fabien LEHUÉDÉ, Maître de Conférences, IMT Atlantique
  • Prof. Marc SEVAUX, Université Bretagne Sud, Lab-STICC
  • Prof. Romain BILLOT, IMT Atlantique

 

École doctorale MathSTIC

Informations pratiques

Jeudi 19 novembre 2020 à 14h

Soutenance dématérialisée
Lorient