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.

Distributed conditional computation

L'objectif de cette thèse est de présenter différentes applications du programme de recherche de calcul conditionnel distribué. On espère que ces applications, ainsi que la théorie présentée ici, mènera à une solution générale du problème d'intelligence artificielle, en particulier en ce qui a trait à la nécessité d'efficience. La vision du calcul conditionnel distribué consiste à accélérer l'évaluation et l'entraînement de modèles profonds, ce qui est très différent de l'objectif usuel d'améliorer sa capacité de généralisation et d'optimisation. Le travail présenté ici a des liens étroits avec les modèles de type mélange d'experts. Dans le chapitre 2, nous présentons un nouvel algorithme d'apprentissage profond qui utilise une forme simple d'apprentissage par renforcement sur un modèle d'arbre de décisions à base de réseau de neurones. Nous démontrons la nécessité d'une contrainte d'équilibre pour maintenir la distribution d'exemples aux experts uniforme et empêcher les monopoles. Pour rendre le calcul efficient, l'entrainement et l'évaluation sont contraints à être éparse en utilisant un routeur échantillonnant des experts d'une distribution multinomiale étant donné un exemple. Dans le chapitre 3, nous présentons un nouveau modèle profond constitué d'une représentation éparse divisée en segments d'experts. Un modèle de langue à base de réseau de neurones est construit à partir des transformations éparses entre ces segments. L'opération éparse par bloc est implémentée pour utilisation sur des cartes graphiques. Sa vitesse est comparée à deux opérations denses du même calibre pour démontrer le gain réel de calcul qui peut être obtenu. Un modèle profond utilisant des opérations éparses contrôlées par un routeur distinct des experts est entraîné sur un ensemble de données d'un milliard de mots. Un nouvel algorithme de partitionnement de données est appliqué sur un ensemble de mots pour hiérarchiser la couche de sortie d'un modèle de langage, la rendant ainsi beaucoup plus efficiente. Le travail présenté dans cette thèse est au centre de la vision de calcul conditionnel distribué émis par Yoshua Bengio. Elle tente d'appliquer la recherche dans le domaine des mélanges d'experts aux modèles profonds pour améliorer leur vitesse ainsi que leur capacité d'optimisation. Nous croyons que la théorie et les expériences de cette thèse sont une étape importante sur la voie du calcul conditionnel distribué car elle cadre bien le problème, surtout en ce qui concerne la compétitivité des systèmes d'experts.

La recherche de naines brunes et étoiles de faible masse dans les associations cinématiques jeunes du voisinage solaire

