Recherche rapide
Fiche descriptive
Contributions théoriques et pratiques pour la recherche dispersée, recherche à voisinage variable et matheuristique pour les programmes en nombres entiers mixtes (Document en Anglais)
Accéder au(x) document(s) : Droits d'auteur : Ce document est protégé en vertu du Code de la Propriété Intellectuelle.
Modalités de diffusion de la thèse :
Modalités de diffusion de la thèse :
Auteur : Todosijevic Raca
Date de soutenance : 22-06-2015
Directeur(s) de thèse : Hanafi Saïd
- Gendron Bernard
Président du jury : Fréville Arnaud
Membres du jury : Hanafi Saïd
- Gendron Bernard
- Glover Fred
- Mladenovic Nenad
- Vasquez Michel
- Hansen Pierre
- Punnen Abraham P.
Rapporteurs : Hansen Pierre
- Punnen Abraham P.
Laboratoire : Laboratoire d'Automatique, de Mécanique et d'Informatique Industrielles et Humaines - LAMIH
Ecole doctorale : Sciences pour l'ingénieur (SPI)
Todosijevic, Raca
Nom
Todosijevic
Prénom
Raca
Nationalité
RS
Date de soutenance : 22-06-2015
Directeur(s) de thèse : Hanafi Saïd
Hanafi, Saïd
Nom
Hanafi
Prénom
Saïd
Gendron, Bernard
Nom
Gendron
Prénom
Bernard
Président du jury : Fréville Arnaud
Fréville, Arnaud
Nom
Fréville
Prénom
Arnaud
Membres du jury : Hanafi Saïd
Hanafi, Saïd
Nom
Hanafi
Prénom
Saïd
Gendron, Bernard
Nom
Gendron
Prénom
Bernard
Glover, Fred
Nom
Glover
Prénom
Fred
Mladenovic, Nenad
Nom
Mladenovic
Prénom
Nenad
Vasquez, Michel
Nom
Vasquez
Prénom
Michel
Hansen, Pierre
Nom
Hansen
Prénom
Pierre
Punnen, Abraham P.
Nom
Punnen
Prénom
Abraham P.
Rapporteurs : Hansen Pierre
Hansen, Pierre
Nom
Hansen
Prénom
Pierre
Punnen, Abraham P.
Nom
Punnen
Prénom
Abraham P.
Laboratoire : Laboratoire d'Automatique, de Mécanique et d'Informatique Industrielles et Humaines - LAMIH
Ecole doctorale : Sciences pour l'ingénieur (SPI)
Discipline : Informatique
Classification : Sciences de l'ingénieur, Informatique
Mots-clés : OptimisationRecherche disperséeRecherche voisinage variableHeuristiqueMétaheuristiqueMatheuristiqueArrondi DirectionnelConvergence0-1 MIPRoutageVoyageur de CommerceElaboration de tournéesLocalisationClusteringOrdonnancementMaintenanceAffectation des unités de production d´énergieConception de réseau.
Métaheuristiques -- Thèses et écrits académiquesHeuristique -- Thèses et écrits académiquesProblème du voyageur de commerce -- Thèses et écrits académiquesOptimisation mathématique -- Thèses et écrits académiques
Résumé : Cette thèse comporte des résultats théoriques et pratiques sur deux métaheuristiques, la Recherche Dispersée et la Recherche Voisinage variable (RVV), ainsi que sur des Matheuristiques. Au niveau théorique, la contribution principale de cette thèse est la proposition d’un algorithme de recherche dispersée avec l’arrondi directionnel convergent pour les programmes en nombres entiers mixtes (0-1 MIP), avec une preuve de cette convergence en un nombre fini d’itérations. En se basant sur cet algorithme convergeant, deux implémentations et plusieurs heuristiques sont proposées et testées sur des instances de 0-1 MIP. Les versions testées reposent sur des implémentations non optimisées pour mettre en évidence la puissance des approches dans une forme simplifiée. Nos résultats démontrent l’efficacité de ces approches initiales, ce qui les rend attractives lorsque des solutions de très haute qualité sont recherchées avec un investissement approprié en termes d’effort de calcul. Cette thèse inclut également quelques nouvelles variantes de la métaheuristique Recherche Voisinage Variable telles qu’une recherche voisinage variable deux niveaux, une recherche voisinage variable imbriquée, une descente voisinage variable cyclique et une heuristique de plongée voisinage variable. En outre, plusieurs implémentations efficaces de ces algorithmes basés sur la recherche voisinage variable ont été appliquées avec succès à des problèmes NP-Difficiles apparaissant en transport, logistique, production d’énergie, ordonnancement, et segmentation. Les heuristiques proposées se sont avérées être les nouvelles heuristiques de référence sur tous les problèmes considérés. La dernière contribution de cette thèse repose sur la proposition de plusieurs matheuristiques pour résoudre le problème de Conception de Réseau Multi-flots avec Coût fixe (CRMC). Les performances de ces matheuristiques ont été évaluées sur un ensemble d’instances de référence du CRMC. Les résultats obtenus démontrent la compétitivité des approches proposées par rapport aux approches existantes de la littérature.
Classification : Sciences de l'ingénieur, Informatique
Mots-clés : OptimisationRecherche disperséeRecherche voisinage variableHeuristiqueMétaheuristiqueMatheuristiqueArrondi DirectionnelConvergence0-1 MIPRoutageVoyageur de CommerceElaboration de tournéesLocalisationClusteringOrdonnancementMaintenanceAffectation des unités de production d´énergieConception de réseau.
Métaheuristiques -- Thèses et écrits académiquesHeuristique -- Thèses et écrits académiquesProblème du voyageur de commerce -- Thèses et écrits académiquesOptimisation mathématique -- Thèses et écrits académiques
Résumé : Cette thèse comporte des résultats théoriques et pratiques sur deux métaheuristiques, la Recherche Dispersée et la Recherche Voisinage variable (RVV), ainsi que sur des Matheuristiques. Au niveau théorique, la contribution principale de cette thèse est la proposition d’un algorithme de recherche dispersée avec l’arrondi directionnel convergent pour les programmes en nombres entiers mixtes (0-1 MIP), avec une preuve de cette convergence en un nombre fini d’itérations. En se basant sur cet algorithme convergeant, deux implémentations et plusieurs heuristiques sont proposées et testées sur des instances de 0-1 MIP. Les versions testées reposent sur des implémentations non optimisées pour mettre en évidence la puissance des approches dans une forme simplifiée. Nos résultats démontrent l’efficacité de ces approches initiales, ce qui les rend attractives lorsque des solutions de très haute qualité sont recherchées avec un investissement approprié en termes d’effort de calcul. Cette thèse inclut également quelques nouvelles variantes de la métaheuristique Recherche Voisinage Variable telles qu’une recherche voisinage variable deux niveaux, une recherche voisinage variable imbriquée, une descente voisinage variable cyclique et une heuristique de plongée voisinage variable. En outre, plusieurs implémentations efficaces de ces algorithmes basés sur la recherche voisinage variable ont été appliquées avec succès à des problèmes NP-Difficiles apparaissant en transport, logistique, production d’énergie, ordonnancement, et segmentation. Les heuristiques proposées se sont avérées être les nouvelles heuristiques de référence sur tous les problèmes considérés. La dernière contribution de cette thèse repose sur la proposition de plusieurs matheuristiques pour résoudre le problème de Conception de Réseau Multi-flots avec Coût fixe (CRMC). Les performances de ces matheuristiques ont été évaluées sur un ensemble d’instances de référence du CRMC. Les résultats obtenus démontrent la compétitivité des approches proposées par rapport aux approches existantes de la littérature.
Type de contenu : Texte
Format : PDF
Format : PDF
Identifiant : uvhc-ori-oai-wf-1-1869
Type de ressource : Thèse
Type de ressource : Thèse