Algorithmes génétiques pour le CARP - Université de technologie de Troyes Accéder directement au contenu
Communication Dans Un Congrès Année : 2001

Algorithmes génétiques pour le CARP

Résumé

Le CARP (Capacitated Arc Routing Problem) est un problème NP-difficile, utile pour modéliser par exemple le ramassage des ordures ménagères ou le déneigement des routes. Les méthodes exactes de résolution ne résolvent que de petites instances et les problèmes de grande taille sont traitables uniquement par des heuristiques ou des métaheuristiques. Nous présentons les premiers algorithmes génétiques de la littérature pour résoudre le CARP. Le modèle de données étendu permet de prendre en compte efficacement plusieurs extensions telles que les rues à sens unique ou à double sens et les interdictions de tourner. Notre meilleur algorithme génétique, de type hybride, a été testé sur des instances de la littérature et se montre compétitif avec les métaheuristiques déjà publiées.
Fichier non déposé

Dates et versions

hal-02895342 , version 1 (09-07-2020)

Identifiants

  • HAL Id : hal-02895342 , version 1

Citer

Philippe Lacomme, Christian Prins, Wahiba Ramdane-Cherif. Algorithmes génétiques pour le CARP. MOSIM'01 (3ème Conférence Francophone de Modélisation et Simulation), Apr 2001, Troyes, France. ⟨hal-02895342⟩
36 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More