Une heuristique de recherche à voisinage variable pour le problème du voyageur de commerce avec fenêtres de temps

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois.

Méthodes heuristiques pour un problème d'ordonnancement avec contraintes sur les ressources

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cartographie récente et écologie du nerprun bourdaine en Estrie

Le nerprun bourdaine (Rhamnus frangula L.) est une espèce exotique qui envahit plusieurs régions du sud du Québec, et plus particulièrement la région administrative de l'Estrie. Actuellement, on connaît encore peu l'écologie de l'espèce dans le contexte québécois et il n’existe pas de portrait d’ensemble de sa distribution dans les forêts tempérées de cette région. Dans ce contexte, le premier objectif du projet était de cartographier par télédétection la distribution du nerprun bourdaine dans deux secteurs de l'Estrie. Un second objectif était d'évaluer les variables environnementales déterminantes pour expliquer le recouvrement de nerprun bourdaine. La phénologie du nerprun bourdaine diffère de celle de la plupart des espèces indigènes arborescentes puisque ses feuilles tombent plus tard en automne. Cette caractéristique a permis de cartographier, par démixage spectral, la probabilité d'occurrence du nerprun bourdaine grâce à une série temporelle d'images du capteur OLI de Landsat 8. Le recouvrement du nerprun bourdaine a été calculé dans 119 placettes sur le terrain. La cartographie résultante a montré un accord de 69% avec les données terrain. Une image SPOT-7, dont la résolution spatiale est plus fine, a ensuite été utilisée, mais n’a pas permis d'améliorer la cartographie, puisque la date d’acquisition de l’image n’était pas optimale dû à un manque de disponibilité. Concernant le second objectif de la recherche, la variable la plus significative pour expliquer la présence de nerprun bourdaine était la densité du peuplement, ce qui suggère que l’ouverture de la couverture forestière pourrait favoriser l’envahissement. Néanmoins, les résultats tendent à démontrer que le nerprun bourdaine est une espèce «généraliste» qui s’adapte bien à plusieurs conditions environnementales.

Méthode de recherche à grand voisinage pour un problème de tournées de véhicules avec flotte privée et transporteur externe

Dans ce mémoire, nous étudions un problème de tournées de véhicules dans lequel une flotte privée de véhicules n’a pas la capacité suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel à un transporteur externe. Ce dernier n’a aucune contrainte de capacité, mais un coût est encouru lorsqu’un client lui est affecté. Il n’est pas nécessaire de mettre tous les véhicules de la flotte privée en service si cette approche se révèle plus économique. L’objectif consiste à minimiser le coût fixe des véhicules, puis le coût variable de transport et le coût chargé par le transporteur externe. Notre travail consiste à appliquer la métaheuristique de recherche adaptative à grand voisinage sur ce problème. Nous comparons nos résultats avec ceux obtenus précédemment avec différentes techniques connues sur les instances de Christofides et celles de Golden.