Méthodes exactes et heuristiques pour le problème de tournées de véhicules avec fenêtres de temps et réutilisation de véhicules

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future.

Models and algorithms for the capacitated location-routing problem

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48].

Discussions politiques sur Internet : les raisons expliquant le degré de participation de jeunes adultes québécois

Ce mémoire porte sur les raisons qu’ont de jeunes adultes québécois de discuter ou non de politique sur Internet. Il s’inscrit dans le contexte général de l’avènement du Web 2.0 et dans le contexte particulier des élections canadiennes de mai 2011. Au niveau théorique, nous avons mobilisé la théorie de l’agir communicationnel du philosophe allemand Jürgen Habermas ainsi que sa conception de la sphère publique. Du point de vue méthodologique, nous avons étudié un échantillon composé de jeunes adultes québécois, hommes et femmes, âgés de 19 à 30 ans, qui habitent à Montréal et dans ses environs. Ces jeunes citoyens ont été interrogés dans le cadre de quatre focus groups. Les données recueillies ont été analysées selon une méthode d’extraction des arguments en accord avec la méthodologie de la reconstruction rationnelle. Les résultats ont permis d’exposer plusieurs raisons qu’ont avancées les jeunes adultes interrogés pour expliquer leur degré de participation à des discussions politiques sur Internet. Celles-­‐ci ont été regroupées en quatre thèmes: le manque de connaissances et l’aspect public; la conscientisation et l’obtention de feedback; la réaction par rapport au contenu, la composition du réseau et la valeur de l’information; le face à face, l’anonymat et les sujets controversés. Ces résultats ont été discutés en considérant ceux obtenus par d’autres chercheurs afin de faire ressortir les apports de cette étude au domaine de la communication. La discussion a également permis d’adopter un point de vue théorique critique pour explorer ce que les résultats de ce mémoire révèlent sur l’état de la sphère publique québécoise.

L'évaluation pédagogique des activités éducatives mises en ligne sur Internet par les musées québécois

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Les interactions collaboratives dans des cours à distance sur Internet

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.

La chasse aux trésors subaquatiques : portrait d'une industrie marginale à l'ère de l'internet

En marge des recherches archéologiques traditionnelles, nous retrouvons aujourd’hui des compagnies privées qui contractent des accords et obtiennent des permis leur donnant le droit de prélever des objets à des fins lucratives sur les vestiges archéologiques submergés. Ces pratiques commerciales causent une controverse vive et enflammée au sein du monde archéologique. Le principal point de litiges concerne la mise en vente des objets extraits lors de fouille. La mise en marché du patrimoine archéologique éveille les fibres protectionnistes. Cela incite certains organismes à poser des gestes pour la protection du patrimoine. C’est le cas pour l’UNESCO qui fait la promotion depuis 2001 d’une Convention pour la protection du patrimoine submergé. Malgré tous les arguments à l’encontre des compagnies de « chasse aux trésors », cette Convention est loin de faire l’unanimité des gouvernements à travers le monde, qui ne semblent pas prêts à rendre ces pratiques illégales. Les méthodes utilisées par ces compagnies semblent aussi représenter un point de friction avec les archéologues. Toutefois, la connaissance de leurs pratiques sur le terrain semble très incomplète. De plus, contrairement à une certaine idée préconçue, ces compagnies ne sont pas des « pilleurs de tombes » œuvrant sous le couvert de l’anonymat, mais bien des compagnies dûment enregistrées, œuvrant en toute légalité et passant même des contrats avec les gouvernements. Ce mémoire a donc pour objectif de mettre en lumière les actions réelles des compagnies de chasse aux trésors subaquatiques en regardant leurs méthodes et leur fonctionnement, tels qu’on les voit dans les 10 dernières années. Pour mieux conceptualiser les pratiques de ces compagnies, nous nous interrogerons sur le rapport entre légalité et éthique et, plus précisément, sur l’éthique commerciale et archéologique.

La promotion sur Internet : analyse d’un discours sous l’angle du mythe. Le cas de labels indépendants de rap au Québec