L’objectif principal de cette thèse est d’identifier les étoiles de faible masse et naines brunes membres d’associations cinématiques jeunes du voisinage solaire. Ces associations sont typiquement âgées de moins de 200 millions d’années et regroupent chacune un ensemble d’étoiles s’étant formées au même moment et dans un même environnement. La majorité de leurs membres d'environ plus de 0.3 fois la masse du Soleil sont déjà connus, cependant les membres moins massifs (et moins brillants) nous échappent encore. Leur identification permettra de lever le voile sur plusieurs questions fondamentales en astrophysique. En particulier, le fait de cibler des objets jeunes, encore chauds et lumineux par leur formation récente, permettra d’atteindre un régime de masses encore peu exploré, jusqu'à seulement quelques fois la masse de Jupiter. Elles nous permettront entre autres de contraindre la fonction de masse initiale et d'explorer la connection entre naines brunes et exoplanètes, étant donné que les moins massives des naines brunes jeunes auront des propriétés physiques très semblables aux exoplanètes géantes gazeuses. Pour mener à bien ce projet, nous avons adapté l'outil statistique BANYAN I pour qu'il soit applicable aux objets de très faibles masses en plus de lui apporter plusieurs améliorations. Nous avons entre autres inclus l'utilisation de deux diagrammes couleur-magnitude permettant de différencier les étoiles de faible masse et naines brunes jeunes à celles plus vieilles, ajouté l'utilisation de probabilités a priori pour rendre les résultats plus réalistes, adapté les modèles spatiaux et cinématiques des associations jeunes en utilisant des ellipsoïdes gaussiennes tridimensionnelles dont l'alignement des axes est libre, effectué une analyse Monte Carlo pour caractériser le taux de faux-positifs et faux-négatifs, puis revu la structure du code informatique pour le rendre plus efficace. Dans un premier temps, nous avons utilisé ce nouvel algorithme, BANYAN II, pour identifier 25 nouvelles candidates membres d'associations jeunes parmi un échantillon de 158 étoiles de faible masse (de types spectraux > M4) et naines brunes jeunes déjà connues. Nous avons ensuite effectué la corrélation croisée de deux catalogues couvrant tout le ciel en lumière proche-infrarouge et contenant ~ 500 millions d’objets célestes pour identifier environ 100 000 candidates naines brunes et étoiles de faible masse du voisinage solaire. À l'aide de l'outil BANYAN II, nous avons alors identifié quelques centaines d'objets appartenant fort probablement à une association jeune parmi cet échantillon et effectué un suivi spectroscopique en lumière proche-infrarouge pour les caractériser. Les travaux présentés ici ont mené à l'identification de 79 candidates naines brunes jeunes ainsi que 150 candidates étoiles de faible masse jeunes, puis un suivi spectroscopique nous a permis de confirmer le jeune âge de 49 de ces naines brunes et 62 de ces étoiles de faible masse. Nous avons ainsi approximativement doublé le nombre de naines brunes jeunes connues, ce qui a ouvert la porte à une caractérisation statistique de leur population. Ces nouvelles naines brunes jeunes représentent un laboratoire idéal pour mieux comprendre l'atmosphère des exoplanètes géantes gazeuses. Nous avons identifié les premiers signes d’une remontée dans la fonction de masse initiale des naines brunes aux très faibles masses dans l'association jeune Tucana-Horologium, ce qui pourrait indiquer que l’éjection d’exoplanètes joue un rôle important dans la composition de leur population. Les résultats du suivi spectroscopique nous ont permis de construire une séquence empirique complète pour les types spectraux M5-L5 à l'âge du champ, à faible (β) et très faible (γ) gravité de surface. Nous avons effectué une comparaison de ces données aux modèles d'évolution et d'atmosphère, puis nous avons construit un ensemble de séquences empiriques de couleur-magnitude et types spectraux-magnitude pour les naines brunes jeunes. Finalement, nous avons découvert deux nouvelles exoplanètes par un suivi en imagerie directe des étoiles jeunes de faible masse identifiées dans ce projet. La future mission GAIA et le suivi spectroscopique complet des candidates présentées dans cette thèse permettront de confirmer leur appartenance aux associations jeunes et de contraindre la fonction de masse initiale dans le régime sous-stellaire.

On Space-Time Trade-Off for Montgomery Multipliers over Finite Fields

La multiplication dans le corps de Galois à 2^m éléments (i.e. GF(2^m)) est une opérations très importante pour les applications de la théorie des correcteurs et de la cryptographie. Dans ce mémoire, nous nous intéressons aux réalisations parallèles de multiplicateurs dans GF(2^m) lorsque ce dernier est généré par des trinômes irréductibles. Notre point de départ est le multiplicateur de Montgomery qui calcule A(x)B(x)x^(-u) efficacement, étant donné A(x), B(x) in GF(2^m) pour u choisi judicieusement. Nous étudions ensuite l'algorithme diviser pour régner PCHS qui permet de partitionner les multiplicandes d'un produit dans GF(2^m) lorsque m est impair. Nous l'appliquons pour la partitionnement de A(x) et de B(x) dans la multiplication de Montgomery A(x)B(x)x^(-u) pour GF(2^m) même si m est pair. Basé sur cette nouvelle approche, nous construisons un multiplicateur dans GF(2^m) généré par des trinôme irréductibles. Une nouvelle astuce de réutilisation des résultats intermédiaires nous permet d'éliminer plusieurs portes XOR redondantes. Les complexités de temps (i.e. le délais) et d'espace (i.e. le nombre de portes logiques) du nouveau multiplicateur sont ensuite analysées: 1. Le nouveau multiplicateur demande environ 25% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito lorsque GF(2^m) est généré par des trinômes irréductible et m est suffisamment grand. Le nombre de portes du nouveau multiplicateur est presque identique à celui du multiplicateur de Karatsuba proposé par Elia. 2. Le délai de calcul du nouveau multiplicateur excède celui des meilleurs multiplicateurs d'au plus deux évaluations de portes XOR. 3. Nous determinons le délai et le nombre de portes logiques du nouveau multiplicateur sur les deux corps de Galois recommandés par le National Institute of Standards and Technology (NIST). Nous montrons que notre multiplicateurs contient 15% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito au coût d'un délai d'au plus une porte XOR supplémentaire. De plus, notre multiplicateur a un délai d'une porte XOR moindre que celui du multiplicateur d'Elia au coût d'une augmentation de moins de 1% du nombre total de portes logiques.

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.

