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.

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.

Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Optimization models and methods for real-time transportation planning in forestry

Lors du transport du bois de la forêt vers les usines, de nombreux événements imprévus peuvent se produire, événements qui perturbent les trajets prévus (par exemple, en raison des conditions météo, des feux de forêt, de la présence de nouveaux chargements, etc.). Lorsque de tels événements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit être détourné vers un chemin alternatif. En l’absence d’informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-même "fermé" suite à un événement imprévu. Il est donc essentiel de fournir aux chauffeurs des informations en temps réel, en particulier des suggestions de chemins alternatifs lorsqu’une route prévue s’avère impraticable. Les possibilités de recours en cas d’imprévus dépendent des caractéristiques de la chaîne logistique étudiée comme la présence de camions auto-chargeurs et la politique de gestion du transport. Nous présentons trois articles traitant de contextes d’application différents ainsi que des modèles et des méthodes de résolution adaptés à chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l’ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent être faits pour minimiser les changements apportés au plan initial. Bien que la flotte de camions soit homogène, il y a un ordre de priorité des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est également une priorité. Étant donné que les conséquences des événements imprévus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l’approche proposée traite d’abord l’annulation et le retard d’un seul voyage, puis elle est généralisée pour traiter des événements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impactés durant la même semaine de telle sorte qu’une chargeuse soit libre au moment de l’arrivée du camion à la fois au site forestier et à l’usine. De cette façon, les voyages des autres camions ne seront pas mo- difiés. Cette approche fournit aux répartiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient être obtenues si le répartiteur était autorisé à apporter plus de modifications au plan initial. Dans le second article, nous considérons un contexte où un seul voyage à la fois est communiqué aux chauffeurs. Le répartiteur attend jusqu’à ce que le chauffeur termine son voyage avant de lui révéler le prochain voyage. Ce contexte est plus souple et offre plus de possibilités de recours en cas d’imprévus. En plus, le problème hebdomadaire peut être divisé en des problèmes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des périodes limitées durant la journée. Nous utilisons un modèle de programmation mathématique basé sur un réseau espace-temps pour réagir aux perturbations. Bien que ces dernières puissent avoir des effets différents sur le plan de transport initial, une caractéristique clé du modèle proposé est qu’il reste valable pour traiter tous les imprévus, quelle que soit leur nature. En effet, l’impact de ces événements est capturé dans le réseau espace-temps et dans les paramètres d’entrée plutôt que dans le modèle lui-même. Le modèle est résolu pour la journée en cours chaque fois qu’un événement imprévu est révélé. Dans le dernier article, la flotte de camions est hétérogène, comprenant des camions avec des chargeuses à bord. La configuration des routes de ces camions est différente de celle des camions réguliers, car ils ne doivent pas être synchronisés avec les chargeuses. Nous utilisons un modèle mathématique où les colonnes peuvent être facilement et naturellement interprétées comme des itinéraires de camions. Nous résolvons ce modèle en utilisant la génération de colonnes. Dans un premier temps, nous relaxons l’intégralité des variables de décision et nous considérons seulement un sous-ensemble des itinéraires réalisables. Les itinéraires avec un potentiel d’amélioration de la solution courante sont ajoutés au modèle de manière itérative. Un réseau espace-temps est utilisé à la fois pour représenter les impacts des événements imprévus et pour générer ces itinéraires. La solution obtenue est généralement fractionnaire et un algorithme de branch-and-price est utilisé pour trouver des solutions entières. Plusieurs scénarios de perturbation ont été développés pour tester l’approche proposée sur des études de cas provenant de l’industrie forestière canadienne et les résultats numériques sont présentés pour les trois contextes.

Development of new scenario decomposition techniques for linear and nonlinear stochastic programming

Une approche classique pour traiter les problèmes d’optimisation avec incertitude à deux- et multi-étapes est d’utiliser l’analyse par scénario. Pour ce faire, l’incertitude de certaines données du problème est modélisée par vecteurs aléatoires avec des supports finis spécifiques aux étapes. Chacune de ces réalisations représente un scénario. En utilisant des scénarios, il est possible d’étudier des versions plus simples (sous-problèmes) du problème original. Comme technique de décomposition par scénario, l’algorithme de recouvrement progressif est une des méthodes les plus populaires pour résoudre les problèmes de programmation stochastique multi-étapes. Malgré la décomposition complète par scénario, l’efficacité de la méthode du recouvrement progressif est très sensible à certains aspects pratiques, tels que le choix du paramètre de pénalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augmenté. Pour le choix du paramètre de pénalisation, nous examinons quelques-unes des méthodes populaires, et nous proposons une nouvelle stratégie adaptive qui vise à mieux suivre le processus de l’algorithme. Des expériences numériques sur des exemples de problèmes stochastiques linéaires multi-étapes suggèrent que la plupart des techniques existantes peuvent présenter une convergence prématurée à une solution sous-optimale ou converger vers la solution optimale, mais avec un taux très lent. En revanche, la nouvelle stratégie paraît robuste et efficace. Elle a convergé vers l’optimalité dans toutes nos expériences et a été la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l’idée de remplacer le terme quadratique par un terme linéaire. Bien que qu’il nous reste encore à tester notre méthode, nous avons l’intuition qu’elle réduira certaines difficultés numériques et théoriques de la méthode de recouvrement progressif.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.

