La présente invention concerne la préparation d'une commande à partir de produits stockés dans un entrepôt, sur une plateforme ou directement en les prélevant dans les rayons d'un point de vente où lesdits produits sont placés pour une vente en libre-service.

Plus particulièrement, l'invention a pour objet un système d'optimisation de préparation de commandes de produits à distance.

Un tel type de système est mis en place de façon connue dans le cadre d'entrepôts avec de grandes surfaces de stockage ou dans certains hypermarchés qui ont mis en place un service de commande à distance dans l eq uel u n préparateur de commande effectue la collecte des produits commandés à la place du client.

E n pa rt i cu l ie r, d es systè m es d e g est io n d ' e ntre pôt ou WMS (Warehouse Management Systems), connus par exemple sous les marques Reflex ^® ou Magistore ^® sont utilisés.

Les systèmes connus sont agencés pour la supervision d'opérations de stockage dans un entrepôt, de prise en compte des commandes et d'optimisation de leur préparation.

Il apparaît toutefois que ces systèmes nécessitent une mise en place longue et complexe et se basent sur un positionnement défini des produits au sein de l'entrepôt qui n'est pas adapté à la préparation d'une commande dans un espace ouvert au libre service, en particulier dans le cadre de point de vente de proximité ou de petite surface.

En conséquence, l'étape de préparation de commande reste une étape longue, pouvant durer environ une heure par commande. Le parcours de l'utilisateur pour la collecte des produits n'est pas optimal car il peut être aléatoire et/ou cloisonné à une liste de produits d'une commande spécifique.

La présente invention a pour but de résoudre tout ou partie des inconvénients mentionnés ci-dessus.

A cet effet, l a présente i nvention a pou r obj et un système d'optimisation de préparation de commandes de produits à distance caractérisé en ce qu'il comprend : - une plate-forme de commande en ligne comportant une base de données comprenant une liste de produits,

- un terminal à disposition d'un utilisateur, client ou préparateur de commande, dans un espace de stockage déterminé,

- un serveur local dédié à l'espace de stockage relié à la plateforme de commande en ligne par des premiers moyens de communication et relié au terminal par des deuxièmes moyens de communication,

ledit serveur local dédié comprenant :

- des moyens de gestion de flux de données agencés pour permettre l'échange de données entre d'une part la plate-forme de commande en ligne et le serveur local et d'autre part entre le terminal et le serveur local,

- une base de données pour stocker des données reçues et transmises par le serveur local, ladite base de données comportant :

- une liste de produits présents dans l'espace de stockage déterminé, et fournie par la base de données de la plate-forme de commande en ligne,

- une liste de commandes de produits à préparer par l'utilisateur parmi la liste de produits, fournie par la base de données de la plate-forme de commande en ligne, et récupérable par le terminal,

- un ensemble de données de géolocalisation des produits dans l'espace de stockage déterminé, cet ensemble de données de géolocalisation des produits dans l'espace de stockage étant fourni à partir du terminal de l'utilisateur,

- un ensemble de données de modélisation de l'espace de stockage,

- des moyens de traitement agencés pour calculer un temps de parcours optimisé lors de la collecte des produits de la liste de commandes de produits à préparer de la base de données en fonction de l'ensemble de données de géolocalisation des produits dans l'espace de stockage déterminé de la base de données.

Les dispositions selon l'invention définissent un système de commande à distance optimisé par le biais de la plate forme de commande en ligne permettant à des utilisateurs d'effectuer la collecte de produits au sein d'un ou de plusieurs espaces de stockages. Le système est adapté à des espaces de stockages de toute taille, notamment à des points de vente de toute taille, sans nécessiter un placement fixe des produits.

Il est à noter qu'au sens de la présente invention, on entend par utilisateur notamment un préparateur(s) de commande effectuant une collecte pour un ou plusieurs clients ou, un client cherchant à optimiser son temps de parcours pour effectuer ses achats à l'intérieur du ou des espaces de stockages.

Selon un aspect de l'invention, les moyens de traitement calculent un temps de parcours optimisé en fonction de plusieurs paramètres parmi :

- les types de produit à préparer,

- la configuration spatiale de l'espace de stockage,

- le nombre de préparateurs disponibles,

- le temps imparti pour la préparation des commandes. Selon un aspect de l'invention, la base de données comporte une l iste de commandes de prod u its préparés, fou rn ie par le terminal, et récupérable par la base de données de la plate-forme de commande en ligne.

Selon un aspect de l'invention, le serveur local comprend des moyens de modélisation de l'espace de stockage, notamment une application graphique, agencés pour générer l'ensemble de données de modélisation de l'espace de stockage.

Cette disposition permet de repérer plus facilement les zones, les rayons et les étagères à l'intérieur d'un point de vente dans ou sur lesquelles se trouvent les différents produits à commander.

Selon un aspect de l'invention, le serveur local comprend des moyens de configuration agencés pour permettre un réglage de tout ou partie d'un ensemble de paramètres par un superviseur de l'espace de stockage.

Selon un aspect de l 'invention , l'ensemble des paramètres proposés par les moyens de configuration du serveur local comprennent au moins un paramètre parmi :

- la finesse de la géolocalisation,

