Colloque

Résolution du problème de plus court chemin bicritère par les deux bouts

P. Hansen

Brigitte Jaumard

T. Vovor

Membre a labase

P. Hansen

Résumé du colloque

Un nouvel algorithme qui exploite de l'information en provenance de la source et du puits, est présenté pour le problème du plus court chemin bicritère. Ce problème peut se rencontrer, par exemple, en transport de matières dangereuses si l'on minimise à la fois le coût de transport et la population exposée. Les tests de dominance utilisent des extensions non-dominées déjà calculées au sommet courant, ainsi qu'une approximation extérieure de l'ensemble des extensions efficaces possibles pour ce sommet. Une technique est également donnée pour générer efficacement les chemins proprement efficaces et peut être utilisée pour initialiser l'algorithme. Les deux procédures se généralisent aisément à l'énumération de toutes les étiquettes qui sont contenues dans une fenêtre définie sur les critères. De telles bornes peuvent servir, en pratique, à éliminer les solutions efficaces comportant une trop grande détérioration de l'un des critères. Des tests effectués sur des graphes aléatoires indiquent que l'algorithme se compare favorablement à la méthode de résolution par d'un seul bout, lorsque la taille ou la densité du graphe augmente.

Contexte

Section :

Recherche opérationnelle

Thème du colloque :

Recherche opérationnelle

Responsables :

Bernard Lamond

Hôte : Université Laval

Découvrez d'autres communications scientifiques

Dans le même colloque
Du même congressiste

Titre du colloque :

Recherche opérationnelle

Technologies communes dans l'analyse d'enveloppement de données (DEA)

Pascal Lang

Stabilisation dans le cadre de la génération de colonnes

O. Du Merle

Allocation dynamique de la largeur de bande pour des réseaux à plusieurs technologies

M. Plante

Voir tous les contenus de ce colloque

Autres communications du même congressiste :

Thème du colloque :

Recherche opérationnelle

Recherche à voisinage variable de graphes extrêmaux

G. Caporossi

Résolution du problème de plus court chemin bicritère par les deux bouts

P. Hansen

Introduction à la recherche à voisinage variable

P. Hansen