Groupe d’études et de recherche en analyse des décisions

Approches métaheuristiques pour le problème de synthèse de réseau multi-produits ave coûts fixes et capacités

Michel Gendreau

Le problème de synthèse de réseau multi-produits avec coûts fixes et capacités est le problème « abstrait » qu’on doit traiter quand on veut faire la synthèse de réseaux de transport ou de télécommunications. Il consiste à trouver la configuration optimale, c.-à-d. les arcs à inclure dans un réseau sur lequel on veut faire circuler des flux de divers produits afin de satisfaire des demandes données entre des paires origine-destination. Chaque arc du réseau est caractérisé par sa capacité (le flux maximal de tous les produits qui peut y circuler), un coût fixe à payer si l’arc est choisi et un coût variable par unité de flux qui y circule. L’objectif du problème consiste à minimiser le coût total du réseau, c.-à-d. la somme des coûts fixes et des coûts variables encourus, tout en respectant les contraintes de capacité. Nous présenterons diverses approches heuristiques que nous avons développées au cours des quinze dernières années, avec différents coauteurs, pour aborder ce problème. Elles couvrent plusieurs types de métaheuristiques : recherche avec tabous, « Path Relinking » et « Scatter Search ». À notre connaissance, ces approches sont toujours les plus efficaces qui ont été proposées pour résoudre le problème de synthèse de réseau multi-produits avec coûts fixes et capacités.

(Travail conjoint avec Teodor Gabriel Crainic et plusieurs autres coauteurs)