• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 45
  • 14
  • 8
  • 2
  • 1
  • 1
  • Tagged with
  • 76
  • 48
  • 22
  • 19
  • 17
  • 16
  • 16
  • 12
  • 12
  • 12
  • 11
  • 9
  • 9
  • 8
  • 8
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
61

Logistique inverse et collecte des produits techniques en fin de vie. Tournées de véhicules avec contraintes

Landrieu, Antoine 21 September 2001 (has links) (PDF)
La logistique inverse des déchets techniques encombrants de type blanc ou brun se développe de nos jours afin de répondre aux contraintes législatives fortes qui n'autorisent à partir de juillet 2002 que la mise en décharge des déchets dits « ultimes ». Le recyclage noble apparaît comme une solution prometteuse, économiquement viable et écologique, où la collecte, approvisionneuse exclusive du processus de récupération des déchets, doit être appréhendée et planifiée dans l'objectif de maîtrise des coûts. Après avoir identifié les caractéristiques principales des systèmes de collecte existants, nous nous attardons sur le ramassage à domicile des produits usagés de la population. Afin de pouvoir établir une planification opérationnelle, ce mode de collecte est modélisé comme un problème de routage de véhicules : le problème de chargement et de déchargement avec contraintes de fenêtres temporelles, de précédence et de capacité. Ce problème d'Optimisation Combinatoire est ensuite résolu de manière algorithmique, en considérant successivement le cas d'un véhicule, puis de plusieurs véhicules. La résolution du problème se base sur la recherche tabou et la recherche tabou probabiliste, et fournit des résultats très satisfaisants sur le plan qualitatif et en temps d'exécution. Finalement, nous décrivons, grâce au langage de modélisation unifié orienté objet UML, une manière d'intégrer nos résultats algorithmiques dans un module d'aide à la décision pour la planification opérationnelle de la collecte, où l'opérateur humain est chargé de définir le plan de collecte à exécuter.
62

Une Approche Hybride de Simulation-Optimisation Basée sur la fouille de Données pour les problèmes d'ordonnancement

Shahzad, Atif 16 March 2011 (has links) (PDF)
Une approche hybride basée sur la fouille de données pour découvrir de nouvelles règles de priorité pour le problème l'ordonnancement job-shop est présentée. Cette approche est basée sur la recherche de connaissances supposées être intégrés dans les solutions efficaces fournies par un module d'optimisation préalablement mis en oeuvre et utilisant la recherche tabou. L'objectif est de découvrir les principes directeurs de l'ordonnancement à l'aide de la fouille de données et donc d'obtenir un ensemble de règles capables d'obtenir des solutions efficaces pour un problème d'ordonnancement. Une structure basée sur fouille de données est présentée et mise en œuvre pour un problème de job shop avec comme objectifs le retard maximum et le retard moyen. Les résultats obtenus sont très prometteurs.
63

Méthodes de résolution exactes et heuristiques pour un problème de tournées de techniciens

Mathlouthi, Ines 12 1900 (has links)
No description available.
64

Matheuristic algorithms for minimizing total tardiness in flow shop scheduling problems / Algorithmes métaheuristiques pour minimiser la somme des retards des problèmes d'ordonnancement de type flowshop

