Heuristic solution methods for multi-attribute vehicle routing problems

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques.

Quantitative functional neuroimaging of cerebral physiology in healthy aging

Les études d’imagerie par résonance magnétique fonctionnelle (IRMf) ont pour prémisse générale l’idée que le signal BOLD peut être utilisé comme un succédané direct de l’activation neurale. Les études portant sur le vieillissement cognitif souvent comparent directement l’amplitude et l’étendue du signal BOLD entre des groupes de personnes jeunes et âgés. Ces études comportent donc un a priori additionnel selon lequel la relation entre l’activité neurale et la réponse hémodynamique à laquelle cette activité donne lieu restent inchangée par le vieillissement. Cependant, le signal BOLD provient d’une combinaison ambiguë de changements de métabolisme oxydatif, de flux et de volume sanguin. De plus, certaines études ont démontré que plusieurs des facteurs influençant les propriétés du signal BOLD subissent des changements lors du vieillissement. L’acquisition d’information physiologiquement spécifique comme le flux sanguin cérébral et le métabolisme oxydatif permettrait de mieux comprendre les changements qui sous-tendent le contraste BOLD, ainsi que les altérations physiologiques et cognitives propres au vieillissement. Le travail présenté ici démontre l’application de nouvelles techniques permettant de mesurer le métabolisme oxydatif au repos, ainsi que pendant l’exécution d’une tâche. Ces techniques représentent des extensions de méthodes d’IRMf calibrée existantes. La première méthode présentée est une généralisation des modèles existants pour l’estimation du métabolisme oxydatif évoqué par une tâche, permettant de prendre en compte tant des changements arbitraires en flux sanguin que des changements en concentrations sanguine d’O2. Des améliorations en terme de robustesse et de précisions sont démontrées dans la matière grise et le cortex visuel lorsque cette méthode est combinée à une manipulation respiratoire incluant une composante d’hypercapnie et d’hyperoxie. Le seconde technique présentée ici est une extension de la première et utilise une combinaison de manipulations respiratoires incluant l’hypercapnie, l’hyperoxie et l’administration simultanée des deux afin d’obtenir des valeurs expérimentales de la fraction d’extraction d’oxygène et du métabolisme oxydatif au repos. Dans la deuxième partie de cette thèse, les changements vasculaires et métaboliques liés à l’âge sont explorés dans un groupe de jeunes et aînés, grâce au cadre conceptuel de l’IRMf calibrée, combiné à une manipulation respiratoire d’hypercapnie et une tâche modifiée de Stroop. Des changements de flux sanguin au repos, de réactivité vasculaire au CO2 et de paramètre de calibration M ont été identifiés chez les aînés. Les biais affectant les mesures de signal BOLD obtenues chez les participants âgés découlant de ces changements physiologiques sont de plus discutés. Finalement, la relation entre ces changements cérébraux et la performance dans la tâche de Stroop, la santé vasculaire centrale et la condition cardiovasculaire est explorée. Les résultats présentés ici sont en accord avec l’hypothèse selon laquelle une meilleure condition cardiovasculaire est associée à une meilleure fonction vasculaire centrale, contribuant ainsi à l’amélioration de la santé vasculaire cérébrale et cognitive.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Conflict of Interest in University Technology Transfer

Étude de cas / Case study

Méthodes numériques pour la capture et la résolution des discontinuités dans les solutions des systèmes hyperboliques

Réalisé en majeure partie sous la tutelle de feu le Professeur Paul Arminjon. Après sa disparition, le Docteur Aziz Madrane a pris la relève de la direction de mes travaux.

La notion d'inventeur dans le contexte universitaire

