Une Résolution exacte du Pollution Routing Problem continu à l'aide d'un algorithme de Branch and Price
Théo Le Brun  1@  , Sandra Ulrich Ngueveu  1@  
1 : Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Centre National de la Recherche Scientifique : UPR8001, Institut National Polytechnique [Toulouse]

Le Pollution Routing Problem est une variante du problème de tournée de véhicules faisant intervenir les émissions des véhicules dans son objectif de minimisation. La version originelle se présente sous forme d'un Mixed-Integer Non-Linear Problem, généralement résolu via une discrétisation du problème ou des méthodes heuristiques. A notre connaissance, seule deux méthodes résolvent exactement la version continue du Pollution Routing Problem, mais ce à une précision préfédinie près. La présente approche se propose de résoudre exactement le Pollution Routing Problem continu, en se basant sur un algorithme de Branch and Price. Le problème maître de la génération de colonne est alimenté par des colonnes associées à leur coût non-linéaire, tandis que le sous problème travaille sur des coûts simplifiés et minorés, garantissant de retourner toutes les colonnes potentiellement améliorantes. Les coûts non-linéaires sont ensuite recalculés avant ajout au problème maître. En partant de solutions de bonne qualité, cette méthode a pour ambition de converger vers la solution optimale. 


Personnes connectées : 2 Vie privée
Chargement...