Ta, Quang-Chieu 12 February 2015 (has links)
Nous considérons dans cette thèse un problème d’ordonnancement de flow-shop de permutation où un ensemble de travaux doit être ordonnancé sur un ensemble de machines. Les travaux doivent être ordonnancés sur les machines dans le même ordre. L’objectif est de minimiser le retard total. Nous proposons des algorithmes heuristiques et des nouvelles matheuristiques pour ce problème. Les matheuristiques sont un nouveau type d’algorithmes approchés qui ont été proposés pour résoudre des problèmes d’optimisation combinatoire. Les méthodes importent de la résolution exacte au sein des approches (méta) heuristiques. Ce type de méthode de résolution a reçu un grand intérêt en raison de leurs très bonnes performances pour résoudre des problèmes difficiles. Nous présentons d’abord les concepts de base d’un problème d’ordonnancement. Nous donnons aussi une brève introduction à la théorie de l’ordonnancement et nous présentons un panel de méthodes de résolution. Enfin, nous considérons un problème où un flow shop de permutation à m-machine et un problème de tournées de véhicules sont intégrés, avec pour objectif la minimisation de la somme des retards. Nous proposons un codage direct d’une solution et une méthode de voisinage. Les résultats montrent que l’algorithme Tabou améliore grandement la solution initiale donnée par EDD et où chaque voyage ne délivre qu’un travail. / We consider in this thesis a permutation flow shop scheduling problem where a set of jobs have to be scheduled on a set of machines. The jobs have to be processed on the machines in the same order. The objective is to minimize the total tardiness. We propose heuristic algorithms and many new matheuristic algorithms for this problem. The matheuristic methods are a new type of approximated algorithms that have been proposed for solving combinatorial optimization problems. These methods embed exact resolution into (meta)heuristic approaches. This type of resolution method has received a great interest because of their very good performances for solving some difficult problems. We present the basic concepts and components of a scheduling problem and the aspects related to these components. We also give a brief introduction to the theory of scheduling and present an overview of resolution methods. Finally, we consider a problem where m-machine permutation flow shop scheduling problem and a vehicle routing problem are integrated and the objective is to minimize the total tardiness. We introduce a direct coding for a complete solution and a Tabu search for finding a sequence and trips. The results show that the TS greatly improves the initial solution given by EDD heuristic where each trip serves only one job at a time.
65

Contribution à la conception des filtres bidimensionnels non récursifs en utilisant les techniques de l’intelligence artificielle : application au traitement d’images / Contribution to the design of two-dimensional non-recursive filters using artificial intelligence techniques : application to image processing

Boudjelaba, Kamal 11 June 2014 (has links)
La conception des filtres a réponse impulsionnelle finie (RIF) peut être formulée comme un problème d'optimisation non linéaire réputé pour être difficile sa résolution par les approches conventionnelles. Afin d'optimiser la conception des filtres RIF, nous explorons plusieurs méthodes stochastiques capables de traiter de grands espaces. Nous proposons un nouvel algorithme génétique dans lequel certains concepts innovants sont introduits pour améliorer la convergence et rendre son utilisation plus facile pour les praticiens. Le point clé de notre approche découle de la capacité de l'algorithme génétique (AG) pour adapter les opérateurs génétiques au cours de la vie génétique tout en restant simple et facile à mettre en oeuvre. Ensuite, l’optimisation par essaim de particules (PSO) est proposée pour la conception de filtres RIF. Finalement, un algorithme génétique hybride (HGA) est proposé pour la conception de filtres numériques. L'algorithme est composé d'un processus génétique pur et d’une approche locale dédiée. Notre contribution vise à relever le défi actuel de démocratisation de l'utilisation des AG’s pour les problèmes d’optimisation. Les expériences réalisées avec différents types de filtres mettent en évidence la contribution récurrente de l'hybridation dans l'amélioration des performances et montrent également les avantages de notre proposition par rapport à d'autres approches classiques de conception de filtres et d’autres AG’s de référence dans ce domaine d'application. / The design of finite impulse response (FIR) filters can be formulated as a non-linear optimization problem reputed to be difficult for conventional approaches. In order to optimize the design of FIR filters, we explore several stochastic methodologies capable of handling large spaces. We propose a new genetic algorithm in which some innovative concepts are introduced to improve the convergence and make its use easier for practitioners. The key point of our approach stems from the capacity of the genetic algorithm (GA) to adapt the genetic operators during the genetic life while remaining simple and easy to implement. Then, the Particle Swarm Optimization (PSO) is proposed for FIR filter design. Finally, a hybrid genetic algorithm (HGA) is proposed for the design of digital filters. The algorithm is composed of a pure genetic process and a dedicated local approach. Our contribution seeks to address the current challenge of democratizing the use of GAs for real optimization problems. Experiments performed with various types of filters highlight the recurrent contribution of hybridization in improving performance. The experiments also reveal the advantages of our proposal compared to more conventional filter design approaches and some reference GAs in this field of application.
66

Les termes de la gynécologie obstétrique en igbo : enquête sur un domaine tabou dans une langue sans documents écrits / Igbo gynaecology-obstetrics terminology : a Survey of a Domain Shrouded in Taboo in a language without Written Sources