Methylene Blue Doped Polymers: efficient Media for Optical Recording

Polymer materials find application in optical storage technology, namely in the development of high information density and fast access type memories. A new polymer blend of methylene blue sensitized polyvinyl alcohol (PVA) and polyacrylic acid (PAA) in methanol is prepared and characterized and its comparison with methylene blue sensitized PVA in methanol and complexed methylene blue sensitized polyvinyl chloride (CMBPVC) is presented. The optical absorption spectra of the thin films of these polymers showed a strong and broad absorption region at 670-650 nm, matching the wavelength of the laser used. A very slow recovery of the dye on irradiation was observed when a 7:3 blend of polyvinyl alcohol/polyacrylic acid at a pHof 3.8 and a sensitizer concentration of 4.67 10 5 g/ml were used. A diffraction efficiency of up to 20% was observed for the MBPVA/alcohol system and an energetic sensitivity of 2000 mJ/cm2 was obtained in the photosensitive films with a spatial frequency of 588 lines/mm.

Methylene Blue Doped Polymers:Efficient Media for Optical Recording

Polymer materials find application in optical storage technology, namely in the development of high information density and fast access type memories. A new polymer blend of methylene blue sensitized polyvinyl alcohol (PVA) and polyacrylic acid (PAA) in methanol is prepared and characterized and its comparison with methylene blue sensitized PVA in methanol and complexed methylene blue sensitized polyvinyl chloride (CMBPVC) is presented. The optical absorption spectra of the thin films of these polymers showed a strong and broad absorption region at 670-650 nm, matching the wavelength of the laser used. A very slow recovery of the dye on irradiation was observed when a 7:3 blend of polyvinyl alcohol/polyacrylic acid at a pHof 3.8 and a sensitizer concentration of 4.67 10 5 g/ml were used. A diffraction efficiency of up to 20% was observed for the MBPVA/alcohol system and an energetic sensitivity of 2000 mJ/cm2 was obtained in the photosensitive films with a spatial frequency of 588 lines/mm.

Tribasic Lead Sulphate as Efficient Curing Agent for Polychloroprene

Tribasic lead sulphate is tried as a practical curing agent for polychloroprene. The cure characteristics of the compounds as well as the technical properties of the vulcanizates show that it can act as a potential curative.

Array pattern nulling by element position perturbations using a genetic algorithm

A genetic algorithm has been used for null steering in phased and adaptive arrays . It has been shown that it is possible to steer the array null s precisely to the required interference directions and to achieve any prescribed null depths . A comparison with the results obtained from the analytic solution shows the advantages of using the genetic algorithm for null steering in linear array patterns

Ruthenium complexes of Schiff base ligands as efficient catalysts for catechol–hydrogen peroxide reaction

Zeolite Y-encapsulated ruthenium(III) complexes of Schiff bases derived from 3-hydroxyquinoxaline-2-carboxaldehyde and 1,2- phenylenediamine, 2-aminophenol, or 2-aminobenzimidazole (RuYqpd, RuYqap and RuYqab, respectively) and the Schiff bases derived from salicylaldehyde and 1,2-phenylenediamine, 2-aminophenol, or 2-aminobenzimidazole (RuYsalpd, RuYsalap and RuYsalab, respectively) have been prepared and characterized. These complexes, except RuYqpd, catalyze catechol oxidation by H2O2 selectively to 1,2,4-trihydroxybenzene. RuYqpd is inactive. A comparative study of the initial rates and percentage conversion of the reaction was done in all cases. Turn over frequency of the catalysts was also calculated. The catalytic activity of the complexes is in the order RuYqap > RuYqab for quinoxaline-based complexes and RuYsalap > RuYsalpd > RuYsalab for salicylidene-based complexes. The reaction is believed to proceed through the formation of a Ru(V) species.

First Example of Organocatalysis by Polystyrene-Supported PAMAM Dendrimers: Highly Efficient and Reusable Catalyst for Knoevenagel Condensations

