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.

Standardisation de l’aménagement d’une unité d’endoscopie : Aires de transit des équipements biomédicaux

Rapport de projet

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.

La planification métropolitaine et le transit-oriented development (TOD) : les nouveaux instruments de la gouvernance du Grand Montréal

Cette thèse croise les concepts de planification, de gouvernance et de transit-oriented development (TOD) par une étude de la production, de la mise en débat et de l'adoption du plan métropolitain d'aménagement et de développement (PMAD) de la Communauté métropolitaine de Montréal (CMM). Elle expose les résultats de quatre années de recherche qualitative sur les impacts de l'épisode du PMAD et de la stratégie TOD de la CMM sur les pratiques planificatrices et les processus décisionnels du Grand Montréal à l'échelle métropolitaine. Elle révèle que la planification métropolitaine et l'objectif de coordination du transport et de l'aménagement en général ainsi que le PMAD et le concept de TOD en particulier y sont des instruments de gouvernance. Les chapitres 2, 3 et 4 présentent la problématique, le terrain d'enquête et la démarche méthodologique de cette recherche. Le chapitre 5 relate l'épisode du PMAD en analysant son contenu, les procédures par lesquelles la CMM l'a produit, mis en débat et adopté, les réactions des parties prenantes de la région quant à ces aspects et la façon dont elles comptent assurer le suivi de sa mise en œuvre. Le chapitre 6 illustre comment cet épisode a fait du PMAD un instrument de gouvernance pour le Grand Montréal en décortiquant le rôle de la participation publique, des médias, des acteurs des milieux régional et local, des élus, de la CMM et de la société civile de la région au sein de ce processus de changement de registre de la planification et de la gouvernance les déployant sur des bases plus stratégiques et collaboratives. Le chapitre 7 montre que cet épisode a aussi fait du TOD un instrument de gouvernance pour le Grand Montréal en détaillant les tenants et aboutissants du processus d'appropriation, de marchand(is)age et d'instrumentalisation du concept par les élites politiques et techniques à des fins de marketing territorial et de construction de capital politique ouvrant la voie à la stabilisation d'une gouvernance en matière d'aménagement métropolitain. Il se dégage de cette thèse que ces profondes transformations que subissent actuellement la planification et la gouvernance exacerbent le caractère symbiotique de la relation qui les unit.

Receivable Management in Non Banking Finance Companies with Special Reference to Vehicle Financing

In the absence of entry barrier or regulatory restrictions, Non Banking Financial Companies frantically grew and accessed the public deposit without any regulatory control. The deposit of NBFCs grew from Rs. 41.9 crore in 1971 to 53116.0 crore in 1997. This growth was the result of a combined effect of increase in the number of NBFCs and increase in the amount of deposits. The deposits amazed as above was invested in various assets especially that in motor vehicles by these asset financing NBFCs. Various tactics were adopted by these NBFCs and their agents for recovering the receivable outstanding from such assets. Both central government and RBI were concerned about the protection of depositors‘ interest and various committees were set up to frame a comprehensive regulation for the functioning of these NBFCs.

Integrated Environment for Launch Vehicle Telemetry Data Management

The telemetry data processing operation intended for a given mission are pre-defined by an onboard telemetry configuration, mission trajectory and overall telemetry methodology have stabilized lately for ISRO vehicles. The given problem on telemetry data processing is reduced through hierarchical problem reduction whereby the sequencing of operations evolves as the control task and operations on data as the function task. The function task Input, Output and execution criteria are captured into tables which are examined by the control task and then schedules when the function task when the criteria is being met.

Influence of Frequent Flyer Programme and Airline Service Quality on Re-buy Intentions of Airline Frequent Passengers

The growth potential of service sector, especially the aviation sector in the Indian economy is splendid. Therefore, it is crucial for the airline service providers to realize their customers, design offers and deliver the desired value to their customers. This study reveals the effect of airline passenger satisfactions particularly on re-buy intentions derived from the attributes-level performance dimensions of both service aspects and loyalty programme of an airline. The mediation effect of satisfaction and other selected antecedents on the re-buy intention of a passenger is hypothesized in this study. Critical areas affecting buying intentions such as core service quality and loyalty attribute-level performances, effect of frequent flyer programme and service quality satisfaction, passenger trust on airline, brand image and moderating effects of perceived value, frequent programme status and travel frequency of airline passengers are linked in a structural model to assess the strength of each facet in affecting re-buy intentions. Implications to the airlines were made based on the finding that re-buy intentions cannot be attributed solely to the impacts of frequent flyer programme, rather affected through the mediation effect of airline service quality satisfaction, which is very much valid for the higher FFP status category of frequent travelers. The effects of moderation caused by perceived value, FFP status and flying experience were also found to be significant in making re-buy intentions.