Dans le domaine des brevets d'invention, la notion d'inventeur pose des difficultés particulières dans le contexte universitaire. L'une d'elles concerne l'identification de l'inventeur. La loi canadienne est très claire sur ce point: un brevet est accordé « à l'inventeur ». Cela peut être problématique quand on a affaire à une équipe de chercheurs composée de personnes qui n'ont pas le même statut: professeur régulier de l'Université, professeur chercheur payé par une subvention de recherche, chercheur qui s'est joint temporairement à l'équipe, étudiants gradués ou non, etc. Une autre problématique concerne la question de savoir si une Université peut prétendre qu'elle s'est fait céder les droits des brevetés, soit parce qu'ils ont le statut d'employé, ou par le libellé d'une clause dans une convention collective, ou par l'existence d'une politique adoptée sur ce sujet. Le présent texte cherche à faire connaître l'état du droit sur ces questions.

Libres propos sur la législation OAPI relative aux obtentions végétales

Les innovations en matière variétale et de biotechnologie végétale sont présentées comme un moyen efficace et approprié susceptible de favoriser l'amélioration de la production alimentaire et des conditions de travail et de vie des agriculteurs ainsi que celles des collectivités coutumières dans les pays membres de l'Organisation africaine de la propriété intellectuelle (OAPI). Sur le plan juridique, il se pose le problème de la protection juridique de ces innovations ou obtentions végétales. Le législateur OAPI de 1977 n'avait pas envisagé de protection pour les obtentions végétales. À la différence de certains États industrialisés qui organisaient un régime de protection sui generis ou par le système des brevets, il n'évoquait les variétés végétales et les procédés d'obtention des végétaux que pour les exclure du domaine brevetable. L'accord sur les aspects des droits de propriété intellectuelle qui touchent au commerce (ADPIC) de l'organisation mondiale du commerce (OMC) est venu modifier la donne en imposant que les obtentions végétales puissent être protégées par les brevets, par un système sui generis ou par une combinaison des deux moyens. Le législateur OAPI de 1999 a voulu intégrer ces nouvelles exigences internationales en révisant l'Accord de Bangui. Ce faisant, l'exclusion de la brevetabilité des variétés végétales a été maintenue. Il ne restait plus au législateur qu'une seule option, l'adoption d'un régime de protection sui generis. Son choix s'est matérialisé par l'adoption de l'annexe X de l'Accord de Bangui de 1999 consacrée à « la protection des obtentions végétales ». Cette annexe est calquée sur la version de 1991 de la Convention Internationale pour la protection des obtentions végétales, mise en place par les pays européens. Il s'agit là d'un choix discutable. En effet, l'annexe X introduit dans l'espace OAPI une législation désincarnée, parce que à la fois incomplète et inadaptée à l'environnement socio-économique des pays membres de l'OAPI.

Paradigm Shift in European Intellectual Property Law? From Microsoft to Linux

"L’auteure Lucie Guibault aborde la question des ""logiciels libres"" dans le cadre des droits d’auteurs et des brevets. Ces logiciels sont des programmes informatiques qui sont gratuitement distribués au public, dont la modification et la redistribution sont fortement encouragées, mais dont la vente ou la commercialisation est découragée ou même carrément prohibée. Ces caractéristiques particulières distinguent les logiciels libres des ""programmes propriétés"" traditionnels, qui se basent sur le principe que le créateur d’un programme en possède les droits de propriété et qu’il est le seul autorisé à le modifier ou le vendre, sous réserve de sa capacité à faire cession de ces droits. Les logiciels libres sont fondés sur une idéologie de coopération, qui promeut la propagation des idées et des connaissances et qui favorise ainsi la création de meilleurs logiciels. L’auteure présente les grandes caractéristiques des trois principales licences de logiciels libres, soit la ""General Public License"", la licence ""Berkeley Software Distribution"" et la ""Mozilla Public License"". Elle soutient que ces logiciels libres et les régimes normatifs qui les encadrent sont à l’origine d’un changement de paradigme au sein des régimes européens et hollandais de protection des droits d’auteurs et des brevets. La première partie de l’article analyse les régimes des droits d’auteur des trois licences de logiciels libres. L’auteure souligne que ces régimes ont été établis en se basant sur la prémisse qu’il n’y a pas de distinction significative entre les créateurs et les utilisateurs de logiciels libres. Les régimes normatifs reflètent cette situation en prévoyant un ensemble de droits et d’obligations pour les utilisateurs dans le cadre de l’utilisation, de la reproduction, de la modification et de la redistribution gratuite des logiciels libres. L’auteur explique comment ces régimes normatifs s’intègrent au sein de la législation européenne et hollandaise, entre autre au niveau du droit de propriété, du droit commercial, du droit des communications et du droit des obligations. L’auteur démontre que, de façon générale, ces régimes normatifs législatifs semblent s’être adéquatement adaptés aux nouvelles réalités posées par les règles de droits d’auteurs des logiciels libres. La seconde partie aborde la problématique du droit des brevets, tel que défini par la législation européenne et hollandaise. La plupart des utilisateurs et créateurs de logiciels libres s’opposent aux régimes de brevets traditionnels, qui limitent l’innovation et les possibilités de développement techniques. L’auteur décrit les différents régimes alternatifs de brevets offerts par les trois licences de logiciels libres. De plus, l’auteur présente l’encadrement légal pour ces nouveaux brevets, tel que défini par les législations européennes et hollandaises. Elle soutient que cet encadrement légal est inadéquat et qu’il n’est pas adapté aux besoins des utilisateurs de logiciels libres."

