Un déploiement adéquat et une bonne gestion des ambulances amènent des temps de réponse plus courts lors d'un appel d'urgence et ainsi permettent de réduire la souffrance, la mortalité et les conséquences néfastes sur la santé des patients. Ce mémoire est divisé en deux parties et adresse sous forme de deux articles les problèmes de la localisation des ambulances et de leur gestion. L'objectif du premier article est de résoudre le problème de localisation d'ambulances multi-périodes en faisant l'hypothèse d'une demande déterministe, dynamique et cyclique. Un modèle mathématique ainsi que deux méthodes heuristiques sont proposés pour aider à résoudre ce problème. La première heuristique utilise de façon répétitive la version mono-période du modèle mathématique proposé alors que la deuxième est une heuristique itérative composée d'une phase de construction et une phase d'amélioration. L'efficacité de ces méthodes est démontrée par leur application pour résoudre des problèmes fictifs ainsi qu'un problème réel fourni par la corporation Urgences-santé. Les résultats obtenus avec les deux méthodes heuristiques nous indiquent que ces méthodes, en plus d'être très rapides, donnent des plans de déploiement près du plan optimal. De plus, la méthode heuristique basée sur le modèle mono-période semble dominer la méthode heuristique itérative sur tous les points en plus d'être plus simple. L'objectif du deuxième article est d'évaluer l'efficacité de plusieurs règles de répartition dans le cadre de la gestion des demandes d'intervention d'un réseau de service ambulancier. Deux types de décisions font l'objet de cette étude : le choix d'une ambulance pour répondre à une demande d'intervention et le choix du poste d'attente où ce véhicule sera redéployé après son intervention. Les règles généralement utilisées en pratique sont comparées à des règles visant non seulement la réduction des temps d'attente mais aussi le maintient d'une bonne couverture territoriale. Différentes règles sont testées sur des problèmes fictifs ainsi que sur un problème réel fourni par la corporation Urgences-santé. Les résultats obtenus démontrent que l'application d'une règle d'assignation simple comme affecter l'ambulance qui peut se rendre le plus rapidement possible sur les lieux de la demande d'intervention peut être efficace seulement si un bon plan de déploiement et de redéploiement est maintenu. On démontre que l'utilisation d'une règle de redéploiement visant la maximisation de la couverture du territoire permet d'atteindre un bon niveau d'efficacité.

Dans l'industrie de la fabrication de planchers de bois pour les remorques, la qualité d'un plancher est directement liée à la position relative des lattes de bois. Le procédé de fabrication actuellement en place chez notre partenaire industriel utilise une main-d'oeuvre abondante. Les planchers sont produits en continu et puisque les décisions de positionnement de lattes doivent se prendre très rapidement (chaque employé doit placer une latte à toutes les 1,5 seconde), même des employés d'expérience peuvent commettre des erreurs. Dans ce mémoire, nous proposons des méthodes rapides et efficaces pouvant être utilisées par un processus d'assemblage mécanique. Ces méthodes ont été utilisées pour assembler des planchers à l'aide de simulation par ordinateur. Par comparaison à l'assemblage manuel, qui produit des planchers ayant environ 5% de joints défectueux, nos méthodes d'assemblage produisent des planchers presque parfaits.

Cette recherche introduit un modèle de décision multiobjectif qui aide le gestionnaire de projets à allouer les ressources à son projet. Le modèle comporte trois axes de décision représentant les compromis à faire entre la durée du projet, le coût du projet et les quantités de ressources allouées. L'allocation des ressources est déterminée en considérant le coût de chaque ressource. Le modèle incorpore le processus d'assignation des ressources, une problématique typique de l'affectation des ressources en gestion projets, à celui de !'ordonnancement des activités. Pour le résoudre, il a fallu concevoir et expérimenter de nouveaux algorithmes. La recherche comporte trois volets où chacun des volets alimente le volet suivant. Le premier volet propose de nouvelles procédures pour minimiser la durée du projet sous contraintes de disponibilités variables de ressources, dans le cas de problèmes ayant des activités avec un seul mode de réalisation ou de problèmes ayant des activités avec plusieurs modes de réalisation. Ces procédures comprennent une nouvelle règle de priorité selon un schème que nous qualifions d'ensembliste et une adaptation de la méthode Tabou. Les résultats de l'expérimentation montrent l'efficacité de la nouvelle règle de priorité et de l'adaptation de la méthode Tabou. Le deuxième volet propose des procédures pour minimiser le coût de disponibilité et le coût d'assignation des ressources allouées sous contrainte d'une date d'échéance du projet. La procédure incorpore l'adaptation de la méthode Tabou élaborée au volet précédent. Les résultats de l'expérimentation montrent la bonne performance des procédures développées. Le troisième volet propose une approche interactive par laquelle le gestionnaire de projets évalue des choix d'allocation de ressources afin de parvenir à une solution de compromis entre les trois axes de décision. Pour y parvenir, on évalue des solutions dans une région délimitée par les buts du gestionnaire de projets au lieu d'effectuer une approximation de la frontière efficace. L'expérimentation montre la faisabilité de l'approche interactive ainsi que l'efficacité de l'adaptation proposée de la méthode Tabou. Ces trois volets permettent d'élaborer l'architecture d'un Système Interactif d'Aide à la Décision pour l'allocation multiobjective des ressources en gestion de projets.