An adaptive neighborhood search algorithm for optimizing stochastic mining complexes

Les métaheuristiques sont très utilisées dans le domaine de l'optimisation discrète. Elles permettent d’obtenir une solution de bonne qualité en un temps raisonnable, pour des problèmes qui sont de grande taille, complexes, et difficiles à résoudre. Souvent, les métaheuristiques ont beaucoup de paramètres que l’utilisateur doit ajuster manuellement pour un problème donné. L'objectif d'une métaheuristique adaptative est de permettre l'ajustement automatique de certains paramètres par la méthode, en se basant sur l’instance à résoudre. La métaheuristique adaptative, en utilisant les connaissances préalables dans la compréhension du problème, des notions de l'apprentissage machine et des domaines associés, crée une méthode plus générale et automatique pour résoudre des problèmes. L’optimisation globale des complexes miniers vise à établir les mouvements des matériaux dans les mines et les flux de traitement afin de maximiser la valeur économique du système. Souvent, en raison du grand nombre de variables entières dans le modèle, de la présence de contraintes complexes et de contraintes non-linéaires, il devient prohibitif de résoudre ces modèles en utilisant les optimiseurs disponibles dans l’industrie. Par conséquent, les métaheuristiques sont souvent utilisées pour l’optimisation de complexes miniers. Ce mémoire améliore un procédé de recuit simulé développé par Goodfellow & Dimitrakopoulos (2016) pour l’optimisation stochastique des complexes miniers stochastiques. La méthode développée par les auteurs nécessite beaucoup de paramètres pour fonctionner. Un de ceux-ci est de savoir comment la méthode de recuit simulé cherche dans le voisinage local de solutions. Ce mémoire implémente une méthode adaptative de recherche dans le voisinage pour améliorer la qualité d'une solution. Les résultats numériques montrent une augmentation jusqu'à 10% de la valeur de la fonction économique.

La distribution ‘juste’ de la signature savante dans les collaborations de recherche multidisciplinaire en sciences de la santé

L’auteur qui appose son nom à une publication universitaire sera reconnu pour sa contribution à la recherche et devra également en assumer la responsabilité. Il existe divers types d’agencements pouvant être utilisés afin de nommer les auteurs et souligner l’ampleur de leur contribution à ladite recherche. Par exemple, les auteurs peuvent être nommés en ordre décroissant selon l’importance de leurs contributions, ce qui permet d’allouer davantage de mérite et de responsabilité aux premiers auteurs (à l’instar des sciences de la santé) ou bien les individus peuvent être nommés en ordre alphabétique, donnant une reconnaissance égale à tous (tel qu’on le note dans certains domaines des sciences sociales). On observe aussi des pratiques émergeant de certaines disciplines ou des champs de recherche (tel que la notion d’auteur correspondant, ou directeur de recherche nommé à la fin de la liste d’auteurs). En science de la santé, lorsque la recherche est de nature multidisciplinaire, il existe différentes normes et pratiques concernant la distribution et l’ordre de la signature savante, ce qui peut donner lieu à des désaccords, voire à des conflits au sein des équipes de recherche. Même si les chercheurs s’entendent pour dire que la signature savante devrait être distribué de façon ‘juste’, il n’y a pas de consensus sur ce que l’on qualifie de ‘juste’ dans le contexte des équipes de recherche multidisciplinaire. Dans cette thèse, nous proposons un cadre éthique pour la distribution juste de la signature savante dans les équipes multidisciplinaires en sciences de la santé. Nous présentons une critique de la documentation sur la distribution de la signature savante en recherche. Nous analysons les enjeux qui peuvent entraver ou compliquer une distribution juste de la signature savante tels que les déséquilibres de pouvoir, les conflits d’intérêts et la diversité de cultures disciplinaires. Nous constatons que les normes internationales sont trop vagues; par conséquent, elles n’aident pas les chercheurs à gérer la complexité des enjeux concernant la distribution de la signature savante. Cette limitation devient particulièrement importante en santé mondiale lorsque les chercheurs provenant de pays développés collaborent avec des chercheurs provenant de pays en voie de développement. Afin de créer un cadre conceptuel flexible en mesure de s’adapter à la diversité des types de recherche multidisciplinaire, nous proposons une approche influencée par le Contractualisme de T.M. Scanlon. Cette approche utilise le respect mutuel et la force normative de la raison comme fondation, afin de justifier l’application de principes éthiques. Nous avons ainsi développé quatre principes pour la distribution juste de la signature savante en recherche: le mérite, la juste reconnaissance, la transparence et la collégialité. Enfin, nous proposons un processus qui intègre une taxonomie basée sur la contribution, afin de délimiter les rôles de chacun dans le projet de recherche. Les contributions peuvent alors être mieux comparées et évaluées pour déterminer l’ordre de la signature savante dans les équipes de recherche multidisciplinaire en science de la santé.

