27 resultados para A* search algorithm
Resumo:
Thse ralise en cotutelle avec l'Universit d'Avignon.
Resumo:
Nous proposons de construire un atlas numrique 3D contenant les caractristiques moyennes et les variabilits de la morphologie dun organe. Nos travaux seront appliqus particulirement la construction d'un atlas numrique 3D de la totalit de la corne humaine incluant la surface antrieure et postrieure partir des cartes topographiques fournies par le topographe Orbscan II. Nous procdons tout d'abord par normalisation de toute une population de cornes. Dans cette tape, nous nous sommes bass sur l'algorithme de recalage ICP (iterative closest point) pour aligner simultanment les surfaces antrieures et postrieures d'une population de corne vers les surfaces antrieure et postrieure d'une corne de rfrence. En effet, nous avons labor une variante de l'algorithme ICP adapt aux images (cartes) de cornes qui tient compte de changement d'chelle pendant le recalage et qui se base sur la recherche par voisinage via la distance euclidienne pour tablir la correspondance entre les points. Aprs, nous avons procd pour la construction de l'atlas cornen par le calcul des moyennes des lvations de surfaces antrieures et postrieures recales et leurs carts-types associs. Une population de 100 cornes saines a t utilise pour construire l'atlas cornen normal. Pour visualiser latlas, on a eu recours des cartes topographiques couleurs similairement ce quoffrent dj les systmes topographiques actuels. Enfin, des observations ont t ralises sur l'atlas cornen refltant sa prcision et permettant de dvelopper une meilleure connaissance de lanatomie cornenne.
Resumo:
Thse ralise en cotutelle entre l'Universit de Montral et l'Universit de Technologie de Troyes
Resumo:
Utilisant les plus recentes donnees recueillies par le detecteur ATLAS lors de collisions pp a 7 et 8 TeV au LHC, cette these etablira des contraintes severes sur une multitude de modeles allant au-dela du modele standard (MS) de la physique des particules. Plus particulierement, deux types de particules hypothetiques, existant dans divers modeles theoriques et qui ne sont pas presentes dans le MS, seront etudies et sondes. Le premier type etudie sera les quarks-vectoriels (QV) produits lors de collisions pp par lentremise de couplages electrofaibles avec les quarks legers u et d. On recherchera ces QV lorsquils se desintegrent en un boson W ou Z, et un quark leger. Des arguments theoriques etablissent que sous certaines conditions raisonnables la production simple dominerait la production en paires des QV. La topologie particuliere des evenements en production simple des QV permettra alors la mise en oeuvre de techniques doptimisation efficaces pour leur extraction des bruits de fond electrofaibles. Le deuxieme type de particules recherche sera celles qui se desintegrent en WZ lorsque ces bosons de jauges W, et Z se desintegrent leptoniquement. Les etats finaux detectes par ATLAS seront par consequent des evenements ayant trois leptons et de lenergie transverse manquante. La distribution de la masse invariante de ces objets sera alors examinee pour determiner la presence ou non de nouvelles resonances qui se manifesterait par un exces localise. Malgre le fait qua premiere vue ces deux nouveaux types de particules nont que tres peu en commun, ils ont en realite tous deux un lien etroit avec la brisure de symetrie electrofaible. Dans plusieurs modeles theoriques, lexistence hypothetique des QV est propose pour annuler les contributions du quark top aux corrections radiatives de la masse du Higgs du MS. Parallelement, dautres modeles predisent quant a eux des resonances en WZ tout en suggerant que le Higgs est une particule composite, chambardant ainsi tout le sector Higgs du MS. Ainsi, les deux analyses presentees dans cette these ont un lien fondamental avec la nature meme du Higgs, elargissant par le fait meme nos connaissances sur lorigine de la masse intrinseque des particules. En fin de compte, les deux analyses nont pas observe dexces significatif dans leurs regions de signal respectives, ce qui permet detablir des limites sur la section efficace de production en fonction de la masse des resonances.
Resumo:
De nombreux problmes pratiques qui se posent dans dans le domaine de la logistique, peuvent tre modliss comme des problmes de tournes de vhicules. De faon gnrale, cette famille de problmes implique la conception de routes, dbutant et se terminant un dpt, qui sont utilises pour distribuer des biens un nombre de clients gographiquement dispers dans un contexte o les cots associs aux routes sont minimiss. Selon le type de problme, un ou plusieurs dpts peuvent-tre prsents. Les problmes de tournes de vhicules sont parmi les problmes combinatoires les plus difficiles rsoudre. Dans cette thse, nous tudions un problme doptimisation combinatoire, appartenant aux classes des problmes de tournes de vhicules, qui est lie au contexte des rseaux de transport. Nous introduisons un nouveau problme qui est principalement inspir des activits de collecte de lait des fermes de production, et de la redistribution du produit collect aux usines de transformation, pour la province de Qubec. Deux variantes de ce problme sont considres. La premire, vise la conception dun plan tactique de routage pour le problme de la collecte-redistribution de lait sur un horizon donn, en supposant que le niveau de la production au cours de lhorizon est fix. La deuxime variante, vise fournir un plan plus prcis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de lhorizon considr. Dans la premire partie de cette thse, nous dcrivons un algorithme exact pour la premire variante du problme qui se caractrise par la prsence de fentres de temps, plusieurs dpts, et une flotte htrogne de vhicules, et dont lobjectif est de minimiser le cot de routage. cette fin, le problme est modlis comme un problme multi-attributs de tournes de vhicules. Lalgorithme exact est bas sur la gnration de colonnes impliquant un algorithme de plus court chemin lmentaire avec contraintes de ressources. Dans la deuxime partie, nous concevons un algorithme exact pour rsoudre la deuxime variante du problme. cette fin, le problme est modlis comme un problme de tournes de vhicules multi-priodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donn. De nouvelles stratgies sont proposes pour rsoudre le problme de plus court chemin lmentaire avec contraintes de ressources, impliquant dans ce cas une structure particulire tant donn la caractristique multi-priodes du problme gnral. Pour rsoudre des instances de taille raliste dans des temps de calcul raisonnables, une approche de rsolution de nature heuristique est requise. La troisime partie propose un algorithme de recherche adaptative grands voisinages o de nombreuses nouvelles stratgies dexploration et dexploitation sont proposes pour amliorer la performances de lalgorithme propos en termes de la qualit de la solution obtenue et du temps de calcul ncessaire.
Resumo:
Nous tudions la gestion de centres d'appels multi-comptences, ayant plusieurs types d'appels et groupes d'agents. Un centre d'appels est un systme de files d'attente trs complexe, o il faut gnralement utiliser un simulateur pour valuer ses performances. Tout d'abord, nous dveloppons un simulateur de centres d'appels bas sur la simulation d'une chane de Markov en temps continu (CMTC), qui est plus rapide que la simulation conventionnelle par vnements discrets. l'aide d'une mthode d'uniformisation de la CMTC, le simulateur simule la chane de Markov en temps discret imbrique de la CMTC. Nous proposons des stratgies pour utiliser efficacement ce simulateur dans l'optimisation de l'affectation des agents. En particulier, nous tudions l'utilisation des variables alatoires communes. Deuximement, nous optimisons les horaires des agents sur plusieurs priodes en proposant un algorithme bas sur des coupes de sous-gradients et la simulation. Ce problme est gnralement trop grand pour tre optimis par la programmation en nombres entiers. Alors, nous relaxons l'intgralit des variables et nous proposons des mthodes pour arrondir les solutions. Nous prsentons une recherche locale pour amliorer la solution finale. Ensuite, nous tudions l'optimisation du routage des appels aux agents. Nous proposons une nouvelle politique de routage bas sur des poids, les temps d'attente des appels, et les temps d'inoccupation des agents ou le nombre d'agents libres. Nous dveloppons un algorithme gntique modifi pour optimiser les paramtres de routage. Au lieu d'effectuer des mutations ou des croisements, cet algorithme optimise les paramtres des lois de probabilit qui gnrent la population de solutions. Par la suite, nous dveloppons un algorithme d'affectation des agents bas sur l'agrgation, la thorie des files d'attente et la probabilit de dlai. Cet algorithme heuristique est rapide, car il n'emploie pas la simulation. La contrainte sur le niveau de service est convertie en une contrainte sur la probabilit de dlai. Par aprs, nous proposons une variante d'un modle de CMTC bas sur le temps d'attente du client la tte de la file. Et finalement, nous prsentons une extension d'un algorithme de coupe pour l'optimisation stochastique avec recours de l'affectation des agents dans un centre d'appels multi-comptences.
Resumo:
We consider envy-free (and budget-balanced) rules that are least manipulable with respect to agents counting or with respect to utility gains. Recently it has been shown that for any profile of quasi-linear preferences, the outcome of any such least manipulable envy-free rule can be obtained via agent-k-linked allocations. This note provides an algorithm for identifying agent-k-linked allocations.
Resumo:
Le problme de tournes de vhicules (VRP), introduit par Dantzig and Ramser en 1959, est devenu l'un des problmes les plus tudis en recherche oprationnelle, et ce, en raison de son intrt mthodologique et de ses retombes pratiques dans de nombreux domaines tels que le transport, la logistique, les tlcommunications et la production. L'objectif gnral du VRP est d'optimiser l'utilisation des ressources de transport afin de rpondre aux besoins des clients tout en respectant les contraintes dcoulant des exigences du contexte dapplication. Les applications relles du VRP doivent tenir compte dune grande varit de contraintes et plus ces contraintes sont nombreuse, plus le problme est difficile rsoudre. Les VRPs qui tiennent compte de lensemble de ces contraintes rencontres en pratique et qui se rapprochent des applications relles forment la classe des problmes riches de tournes de vhicules. Rsoudre ces problmes de manire efficiente pose des dfis considrables pour la communaut de chercheurs qui se penchent sur les VRPs. Cette thse, compose de deux parties, explore certaines extensions du VRP vers ces problmes. La premire partie de cette thse porte sur le VRP priodique avec des contraintes de fentres de temps (PVRPTW). Celui-ci est une extension du VRP classique avec fentres de temps (VRPTW) puisquil considre un horizon de planification de plusieurs jours pendant lesquels les clients n'ont gnralement pas besoin dtre desservi tous les jours, mais plutt peuvent tre visits selon un certain nombre de combinaisons possibles de jours de livraison. Cette gnralisation tend l'ventail d'applications de ce problme diverses activits de distributions commerciales, telle la collecte des dchets, le balayage des rues, la distribution de produits alimentaires, la livraison du courrier, etc. La principale contribution scientifique de la premire partie de cette thse est le dveloppement d'une mta-heuristique hybride dans la quelle un ensemble de procdures de recherche locales et de mta-heuristiques bases sur les principes de voisinages cooprent avec un algorithme gntique afin damliorer la qualit des solutions et de promouvoir la diversit de la population. Les rsultats obtenus montrent que la mthode propose est trs performante et donne de nouvelles meilleures solutions pour certains grands exemplaires du problme. La deuxime partie de cette tude a pour but de prsenter, modliser et rsoudre deux problmes riches de tournes de vhicules, qui sont des extensions du VRPTW en ce sens qu'ils incluent des demandes dpendantes du temps de ramassage et de livraison avec des restrictions au niveau de la synchronization temporelle. Ces problmes 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 problmes proviennent de la planification des oprations de systmes logistiques urbains deux niveaux. La difficult de ces problmes rside dans la manipulation de deux ensembles entrelacs de dcisions: la composante des tournes de vhicules qui vise dterminer les squences de clients visits par chaque vhicule, et la composante de planification qui vise faciliter l'arrive des vhicules selon des restrictions au niveau de la synchronisation temporelle. Auparavant, ces questions ont t abordes sparment. La combinaison de ces types de dcisions dans une seule formulation mathmatique et dans une mme mthode de rsolution devrait donc donner de meilleurs rsultats que de considrer ces dcisions sparment. Dans cette tude, nous proposons des solutions heuristiques qui tiennent compte de ces deux types de dcisions simultanment, et ce, d'une manire complte et efficace. Les rsultats de tests exprimentaux confirment la performance de la mthode propose lorsquon la compare aux autres mthodes prsentes dans la littrature. En effet, la mthode dveloppe propose des solutions ncessitant moins de vhicules et engendrant de moindres frais de dplacement pour effectuer efficacement la mme quantit de travail. Dans le contexte des systmes logistiques urbains, nos rsultats impliquent une rduction de la prsence de vhicules dans les rues de la ville et, par consquent, de leur impact ngatif sur la congestion et sur lenvironnement.
Resumo:
La gestion des ressources, quipements, quipes de travail, et autres, devrait tre prise en compte lors de la conception de tout plan ralisable pour le problme de conception de rseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de rseaux de services restent limits. La prsente thse a pour objectif de combler cette lacune en faisant lexamen de problmes de conception de rseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thse se dcline en trois tudes portant sur la conception de rseaux. La premire tude considre le problme 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 mme que ses contraintes design-balance, font quil apparat comme sous-problme dans de nombreux problmes relis la conception de rseaux de services, do lintrt dtudier le DBCMND dans le contexte de cette thse. Nous proposons une nouvelle approche pour rsoudre ce problme combinant la recherche tabou, la recomposition de chemin, et une procdure dintensification de la recherche dans une rgion particulire de lespace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions ralisables. Ensuite la recomposition de chemin est utilise pour augmenter le nombre de solutions ralisables. Les solutions trouves par ces deux mta-heuristiques permettent didentifier un sous-ensemble darcs qui ont de bonnes chances davoir un statut ouvert ou ferm dans une solution optimale. Le statut de ces arcs est alors fix selon la valeur qui prdomine dans les solutions trouves pralablement. Enfin, nous utilisons la puissance dun solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problme restreint par le statut fix ouvert/ferm de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problmes de grandes tailles dans des temps raisonnables. Cette recherche est publie dans la revue scientifique Journal of heuristics. La deuxime tude introduit la gestion des ressources au niveau de la conception de rseaux de services en prenant en compte explicitement le nombre fini de vhicules utiliss chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la gnration de colonnes et des heuristiques bases sur une formulation en cycles est ainsi propose. La gnration de colonnes rsout une relaxation linaire du problme de conception de rseaux, gnrant des colonnes qui sont ensuite utilises par le slope-scaling. Le slope-scaling rsout une approximation linaire du problme de conception de rseaux, do lutilisation dune heuristique pour convertir les solutions obtenues par le slope-scaling en solutions ralisables pour le problme original. Lalgorithme se termine avec une procdure de perturbation qui amliore les solutions ralisables. Les tests montrent que lalgorithme propos est capable de trouver de bonnes solutions au problme de conception de rseaux de services avec un nombre fixe des ressources chaque terminal. Les rsultats de cette recherche seront publis dans la revue scientifique Transportation Science. La troisime tude largie nos considrations sur la gestion des ressources en prenant en compte lachat ou la location de nouvelles ressources de mme que le repositionnement de ressources existantes. Nous faisons les hypothses suivantes: une unit de ressource est ncessaire pour faire fonctionner un service, chaque ressource doit retourner son terminal dorigine, il existe un nombre fixe de ressources chaque terminal, et la longueur du circuit des ressources est limite. Nous considrons 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 diffrents terminaux, 3) externalisation de certains services. Nous prsentons une formulation intgre combinant les dcisions relies la gestion des ressources avec les dcisions relies la conception des rseaux de services. Nous prsentons galement une mthode de rsolution matheuristique combinant le slope-scaling et la gnration de colonnes. Nous discutons des performances de cette mthode de rsolution, et nous faisons une analyse de limpact de diffrentes dcisions de gestion des ressources dans le contexte de la conception de rseaux de services. Cette tude sera prsente au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En rsum, trois tudes diffrentes sont considres dans la prsente thse. La premire porte sur une nouvelle mthode 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 loptimisation exacte. Dans la deuxime tude, nous prsentons un nouveau modle de conception de rseaux de services prenant en compte un nombre fini de ressources chaque terminal. Nous y proposons une matheuristique avance base sur la formulation en cycles comprenant le slope-scaling, la gnration de colonnes, des heuristiques et loptimisation exacte. Enfin, nous tudions lallocation des ressources dans la conception de rseaux de services en introduisant des formulations qui modlent le repositionnement, lacquisition et la location de ressources, et lexternalisation de certains services. cet gard, un cadre de solution slope-scaling dvelopp partir dune formulation en cycles est propos. Ce dernier comporte la gnration de colonnes et une heuristique. Les mthodes proposes dans ces trois tudes ont montr leur capacit trouver de bonnes solutions.
Resumo:
Le Canada accepte des demandes dasile sur la base de l'orientation sexuelle depuis plus de 20 ans. Quoi quil en soit, cette recherche permet de douter du fait que les demandes sur la base de lorientation sexuelle dposes par des femmes soient traites de faon adquate. Pour garantir laccs la protection des femmes appartenant des minorits sexuelles, une analyse du risque de perscution fond sur l'orientation sexuelle doit incorporer des considrations de genre ainsi que divers autres facteurs dordre social et culturel. partir dune tude de cas de demandes du statut de refugi dposes par des femmes sur la base de lorientation sexuelle et rejetes par la Commission de l'immigration et du statut de rfugi entre 2010 et 2013, cette recherche identifie des procds dcisionnels problmatiques qui font obstacle au droit dasile de ces femmes. Les rsultats de cette tude rvlent quune analyse intersectionnelle, laquelle prend acte des formes varies et multiples de loppression dans un contexte social donn, est dimportance cruciale pour une valuation claire et non tronque des risques de perscution pour les minorits sexuelles fminines. la lumire de ces rsultats, ce mmoire propose quune analyse intersectionnelle accompagne une ncessaire formation pour les membres de la Commission de l'immigration et du statut de rfugi du Canada sur des questions particulires des minorits sexuelles.
Resumo:
La microscopie par fluorescence de cellules vivantes produit de grandes quantits de donnes. Ces donnes sont composes dune grande diversit au niveau de la forme des objets dintrts et possdent un ratio signaux/bruit trs bas. Pour concevoir un pipeline dalgorithmes efficaces en traitement dimage de microscopie par fluorescence, il est important davoir une segmentation robuste et fiable tant donn que celle-ci constitue ltape initiale du traitement dimage. Dans ce mmoire, je prsente MinSeg, un algorithme de segmentation dimage de microscopie par fluorescence qui fait peu dassomptions sur limage et utilise des proprits statistiques pour distinguer le signal par rapport au bruit. MinSeg ne fait pas dassomption sur la taille ou la forme des objets contenus dans limage. Par ce fait, il est donc applicable sur une grande varit dimages. Je prsente aussi une suite dalgorithmes pour la quantification de petits complexes dans des expriences de microscopie par fluorescence de molcules simples utilisant lalgorithme de segmentation MinSeg. Cette suite dalgorithmes a t utilise pour la quantification dune protine nomme CENP-A qui est une variante de lhistone H3. Par cette technique, nous avons trouv que CENP-A est principalement prsente sous forme de dimre.
Resumo:
Dans des contextes de post-urgence tels que le vit la partie occidentale de la Rpublique Dmocratique du Congo (RDC), lun des dfis cruciaux auxquels font face les hpitaux ruraux est de maintenir un niveau de mdicaments essentiels dans la pharmacie. Sans ces mdicaments pour traiter les maladies graves, limpact sur la sant de la population est significatif. Les hpitaux encourent galement des pertes financires dues la premption lorsque trop de mdicaments sont commands. De plus, les cots du transport des mdicaments ainsi que du superviseur sont trs levs pour les hpitaux isols ; les cots du transport peuvent eux seuls dpasser ceux des mdicaments. En utilisant la province du Bandundu, RDC pour une tude de cas, notre recherche tente de dterminer la faisabilit (en termes et de la complexit du problme et des conomies potentielles) dun problme de routage synchronis pour la livraison de mdicaments et pour les visites de supervision. Nous proposons une formulation du problme de tournes de vhicules avec capacit limite qui gre plusieurs exigences nouvelles, soit la synchronisation des activits, la prsance et deux frquences dactivits. Nous mettons en uvre une heuristique cluster first, route second avec une base de donnes gospatiales qui permet de rsoudre le problme. Nous prsentons galement un outil Internet qui permet de visualiser les solutions sur des cartes. Les rsultats prliminaires de notre tude suggrent quune solution synchronise pourrait offrir la possibilit aux hpitaux ruraux daugmenter laccessibilit des services mdicaux aux populations rurales avec une augmentation modique du cot de transport actuel.