Prostaglandine E2 et mesures du flux mésentérique par Doppler à la suite d’un traitement du canal artériel à l’ibuprofène par voie intraveineuse et entérale chez les bébés prématurés

En dépit du nombre croissant d’études cliniques sur le canal artériel (CA), des failles méthodologiques entretiennent plusieurs incertitudes concernant l’efficacité et la sécurité des traitements chez les bébés nés prématurés. L’objectif de cette recherche était de comparer les concentrations de prostaglandine E2 (PGE2) et les mesures du flux mésentérique par échographie Doppler chez les enfants nés prématurément et ayant un canal artériel traité à l’ibuprofène par voie intraveineuse ou entérale, en utilisant la méthodologie randomisée contrôlée et à double insu. Dans notre étude pilote, 20 nouveau-nés prématurés de moins de 34 semaines ayant un CA symptomatique confirmé par échocardiographie, furent randomisés au traitement à l’ibuprofène par voie intraveineuse ou entérale. La voie d’administration fut maintenue à l’insu de l’équipe traitante, des cardiologues et des investigateurs. Des dosages des prostaglandines plasmatiques ont été mesurés avant le début du traitement ainsi que 3, 24 et 48 h après le début du traitement. Les mesures du flux mésentérique ont été effectuées avant le traitement à l’ibuprofène ainsi que 1 h et 3 h après le traitement. Nous avons démontré à partir de nos observations que les niveaux plasmatiques de prostaglandines E2 diminuent chez les patients ayant répondu au traitement à l’ibuprofène, indépendamment de la voie d’administration. Nous n’avons pas observé de changement dans l’évolution des dosages de PGE2 chez les patients qui n’ont pas répondu au traitement. Les paramètres mesurés par échographie Doppler au niveau de l’artère mésentérique supérieure n’étaient pas affectés par la voie d’administration du traitement à l’ibuprofène, intraveineuse ou entérale. La présente étude suggère ainsi que le traitement du CA par ibuprofène intraveineux ou entéral n’influe pas sur le flux sanguin mesuré par échographie Doppler. La baisse de la prostaglandine E2 coïncide avec la fermeture du CA, et son dosage pourrait jouer un rôle dans la gestion du traitement. Nous avons démontré la faisabilité d’une étude clinique randomisée à double insu dans le traitement du canal artériel; une méthodologie qui devrait désormait être employé dans la recherche clinique sur les traitements de la persistance du CA.

Facial artery musculomucosal flap for reconstruction of skull base defects