Les pratiques culturelles des excisions et des infibulations à Bamako au Mali : la contribution de la dignité humaine au respect de l’intégrité physique des femmes

Une des questions les plus débattues dans le domaine de l’éthique en ce XXIème siècle entre l’Afrique et le monde occidental concerne le respect de l’intégrité physique des femmes. Parmi les actions humaines qui touchent le plus l’intégrité corporelle, les excisions et les infibulations sont les plus dénoncées en Afrique. Longtemps considérées comme des rites d’initiation pubertaire des filles, ces pratiques sont maintenant considérées comme néfastes à la santé, et communément désignées par la communauté internationale de « mutilations sexuelles féminines ». Au cours des dernières décennies, ces pratiques ont été progressivement interdites légalement tant dans la plupart des pays d’Afrique que dans les pays occidentaux. Le Comité Inter-Africain (CIAF) contre les mutilations sexuelles demande la « tolérance zéro » par rapport à ces pratiques. La communauté internationale les combat avec des armes juridiques, en se référant aux conséquences médicales et aux droits de l’homme. Notre thèse est née d’une interrogation sur les raisons pour lesquelles ces rites se poursuivent encore en Afrique et plus spécialement au Mali, alors que dans les pays occidentaux, on élève fortement la voix pour les dénoncer comme sévices infligés aux femmes. Sur le plan international, on hésite à imposer des valeurs universelles à un phénomène perçu dans une large mesure comme une tradition conforme aux normes sociales des communautés qui les maintiennent. Afin de mieux cerner le sujet, notre questionnement a été le suivant : « Comment les pratiques culturelles des excisions et des infibulations, dans la ville de Bamako au Mali, interpellent-elles l’éthique : en quoi l’analyse de ces rites constitue-t-elle un domaine légitime d’application des principes de la bioéthique ? » Notre réflexion part du postulat que la dignité humaine est une norme à l’aune de laquelle se mesurent les défis éthiques liés à ces rites. Un proverbe Bambara dit ceci : « Une seule main ne lave pas proprement un éléphant ». La logique de cette sagesse met en évidence qu’une seule approche disciplinaire ne saurait faire ressortir les enjeux éthiques de ces pratiques. Notre analyse bioéthique se veut une démarche interdisciplinaire, qui permet d’articuler les approches philosophiques, anthropologiques, sociologiques et biomédicales de ces pratiques. Le premier chapitre, à travers la revue des écrits, présente la problématique de ces rites. Le deuxième chapitre présente le cadre théorique basé sur la notion de dignité humaine et délimite « ses contours, ses sources, ses formes et ses conséquences » afin de la rendre plus efficace et opérationnelle comme moyen de protection de l’être humain. Le troisième chapitre présente la méthodologie de la recherche basée sur la méthode qualitative et l’induction analytique et décrit le contexte de l’étude. Le quatrième chapitre présente les résultats de la recherche qui font ressortir que ces pratiques se résument essentiellement au contrôle du désir sexuel féminin. Ces pratiques sont par ailleurs déritualisées, touchent de plus en plus des enfants, comportent des risques et des conséquences sur la santé avec des coûts humains et financiers pour la société. Le cinquième chapitre analyse ces pratiques avec les principes éthiques qui démontrent qu’elles constituent un problème de santé publique malgré leur caractère culturel. Enfin, le sixième chapitre présente la portée et la limite de la thèse. Celle-ci montre qu’il est possible de mener un débat sur les excisions et les infibulations à travers une éthique de discussion. Elle offre un moyen pour y parvenir avec une vision de la notion de dignité humaine comme une « valeur éthique universelle » susceptible d’être utilisée dans toutes les actions impliquant l’être humain et dans tous les contextes socio-culturels. Notre démarche élargit ainsi le champ d’application des principes bioéthiques à des pratiques non-médicales. Par cette thèse, nous souhaitons contribuer à enrichir la réflexion éthique sur les excisions et les infibulations et inspirer les politiques de santé publique dans le respect des diversités culturelles. Nous espérons pouvoir inspirer aussi d’autres recherches en vue de rapprocher la bioéthique des pratiques culturelles traditionnelles afin de trouver des compromis raisonnables qui pourraient renforcer le rôle de protection de la dignité humaine.

Art + Bioéthique : quand la recherche en bioéthique quitte les murs de l’université

Éditoral / Editorial

À la recherche de marqueurs protéiques de la prééclampsie

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

Analyse du concept d'addiction dans l'étude des phénomènes sectaires : comment passer d'une recherche de signification à une logique du signifiant?

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

Recherche de motifs structuraux dans les complexes acides ribonucléiques/protéines

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

Expansion de requête dans la recherche d'information : comparaison des ressources et des méthodes

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