Grant: Discovery Grants Program - Individual

Les problèmes d'itinéraires et d'horaires peuvent être formulés à l'aide de modèles de flot multi-commodités, non-linéaires et en nombres entiers, avec des contraintes liantes et des variables de ressource. La structure de flot de chaque commodité définit un chemin élémentaire sur un réseau espace-temps; les arcs représentent diverses activités alors que les noeuds sont des lieux à des temps spécifiques. Les contraintes liantes imposent la couverture de tâches : clients, vols, trains, trajets d'autobus, rotations de pilote, etc. Les ressources servent à modéliser les restrictions locales sur un seul chemin à la fois. On exploite la structure de ces modèles avec des méthodes de décomposition mathématique. La plus utilisée est celle de Dantzig et Wolfe (génération de colonnes), méthode linéaire que nous avons adaptée pour des cas non-linéaires et en nombres entiers. Nous poursuivrons l'étude des algorithmes de plus court chemin élémentaire et des méthodes de stabilisation des variables duales. Dans ce dernier cas, le but principal est de contrôler la dégénérescence souvent rencontrée pour le problème maître. La méthode que nous avons développé a l'avantage d'être complètement linéaire et peut ainsi tirer profit des logiciels très performants comme CPLEX. Au niveau de la théorie, nous travaillerons à la combinaison de deux méthodes d'accélération de l'approche classique de résolution par génération de colonnes : d'une part, la stabilisation des variables duales, d'autre part, l'agrégation dynamique de contraintes. Ces deux méthodes ont fait l'objet de recherches intensives distinctes au cours des dernières années et elles ont toutes deux apporté une forte réduction des temps de calcul. Au niveau des applications industrielles, nous nous intéresserons plus particulièrement aux problèmes du transport par bateau de gaz naturel liquéfié. C'est un secteur en pleine expansion : la demande mondiale prévue pour les quinze prochaines années devrait connaître une croissance de 70% alors que la flotte de cargos affectée à ce type de transport spécialisé devrait doubler d'ici cinq ans.