- le cas échéant, l'utilisation ou non des moyens de modélisation,

- la largeur des étagères,

- l'ajout d'utilisateurs,

- les chemins d'import des flux de données et d'accès aux scripts d'import. Cette disposition permet d'adapter le système à la configuration spatiale de chaque espace de stockage.

Selon un aspect de l'invention, la liste de géolocalisation comprend une série de produits identifiés avec un code alphanumérique correspondant à leur emplacement dans l'espace de stockage.

Cette disposition permet d'élaborer un codage simple permettant de repérer facilement un produit à l'intérieur du point de vente.

Selon un aspect de l'invention, le terminal est du type assistant numérique personnel ou ordiphone.

Selon un aspect de l'invention, le système comporte en plus du premier terminal, un deuxième terminal à disposition d'un superviseur de l'espace de stockage relié au serveur local par des troisièmes moyens de communication.

Selon un aspect de l'invention, le serveur local comprend des moyens d'aide à la décision agencés pour proposer sur le deuxième terminal du su perviseu r de l 'espace de stockage une affectation optimale des commandes de produits à préparer par l'utilisateur, notamment en fonction de plusieurs modes de préparation intégrant par exemple le nombre de préparateurs disponibles et le temps imparti pour la préparation des commandes.

Selon un aspect de l'invention, le deuxième terminal est du type micro ordinateur ou ordiphone.

Selon un aspect de l'invention, les moyens de traitement agencés pour calculer un temps de parcours optimisé sont également agencés pour calculer des statistiques à destination du superviseur et concernant notamment les produits commandés, leurs situations dans l'espace de stockage ainsi que des informations sur les préparateurs.

Selon un aspect de l'invention, les statistiques comprennent au moins une donnée parmi :

- le temps de préparation d'une commande : temps moyen par jour, par mois ou sur une période et courbe d'évolution,

- l e temps de préparation d'une commande par mode de préparation, notamment en mode mono-commande ou multi-commande et/ou mono-zone ou multi-zone, et par mode de livraison,

- le temps de préparation d'une commande par préparateur ainsi que le classement des préparateurs, - le temps moyen de préparation par produit,

- le taux de rupture de stock des produits,

- le taux de substitution d'un produit par un autre,

- l e nombre de produits moyen par commande, notamment par période, ainsi que son évolution, et/ou

- l e nombre de produits moyen par commande et par type de commande, notamment livraison à dom icil e ou retrait dans l'espace de stockage.

Selon un aspect de l'invention, les moyens de traitement utilisent plusieurs algorithme dont :

- la matrice d'adjacence,

- l'algorithme de Dijkstra, et

- l'algorithme inhérent au problème du voyageur de commerce.

De toute façon, l'invention sera bien comprise à l'aide de la description qui suit, en référence au dessin schématique annexé représentant, à titre d'exemple non limitatif, un système selon l'invention.

La figu re 1 est un schéma synoptiq ue il l ustrant un mode de réalisation d'un système 10 selon l'invention.

Comme illustré à la figure 1 un système 1 0 comprend une plate- forme 20 de commande en ligne par exemple de la marque Proxi-Store® et un terminal 31 à disposition d'un utilisateur, client ou préparateur de commande, dans un espace de stockage 30 déterminé.

La plate-forme 20 de commande en ligne comprend une base de données 21 comprenant une l iste de produ its présents dans un espace de stockage 30 déterm iné a insi qu'une l iste d e commandes de produits à préparer, les commandes ayant été effectuées à distance par des clients de la plate-forme 20 de commande en ligne.

L'espace de stockage 30 est géré par un ensemble de superviseurs qui gèrent à l e u r to u r un ensemble de préparateurs de commandes de l'espace de stockage 30 déterminé.

En outre, le système 1 0 comprend un serveur local 40 dédié à l'espace de stockage 30 déterminé.

Le serveur local 40 est relié à la plate-forme 20 de commande en ligne par des premiers moyens de communication 1 , par exemple du type réseau Internet. Le serveur local 40 est rel ié au term inal 31 par des deuxièmes moyens de communication 2, par exemple du type sans fil ou bien filaire.

Le terminal 31 peut par exemple être un PDA ou bien une imprimante fournissant une liste de produit à préparer dans un fonctionnement du système 10 selon un mode dégradé décrit plus loin dans le texte.

L'util isateur peut être un préparateur de commande effectuant la préparation de la commande d'un client ou bien un client lui-même prélevant ses propres produits commandés dans les différents rayons de l 'espace de stockage 30 ou zone de préparation 30, par exemple un entrepôt sec, un entrepôt frais, un fournisseur extérieur...

De plus, dans le mode de réal isation présenté à la figure 1 , le système 10 comprend des troisièmes moyens de communication 3 avec un deuxième terminal 32 à disposition d'un superviseur de l'espace de stockage 30.

Les troisièmes moyens de communication 3 peuvent par exemple par exemple être du type sans fil ou bien filaire.

Le deuxième terminal 32 peut par exemple être un micro ordinateur ou bien un PDA.

En outre, le système 10 comprend des moyens de configuration 45 du système 10 agencés pour permettre un réglage de tout ou partie d'un ensemble de paramètres par un superviseur de l'espace de stockage 30.