Ngwaba, Chidinma 23 November 2016 (has links)
La présente étude porte sur la terminologie de la gynécologie-obstétrique en langue igbo. L’objectif principal est double : d’une part, recenser et classer les termes de la gynécologie-obstétrique en igbo et examiner l’adéquation entre la terminologie igbo et la terminologie internationale des langues de grande diffusion comme l’anglais et le français ; d’autre part, tenter de dégager les procédés à l’œuvre dans la création terminologique du domaine. Des vides ayant été constatés dans la terminologie igbo du domaine par rapport au français et à l’anglais, nous avons essayé de les combler, validant ainsi l’idée selon laquelle la langue igbo, à l’instar de toutes les langues, a bel et bien la capacité de désigner tout concept, quel qu’en soit le domaine. Notre recherche vise spécifiquement à recueillir les termes igbo de la gynécologie-obstétrique autant pour permettre les types de jugement théorique que nous nous sommes engagée à faire que pour les fins utilitaires d’un tel recueil. La méthode utilisée pour étudier la terminologie de la gynécologie-obstétrique en igbo devait convenir à l’étude d’un domaine tabou dans une langue sans documents écrits. Nous avons donc dû tenter de recueillir oralement les termes recherchés, en utilisant des techniques permettant de contourner la réticence de nombreux locuteurs igbo à s’exprimer sur le sujet.Pour constituer la nomenclature du domaine, nous avons mené une enquête sur le terrain auprès d’un groupe de locuteurs igbo constitué de 57 professionnels de santé soit 20 gynécologues-obstétriciens, 10 sages-femmes, 3 infirmiers, 15 médecins traditionnels, 5 sages-femmes traditionnelles, deux chefs de village et deux personnes âgées. Notre démarche s’est inspirée de la socioterminologie de Gaudin (2003, 2005) et de la méthodologie d’enquête d’Halaoui (1990, 1991), auxquelles nous avons emprunté l’aspect méthodologique de la recherche en terminologie des langues africaines. Au vu des résultats de notre enquête, nous avons constaté des vides terminologiques que nous avons tenté de combler à partir des propositions des personnes rencontrées et en nous inspirant de la démarche proposée par Diki-Kidiri (2008). Les matrices terminologiques sous-jacentes aux termes proposés ont été dégagées et analysées. Elles témoignent des tendances générales de l’igbo en la matière. Ce travail aboutit donc à la création d’un lexique trilingue anglais-français-igbo des termes de la gynécologie-obstétrique. Ce lexique contient les termes désignant l’anatomie du bassin féminin et parties génitales, l’anatomie des parties génitales internes femelles, l’anatomie de l’organe sexuel masculin, la physiologie du système reproducteur, le développement de l’embryon, la physiologie de la nutrition pendant la lactation et la grossesse, la surveillance fœtale, le travail/accouchement, le nouveau-né, les maladies liées aux organes reproducteurs, les maladies sexuellement transmissibles, les anomalies structurales, le cancer du système reproducteur et les maladies du système urinaire. Notre travail comprend trois parties. La première partie intitulée « La langue igbo du Nigeria » est composée de trois chapitres. Le chapitre 1 : « le Nigeria Terre de diversité ethnique et Linguistique », le chapitre 2 : « Description de la langue Igbo » et le chapitre 3 : « Problèmes Terminologiques igbo ». La deuxième partie intitulé « Un domaine Terminologique particulier : La médecine » comporte deux chapitres. Le chapitre 4 : « La maladie et la santé chez les igbo », et le chapitre 5 : « La pratique de la médecine au Nigeria ». La troisième partie : « La terminologie igbo de la gynécologie-obstétrique : Etat des lieux » comprends deux chapitres. Le chapitre 6 : « L’enquête sur le terrain » et Le chapitre 7 : « La création Terminologique en igbo : Le cas de la gynécologie-obstétrique ». / This study focuses on gynaecology-obstetrics terminology in Igbo. Our main objective is to take an inventory of Igbo terms in the area of gynaecology-obstetrics and classify them. This will enable us to examine and evaluate the adequacy of Igbo terms in relation to English and French terms. A second objective involves exposing the methodology used in Igbo term creation in the gynaecology-obstetrics domain.In our research we noticed that gaps exist in the area of gynaecology-obstetrics of the Igbo language when compared to English and French languages. We tried to fill in the gaps thereby validating the idea whereby the Igbo language like all other languages, is capable of naming concepts in any area. Our research specifically aims at collecting Igbo terms from the domain of gynaecology-obstetrics in a way that enables us explain or give information on the method of collection of such terms.The method used in the terminological study of the gynaecology-obstetrics domain in Igbo, should be suitable in studying a taboo domain of a language without written documents. An oral documentary research became necessary. Thus the Igbo terms were compiled by means oral documentation research using techniques that helped us bypass the hesitation or reluctance of many Igbo speakers to express themselves on our area of research.To constitute the nomenclature of the domain, we carried out field work. This involved the observation of and interviews with Igbo speakers namely: traditional doctors, orthodox doctors, midwives both traditional and orthodox, nurses, local chiefs and elderly persons. We thus interviewed 57 resource-persons and experts: 20 doctors, 3 nurses and 10 midwives (for the orthodox medicine component), 15 traditional doctors, 5 traditional midwives, 2 local chiefs and 2 elderly persons (for the traditional medicine component). We were equally inspired by socioterminology as exposed by Gaudin (2003, 2005) and the methodology of research as outlined in Halaoui (1990, 1991) from which we borrowed the methodology of research in terminology of African languages.Looking at our field work result, we noticed terminological gaps which we tried to fill using proposals from the people we interviewed. The work also involved the creation of terms for concepts and objects not already named in Igbo. This naming drew principally on the method described in Diki-Kidiri (2008). An analysis of the process underlying each coinage is included. The result obtained is a clear indication that the Igbo language can be used to name things.This work equally proposes a trilingual glossary: English-French-Igbo. The glossary covers such areas as: Anatomy of the female pelvis and the external genitalia, Anatomy of the internal genital organs – female, Anatomy of the male reproductive system, Physiology of the reproductive system, Development of the embryo, Physiology and nutrition in pregnancy and lactation, Foetal surveillance, Labour, The new born infant, Infections of the reproductive organs, Infections of the reproductive tract, Sexually transmitted diseases, Structural anomalies, Cancers of the reproductive system and Disorders of the urinary system.Our work comprises three parts. Part 1: “The Igbo Language of Nigeria” consists of three chapters. Chapter 1: “Nigeria a Land with ethnicity and Linguistic diversity”, Chapter 2: “Description of the Igbo Language” and Chapter 3: “Problems of Igbo Terminology”. Part 2: entitled “A Distinctive Terminological Domain: Medicine” is made up of two chapters. Chapter 4: “Sickness and Heath among the Igbos” and Chapter 5: “Practicing Medicine in Nigeria”. Part 3 comprises two chapters. Chapter 6: “Field Work” and Chapter 7: “Creating Terms in Igbo: the Gynaecology-Obstetrics Domain”. / Nnyọcha anyị a dabere n’ihe gbasara amụmamụ maka ọmụmụ nwa na nwa ohụụ n’asụsụ igbo.Ebum n’obi anyị nke mbụ bụ ịchọpụta ma hazie aha dị iche iche e nwere n’asụsụ igbo gbasaraọmụmụ nwa na nwa ohụụ na ngalaba amụmamụ maka ọmụmụ nwa na nlekọta nwa ohụụ. Nkea ga-eme ka anyị nwalee aha ndịa e nwere n’asụsụ igbo na ngalaba amụmamụ maka ọmụmụnwa na nlekọta nwa ohụụ na aha ndi e nwere na olu bekee m’obụ frenchi. Ebum n’obi anyị nkeabụọ bụ ikwupụta otu anyị si nwete ma depụta aha gbasara ọmụmụ nwa na nlekọta nwa ohụụn’asụsụ igbo. Anyị kwadoro usoro mkpụrụ edemede nke igbo izugbe.Mgbe anyi n’eme nnyocha a, anyị chọpụtara n’oghere dị n’asụsụ igbo n’ihe metutara mkpọpụtaaha ihe. Nke a mere n’enwere ọtụtụ ihe ndi n’enweghị aha n’asụsụ igbo na ngalaba amụmamụmaka ọmụmụ nwa na nlekọta nwa ohụụ. Ihe ndia nwechara aha n’asụsụ ndi ọzọ. Anyị gbalịrịịfachisi oghere ndia dị n’asụsụ igbo iji gosi n’asụsụ a bụ asụsụ igbo nwekwara ike ịkpọpụta ahaihe ndi ha aka akpọbeghị aha.Usoro anyị kwesiri ịgbaso mgbe anyị na-amụ gbasara mkpọ aha n’asụsụ igbo na ngalabaamụmamụ maka ọmụmụ nwa na nlekọta nwa ohụụ, kwesiri ka ọ bụrụ nke ga-adaba na ọmụmụihe gbasara asụsụ n’enweghị ihe ndeda gbasara ngalaba amụmamụ a na kwa ngalaba nwereọtụtụ nsọ ala. Nke a mere oji dị mkpa na anyị gara mee nchọpụta n’obodo jụọ ajụjụ ọnụ iji mataaha ndi a n’agbanyeghị na ọ dịghịrị ndi mmadụ mfe ikwu maka ngalaba ihe ọmụmụ a.viNdi anyị gakwuru maka ajụjụ ọnụ a bụ ndi dibịa bekee, ndi nọọsụ, ndi dibịa ọdịnala, ndi ọghọnwa, ndi nchịkọta obodo na ndi okenye. N’ihe niile, anyị na ihe dịka mmadụ 57 kparịtara ụka.Nke a gụnyere ndi ọkachamara. N’ime ha e nwere ndi dibịa bekee 20, ndi nọọsụ 3 na ndi ọghọnwa bekee 10 n’otu akụkụ. N’akụkụ nke ọzọ, e nwere ndi dibịa ọdịnala 15, ndi ọghọ nwaọdịnala 5, ndi nchịkọta obodo 2 na ndi okenye 2. Anyị dabekwara na sosioteminọlọjị nkeGaudin (2003, 2005) na kwa usoro Halaoui (1990, 1991). Usoro a gbasara ịjụ ndi igbo ụfọdụajụjụ ọnụ na iso ha nọrọ mgbe ha na-arụ ọrụ.Nchọcha anyị gụnyekwara ịkpọpụta aha dị iche iche n’asụsụ igbo nke sistemu njiamụnwa nkenwoke na nwaanyị, aha gbasara nwa e bu n’afọ na nke nwa a mụrụ ọhụụ. Anyị gbasoro usoroDiki-Kidiri (2008) maka mkpọpụta aha. Anyị mekwara nkọwa iji gosipụta otu anyị si kpọọ ahandịa. N’ikpe azụ anyị depụtara aha ndi niile anyị ji rụọ ọrụ na asụsụ bekee, frenchi na kwa igbo.Aha ndi anyị depụtara gbasara : Amụmamụ ọkpụkpụ ukwu nwaanyị na njiamụnwa, Amụmamụime njiamụnwa kenwaanyị, Amụmamụ ọganụ njiamụnwa kenwoke, Fiziọlọjị sistemunjiamụnwa, Ntolite nwa nọ n’afọ, Fiziọlọjị kenri na mmiriara n’afọ ime, Nledo nwa nọ n’afọna kwa nwaọhụụ, Imeomume, Mbido ndụ nwaọhụụ, Ọrịa ọganụ njiamụnwa, Ọrịa nwaanyị,Nkwarụ, Kansa njiamụnwa na kwa Ọrịa akpamamịrị.
67