Les problèmes d'optimisation combinatoire sont généralement NP-difficiles et les méthodes exactes demeurent inefficaces pour les résoudre rapidement. Les métaheuristiques sont des méthodes génériques de résolution connues et utilisées pour leur efficacité. Elles possèdent souvent plusieurs paramètres qui s'avèrent fastidieux à régler pour obtenir de bonnes performances. Il est alors intéressant de chercher à rendre plus évident, voire à automatiser, ce réglage des paramètres. Le paysage d'un problème d'optimisation combinatoire est une structure, basée sur la notion de voisinage, permettant de caractériser le problème puis de suivre la dynamique d'une méthode d'optimisation pour comprendre son efficacité. Les travaux de cette thèse portent sur l'analyse de paysage de problèmes d'optimisation combinatoire et le lien étroit avec certaines classes de métaheuristiques, basées sur une exploration du voisinage des solutions. Ainsi, nous montrons l'influence de la structure de paysage sur la dynamique d'une métaheuristique, pour deux problèmes issus de la logistique. Ensuite, nous analysons les caractéristiques du paysage qui permettent de concevoir et/ou paramétrer des métaheuristiques, principalement des recherches locales, efficaces. La neutralité est, en particulier, une caractéristique structurelle importante des paysages. De tels paysages présentent de nombreux plateaux bloquant la progression d'une recherche locale. Après une analyse fine des plateaux, nous prouvons que cette structure neutre ne doit pas être ignorée. Puis, nous utilisons plusieurs informations liées à la neutralité, et plus particulièrement aux plateaux bloquants, pour concevoir une première recherche locale simple à mettre en œuvre et efficace. Enfin, pour approfondir nos travaux sur les structures neutres, nous avons choisi d'exploiter la neutralité à tous les niveaux du paysage pour concevoir une nouvelle recherche locale basée sur la capacité des solutions d'un même plateau à produire une amélioration. Une stratégie de guidage vers cette solution est alors proposée. La thèse se termine par l'analyse comparative des deux méthodes d'optimisation proposées pour les problèmes neutres afin d'en exploiter de nouvelles caractéristiques, et ainsi, renforcer le lien entre l'analyse de paysage et la conception de méthodes efficaces.

<p>De nos jours, il est peu de processus ou de tâches qui ne requièrent pas l'optimisation d'une quantité :diminuer le temps de livraison, diminuer l'espace utilisé, réduire les efforts de développement, C'est donc sans surprise que la recherche en optimisation soit l'un des domaines les plus actifs des sciences des technologies de l'information. En optimisation combinatoire, les métaheuristiques sont à compter parmi le fleuron des techniques algorithmiques. Mais ce succès est encore au prix d'une quantité significative de temps de conception et développement. Ne serait-il pas possible d'aller encore plus loin ?D'automatiser la préparation des métaheuristiques ?En particulier dans des conditions telles le manque de temps, l'ignorance de techniques spécialisées ou encore la mauvaise compréhension du problème traité ?C'est ce à quoi nous répondons dans la présente thèse au moyen d'une approche de méta-modélisation de la recherche :l'heuristique de la Gestalt.</p><p><p><p>Considérant la représentation du problème comme un levier que l'on peut activer sous le processus de recherche mené par une métaheuristique, la thèse suggère la construction d'une abstraction de cette représentation capable d'assister la métaheuristique à trouver de bonnes solutions en contraignant sa recherche. Cette approche, inspirée de la psychologie de la Gestalt, nous l'appelons l'heuristique de la Gestalt. Son fonctionnement repose principalement sur l'agrégation des variables de la représentation. Cette agrégation donne lieu à une abstraction structurelle, mais également fonctionnelle en ce sens que les opérateurs de la métaheuristique doivent désormais respecter l'intégrité des agrégats définis.</p><p><p><p>Après avoir établi le contexte de la dissertation, nous discutons de la transposition de la psychologie de la Gestalt dans le cadre de l'optimisation combinatoire et des métaheuristiques. S'ensuit la formalisation de l'heuristique de la Gestalt et la description de sa réalisation. Finalement, une série d'études expérimentales sont menées pour éprouver le concept avancé et valider l'implémentation basée sur les algorithmes évolutionnistes que nous proposons. En conclusion, nous affirmons que l'implémentation de l'heuristique de la Gestalt basée, entre autres, sur un algorithme génétique de groupement est capable d'assister positivement des algorithmes génétiques lorsque les instances de problèmes traitées possèdent une structure riche et complexe, que leur taille est importante, que l'on est tôt dans le processus d'optimisation et que l'algorithme génétique n'est pas paramétré spécifiquement.</p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization.<p><p>* A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. <p><p>* The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier.<p><p>* Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception.<p><p>* ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem.<p><p>* ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.<p><p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished