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.

AURA : a hybrid approach to identify framework evolution

Les cadriciels et les bibliothèques sont indispensables aux systèmes logiciels d'aujourd'hui. Quand ils évoluent, il est souvent fastidieux et coûteux pour les développeurs de faire la mise à jour de leur code. Par conséquent, des approches ont été proposées pour aider les développeurs à migrer leur code. Généralement, ces approches ne peuvent identifier automatiquement les règles de modification une-remplacée-par-plusieurs méthodes et plusieurs-remplacées-par-une méthode. De plus, elles font souvent un compromis entre rappel et précision dans leur résultats en utilisant un ou plusieurs seuils expérimentaux. Nous présentons AURA (AUtomatic change Rule Assistant), une nouvelle approche hybride qui combine call dependency analysis et text similarity analysis pour surmonter ces limitations. Nous avons implanté AURA en Java et comparé ses résultats sur cinq cadriciels avec trois approches précédentes par Dagenais et Robillard, M. Kim et al., et Schäfer et al. Les résultats de cette comparaison montrent que, en moyenne, le rappel de AURA est 53,07% plus que celui des autre approches avec une précision similaire (0,10% en moins).

Le rôle de la rhétorique dans le projet en design : une exploration du concept d’argumentation de Perelman et Olbrechts-Tyteca

Les projets interdisciplinaires constituent rarement le terrain des études 
sur le processus de conception en design. Les théories générales du design, en tentant de définir ce qui est commun à toutes les disciplines du design, ont davantage étudié les cas typiques que les cas atypiques. Or, nous croyons qu’il existe dans les projets interdisciplinaires une négociation argumentative et une ouverture vers l’autre, propice à l’analyse du processus de conception en design. Pour réaliser l’étude de ce processus, la stratégie empruntée a été la «recherche-projet» qui propose une participation active sur le terrain. 
À l’intérieur de cette stratégie méthodologique, nous avons réalisé l’étude de cas d’un projet hybride, une signalétique identitaire destinée à marquer les écocentres montréalais et orienter leurs usagers. Comme plusieurs autres pratiques du design, la complexité des projets interdisciplinaires demande l’apport de plusieurs acteurs dans le processus. 
Ces personnes conçoivent le projet à travers des représentations visuelles et des échanges verbaux, nous avons choisi de faire porter notre étude principalement sur le second. Pour ce faire, nous avons choisi comme cadre théorique le Traité de l’argumentation de Chaïm Perelman et Lucie Olbrechts-Tyteca en nous intéressant plus spécifiquement aux concepts d’«accord» et d’«auditoire». Parce que le véhicule de l’action en design est la notion de «projet», l’Anthropologie du projet de Jean-Pierre Boutinet sera notre guide à travers cette conduite. L’objet de recherche de ce mémoire sera donc le processus de conception en design qui sera étudié à travers le regard de l’argumentation. L’argumentation s'est révélée la clé du problème que posent les jugements de valeur, commune à toutes les disciplines du design. Qu’est-ce qu’un «bon» projet réalisé? Est-il possible de répondre à cette question, sans tomber dans un cadre argumentatif, sans devoir révéler les arguments qui nous permettent de croire vraisemblable une telle proposition? C’est en mettant en lien la théorie du projet en design et la théorie de l’argumentation que nous avons éclairé la pratique du designer, sa relation à ses collègues et ultimement avec lui-même. L’argumentation s’est avérée un outil permettant la construction de la réalité dans le projet interdisciplinaire.

Between play and design : the emergence of hybrid-identity in single-player videogames

Pour respecter les droits auteur, la version electronique de cette thèse a été dépouillée de ses documents visuels et audio-visuels. La version intégrale de la thèse a été déposée au Service de la gestion des documents et des archives de l'Université de Montréal.

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.

Alliance Politics in Hybrid Regimes : Political Stability and Instability since World War II

