Colloque

Une heuristique d'insertion de lignes pour le problème du voyageur de commerce dans le plan

Fabien Chauny

Richard Loulou

Membre a labase

Fabien Chauny

Résumé du colloque

Le problème du voyageur de commerce consiste à trouver le plus court chemin reliant tous les points d'un ensemble. L'heuristique proposée tire avantage du fait que les points se trouvent naturellement alignés. Cette situation est fréquente dans l'insertion de circuits imprimés, le perçage de métal en feuille, et d'autres applications. L'heuristique se divise en deux phases. On repère d'abord les lignes, puis ces lignes sont fusionnées les unes aux autres pour former un chemin hamiltonien. La complexité, la performance garantie et des variantes sont analysées. Des résultats numériques sur des problèmes réels et des problèmes issus de la littérature sont présentés.

Contexte

Section :

Informatique et recherche opérationnelle

Thème du colloque :

Informatique et recherche opérationnelle

Hôte : Université de Montréal

Découvrez d'autres communications scientifiques

Dans le même colloque
Du même congressiste

Titre du colloque :

Informatique et recherche opérationnelle

Méthodologie de développement d'interfaces pour systèmes hypermédias

Lison Sergerie

Applications d'hypertexte à l'analyse de la littérature orale

Imants Freibergs

Une heuristique d'insertion de lignes pour le problème du voyageur de commerce dans le plan

Fabien Chauny

Voir tous les contenus de ce colloque

Autres communications du même congressiste :

Thème du colloque :

Informatique et recherche opérationnelle

Une nouvelle heuristique pour le problème de découpe rectangulaire

Fabien Chauny

Une heuristique d'insertion de lignes pour le problème du voyageur de commerce dans le plan

Fabien Chauny