Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

HAL Id: tel-00605118 https://tel.archives-ouvertes.fr/tel-00605118 Submitted on

HAL Id: tel-00605118 https://tel.archives-ouvertes.fr/tel-00605118 Submitted on 30 Jun 2011 HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entific research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. Approches de modélisation et d’optimisation pour la conception d’un système interactif d’aide au déplacement dans un hypermarché Ismahène Hadj Khalifa To cite this version: Ismahène Hadj Khalifa. Approches de modélisation et d’optimisation pour la conception d’un système interactif d’aide au déplacement dans un hypermarché. Autre. Ecole Centrale de Lille, 2011. Français. NNT : 2011ECLI0008. tel-00605118 N° d’ordre : 150 Thèse préparée au sein LAGIS, FRE CNRS 3303, EC Lille Ecole Doctorale SPI 072 PRES Université Lille Nord-de-France ECOLE CENTRALE DE LILLE THÈSE Présentée en vue d’obtenir le grade de DOCTEUR Discipline : Automatique et Informatique Industrielle Par Ismahène HADJ KHALIFA Maîtrise en Hautes Etudes Commerciales (IHEC Carthage) Master Systèmes d’Information et d’Ingénierie de la Conception (EC Lille) Approches de modélisation et d’optimisation pour la conception d’un système interactif d’aide au déplacement dans un hypermarché Soutenue publiquement le 16 juin 2011 devant le jury : M. Pierre BORNE Ecole Centrale de Lille Président M. Jean-Pierre CAMPAGNE INSA de Lyon Rapporteur M. Gaston LEFRANC Pontificia Universidad Catolica de Valparaiso, Chili Rapporteur M. Khaled MELLOULI Institut des Hautes Etudes Commerciales de Carthage, Tunisie Rapporteur M. Abdelhakim ARTIBA Université de Valenciennes et du Hainaut-Cambrésis Examinateur M. Bernard BARFETY Leroy Merlin Invité M. Abdelkader EL KAMEL Ecole Centrale de Lille Directeur de thèse M. Sami FAIZ Faculté des Science Juridiques, Economiques et de Gestion de Jendouba, Tunisie Examinateur A Baba Fadhil et Hanéna A mon adorable mère et mon cher père A Mehdi, mon cher mari, et à mes beaux parents A tous ceux qui me sont chers Avant-propos 5 Avant-propos Les travaux présentés dans cette thèse ont été réalisés au sein du Laboratoire d’Automatique, Génie Informatique et Signal (LAGIS) de l’Ecole Centrale de Lille et s’inscrivent dans le cadre des activités du Pôle de Compétitivité des Industries du Commerce (PICOM). Cette thèse a été labellisée par le PICOM et a ainsi bénéficié d’une bourse cofinancée Leroy Merlin/Région Nord-Pas-de-Calais. Je tiens à remercier chaleureusement Monsieur Bernard Barfety, Directeur Organisation et Systèmes d'information de Leroy Merlin et Monsieur Didier Lieven, Coordonnateur du PICOM pour la confiance qu’ils m’ont accordée en finançant mes trois années de thèse. C’est un agréable devoir pour moi d’exprimer ma profonde gratitude à mon directeur de thèse Monsieur Abdelkader EL KAMEL. Je tiens à le remercier et lui manifester ma sincère reconnaissance pour ses grandes qualités humaines, son encadrement plein d’enthousiasme et de rigueur et pour la confiance dont il a fait preuve à mon égard. Je suis particulièrement sensible au grand honneur que Monsieur Pierre BORNE me fait en acceptant de présider mon Jury de thèse. Qu’il trouve ici l’expression de ma profonde reconnaissance. Je tiens à exprimer ma vive gratitude à Monsieur Khaled MELLOULI, Monsieur Jean- Pierre CAMPAGNE et Monsieur Gaston LEFRANC pour l’intérêt qu’ils ont bien voulu porter à mes travaux en acceptant d’être les rapporteurs de cette thèse. Qu’ils trouvent ici le témoignage de ma profonde reconnaissance. Je souhaite également témoigner de mes vifs remerciements à Monsieur Sami FAIZ et Monsieur Abdelhakim ARTIBA d’avoir accepté de participer à mon Jury d’Examen. Je tiens à remercier mes collègues de l’équipe dirigée par Monsieur EL KAMEL et en particulier Jin Zhao, Minzhi Luo, Stanislas Legendre, Harald Pillu ainsi que tous mes Avant-propos 6 collègues du LAGIS et tout le personnel de l’Ecole Centrale de Lille pour leur bonne humeur et leur disponibilité. Un témoignage de ma profonde reconnaissance s’adresse à toute ma famille et mes amis : mes parents, mon frère et ma sœur, mes grands-parents, mes tantes et oncles, mes cousins et cousines, ma belle famille, mes amis en Tunisie et en France qui ont toujours cru en moi et encouragé pour aller jusqu’au bout. Un MERCI à mon mari pour sa patience, ses sacrifices et ses encouragements. Résumé 7 RESUME Les travaux présentés dans cette thèse ont porté sur l’étude de faisabilité technique et logicielle du système i-GUIDE, système interactif de guidage des personnes dans les hypermarchés. Nous avons détaillé l’analyse fonctionnelle du besoin du système. Ensuite, nous avons étudié l’impact de l’intégration du système dans le magasin à travers le diagramme BPMN. Nous avons opté pour l’approche UML pour décrire les principales fonctionnalités de notre système ainsi que les objets nécessaires pour son bon fonctionnement. Une architecture du système i-GUIDE, basée sur la technologie RFID avec une application sous Android, a été présentée. Par ailleurs, nous avons proposé des approches d’optimisation de parcours dans un hypermarché basées sur la méthode de recherche tabou pour deux problèmes. Pour le premier problème, nous avons choisi le critère de la plus courte distance pour la détermination du chemin et pour le deuxième nous avons ajouté une contrainte de temps pour des articles en promotion. Avant de chercher le chemin le plus court à parcourir pour trouver les articles existants dans la liste de courses, nous avons proposé une méthode pour la détermination des distances entre les articles de l’hypermarché pris deux à deux. Mots clés : Système interactif de guidage, Intelligence ambiante, BPMN, UML, Technologies de localisation, RFID, Android, Optimisation de parcours avec et sans fenêtres de temps, Heuristique de plus proche voisin adaptée, Recherche tabou avec ensembles. ABSTRACT The present work focuses on the technical feasibility study of i-GUIDE system which is a real time indoor navigation system dedicated to assist persons inside hypermarkets. We detailed its functional analysis. Then, we studied the impact of integrating the system inside hypermarkets. We opted for an UML design to describe its main functionalities and objects required. We presented architecture of i-GUIDE system based on RFID technology with an Android application. Furthermore, we introduced optimization approaches based on tabu search to compute the route visiting items existing in a shopping list for two problems. The first one treats the shortest path to pick up items and the second one adds a time constraint for promotional items. Before computing the shortest path, we introduced a method to determine distance between each two items existing in the hypermarket. Keywords: Intelligent Navigation system, Ambient intelligence, BPMN, UML, Localization technologies, RFID, Android, itinerary optimization with and without time constraint, Adapted Nearest Neighbour Heuristic, Tabu Search with sets. Liste des figures 9 LISTE DES FIGURES Figure 1 : Fonctionnement du système BlueEyes [Mab09] .................................................................. 24 Figure 2 : Le Robocart [Kul07]............................................................................................................. 26 Figure 3 : Schéma de fonctionnement du dispositif [RAS09]............................................................... 27 Figure 4 : Utilisation du mobile NTT DoCoMo [Pou07]...................................................................... 28 Figure 5 : Plan du magasin avec le chemin à parcourir [Pue10]........................................................... 32 Figure 6 : La " bête à cornes" du système global .................................................................................. 33 Figure 7 : Diagramme pieuvre du système global................................................................................. 34 Figure 8 : Exemple de grille GRAI [Lat06] .......................................................................................... 45 Figure 9 : Les diagrammes dans UML 2.0 [OMG05]........................................................................... 46 Figure 10 : Extrait du diagramme BPMN ............................................................................................. 52 Figure 11 : Modélisation BPMN de la chaîne logistique d'achat et de vente de produits..................... 53 Figure 12 : Diagramme de Cas d’utilisation UML de notre système de guidage [HEB10a] ................ 56 Figure 13 : Diagramme d’activité UML de la fonction « Guider l’utilisateur et lui donner des instructions » [HEB10a]........................................................................................................................ 57 Figure 14 : Diagramme de séquence de la fonction calcul du chemin le plus court [HEB10a]............ 59 Figure 15 : Architecture globale du système de navigation temps réel................................................. 67 Figure 16 : Prototype de la solution ...................................................................................................... 68 Figure 17 : Disposition des repères sur les gondoles ............................................................................ 68 Figure 18 : Comparaison entre les parts de marché des ventes de Smartphones par systèmes d’exploitation en 2009 et 2010 [Alt11] ................................................................................................. 71 Figure 19 : Architecture du système de guidage avec un calculateur et une BDD embarqués ............ 72 Figure 20 : Architecture du système de guidage avec un calculateur et une base de données externes 73 Figure 21: Exemple de bloc : Gestion de la connexion Bluetooth........................................................ 74 Figure 22 : Ecran d'accueil pour Android ............................................................................................. 74 Figure 23 : Architecture de l'application sous Android en cours .......................................................... 75 Liste des figures 10 Figure 24 : Présentation du problème d'optimisation de l’itinéraire dans un hypermarché .................. 85 Figure 25 : Base de données d'un magasin............................................................................................ 88 Figure 26: Division d’un magasin Leroy Merlin en 6 zones................................................................ 89 Figure 27 : Attribution de repères sur les gondoles............................................................................... 90 Figure 28 : Extrait de l’algorithme de calcul des distances................................................................... 92 Figure 29 : Détermination des distances entre deux articles appartenant à deux zones différentes...... 93 Figure 30 : Algorithme de Branch and Bound ...................................................................................... 96 Figure 31 : Exemple de l'algorithme de Christofides............................................................................ 97 Figure 32 : Amélioration de la solution uploads/Finance/ hadj-khalifa-ismahene-pdf.pdf