Cette thèse étudie la stabilité et l’instabilité politique des régimes hybrides. Elle pose la question suivante : dans quelles conditions l’autorité des élites au pouvoir est-elle reconnue ou contestée? Notre réponse s’articule en lien avec le caractère inclusif ou exclusif de la coalition dirigeante : c’est-à-dire, l’alliance stratégique des élites dirigeantes avec les groupes sociaux dominants. L’inclusion de ces derniers favorise le consentement et la stabilité; leur exclusion entraîne l’affrontement et l’instabilité politique. Sa composition dépend (i) du degré de violence organisée extra-légale et (ii) du degré de pénétration de l’État sur le territoire et dans l’économie. La première variable permet d’identifier quel groupe social au sein de l’État (militaires) ou du régime (partis d’opposition) est dominant et influence les formes de communication politique avec les élites dirigeantes. La deuxième variable permet d’identifier quel groupe social au sein de l’État (fonctionnaires) ou de la société (chefs locaux) est dominant et oriente les rapports entre les régions et le pouvoir central. L’apport de la recherche est d’approfondir notre compréhension des institutions politiques dans les régimes hybrides en mettant l’accent sur l’identité des groupes sociaux dominants dans un contexte donné. La thèse propose un modèle simple, flexible et original permettant d’appréhender des relations causales autrement contre-intuitives. En ce sens, la stabilité politique est également possible dans un pays où l’État est faible et/ou aux prises avec des mouvements de rébellion; et l’instabilité dans un contexte inverse. Tout dépend de la composition de la coalition dirigeante. Afin d’illustrer les liens logiques formulés et d’exposer les nuances de notre théorie, nous employons une analyse historique comparative de la coalition dirigeante en Malaisie (1957-2010), en Indonésie (1945-1998), au Sénégal (1960-2010) et au Paraguay (1945-2008). La principale conclusion est que les deux variables sont incontournables. L’une sans l’autre offre nécessairement une explication incomplète des alliances politiques qui forgent les conditions de stabilité et d'instabilité dans les régimes hybrides.

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

Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire.

Evaluation of multiple reaction monitoring cubed for the analysis of tachykinin related peptides in rat spinal cord using a hybrid triple quadrupole–linear ion trap mass spectrometer

Targeted peptide methods generally use HPLC-MS/MRM approaches. Although dependent on the instrumental resolution, interferences may occur while performing analysis of complex biological matrices. HPLC-MS/MRM3 is a technique, which provides a significantly better selectivity, compared with HPLC-MS/MRM assay. HPLC-MS/MRM3 allows the detection and quantitation by enriching standard MRM with secondary product ions that are generated within the linear ion trap. Substance P (SP) and neurokinin A (NKA) are tachykinin peptides playing a central role in pain transmission. The objective of this study was to verify whether HPLC-HPLCMS/ MRM3 could provide significant advantages over a more traditional HPLC-MS/MRM assay for the quantification of SP and NKA in rat spinal cord. The results suggest that reconstructed MRM3 chromatograms display significant improvements with the nearly complete elimination of interfering peaks but the sensitivity (i.e. signal-to-noise ratio) was severely reduced. The precision (%CV) observed was between 3.5% - 24.1% using HPLC-MS/MRM and in the range of 4.3% - 13.1% with HPLC-MS/MRM3, for SP and NKA. The observed accuracy was within 10% of the theoretical concentrations tested. HPLC-MS/MRM3 may improve the assay sensitivity to detect difference between samples by reducing significantly the potential of interferences and therefore reduce instrumental errors.

A heuristic algorithm for the Capacitated Vehicle Routing Problem with Synchronized Pick-ups and Drop-offs : a case study for medications delivery and supervision in DR Congo

Dans des contextes de post-urgence tels que le vit la partie occidentale de la République Démocratique du Congo (RDC), l’un des défis cruciaux auxquels font face les hôpitaux ruraux est de maintenir un niveau de médicaments essentiels dans la pharmacie. Sans ces médicaments pour traiter les maladies graves, l’impact sur la santé de la population est significatif. Les hôpitaux encourent également des pertes financières dues à la péremption lorsque trop de médicaments sont commandés. De plus, les coûts du transport des médicaments ainsi que du superviseur sont très élevés pour les hôpitaux isolés ; les coûts du transport peuvent à eux seuls dépasser ceux des médicaments. En utilisant la province du Bandundu, RDC pour une étude de cas, notre recherche tente de déterminer la faisabilité (en termes et de la complexité du problème et des économies potentielles) d’un problème de routage synchronisé pour la livraison de médicaments et pour les visites de supervision. Nous proposons une formulation du problème de tournées de véhicules avec capacité limitée qui gère plusieurs exigences nouvelles, soit la synchronisation des activités, la préséance et deux fréquences d’activités. Nous mettons en œuvre une heuristique « cluster first, route second » avec une base de données géospatiales qui permet de résoudre le problème. Nous présentons également un outil Internet qui permet de visualiser les solutions sur des cartes. Les résultats préliminaires de notre étude suggèrent qu’une solution synchronisée pourrait offrir la possibilité aux hôpitaux ruraux d’augmenter l’accessibilité des services médicaux aux populations rurales avec une augmentation modique du coût de transport actuel.