Funktionsanalysen der Domänen des Vacuolin B und die Rolle des filamentösen Actins am Vacuolin B-positiven Kompartiment im endocytotischen Transit in Dictyostelium discoideum

Ähnlich wie in Säugerzellen ist das neutrale Postlysosom in Dictyostelium discoideum von einem Coat aus filamentösem Actin umgeben. In dieser Arbeit wurde der Frage nach der Funktion dieses Actin-Cytoskeletts am späten Endosom nachgegangen. Hierzu wurde zunächst eine Analyse der Domänen des Vacuolin B durchgeführt, das als bisher spätester bekannter Marker im Endocytoseweg in Dictyostelium discoideum das neutrale, postlysosomale Kompartiment dekoriert. In einer Yeast Two Hybrid-Analyse wurden die Bereiche des Vacuolin B identifiziert, die für eine Selbst-Interaktion des Proteins notwendig und ausreichend sind. Es handelt sich dabei um die coiled-coil-Domäne und einen daran anschließenden, 18 Aminosäuren langen, alpha-helicalen Abschnitt. Diesem helicalen Bereich scheint die Funktion einer modifizierenden, die coiled-coil-Ausbildung vermittelnden oder initiierenden Faltungseinheit zuzukommen. Sie weist jedoch nicht die typischen Merkmale einer trigger-Helix auf. Lokalisationsuntersuchungen mit GFP-Deletionskonstrukten zeigten, dass es einen Zusammenhang zwischen Interaktionsfähigkeit und Bindung des Vacuolin an die Oberfläche später Endosomen gibt: Eine korrekte Lokalisation und Membranassoziation waren nur dann zu beobachten, wenn in der Yeast Two Hybrid-Analyse eine Interaktion nachgewiesen werden konnte. Es wurden die für die Lokalisation und Assoziation mit der vacuolären Membran notwendigen Sequenzbereiche identifiziert; diese waren jedoch nicht hinreichend. Vermutlich sind hierfür auch Sequenzen des N-Terminus notwendig. Die erhobenen Daten legen weiterhin eine Bedeutung der hydrophoben Domäne des Vacuolin B für die korrekte Faltung des Proteins nahe. Im Anschluss an die Domänenanalyse wurde Vacuolin dazu benutzt, durch Herstellung von Hybridproteinen Actin-interagierende Proteine gezielt an das späte Endosom zu transportieren. Es wurde deren Einfluss auf den lokalen Actin Coat und den endocytotischen Transit untersucht. Zwei Actin-bindende Proteine mit depolymerisierender Wirkung konnten im Rahmen dieser Arbeit getestet werden, nämlich Severin und Cofilin. Die Schwächung des lokalen Actin Coats durch das Vorhandensein von Severin an der späten Vacuole war nicht eindeutig festzustellen. Severin am Postlysosom führte nicht zu einer Veränderung der Transitkinetik von Flüssigphasenmarker. Allerdings konnte ein Defekt in der Phagocytose festgestellt werden. Es könnte hierbei ein Zusammenhang zwischen der Mobilisierung von intrazellulärem Calcium während der Partikelaufnahme und der Calcium-abhängigen Regulation der Severin-Aktivität bestehen. Das Hybridprotein aus Vacuolin und Cofilin zeigte neben einer Assoziation mit der vacuolären Membran auch eine Lokalisation im Cytoplasma und Cortex der Zellen. Mit der Lokalisation im Cytoplasma und Cortex korrelierte eine Veränderung der endocytotischen Aktivität. Das Vacuolin-Cofilin-Fusionsprotein am Postlysosom rief einen Verlust des lokalen Actin Coats hervor. Dies führte zu einer traubenförmigen Assoziation der späten Endosomen; exocytotische Parameter blieben jedoch unbeeinflusst. Aufgrund der hier erhobenen Daten kann vermutet werden, dass der Actin Coat am Postlysosom dazu dient, eine Agglutination dieser Endosomen zu inhibieren. Dies könnte ein Schutzmechanismus zum Ausschluss von Docking- und Fusionsereignissen sein.

Investigation of Multiphase Power Converter using Integrated Coupled Inductor Regarding Electric Vehicle Application