Ces paramètres sont envoyés vers le deuxième terminal 32 d u superviseur via les troisièmes moyens de communication 3. Ces paramètres sont détaillés plus loin dans le texte.

Le système 10 comprend également des moyens de gestion 42 de flux de données comprenant des scripts d'import de données et agencés pour gérer le contenu d'une base de données 41 du serveur local 40.

Dans le mode de réalisation présenté, cette base de données 41 comporte notamment :

- une l iste de produ its présents dans l 'espace de stockage 30 déterminé, et fournie par la base de données 21 de la plate forme 20 de commande en ligne,

- une liste de commandes de produits à préparer par l'utilisateur, fournie par la base de données 21 de la plate forme 20 de commande en ligne et récupérable par le terminal 31 de l'utilisateur, - une l iste de commandes de produits préparés, fournie par le terminal 31 de l'utilisateur et récupérable par la base de données 21 de la plate-forme 20 de commande en ligne, et

- un ensemble de données de géolocalisation des produits dans l'espace de stockage 30 déterminé.

La liste de commandes de produits préparés n'est pas essentielle au bon fonctionnement du système 10 mais permet néanmoins un retour d'informations vers la plate-forme 20 de commande en ligne permettant de renvoyer au cl ient des informations su r le su ivi de l a préparation de sa commande.

L'ensemble de données de géolocalisation des produits dans l'espace de stockage 30 est fourni par le terminal 31 après qu'un préparateur ait enregistré sur son terminal 31 , les données de géolocalisation de chacun des produits présents dans l'espace de stockage 30.

Cette étape, détaillée plus loin dans le texte, n'est réalisée qu'une seule fois ou chaque fois qu'un produit est déplacé dans l'espace de stockage 30.

Enfin, le système comprend des moyens de traitement 12 agencés pour calculer un temps de parcours optimisé lors de la collecte des produits de la liste de commandes de produits à préparer de la base de données 41 en fonction de l'ensemble de données de géolocalisation des produits dans l'espace de stockage 30 déterminé de la base de données 41 .

Ces moyens de traitement 12 sont de préférence constitués par un microprocesseur.

La base de données 21 comprend également un ensemble de données de modélisation de l'espace de stockage 30.

Pa r défa ut, le serveur local 40 propose des moyens de modélisation 13, déta illés pl us loin dans le texte, permettant de générer l 'ensem ble de don nées de modél isation de l 'espace de stockage 30, et facilitant ainsi le repérage des produits à l'intérieur de l'espace de stockage 30 notamment grâce à une application graphique.

En o u t re , l e serveur local 40 comprend des moyens de configuration 45 agencés pour permettre un réglage de tout ou partie d'un ensemble de paramètres par un superviseur de l'espace de stockage 30. La config u ration d u serveur local 40 par les moyens de configuration 45 peut être utile lors de l'association du serveur local 40 à un espace de stockage 30 particulier.

Ces moyens de configuration 45 permettent à un superviseur de cet espace de stockage 30 de configurer des paramètres globaux tels que :

- la finesse de la géolocalisation,

- le cas échéant, l'utilisation ou non des moyens de modélisation,

- la largeur des étagères,

- l'ajout d'utilisateurs,

- les chemins d'import des flux et d'accès aux scripts d'import.

Une mod ification d'un de ces paramètres, à l'exception des informations concernant les bases de données et les utilisateurs, entraîne une nouvelle géolocalisation des produits dans l'espace de stockage 30.

Le superviseur de l'espace de stockage 30 est invité sur son micro- ordinateur 32 à choisir la finesse avec laquelle sont repérés les produits dans l'espace de stockage 30. Cette finesse pourra être de l'ordre du rayon, du segment dans le rayon ou de l'étagère dans le segment.

Un rayon peut comprendre plusieurs segments correspondant à des portions divisant longitudinalement le rayon, chaque segment pouvant comprendre plusieurs étagères superposées.

Le système 10 peut fonctionner selon un mode dégradé, dans le cas où l'ensemble de données de modélisation de l'espace de stockage 30 ne seraient pas d ispon ibles. D a n s c e ca s , l'utilisateur doit quand même géolocaliser les produits mais dans un ordre logique de prélèvement. En effet, sans l'ensemble de données de modél isation de l'espace de stockage 30, l'optimisation du parcours du préparateur est impossible, et est fait par ordre alphabétique des codes de géolocalisation détaillée plus loin dans le texte.

Par défaut, la largeur de l'étagère est de 1 m10. Mais il est possible de modifier ce paramètre lors de la configuration du système 1 .

Lors de la mise en place du système 10 dans l'espace de stockage

30, différents administrateurs en charge du développement du système 10 dans l'espace de stockage 30 sont ajoutés. Les utilisateurs, tels que les préparateurs sont ajoutés par la suite, de même que les superviseurs.

Les chemins d'import des flux et d'accès aux scripts d'import doivent également être renseignés lors de la configuration du serveur local 40 à l'espace de stockage 30. Notamment, les dossiers contenant les fichiers produits et commandes ainsi que les adresses urls des scripts permettant de les récupérer depuis la plate-forme 20 de commande en ligne doivent être précisés.

