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.