This paper describes the first use of polystyrene-supported poly(amidoamine) (PAMAM) dendrimers as heterogeneous basic organocatalysts for carbon–carbon bond formation. Polystyrene-supported PAMAM dendrimers of first, second and third generations have been used as reusable base catalysts in Knoevenagel condensations of carbonyl compounds with active methylene compounds. The reactions proceed in short periods of time and with 100% selectivity. This novel catalyst eliminates the use of aromatic and halogenated solvents, as well as complex purification processes. The catalysts can be recycled ten times.

A Cryptosystem Using the Concepts of Algebraic Geometric Code

Cryptosystem using linear codes was developed in 1978 by Mc-Eliece. Later in 1985 Niederreiter and others developed a modified version of cryptosystem using concepts of linear codes. But these systems were not used frequently because of its larger key size. In this study we were designing a cryptosystem using the concepts of algebraic geometric codes with smaller key size. Error detection and correction can be done efficiently by simple decoding methods using the cryptosystem developed. Approach: Algebraic geometric codes are codes, generated using curves. The cryptosystem use basic concepts of elliptic curves cryptography and generator matrix. Decrypted information takes the form of a repetition code. Due to this complexity of decoding procedure is reduced. Error detection and correction can be carried out efficiently by solving a simple system of linear equations, there by imposing the concepts of security along with error detection and correction. Results: Implementation of the algorithm is done on MATLAB and comparative analysis is also done on various parameters of the system. Attacks are common to all cryptosystems. But by securely choosing curve, field and representation of elements in field, we can overcome the attacks and a stable system can be generated. Conclusion: The algorithm defined here protects the information from an intruder and also from the error in communication channel by efficient error correction methods.

Design Techniques for Sigmadelta based ADC for Wireless Applications

Analog-to digital Converters (ADC) have an important impact on the overall performance of signal processing system. This research is to explore efficient techniques for the design of sigma-delta ADC,specially for multi-standard wireless tranceivers. In particular, the aim is to develop novel models and algorithms to address this problem and to implement software tools which are avle to assist the designer's decisions in the system-level exploration phase. To this end, this thesis presents a framework of techniques to design sigma-delta analog to digital converters.A2-2-2 reconfigurable sigma-delta modulator is proposed which can meet the design specifications of the three wireless communication standards namely GSM,WCDMA and WLAN. A sigma-delta modulator design tool is developed using the Graphical User Interface Development Environment (GUIDE) In MATLAB.Genetic Algorithm(GA) based search method is introduced to find the optimum value of the scaling coefficients and to maximize the dynamic range in a sigma-delta modulator.

Iron Promoted Sulphated Zirconia Systems as Efficient Catalysts for Phenol Hydroxylation

The present work investigates on the applicability of metal promoted sulphated zirconia catalysts for the hydroxylation of phenol under mild conditions. The percentage conversion and product distribution was highly sensitive towards the reaction parameters like the catalyst composition, reaction temperature, H202/ phenol ratio and the solvent used.

Acid activated montmorillonite: an efficient immobilization support for improving reusability, storage stability and operational stability of enzymes

Three enzymes, α-amylase, glucoamylase and invertase, were immobilized on acid activated montmorillonite K 10 via two independent techniques, adsorption and covalent binding. The immobilized enzymes were characterized by XRD, N2 adsorption measurements and 27Al MAS-NMR spectroscopy. The XRD patterns showed that all enzymes were intercalated into the clay inter-layer space. The entire protein backbone was situated at the periphery of the clay matrix. Intercalation occurred through the side chains of the amino acid residues. A decrease in surface area and pore volume upon immobilization supported this observation. The extent of intercalation was greater for the covalently bound systems. NMR data showed that tetrahedral Al species were involved during enzyme adsorption whereas octahedral Al was involved during covalent binding. The immobilized enzymes demonstrated enhanced storage stability. While the free enzymes lost all activity within a period of 10 days, the immobilized forms retained appreciable activity even after 30 days of storage. Reusability also improved upon immobilization. Here again, covalently bound enzymes exhibited better characteristics than their adsorbed counterparts. The immobilized enzymes could be successfully used continuously in the packed bed reactor for about 96 hours without much loss in activity. Immobilized glucoamylase demonstrated the best results.