En fonction de la finesse de géolocalisation choisie, les produits sont identifiés avec un code correspondant à leur emplacement. Ce code est par exemple formé de 3 parties : RRR-XX-EE, avec :

RRR : Numérique, détermine le rayon,

XX : Alphabétique, détermine le segment,

EE : Numérique, détermine l'étagère.

Par exemple, dans le cas d'un espace de stockage 30 choisissant la finesse de géolocalisation de l'ordre du segment, un produit se trouvant dans le premier étage, dans le cinquième rayon et dans le segment B, le serveur local 40 par l'intermédiare de ses moyens de traitement 43 lui attribue automatiquement 005-B-O comme code de géolocalisation.

Lors du déploiement du système 10 dans l'espace de stockage 30, le géolocalisateur active le mode de géolocalisation sur le terminal 31 . Dans ce mode, le géolocalisateur peut scanner les produits à géolocaliser et indiquer leurs emplacements par rayon, segment et étagère le cas échéant en fonction de la finesse de géolocalisation choisie.

Le term inal 31 util isé par le géolocal isateur incarné par les préparateurs de l'espace de stockage 30, est avant tout simple et intuitif. En effet, le processus de géolocalisation est relativement fastidieux, c'est pourquoi cette interface s'attache à simplifier le plus possible le travail du géolocalisateur. Dans le but de limiter le nombre de manipulations lors de cette phase, des conventions sont mises en place :

- l e d é b u t d e c h a q u e rayo n se t ro u ve à l a g a u ch e d u géolocalisateur lorsqu'il se trouve en face du rayon,

- la première étagère dans le segment est celle se trouvant en haut,