Contribution aux graphes creux pour le problème de tournées sur arcs déterministe et robustes : théorie et algorithmes / Contribution of sparse graphs in the deterministic and robust capacitated arc routing problem : theory and algorithms

Tfaili, Sara 01 December 2017 (has links)
Cette thèse comporte deux parties majeures : la première partie est dédiée à l'étude du problème sparse CARP déterministe où nous avons développé une transformation du sparse CARP en un sparse CVRP. La seconde est consacrée au problème sparse CARP avec coûts sous incertitude. Nous avons donné une formulation mathématique du problème en min-max. Cette modélisation a permis d'identifier le pire scénario pour le problème robuste. Deux approches algorithmiques ont été proposées pour une résolution approchée. / This dissertation consists of two main parts : in the first part, we study the detreministic capacitated arc routing problem over sparse underlying graphs wher we have developed a new transformation techniquevof sparse CARP into sparse CVRP. The second part is consecrated about the sparse CARP with travel costs uncertainty. We have given a mathematical formulation of the probleme in min-max. A worst scenario for the robust problem is then identified, and two algorithmic approaches are proposed to determine a solution of the studied problem.
68

Les bénéfices relationnels attendus expliqués par le stéréotype du personnel en contact, l'attitude du client, ses valeurs et les incidents critiques : une application à la gestion de patrimoine et à la banque de réseau / The expected relational benefits explained by the personal in contact stereotype, the client’s money attitude, values and critical incidents : an empirical study about wealth management and retail banking