À l’heure où l’industrie de l’enregistrement sonore connait un certain nombre de bouleversements, Internet apparait à la fois comme un responsable d’une crise du disque et comme une plate-forme de diffusion et de promotion de la musique enregistrée. C’est dans ce contexte de mutations des industries culturelles que sont les industries de la musique que les labels indépendants voient les possibilités liées à la promotion se multiplier. Notamment par le biais des sites internet que j’envisage ici comme discours encodé et diffusé. Ce mémoire explore deux sites internet officiels de labels indépendants de rap québécois à l’aide de la proposition de la présence du mythe dans le discours de promotion. S’appuyant sur la théorie de Barthes, mon analyse s’articule autour de l’étude de la signification afin de mettre en lumière la façon dont le mythe fonctionne dans le discours. En m’intéressant principalement à l’image et au texte, je mets notamment en valeur le traitement de l’artiste, de la création musicale et du label dans le discours.

La enseñanza del componente cultural en ELE a través de Internet, con especial referencia al enseignement collégial de Quebec

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Raisonnement clinique avec un simulateur virtuelle de patients sur Internet : l'apprentissage est-il augmenté par l'utilisation d'un groupe de discussion virtuel

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Les campagnes sociales destinées aux jeunes adultes québécois sur Internet : pistes pour l'optimisation des sites Web

Avec la montée en popularité d’Internet et des médias sociaux, de plus en plus d’organismes sociaux et publics, notamment, intègrent des plateformes Web à leurs volets traditionnels. La question d’Internet demeure toutefois peu étudiée eu égard à la publicité sociale. Ce mémoire porte donc sur la question du Web en relation avec les campagnes sociales adressées aux jeunes Québécois de 18 à 25 ans, une population particulièrement réceptive aux nouvelles technologies. Plus exactement, dans cette étude, nous avons analysé trois sites Web rattachés à des campagnes sociales (La vitesse, ça coûte cher de la SAAQ, Les ITSS se propagent du MSSS et 50 000 adeptes, 5 000 toutous de la Fondation CHU Sainte-Justine) dans l’objectif de déterminer leurs forces et leurs faiblesses pour ensuite proposer des pistes pour leur optimisation. C’est à l’aide d’une analyse critique de contenu suivie d’entrevues et d’observations individuelles auprès de 19 participants que nous sommes parvenue à suggérer des pistes pour l’optimisation des sites Web de campagnes sociales destinées aux jeunes adultes québécois. Une des plus grandes difficultés en ce qui a trait à leur conception consiste à choisir les stratégies les plus appropriées pour provoquer un changement d’attitude ou de comportement, a fortiori chez ceux qui adoptent des comportements à risque (fumer, conduire en état d’ébriété, avoir des relations sexuelles non protégées); des stratégies qui, pour être plus efficaces, devraient être adaptées en fonction des caractéristiques propres aux publics cibles et aux médias de diffusion. Afin d’analyser adéquatement les campagnes sociales, nous avons fait appel aux théories de la persuasion et aux théories sur l’influence des médias jugées pertinentes dans notre contexte puisqu’elles sont propres à ce type d’étude. Ces approches combinées nous ont permis d’intégrer à l’analyse d’une campagne donnée les contextes qui l’entourent et les pratiques dans lesquelles elle s’inscrit. Cette étude nous a, entre autres, permis de démontrer qu’il existait d’importants écarts entre les attentes et les besoins des internautes et l’offre des sites Web étudiés.

Heuristic solution methods for multi-attribute vehicle routing problems

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques.

A Summary of the American Bar Association’s (ABA) Jurisdiction in Cyberspace Project: “Achieving Legal and Business Order in Cyberspace: A Report on Global Jurisdiction Issues Created by the Internet”

