Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02895342
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, July 9, 2020 - 4:09:29 PM
Last modification on : Friday, July 10, 2020 - 3:39:59 AM

Identifiers

  • HAL Id : hal-02895342, version 1

Citation

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⟩

Share

Metrics

Record views

19