Hobeika, Janine 06 December 2017 (has links)
La réussite du marketing relationnel dépend des préférences individuelles des clients, ceux-ci n'étant pas tous également réceptifs aux approches relationnelles. Il apparaît, à ce titre, nécessaire d'approfondir la connaissance des bénéfices relationnels attendus par les clients. Dans un design mixte séquentiel, des entretiens non-directifs menés auprès de clients en gestion de patrimoine, puis auprès de clients de banques de réseau, montrent et confirment l'existence de trois profils relationnels distincts : transactionnel, relationnel psychologique et relationnel socio-valorisable. Une matrice combinant l'attitude à l'argent et le stéréotype du banquier révèle des profils hybrides souhaitables vs indésirables. L'étude quantitative crée une échelle de mesure du stéréotype du banquier, enrichit l’échelle de l’attitude à l’argent de la dimension tabou, et aménage une échelle des bénéfices relationnels attendus. Le test d'hypothèses dans un modèle d'équations structurelles montre le rôle du stéréotype du banquier, de l'attitude à l'argent du client, de ses valeurs culturelles et des incidents critiques, dans l'explication des bénéfices relationnels attendu. / The success of relationship marketing depends on individual preferences, knowing that clients are not all equally receptive to relational approaches. It appears necessary for this purpose to improve knowledge about client’s expected relational benefits. Within a sequential mixed design, non-directive interviews conducted with wealth management clients, then with retail bank clients, show and confirm the existence of three distinct types of relational profiles : transactional, psychological relational and socio-valuable relational. A matrix combining the money attitude and the banker stereotype reveals desirable vs undesirable hybrid profiles. The quantitative study creates a scale to measure the banker stereotype, enriches the money attitude scale with the taboo dimension, and produces a scale for the expected relational benefits. The test of hypotheses in a structural equations model shows the role of the banker stereotype, the money attitude, the cultural values and critical incidents, in the formation of expected relational benefits
69

