L'environnement de départ de ce projet était le site Web SmartShopping, un portail permettant de naviguer à travers les différents spéciaux quotidiens des magasins d'alimentation de l'île de Montréal, puis de les ajouter à un panier, et enfin d'observer le trajet nécessaire afin de visiter les différents magasins d'où proviennent ces spéciaux. Le but du projet était d'implémenter l'affichage d'un trajet optimal de type Voyageur de Commerce Généralisé entre les différentes franchises des enseignes à visiter, sur une carte GoogleMapsTM, puis incorporer cette fonctionnalité au site Web SmartShopping. L'algorithme précédemment en place choisissait, pour établir un trajet, les magasins qui se trouvaient les plus proches du point de départ, soit l'adresse du client, pour chaque enseigne à visiter. Ce travail consistait donc à comparer les algorithmes de pointe du moment afin d'implémenter le meilleur d'entre eux en termes de rapidité et d'optimalité, pour un échantillon de petite taille. Après analyse et comparaison, un algorithme de type génétique créé par Tasgetiren et al. [TSPL07] a été implémenté en langage C++, en relation avec une page Web codée en PHP, et avec transmission des paramètres par fichiers texte. Par rapport à l'ancien algorithme, les résultats de ce travail montrent une nette amélioration des trajets proposés, et ceci dans l'ensemble des cas testés, avec une moyenne de baisse des distances de 12%, pour les cas de 2 à 5 magasins. Le site Web avec sa nouvelle fonctionnalité peut être consulté à l'adresse URL suivante : http://www.trex.uqam.ca/~smartshopping. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithme, algorithme de voyageur de commerce généralisé, trajet optimal, site web

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

A Rome, les délégations des Etats présents ont convenu que la CPI n’exercera sa compétence à l’égard des crimes relevant du Statut que s’ils ont été commis sur le territoire, à bord d’un navire ou aéronef ou encore par le ressortissant d’un Etat partie et l’ont expressément codifié dans l’article 12, § 2 du Statut. Rédigé dans les dernières heures de la Conférence, le mécanisme a laissé en suspens beaucoup de questions brûlantes. Depuis, la portée de la disposition en ce qui concerne son champ d’application et son contenu est très discutée. Toutes ces lacunes et inquiétudes ont jusqu’à ce jour entretenu le malentendu persistant observé à l’égard de la Cour pénale internationale et semblent nuire à la clarté de sa mission. La présente étude vient aider à fixer l’état du droit sur les problèmes d’ordre pénal qui surgissent encore. Il s’agira, à partir d’un examen approfondi de la jurisprudence et de la pratique, de clarifier, dans une première partie, les concepts de rattachements territorial et personnel définis dans le Statut de Rome, c'est-à-dire d’en délimiter les contours et d’en déterminer sa consistance. Dans une seconde partie, l’on mettra en lumière la manière dont les deux titres de compétence énoncés alternativement dans le Statut de Rome permettent à la CPI d’étendre sa compétence, en toute légalité, à la fois à l’égard des Etats parties et des Etats non parties / In Rome, the delegations of the participating States agreed that the International Criminal Court (ICC) would only exercise jurisdiction regarding crimes set out in the Statute provided that these crimes were committed on the territory, on board a vessel or aircraft or by a national of a State Party, as stressed in article 12, § 2 of the Statute. This mechanism, which was drafted in the very last hours of the Conference, left open many critical issues. Since then, the scope and content of this provision is the subject of heated debate. These gaps, and the concern they raised until now, have perpetuated the persisting misunderstanding about the ICC and seem to undermine the clarity of the Court’s mission. The study helps to assess the state of the law on the criminal issues that remain so far. As a first step, it aims at clarifying, on the basis of an extensive review of the case-law and practice, the concepts of territorial and personal links defined in the Rome Statute, by marking out their contours and determining their substance. Secondly, it will be demonstrated how these two grounds of jurisdiction set out in the Rome Statute allow the ICC to lawfully expand its jurisdiction, both vis-à-vis State Parties as well as non-Party States.

Nous considèrerons ici les modèles linéaires de multiflots, en mettant l'accent sur leurs multiples applications, notamment dans les domaines de l'ordonnancement et de la gestion de production. Il est bien connu que ces problèmes, présentés sous forme de programmes linéaires, sont difficiles à résoudre, contrairement à leurs homologues en flot simple. Les méthodes de résolution classiques proposent, déjà dans le cas continu, des solutions approchées. On distingue: les méthodes de décomposition par les prix, par les ressources, ainsi que les techniques de partitionnement. Si l'on rajoute la contrainte d'intégralité sur les flots, ces problèmes deviennent extrêmement difficiles. Nous nous sommes intéressés à un cas particulier des problèmes de multiflots, à savoir: le biflot entier de coût minimum. Nous avons développé une approche de résolution heuristique basée sur un principe de décomposition mixte, opérant itérativement, à la fois par une allocation de ressources et par un ajustement des coûts. L'implémentation de cette approche met en évidence des résultats prometteurs, obtenus sur des problèmes de biflot purs, générés aléatoirement. Nous avons donc envisagé une deuxième application sur des problèmes de biflot plus structurés. Ces problèmes de biflot ont été proposés pour la modélisation du problème de voyageur de commerce. Cette application débouche d'une part, sur l'utilisation d'un algorithme de recherche d'un circuit hamiltonien dans un graphe, et d'autre part, sur le développement de techniques heuristiques pour la construction de tournées intéressantes

Le polyèdre associé à un problème d'optimisation combinatoire est l'enveloppe convexe des (vecteurs d'incidence des) solutions réalisables de ce problème. De nombreux problèmes d'optimisation combinatoire se formulent comme une maximisation de fonctions linéaires sur les polyèdres qui leurs sont associés. La description du polyèdre par un système d'inéquations linéaires est intimement liée à la résolution du problème correspondant, par le biais de la programmation linéaire. Afin de déterminer un tel système, une approche classique consiste à décomposer le problème en sous-problèmes tels que les polyèdres associés soient connus ; une composition ultérieure de ces derniers conduit à une description du polyèdre associé au problème considéré. L'objet principal de cette thèse est l'étude de la composition des polyèdres. Dans un premier temps, une approche de composition, basée sur la programmation dynamique et les méthodes de projection polyédrale, est étudiée et des résultats généraux sont proposés, permettant ainsi d'unifier des recherches existantes dans ce domaine. Cette approche est, ensuite, appliquée à la composition de polyèdres associés au problème du voyageur de commerce. En seconde partie, considérant le problème du stable, des opérations sur les graphes (composition par identification de sous-graphes de deux graphes donnés, adjonction d'une nouvelle arête) sont traitées. Des résultats polyédraux sont donc donnés, et des conséquences concernant la perfection et la h-perfection des graphes sont montrés