Optimisation avancée au service du covoiturage dynamique - Université de Lille Accéder directement au contenu
Thèse Année : 2016

Advanced optimization for the dynamic carpooling problem

Optimisation avancée au service du covoiturage dynamique

Résumé

Carpooling is presented as an alternative transport solution that comes treat environmental image, economic and societal personal car. The dynamic carpooling problem is to develop real-time optimized touring vehicles to better respond to the instantaneous transport demands.Our work belongs within this context, where optimization and real time are the key words. Given the exponential complexity of the dynamic ridematching problem, we opt for the approximate methods to solve it. We present our first contribution by proposing a metaheuristic based on the multi-criteria tabu search. The proposed algorithm employs an explicit memory system and several searching strategies developed to avoid the entrapment by local solutions. Afterward, we introduce our second contribution which is in the form of an evolutionary approach supported by a dynamic coding and based on controlled genetic operators. However, the exponential complexity of the problem leads us to consider that a simple metaheuristics is not sufficient to solve effectively the problem of dynamic ridematching. It is with this in mind that we are unveiling our third solving methodology by developing an original evolutionary approach in which chromosomes are defined as autonomous and intelligent agents. Thanks to an accurate protocol negotiation, the Chromosomes Agents can control the genetic operators and guide search for finding optimal solutions within a reasonable period of time. With the prospect of a better combination between carpooling and other modes of transport, we design a system called DyCOS, integrating our approaches and applications dedicated to solving the problem of dynamic ridesharing.
Le covoiturage se présente comme une solution de transport alternative qui vient soigner l’image environnementale, économique et sociétale de la voiture personnelle. Le problème du covoiturage dynamique consiste à élaborer en temps réel des tournées de véhicules optimisés, afin de répondre au mieux aux demandes instantanées de transport.C’est dans ce cadre que s’inscrivent nos travaux où l’optimisation et le temps réel sont les maître-mots. Étant donné la complexité exponentielle du problème, nous optons pour des méthodes approximatives pour le résoudre. Nous présentons notre première contribution en proposant une métaheuristique basée sur la recherche tabou. L'algorithme utilise un système de mémoire explicite et plusieurs stratégies de recherches développées pour éviter le piégeage par des optimums locaux. Ensuite, nous introduisons notre deuxième contribution qui se présente sous la forme d’une approche évolutionnaire supportée par un codage dynamique et basée sur des opérateurs génétiques contrôlés. La complexité exponentielle du problème nous amène à dévoiler notre troisième méthodologie, en proposant une approche évolutionnaire originale dans laquelle les chromosomes sont définis comme des agents autonomes et intelligents. Grâce à un protocole de négociation puissant, les Agents Chromosomes gèrent les opérateurs génétiques et orientent la recherche afin de trouver des solutions optimales dans un temps de calcul réduit. Dans la perspective d’une meilleure combinaison entre le covoiturage et les autres modes de transport, nous concevons un système baptisé DyCOS, intégrant nos approches et applications dédiées à la résolution du problème du covoiturage dynamique.
Fichier principal
Vignette du fichier
Bencheikh_Sondes_DLE.pdf (2.32 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)
Loading...

Dates et versions

tel-01735243 , version 1 (15-03-2018)

Identifiants

  • HAL Id : tel-01735243 , version 1

Citer

Sondes Ben Cheikh. Optimisation avancée au service du covoiturage dynamique. Automatique. Ecole Centrale de Lille, 2016. Français. ⟨NNT : 2016ECLI0002⟩. ⟨tel-01735243⟩
473 Consultations
2381 Téléchargements

Partager

Gmail Facebook X LinkedIn More