Résolution d’un problème de collecte et livraison dynamique sur un réseau routier avec temps de parcours variables

Caron, Félix 03 1900 (has links)
Les services de livraison express font face au défi d’optimiser les routes de leurs véhicules alors que ceux-ci circulent dans un réseau routier où les temps de parcours varient en fonction du moment de la journée et où ils doivent répondre à l’arrivée dynamique de requêtes consistant à récupérer et livrer des colis. Notre but ici est de proposer une modélisation et une méthode de type heuristique pour résoudre ce problème. Nous commençons par explorer les travaux menés précédemment au sujet de l’arrivée dynamique des requêtes, des temps de parcours variables selon le moment de la journée et des collectes et livraisons dans les problèmes de tournées de véhicules. Ensuite, nous décrivons le problème de manière formelle sur le graphe du réseau routier avec des requêtes deux-points où l’objectif est de minimiser le temps total de parcours des véhicules et les temps de retard aux points de service et au dépôt. Par la suite, nous détaillons l’implémentation d’une méthode de résolution basée sur la recherche tabou utilisant une structure de voisinage basée sur la réinsertion d’une requête. Cette méthode utilise également la structure Dominant Shortest Path (DSP) qui considère plusieurs chemins alternatifs entre chaque paire de sommets, contrairement à l’approche traditionnelle où un chemin unique est fixé a priori. Finalement, nous testons notre méthode à l’aide de 390 instances générées de manière synthétique afin d’évaluer son efficacité ainsi que l’impact de certains aspects du problème et de la méthode de résolution. Les résultats démontrent une amélioration particulièrement importante due à l’utilisation de la structure DSP. / Express delivery services face the challenge of optimizing the routes of their vehicles while they are moving in a road network where the travel times vary according to the time of day in order to serve dynamic requests which consist in collecting and delivering parcels. Our goal here is to propose a model and a heuristic method to solve this problem. We begin by exploring previous work on the topic of the dynamic arrival of requests, timedependent travel times and pickups and deliveries in vehicle routing problems. Afterwards, we describe the problem formally on the graph of the road network with the objective of minimizing the total travel time of the vehicles and lateness at the service points and at the depot. Then, we detail the implementation of a solving method based on tabu search using a neighbourhood structure based on the reinsertion of a request. This method also uses the Dominant Shortest Path (DSP) structure which considers multiple alternative paths between each pair of vertices, unlike the traditional approach where a single path is fixed a priori. Finally, we test our method using 390 instances generated synthetically in order to evaluate its efficiency as well as the impact of certain aspects of the problem and solution method. The results show a particularly significant improvement due to the use of the DSP structure.
70