The challenge of reducing carbon emission and achieving emission target until 2050, has become a key development strategy of energy distribution for each country. The automotive industries, as the important portion of implementing energy requirements, are making some related researches to meet energy requirements and customer requirements. For modern energy requirements, it should be clean, green and renewable. For customer requirements, it should be economic, reliable and long life time. Regarding increasing requirements on the market and enlarged customer quantity, EVs and PHEV are more and more important for automotive manufactures. Normally for EVs and PHEV there are two important key parts, which are battery package and power electronics composing of critical components. A rechargeable battery is a quite important element for achieving cost competitiveness, which is mainly used to story energy and provide continue energy to drive an electric motor. In order to recharge battery and drive the electric motor, power electronics group is an essential bridge to convert different energy types for both of them. In modern power electronics there are many different topologies such as non-isolated and isolated power converters which can be used to implement for charging battery. One of most used converter topology is multiphase interleaved power converter, pri- marily due to its prominent advantages, which is frequently employed to obtain optimal dynamic response, high effciency and compact converter size. Concerning its usage, many detailed investigations regarding topology, control strategy and devices have been done. In this thesis, the core research is to investigate some branched contents in term of issues analysis and optimization approaches of building magnetic component. This work starts with an introduction of reasons of developing EVs and PEHV and an overview of different possible topologies regarding specific application requirements. Because of less components, high reliability, high effciency and also no special safety requirement, non-isolated multiphase interleaved converter is selected as the basic research topology of founded W-charge project for investigating its advantages and potential branches on using optimized magnetic components. Following, all those proposed aspects and approaches are investigated and analyzed in details in order to verify constrains and advantages through using integrated coupled inductors. Furthermore, digital controller concept and a novel tapped-inductor topology is proposed for multiphase power converter and electric vehicle application.

Fat-Tree Routing for Transit

The Transit network provides high-speed, low-latency, fault-tolerant interconnect for high-performance, multiprocessor computers. The basic connection scheme for Transit uses bidelta style, multistage networks to support up to 256 processors. Scaling to larger machines by simply extending the bidelta network topology will result in a uniform degradation of network latency between all processors. By employing a fat-tree network structure in larger systems, the network provides locality and universality properties which can help minimize the impact of scaling on network latency. This report details the topology and construction issues associated with integrating Transit routing technology into fat-tree interconnect topologies.

Millora aerodinàmica de la nova carrosseria del vehicle l'Àliga. Estudis dels efectes de la rugositat i l'inserció d'apèndixs aerodinàmics

L' objectiu d' aquest estudi és intentar millorar l' aerodinàmica de la nova carrosseria del vehicle de baix consum de la UdG,l' Àliga, a través de programes informàtics de CFD. Des de fa uns anys l' Escola Politècnica Superior de la Universitat de Girona participa a l' Eco Shell Marathon, mirant d' assolir els millors resultats possibles.El nom del vehicle utilitzat per aquesta carrera és l' Àliga. Aquest projecte parteix dels resultats obtinguts al Projece fi de carrera d' en Daniel Vilavedra Vilà (2006):"Redisseny aerodinàmic de la carrosseria del vehicle de baix consum Àliga"

Estudi i simulació aerodinàmica amb programari de dinàmica de fluids computacional (CFD) en un model bàsic de vehicle de competició de la categoria CM (curses de muntanya)

Aquest projecte té com a objectiu la simulació numérica de la carrosseria d’ un vehicle de curses de muntanya de categoria CM

An approach to vision-based station keeping for an unmanned underwater vehicle

This paper presents an automatic vision-based system for UUV station keeping. The vehicle is equipped with a down-looking camera, which provides images of the sea-floor. The station keeping system is based on a feature-based motion detection algorithm, which exploits standard correlation and explicit textural analysis to solve the correspondence problem. A visual map of the area surveyed by the vehicle is constructed to increase the flexibility of the system, allowing the vehicle to position itself when it has lost the reference image. The testing platform is the URIS underwater vehicle. Experimental results demonstrating the behavior of the system on a real environment are presented

Autonomous underwater vehicle control using reinforcement learning policy search methods

Autonomous underwater vehicles (AUV) represent a challenging control problem with complex, noisy, dynamics. Nowadays, not only the continuous scientific advances in underwater robotics but the increasing number of subsea missions and its complexity ask for an automatization of submarine processes. This paper proposes a high-level control system for solving the action selection problem of an autonomous robot. The system is characterized by the use of reinforcement learning direct policy search methods (RLDPS) for learning the internal state/action mapping of some behaviors. We demonstrate its feasibility with simulated experiments using the model of our underwater robot URIS in a target following task