"Suite à plus de deux années de recherches, le projet de l’American Bar Association (ABA) concernant la juridiction du cyberespace, « Achieving Legal and Business Order in Cyberspace: A Report on Global Jurisdiction Issues Created by the Internet », a été publié dans l’édition du mois d’août 2000 de la revue juridique The Business Lawyer. Ce rapport poursuivait deux objectifs distincts : Tout d’abord, effectuer une analyse globale des complexités potentielles entourant les conflits juridictionnels découlant du commerce en ligne. Ensuite, élaborer une liste exhaustive des solutions pouvant être utilisées pour résoudre de tels conflits. Le présent article se veut un résumé concis et accessible des trois grandes sections du « Cyberspace Jurisdiction Report » : (1) les solutions proposées aux problèmes juridictionnels découlant des conflits résultant du commerce électronique ; (2) afin d’appuyer les solutions proposées : l’utilisation d’exemples d’occasions où la technologie a déjà, par le passé, causé la métamorphose de certains paradigmes juridictionnels; et (3) afin d’appuyer les solutions proposées : l’utilisation d’un contexte doctrinal."

RSS et la publication simultanée sur Internet

"La publication simultanée est un paradigme nouveau de diffusion dans Internet. Au lieu de privilégier l'aspect visuel d'une page, la famille de technologies RSS permet de communiquer la structure d'un site, en vue d'une navigation plus systématique et rapide. À l'instar du foisonnement qui caractérisait la bulle Internet du tournant du millénaire, plusieurs saveurs de cette technologie furent développées en parallèle par différents groupes. L'acronyme RSS reflète cette compétition et désigne, successivement, Rich Site Summary (RSS 0.91); RDF Site Summary (RSS 0.9 and 1.0) ainsi que Really Simple Syndication (RSS 2.0). Par ailleurs, Atom 1.0 représente un format RSS entériné par les organes de standardisation d'Internet. Sont présentés les mécanismes de publication et de compilation de fils RSS."

Internet Law - An Attempt at a Polemic Retrospective

"Herbert Burket trace l’évolution des concepts reliés au ""droit de l’Internet"" dans le cadre du droit de l’Union Européenne. Initialement, ce domaine du droit était perçu comme une nouvelle discipline normative. Or, l’auteur soutient que le ""droit de l’Internet"" n’est pas un domaine normatif distinct, mais correspond aux domaines traditionnels auxquels il a été progressivement intégré. Le ""droit de l’Internet"" a amélioré notre compréhension du processus général d’évolution du droit. L’auteur souligne, entre autres, comment le législateur européen a réagi par diverses législations aux nouveaux impératifs technologiques. De plus, ce domaine offre une nouvelle perspective pour l’analyse de l’évolution des normes face aux innovations technologiques. Les tribunaux, les législateurs et les parties privées sont autant d’acteurs qui interviennent à différents moments et sur différents aspects du processus d’évolution du droit. Enfin, on s’attendait à ce que le droit de l’Internet conduise à la mondialisation des normes, à l’autorégulation des acteurs et à une architecture structurelle normative ouverte. L’auteur constate que la mondialisation des normes ne semble pas s’être réalisée. L’autorégulation, dans le domaine de l’Internet, fait référence aux normes de comportement établies par des acteurs privés et mixtes. Enfin, le concept d’architecture structurelle normative réfère au fait que les créateurs d’un système technologique imposent involontairement certaines règles aux utilisateurs, en dépit de l’affirmation qu’un tel système technologique est normativement neutre. L’auteur soutient que ces attentes, bien qu’elles soient toujours présentes au sein de l’activité normative, n’ont plus la même signification qu’au moment de leur formulation originale. Les concepts traditionnels de période normative, de juridiction, d’acteurs et de procédure ont aussi évolué parallèlement au développement du ""droit de l’Internet"", autant dans le cadre de l’environnement normatif de l’Union Européenne que dans celui du droit international en général. L’évolution de ces concepts modifie le processus de création du droit, ainsi que le rôle et les fonctions des intervenants impliqués dans ce processus.L’auteur conclut en soulignant que le concept même de droit a évolué en perdant ses représentations symboliques traditionnelles grâce au développement de l’accès généralisé à l’information, à l’évolution des technologies de l’information et à leur impact culturel."