Facial Artery Musculomucosal Flap in Skull Base Reconstruction Xie L. MD, Lavigne F. MD, Rahal A. MD, Moubayed SP MD, Ayad T. MD Introduction: Failure in skull base defects reconstruction can have serious consequences such as meningitis and pneumocephalus. The nasoseptal flap is usually the first choice but alternatives are necessary when this flap is not available. The facial artery musculomucosal (FAMM) flap has proven to be successful in head and neck reconstruction but it has never been reported in skull base reconstruction. Objective: To show that the FAMM flap can reach some key areas of the skull base and be considered as a new alternative in skull base defects reconstruction. Methods: We conducted a cadaveric study with harvest of modified FAMM flaps, endoscopic skull base dissection and maxillectomies in 13 specimens. Measures were taken for each harvested FAMM flap. Results: The approximate mean area for reconstruction from the combination of the distal FAMM and the extension flaps is 15.90 cm2. The flaps successfully covered the simulated defects of the frontal sinus, the ethmoid areas, the planum sphenoidale, and the sella turcica. Conclusion: The FAMM flap can be considered as a new alternative in the reconstruction of skull base defects. Modifications add extra length to the traditional FAMM flap and can contribute to a tighter seal of the defect as opposed to the FAMM flap alone.

Meta-heuristic Solution Methods for Rich Vehicle Routing Problems

Le problème de tournées de véhicules (VRP), introduit par Dantzig and Ramser en 1959, est devenu l'un des problèmes les plus étudiés en recherche opérationnelle, et ce, en raison de son intérêt méthodologique et de ses retombées pratiques dans de nombreux domaines tels que le transport, la logistique, les télécommunications et la production. L'objectif général du VRP est d'optimiser l'utilisation des ressources de transport afin de répondre aux besoins des clients tout en respectant les contraintes découlant des exigences du contexte d’application. Les applications réelles du VRP doivent tenir compte d’une grande variété de contraintes et plus ces contraintes sont nombreuse, plus le problème est difficile à résoudre. Les VRPs qui tiennent compte de l’ensemble de ces contraintes rencontrées en pratique et qui se rapprochent des applications réelles forment la classe des problèmes ‘riches’ de tournées de véhicules. Résoudre ces problèmes de manière efficiente pose des défis considérables pour la communauté de chercheurs qui se penchent sur les VRPs. Cette thèse, composée de deux parties, explore certaines extensions du VRP vers ces problèmes. La première partie de cette thèse porte sur le VRP périodique avec des contraintes de fenêtres de temps (PVRPTW). Celui-ci est une extension du VRP classique avec fenêtres de temps (VRPTW) puisqu’il considère un horizon de planification de plusieurs jours pendant lesquels les clients n'ont généralement pas besoin d’être desservi à tous les jours, mais plutôt peuvent être visités selon un certain nombre de combinaisons possibles de jours de livraison. Cette généralisation étend l'éventail d'applications de ce problème à diverses activités de distributions commerciales, telle la collecte des déchets, le balayage des rues, la distribution de produits alimentaires, la livraison du courrier, etc. La principale contribution scientifique de la première partie de cette thèse est le développement d'une méta-heuristique hybride dans la quelle un ensemble de procédures de recherche locales et de méta-heuristiques basées sur les principes de voisinages coopèrent avec un algorithme génétique afin d’améliorer la qualité des solutions et de promouvoir la diversité de la population. Les résultats obtenus montrent que la méthode proposée est très performante et donne de nouvelles meilleures solutions pour certains grands exemplaires du problème. La deuxième partie de cette étude a pour but de présenter, modéliser et résoudre deux problèmes riches de tournées de véhicules, qui sont des extensions du VRPTW en ce sens qu'ils incluent des demandes dépendantes du temps de ramassage et de livraison avec des restrictions au niveau de la synchronization temporelle. Ces problèmes sont connus respectivement sous le nom de Time-dependent Multi-zone Multi-Trip Vehicle Routing Problem with Time Windows (TMZT-VRPTW) et de Multi-zone Mult-Trip Pickup and Delivery Problem with Time Windows and Synchronization (MZT-PDTWS). Ces deux problèmes proviennent de la planification des opérations de systèmes logistiques urbains à deux niveaux. La difficulté de ces problèmes réside dans la manipulation de deux ensembles entrelacés de décisions: la composante des tournées de véhicules qui vise à déterminer les séquences de clients visités par chaque véhicule, et la composante de planification qui vise à faciliter l'arrivée des véhicules selon des restrictions au niveau de la synchronisation temporelle. Auparavant, ces questions ont été abordées séparément. La combinaison de ces types de décisions dans une seule formulation mathématique et dans une même méthode de résolution devrait donc donner de meilleurs résultats que de considérer ces décisions séparément. Dans cette étude, nous proposons des solutions heuristiques qui tiennent compte de ces deux types de décisions simultanément, et ce, d'une manière complète et efficace. Les résultats de tests expérimentaux confirment la performance de la méthode proposée lorsqu’on la compare aux autres méthodes présentées dans la littérature. En effet, la méthode développée propose des solutions nécessitant moins de véhicules et engendrant de moindres frais de déplacement pour effectuer efficacement la même quantité de travail. Dans le contexte des systèmes logistiques urbains, nos résultats impliquent une réduction de la présence de véhicules dans les rues de la ville et, par conséquent, de leur impact négatif sur la congestion et sur l’environnement.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Problème inverse de Galois : critère de rigidité

Dans ce mémoire, on étudie les extensions galoisiennes finies de C(x). On y démontre le théorème d'existence de Riemann. Les notions de rigidité faible, rigidité et rationalité y sont développées. On y obtient le critère de rigidité qui permet de réaliser certains groupes comme groupes de Galois sur Q. Plusieurs exemples de types de ramification sont construis.

Analyse anthropologique des politiques de brevetage génétique : le cas du BRCA 1/2 au Québec

Le diagnostic de prédisposition génétique du cancer du sein et de l’ovaire est détenu par la firme de biotechnologie Myriad Genetics depuis 1996, sous la forme d’un brevet, qui lui octroie une licence d’exploitation internationale, infirmant le droit d’analyse moléculaire aux autres laboratoires. Ce monopole, lui permet de statuer sur un prix excessivement plus élevé qu’en milieu public et d’astreindre en justice, les laboratoires contrevenants. Depuis 2001, le Québec est la seule province qui se soumet (en partie) au brevet, en faisant appel à la compagnie pour le séquençage complet. À travers cette recherche, j’analyse les politiques de brevetage génétique, dans sa construction juridique de la propriété intellectuelle et dans les significations culturelles des biotechnologies. Je m’appuie sur un cadre analytique des théories de propriété et sur la recherche en biomédical. Je procède également à l’analyse du discours des médecins et conseillers généticiens au Québec, à travers des entrevues conduites dans des centres hospitaliers de la région de Montréal et de Sherbrooke. Cette étude qualitative identifie comment les conseillers et médecins généticiens conçoivent le rôle des brevets dans les dépistages et diagnostics du cancer et comment les brevets génétiques expriment une culture médicale. Je cherche à déterminer comment sont perçus par des professionnels de santé les brevets génétiques en analysant et en comparant les variations entre limites idéologiques et limites pratiques.

Sur les prolongements de sous-copules

L’objet du travail est d’étudier les prolongements de sous-copules. Un cas important de l’utilisation de tels prolongements est l’estimation non paramétrique d’une copule par le lissage d’une sous-copule (la copule empirique). Lorsque l’estimateur obtenu est une copule, cet estimateur est un prolongement de la souscopule. La thèse présente au chapitre 2 la construction et la convergence uniforme d’un estimateur bona fide d’une copule ou d’une densité de copule. Cet estimateur est un prolongement de type copule empirique basé sur le lissage par le produit tensoriel de fonctions de répartition splines. Le chapitre 3 donne la caractérisation de l’ensemble des prolongements possibles d’une sous-copule. Ce sujet a été traité par le passé; mais les constructions proposées ne s’appliquent pas à la dépendance dans des espaces très généraux. Le chapitre 4 s’attèle à résoudre le problème suivant posé par [Carley, 2002]. Il s’agit de trouver la borne supérieure des prolongements en dimension 3 d’une sous-copule de domaine fini.