- lorsque le géolocalisateur atteint le niveau maximal de géolocalisation (soit le rayon, soit le segment, soit l'étagère), le géolocalisateur peut scanner les produits dans l'ordre qu'il désire étant donné que tous les produits à ce niveau là possède le même code de géolocalisation,

- la numérotation des segments est incrémentée automatiquement à la fin du traitement d'un segment, et

- chaque segment est de largeur fixe (celle de l'étagère). Pour que le système 10 soit complètement opérationnelle, tous les produits de l'espace de stockage 30 doivent être scannés. Au lancement du mode de géolocalisation, les données sur les géolocalisations existantes sont chargées sur le terminal 31 du géolocalisateur et déchargées en fin de géolocalisation dans la base de données 41 du serveur local 40.

Le processus de géolocalisation peut être réalisé en plusieurs fois. De pl us, un produ it peut être situé à différents endroits dans l'espace de stockage 30, il comporte alors différents codes de géolocalisation en fonction de son emplacement dans l'espace de stockage 30.

Après la phase de géolocalisation , on dispose du nombre de rayons dans l'espace de stockage 30 et de leur taille (nombre de segments dans le rayon). Une application graph ique générée par les moyens de modélisation 44 permet alors de placer ces rayons les uns par rapport aux autres pour modéliser au mieux l'espace de stockage 30, et une indication sur les produits contenus dans les rayons permettra de faciliter ce placement. Les rayons peuvent être composés d'éléments, à savoir des segments et des étagères, de tailles et de formes différentes, deux rayons différents pouvant éventuellement être superposés.

Ce placement se fait par rapport aux caisses qui sont modélisées dans le bas de l'espace de modélisation. Des obstacles redimensionnables pourront également être ajoutés pour empêcher le préparateur de passer à l'endroit où est positionné l'obstacle. Quand le placement est terminé, les coordonnées des rayons sont enregistrées dans la base de données 41 .

Il est ensuite proposé de créer des zones regroupant plusieurs rayons, ainsi que d'ajouter des priorités de passages et des priorités d'effectifs à ces zones. Un rayon ne peut appartenir qu'à une seule zone et une zone ne peut appartenir qu'à un seul étage. Un écran de synthèse récapitule toutes les informations concernant les rayons et les zones telles que le nombre et libellé des rayons par zone, les rayons hors zone, etc. Chaque rayon peut être ordonnancé par rapport aux autres rayons pour spécifier les contraintes de priorité. Par exemple le rayon contenant les boissons fera parti des premiers rayons.

Etant donné que les rayons sont des obstacles infranchissables, ceux-ci doivent être contournés pour calculer l'itinéraire. Les moyens de traitement 43 utilisent donc des points de passages obligatoires pour entrer ou sortir d'un rayon. Ces points de passage, sont placés automatiquement par la personne modélisant l'espace de stockage 30.

Le modélisateur est un superviseur voire un administrateur qui peut effectuer cette modélisation à distance pour la transmettre ensuite vers des quatrièmes moyens de communication 4 compris dans le serveur local 40.

A parti r d e ces points, les différentes allées de l 'espace de stockage 30 par lequelles le préparateur peut passer sont déterminées. Il est alors possible de tracer le graphe qui permet de calculer l'itinéraire de la campagne de collecte des produits dans l'espace de stockage 30.

La modélisation de l'espace de stockage 30 est un processus long et fastidieux qui ne doit être effectué qu'une seule fois (sauf changement physique des rayons au sein d u magasin) . Pour cela, les moyens de modélisation 44 n'impliquent pas les produits mais seulement les étagères, les segments, et les rayons.

Cependant, il est nécessaire qu'une géolocalisation soit au préalablement effectuée ou qu'une liste de rayon soit rentrée ou importée par un superviseur ou un administrateur. Les données de géolocalisation des produits vont fournir la liste des rayons du magasin, ainsi que le nombre de segments qu'ils comportent et le nombre d'étagères par segment. A partir de ces informations, une liste de rayons à modéliser est obtenue avec des tailles différentes (proportionnelles au nombre de segments dans le rayon). Ces informations vont faciliter la modélisation. En effet, l'utilisateur ne devra pas ajouter des rayons, définir leurs tailles, le nombre de segments et le nombre d'étagères par segment car toutes ces informations seront déjà connues grâce à la phase de géolocalisation.

Il est possible que l'administrateur puisse modifier la modélisation ultérieurement. Cependant, le calcul des chemins, détaillé ci après, est relancé à chaque modification . De plus, une commande « réinitialiser » permet à l'administrateur de remettre à zéro la modélisation. Cependant, l'ancienne modélisation est sauvegardée dans la base de données 41 pour pouvoir la récupérer en cas d'erreur.

Les moyens de traitement 43 du serveur local 40 utilisent différents algorithmes pour le calcul des chemins :

- calcul de la matrice d'adjacence.

- calcul du plus court chemin entre deux points (algorithme de

Dijkstra). - calcul du chemin optimal reliant plusieurs points (Problème du voyageur de commerce).

La modélisation graphique de l'espace de stockage 30 signifie que l'utilisateur peut positionner les rayons les uns par rapport aux autres tels qu'ils le sont réellement dans l'espace de stockage 30.

Ainsi , pou r pouvoir déterm iner les chemins des préparations, l'espace de stockage 30 est modélisé sous forme d'un graphe connexe où les sommets sont les points de prélèvement ainsi que les points virages des rayons, et les arêtes sont les segments reliant les points.

Pour ce faire, chaque point est testé avec tous les autres points du graphe de façon à trouver les segments entre les points qui ne coupent pas un rayon ou un obstacle. Cette phase est fastidieuse et dépend du nombre de points, car chaque point et chaque rayon ou obstacle ajouté augmente sérieusement la complexité.

Le langage de développement des algorithmes utilisés par les moyens de tra itement 43 est par exemple l e l a ng ag e P H P (Personal HomePage). Bien entendu, d'autres langages de programmation peuvent être utilisés.

Un tableau en PHP est en fait une carte ordonnée. Une carte est un type qui associe des valeurs en clés.

Les graphes en langage PHP sont représentés par des tableaux à deux dimensions, où les clés sont les sommets du graphe et le contenu est la d istance entre chaque point. La notation diffère pour les points qui sont injoignables. Dans notre cas, par convention, si la distance vaut 1 000 000, les deux points sont injoignables.

Un exemple du calcul de la matrice d'adjacence d'un graphe est proposé en annexe.

De la même man ière, le graphe de l'espace de stockage 30 (les arêtes) est construit, et la matrice d'adjacence (calcul des d istances) est remplie.

Plus le nombre de points et de rayons est grand, plus le temps nécessaire pour remplir cette matrice sera long. Une optimisation possible est donc de limiter le périmètre à tester autour de chaque point.

En effet, si la distance entre le point en cours et un autre point est supérieure à une certaine distance, ce point sera considéré comme à l'infini et l'intersection entre le segment qu'il forme avec le point en cours et un rayon ou un obstacle ne sera pas testée.

De même, si la distance entre le point en cours et un rayon ou un obstacle est supérieure à une certaine distance, l'intersection avec cet élément ne sera pas testée non plus, puisque le segment entre le point en cours et le point testé sera plus court que la distance à l'élément.

La matrice d'adjacence va permettre de savoir s'il est possible de relier un point de passage à un autre point de passage sans couper un objet.

L'algorithme de Dijkstra permet quant à lui de calculer le plus court chemin reliant un point à un autre. Il s'applique sur un graphe connexe dont les arêtes sont pondérées. Autrement dit, l'algorithme a besoin d'une matrice d'adjacence comme celle décrite précédemment.

Maintenant que les distances sont connues pour relier les points de passage entre eux, une implémentation de Dijkstra est utilisée pour connaître la meilleure route à utiliser pour rejoindre un point de passage qui n'est pas relié directement à un autre.

Cet algorithme est donc appliqué sur tous les points du graphe, exceptés les points virage, qui ne sont jamais des points de départ ou d'arrivée de chemin puisqu'ils ne correspondent pas à des produits mais seulement à des points intermédiaires. Pour les points qui sont directement accessibles (par exemple dont la. distance est inférieure à 1 000 000 dans la matrice d'adjacence), le chemin est préservé. Tandis que pour les points injoignables, l'algorithme cherche le plus court chemin les reliant.

Plusieurs méthodes joi ntes en an nexe permettent par cet algorithme de Dijkstra de trouver le plus court chemin entre deux points.

Une fois le plus court chemin entre deux points déterminé, les moyens de traitement 43 calculent le chemin optimal reliant plusieurs points, ce qui revient à résoudre le problème du voyageur de commerce.

Le problème du voyageur de commerce est un problème complexe qui consiste à parcourir tous les points d'un graphe et revenir au point de départ, de façon à réaliser le chemin le plus cours possible. Cependant, ce problème n'est pas soluble avec une approche linéaire combinatoire dans un temps acceptable. Des algorithmes heuristiques sont donc utilisés.

Dans le cas présent, le parcours se fait sur tous les produits en partant d'un point de départ et en arrivant à un point d'arrivée pouvant être différent. De plus, une priorité de prélèvement indiqué par l'utilisateur doit être respectée entre les différents produits. L'algorithme utilisé par les moyens de traitement 43 prend donc en compte ces éléments.

Dans le cas présent, c'est le temps de calcul qui est primordial et non pas l'optimalité à 100% du résultat. En effet, à cause des priorités de passage, des trajets sont rallongés par rapport au parcours réellement optimal ne prenant pas en compte les priorités de prélèvement. Une légère marge d'erreur sur l'optimalité de la solution trouvée est acceptable.

Le choix s'est donc orienté vers un algorithme 2-opt qui donne des temps de réponses très courts tout en garantissant une solution approchée assez proche de l'optimalité.

Cet algorithme prend en entrée un graphe complet ainsi qu'un chemin existant entre tous les points qui respecte l'ordre des priorités. Les indices de changement de priorité sont également nécessaires.

Cet algorithme consiste à permuter deux arêtes dans le graphe si cela provoque une amélioration globale de la distance parcourue. En pratique, cette inversion consiste à retourner le chemin entre deux points.

Pour cela, le graphe est parcouru en entier et pour chaque point, la conséquence d'une permutation avec un point situé plus loin dans le graphe est testée. S'il y a une amélioration, l'inversion est effectuée et le parcours est poursuivi. Tant qu'il y a au moins une amélioration dans le parcours du graphe, le parcours complet du graphe est recommencé.

Pour appliquer cet algorithme au problème, il faut cependant lui appliquer deux modifications majeures :

- il faut imposer le point de départ et le point d'arrivée, - il ne faut pas inverser deux arêtes qui relient des points ayant une priorité différente.

Quelques méthodes permettant l'implémentation de cet algorithme sont proposées en annexe.

Dans un mode de réal isation , le serveur local 40 comprend également des moyens d'aide à la décision 46 des superviseurs qui permet une affectation optimale des commandes de la liste des commandes à préparer de la base de données 41 aux différents préparateurs.

Ces moyens d'aide à la décision 46 prennent en compte le nombre de préparateurs disponibles ainsi que le temps imparti pour la préparation des commandes. En fonction de ces paramètres, ces moyens 46 proposent une solution au superviseur des préparateurs, en affecta nt l es différentes commandes (ou commandes partielles) aux différents préparateurs. Cette affectation peut ensuite être modifiée à la convenance du superviseur.

Il est possible de paramétrer les moyens d'aide à la décision 46 en précisant le ou les modes de préparations dans lesquels on souhaite opérer. Ainsi, dans le cas où le superviseur souhaite n'utiliser qu'un seul mode de préparation, ce paramètre est stocké et utilisé pour chaque affectation. Par défaut, tous les modes de préparations sont utilisables. Si plusieurs modes sont sélectionnés, le système 10 optimise au mieux la répartition dans différents modes.

Les préparations de commandes peuvent se faire de plusieurs façons :

- en mode dégradé dans lequel le préparateur imprime la liste des commandes à préparer durant sa campagne de collecte des produits dans l'espace de stockage 30, de préférence en format PDF. Il est également possible de regrouper plusieurs commandes pour une campagne de collecte des produits dans l'espace de stockage 30,

- en mode mono commande dans lequel un préparateur est chargé de préparer une seule commande durant sa campagne de préparation. Une fois terminée, il revient à la zone de départ, dépose son terminal 31 et la prochaine commande à préparer est chargée sur son terminal 31 ,

- en mode multi commande dans lequel un préparateur peut préparer plusieurs commandes à la fois. Ces dern ières sont groupées par zones et sont traitées comme une seule commande,

- en mode mono ou multi zones de préparation dans lequel un préparateur peut être affecter à une ou plusieurs zones de l 'espace de stockage 30. Ainsi, il est chargé de préparer des commandes partielles situées dans sa zone.

Une fois que les commandes sont réparties et regroupées, le superviseur valide l'affectation et l'itinéraire est calculé pour chaque lot de commandes à effectuer par préparateur. A la fin du calcul, des fichiers d ' iti n éra i res sont gén érés pou r i m press ion (format PDF) ou pour téléchargement sur le terminal 31 .

Dans le cas où une commande prioritaire arrive en cours de journée, le superviseur a la possibilité de l'affecter à un préparateur en mode prioritaire, et sera alors la prochaine commande traitée par ce préparateur. Enfin, dans un mode de réalisation, les moyens de traitement 43 agencés pour calculer un temps de parcours optimisé sont également agencés pour calculer des statistiques à destination du superviseur et concernant notamment les produ its commandés, leurs situations dans l 'espace de stockage 30 ainsi que des informations sur les préparateurs.

Ces statistiques permettent d'afficher une évolution ou d'effectuer des comparaisons. Les superviseurs peuvent aussi avoir la possibilité d'exporter ces statistiques.

Ainsi , il est possible d'afficher des statistiques concernant les produits commandés, leurs situations dans l'espace de stockage 30 ainsi que des informations sur les préparateurs.

La l iste ci-dessous énumère de façon non exhaustive quelques exemples de statistiques pouvant être calculées par les moyens de traitement 43 :

- le temps de préparation d'une commande : Temps moyen par jour, par mois ou sur une période et courbe d'évolution,

- le temps de préparation d'une commande par mode de préparation, notamment en mode mono-commande ou multi-commande et/ou mono zone ou multi-zone, et par mode de livraison,

- le temps de préparation d'une commande par préparateur ainsi que le classement des préparateurs,

- le temps moyen de préparation par produit,

- le taux de rupture de stock des produits,

- le taux de substitution d'un produit par un autre,

- le nombre de produits moyen par commande, notamment par période, ainsi que son évolution, et/ou

- le nombre de produits moyen par commande et par type de commande, notamment livraison à domicile ou retrait dans l'espace de stockage 30.

Bien que l'invention ait été décrite en liaison avec des exemples particuliers de réalisation, il est bien évident qu'elle n'y est nullement limitée et qu'elle comprend tous les équivalents techniques des moyens décrits ainsi que leurs combinaisons.

Selon une variante, l'ensemble des paramètres proposés par les moyens de configuration du serveur local comprennent au moins un paramètre indiquant si la préparation des commandes doit être réalisée selon un mode en Z ou en U. On entend par mode en U un mode dans lequel le préparateur termine un rayon entièrement avant de se retourner et passer au rayon opposé. On entend par mode en Z un mode dans lequel le préparateur prélève des produits dans les deux rayons à la fois (le mode en Z). Le mode en Z est applicable dans les cas où les allées sont étroites. Il est possible de prévoir que le mode de préparation par défaut soit le mode en U.

Selon une variante, l'ensemble des paramètres proposés par les moyens de configuration du serveur local comprennent au moins un paramètre indiquant un nombre d'étages de l'espace de stockage 30. Dans ce cas, le code de l'emplacement d'un produit généré lors de la géolocalisation comprend une information additionnelle N, numérique, déterminant le niveau de l'étage, disposée par exemple au début du code, le format de celui-ci devenant alors N- RRR-XX-EE.

Annexes

1. La matrice d'adiacence :

Exemple du calcul de la matrice d'adjacence d'un graphe en langage de développement PHP :

Soit un graphe comportant 5 sommets nommés (A, B, C, D, E) et représenté comme suit :

La matrice d'adjacence de ce graphe est donc

A B c D E

A 0 1 4 1000000 1

B 1 0 1000000 2 1

C 4 1000000 0 1 2

D 1000000 2 1 0 1

E 1 1 2 1 0

2. L'algorithme de Dijkstra :

L'objet :

L'algorithme de Dijkstra est implémenté sous forme d'un objet dont les attributs sont : · $startNode : Le point de départ.

• $visited: Tableau, clés = les points du graphe, valeurs = true si le point a été visité, false sinon.

• $distance : Tableau, clés = les points du graphe, valeurs = les distances séparant le point de départ aux autres points.

· $previousNode : Tableau, clés = les points du graphe, valeurs = le point précédent la clé.

• $map : La matrice d'adjacence du graphe. • $infinteDistance : La distance représentant l'infini.

• $bestPath : Le chemin le plus court entre deux points.

Le constructeur de l'objet est de la forme suivante : function Dij kstra ( &$ourMap, $infiniteDistance) {

$this -> infiniteDistance = $infiniteDistance; $this -> map = &$ourMap;

$this -> bestPath = 0 ;

}

Il va définir la distance représentant l'infini, la matrice d'adjacence et initialiser le meilleur chemin à 0. Les différentes méthodes de l'objet Dijkstra sont décrire ci-après.

La méthode findShortestPathQ :

Paramètres

$start : le point de départ.

Valeur de retour

$distance : Tableau des distances entre le point $start et tous les autres points. Cette méthode va dans un premier temps initialiser l'attribut

$startNode par le paramètre $start.

Ensuite, elle va parcourir tous les autres points du graphe et mettre à jour le tableau $distance en positionnant toutes les valeur du tableau $visited à false sauf celle du $startNode. Enfin, pour tous les points, le tableau $previousNode sera rempli avec le $startNode. Cela correspond à une phase d'initialisation.

Par la suite, tous les points seront parcourus tant qu'il existera au moins un point non visité et la méthode findBestPathQ , puis la méthode updateDistanceAndPreviousQ seront appelées sur ces points.

La méthode findBestPathQ Paramètres $ourDistance : le tableau $distance.

$ourNodesLeft : les points non encore visités.

Valeur de retour

$bestNode

Cette fonction va parcourir tous les points non encore visités et retourner le point ayant la plus courte distance vers notre point de départ. La méthode updateDistanceAndPreviousO

Paramètres

$obp : le point à mettre à jour. Cette fonction va parcourir tous les points $i du graphe qui ont une distance infinie et mettre à jour la distance entre le $startNode et le point $obp si les conditions suivantes sont vérifiées :

• La distance entre $startNode et $obp est définie dans la matrice d'adjacence.

• La distance entre $startNode et $obp est différente de l'infini ou, différente de 0 dans la matrice d'adjacence.

• La somme de la d istance entre le $startNode et $obp dans le tableau $distance et la distance entre $obp et $i dans la matrice d'adjacence est inférieure à la distance entre le $startNode et $i dans le tableau $distance.

Si toutes ces conditions sont vérifiées alors :

$thi s->di stance [ $i ] = $thi s->di stance [ $obp ] + $thi s -> map [ $obp ] [ $ i ] ;

$thi s->previousNode [ $i ] = $obp ;

La méthode getResultsO

Valeur de retour

$path : Matrice contenant le chem in entre le $startNode et chaque point Cette fonction va parcourir tous les points du graphe et retracer pour chaque point le chemin inverse vers le point de départ. Si le chemin existe, ce chemin sera ensuite retourné et renvoyé dans le tableau Spath, sinon le texte « no route » sera retourné.

3. Implémentation de l'algorithme résolvant le problème du voyageur de commerce :

Utilisation :

$retourPVC = Pvc :: calcul ( $graphe_complet, $Hamiltonien,

$indicel ,

$indice2 ) ;

La fonction calcul nécessite de passer en paramètre un graphe complet contenant les distances entre tous les points, un chemin existant passant par tous les points et respectant les priorités de prélèvement, ainsi que les indices des éléments du chemin pour lesquels la priorité change.

La méthode calcuK)

Paramètres

$graphe_complet le graphe complet

$Hamiltonien le chemin existant

$indice1 l ' ind ice d u prem ier élément ayant u ne priorité moyenne

$indice2 l ' ind ice d u prem ier élément ayant u ne priorité faible

Valeur de retour

$Hamiltonien le chemin ordonné par l'algorithme Cette fonction va ordonner le chemin $Hamiltonien de façon à rendre la distance de parcours de tous les points la plus faible possible.

Tant q ue la boucle provoque un changement su r le chemin $Hamiltonien, une itération sera effectuée de façon à ce qu'il ne soit plus possible de trouver d'amélioration avec l'algorithme.

Tous les points du chemin sont parcourus en commençant à l'indice 1 , de façon à imposer la position du point de départ (indice 0) et ne pas tester des inversions avec ce point. De la même manière, le parcours des points se termine à l'avant dernier élément de façon à imposer le point d'arrivée. Pour chaque point, le gain d'une permutation avec les points suivants dans le chemin est évalué. Cependant, une valeur d'arrêt est définie de façon à ne pas pouvoir inverser d'éléments qui ont des priorités différentes. Pour cela, l'indice du point en cours est comparé avec les indices des priorités passés en paramètres. Ainsi, en fonction de la position du point, il sera testé avec tous les autres points qui ont la même priorité que lui.

Enfin, à l'aide de la fonction difference_cout(), l'amélioration que provoquerait l'inversion des deux points en cours est évaluée.

Si le gain est positif, il n'y a pas d'amélioration et le parcours des points va donc continuer.

Si le gain est négatif, c'est qu'il y a une amélioration et le chemin entre ces deux points va donc être renversé grâce à la fonction renverse _parcours() , puis le parcours des points sera repris.

A la fin, si le chemin a été modifié, le parcours recommence, sinon le chemin optimisé est renvoyé.

La méthode différence coutQ

Paramètres

$i l'indice de l'élément en cours

$j l'indice de l'élément testé

$graphe le graphe complet

$Hamiltonien le chemin existant Valeur de retour

Valeur du gain global provoqué par la permutation (négatif si le chemin est plus court)

Cette fonction va calculer le gain que provoque une permutation du chemin entre l'élément $i et $j.

Si le point testé n'est pas le dernier du chemin, le calcul suivant sera effectué :

Distance entre le point d'indice $/ ^' et le point suivant l'indice $j + Distance entre le point précédent l'indice $i et le point d'indice $j - Distance entre le point précédent l'indice $i et le point d'indice $i

Distance entre le point d'indice $j et le point suivant l'indice $j

Si le point testé est le dernier, le calcul suivant sera effectué :

Distance entre le point précédent l'indice $/ ^' et le point d'indice $j Distance entre le point précédent l'indice $i et le point d'indice $i

La méthode renverse parcoursO

Paramètres

$i : l'indice de l'élément en cours

$j : l'indice de l'élément testé

$Hamiltonien : le chemin existant

Valeur de retour

$Hamiltonien : le chemin mis à jour après retournement du chemin

Cette fonction va vérifier l'ordre des indices $i et $j et appeler la fonction echange_parcours() sur chaque point entre ces deux indices

La méthode échange parcoursO Paramètres

$ordre1 : l'indice du premier élément à inverser

$ordre2 : l'indice du deuxième élément à inverser $Hamiltonien : le chemin existant

Valeur de retour

$Hamiltonien : le chemin mis à jour après permutation de deux points

Cette fonction va inverser les deux points $ordre1 et $ordre2 dans le chemin $Hamiltonien.