Solution Methods for Service Network Design with Resource Management Consideration

Vu, Duc Minh 06 1900 (has links)
La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions. / Resource management in freight transportation service network design is an important issue that has been studied extensively in recent years. Resources such as vehicles, crews, etc. are factors that can not be ignored when designing a feasible plan for any service network design problem. However, contributions related to resource management issues and service network design are still limited. The goal of the thesis is to fill this gap by taking into account service network design problems with resource management issues. In this thesis, we propose and address three service network design problems that consider resource management. In the first study, we consider the capacitated multi-commodity fixed cost network design with design-balance constraints which is a basic sub-problem for many service design problems because of the capacitated multi-commodity structure as well as its design-balance property. We propose a three-phase matheuristic that combines tabu-search, path-relinking and an exactbased intensification procedure to find high quality solutions. Tabu-search identifies feasible solutions while path-relinking extends the set of feasible solutions. The solutions found by these two meta-heuristics are used to fix arcs as open or close. An exact solver intensifies the search on a restricted problem derived from fixing arcs. The experiments on benchmark instances show that the solution approach finds good solutions to large-scale problems in a reasonable amount of time. The contribution with regard to this study has been accepted in the Journal of Heuristics. In the second study, together with the consideration of the design of routes to transport a set of commodities by vehicles, we extend resources management by explicitly taking account of the number of available vehicles at each terminal. We introduce a matheuristic solution framework based on a cycle-based formulation that includes column generation, slope-scaling, heuristic and exact optimization techniques. As far as we know, this is the first matheuristic procedure developed for a cycle-based formulation. The column generation solves the linear relaxation model and provides a set of cycles to define the approximation model used in slopescaling loop. A heuristic is used to convert each solution to the approximation problem into a feasible solution. Memory-based perturbation procedure is used to enhance the performance of the algorithm. Experiments show that the proposed algorithm is able to find good feasible solutions for the problem. The contribution with regard to this study has been accepted for publication in Transportation Science. In the third study, we examine resources allocation issues in service network design. We aim to address a number of fleet utilization issues which usually appear at the beginning of the season because of the change of demand patterns: 1) reposition resources among terminals to account for shifts in demand patterns; 2) acquire (buy or long-term rent) new resources and as sign them to terminals; 3) outsource particular services. We present an integrated formulation combining these selection-location and scheduled service design decisions. The mixed-integer formulation is defined over a time-space network, the initial period modeling the location de cisions on resource acquisition and positioning, while the decisions on service selection and scheduling, resource assignment and cycling routing, and demand satisfaction being modeled on the rest of the network. We also present a matheuristic solution method combining slope scaling and column generation, discuss its algorithmic performance, and explore the impact of combining the location and design decisions in the context of consolidation carrier service design. This study will be presented at XII International Symposium On Locational Deci sion, in conjunction with the XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. In summary, three studies are considered in this thesis. The first one considers the capaciated multi-commodity fixed cost network design with design-balance constraints, a basic problem in many service network design problems with design-balance constraints. We propose an ef ficient three-phase matheuristic solution method that includes tabu search, path relinking and exact optimization. In the second study, we propose a new service network design model that takes into account resources limitations at each terminal. We also propose an advanced matheuristic framework solution method based on a cycle-based formulation which includes slope-scaling, column generation, heuristics and exact optimization for this problem. The last study addresses resources allocation issues in service network design. We introduce formula tions that model the reposition, acquisition/renting of resources and outsourcing of services. A solution framework based on the slope-scaling approach on cycle-based formulations is pro posed. Tests indicate that these proposed algorithms are able to find good feasible solutions for each of threse problems.

Page generated in 0.0241 seconds