FR 2681263 A1 19930319 FR 9111510 A 19910918 Procédé de tri d'objets La présente invention concerne un procédé de tri d'objets, et en particulier de tri de courrier dans un centre postal. Dans toute la suite, on prendra comme exemple de tri celui du courrier Toutefois, le lecteur comprendra bien entendu que cet exemple n'est pas limitatif et que le procédé selon l'invention s'applique au tri d'objets quelconques. La généralisation du traitement automatique du courrier a entraîné la réalisation de machines de tri pour de petits centres de tri réalisant ce que l'on appelle le tri- acheminement et le tri-distribution, qui est le dernier tri à effectuer avant la distribution du courrier aux usagers par les préposés Ce tri- distribution est d'ailleurs également appelé préparation de la tournée du facteur Dans les machines initialement conçues, le15 courrier est réparti en un certain nombre de destinations, et chaque destination est associée à un réceptacle de la machine. A la suite des nombreux problèmes posés par la taille et l'encombrement de ces machines, une optimisation du nombre de destina- tions de tri, et donc du nombre de réceptacles de la machine a été20 effectuée On a ainsi diminué le nombre e réceptacles de la machine, ce qui a conduit à augmenter le nombre de passes de tri, c'est-à-dire le nombre de fois o le courrier est réintroduit dans la machine après avoir subi un tri En effet, à cause de la diminution de la quantité de réceptacles, il n'est plus possible d'affecter un réceptacle à25 chaque destination finale du courrier (c'est-à-dire à chaque adresse, par exemple) Il est donc nécessaire de regrouper les destinations par ensembles, et même de regrouper les ensembles par groupes d'ensembles, chaque groupe pouvant alors être affecté à un réceptacle. Préparer la tournée du facteur signifie trier et ranger le courrier suivant un ordre à respecter scrupuleusement: l'ordonnancement du courrier doit correspondre exactement au trajet réellement suivi par le facteur, et cet ordonnancement doit être impérativement respecté tout au long du processus de tri. Suivant le nombre de lettres à trier, le nombre de destinations, la méthode de tri choisie, etc, plusieurs passes de tri successives -2- sont donc prévues et effectuées. On va maintenant, à l'aide d'un exemple, illustrer le processus opératoire de la préparation de la tournée du facteur On prend l'analogie suivante: on veut trier les 52 cartes d'un jeu de cartes en respectant les deux critères suivants: la valeur des cartes, par exemple dans l'ordre arbitraire croissant suivant: As, 2, 3, 4, 5, 6, 7, 8, 9, 10, Valet, Dame, Roi, la valeur des couleurs, par exemple dans l'ordre suivant: Coeur, Carreau, Pique, Trèfle. Le tri est réalisé en deux passes. Première passe La première passe est réalisée en prenant comme critère de tri la valeur des cartes On utilise donc treize réceptacles. On obtient, par exemple: Réceptacle 1 Réceptacle 2 Réceptacle 13 As Coeur 2 Pique Roi Trèfle As Carreau 2 Trèfle Roi Coeur As Trèfle 2 Coeur Roi Carreau As Pique 2 Carreau Roi Pique On procède ensuite au dépilage du jeu disposé dans les réceptacles en respectant l'ordre des réceptacles:25 Récéptacle 1, Réceptacle 2 Réceptacle 13. Deuxième passe La deuxième passe est réalisée en prenant comme critère de tri la valeur des couleurs On utilise donc quatre réceptacles. Réceptacle 1 Réceptacle 2 Réceptacle 4 As Coeur As Carreau As Trèfle 2 Coeur 2 Carreau 2 Trèfle l l l Roi Carreau Roi Trèfle Roi Coeur 3 - On procède enfin au dépilage du jeu disposé dans les réceptacles en suivant l'ordre des réceptacles et en respectant l'ordonnancement des cartes à l'intérieur de chaque réceptacle On obtient ainsi le classement souhaité.5 On comprend donc que deux exigences principales doivent être satisfaites pour que le tri soit correct: ne pas mélanger l'ordre des réceptacles entre les première et deuxième passes et après la deuxième passe, conserver l'ordonnancement des cartes à l'intérieur de chaque réceptacle. Si l'on revient au cas du tri de courrier, le tri doit être effectué en respectant par exemple le code postal de la ville, le nom de la rue, les numéros dans la rue (ordre décroissant par exemple), la parité des numéros, etc La tournée d'un facteur comporte en moyenne 3000 lettres et environ 800 points de distribution (appelés également "stops") Ces 800 points de distribution correspondent par exemple à 800 immeubles ou maisons Comme on l'a signalé plus haut, si l'on veut effectuer le tri directement en affectant un réceptacle par point de distribution, il faut utiliser une machine très encombrante, qui ne convient pas à un petit centre de distribution comme un bureau de poste local On limite alors le nombre de réceptacles à 10, ce qui conduit à classer25 les 800 points de distribution en 8 groupes contenant chacun 10 "grappes" (ou "bunches") Chaque grappe contient donc 10 points de distribution. Ainsi, chaque lettre affectée à un point de distribution peut être identifiée par trois nombres entiers: celui du groupe auquel elle appartient, compris entre 1 et 8 et noté g, celui de la grappe à laquelle elle appartient, compris entre 1 et 10 et noté b (pour "bunch"), et celui du point de distribution auquel elle est destinée, compris entre 1 et 10 et noté S (pour "stop") On notera dans la suite Lgbs la lettre L affectée au point de distribution S de35 la grappe b dans le groupe g. 4 - Le tri doit donc respecter trois critères distincts: il est effectué en trois passes que l'on va brièvement décrire à présent. Première passe Chaque réceptacle (aussi appelé tasseur ou empileur car les lettres y sont rangées les unes contre les autres en constituant une pile) est affecté à un numéro de stop En fin de passe, on obtient: Réceptacle Réceptacle I 1: 2: Réceptacle 10: Lgbl Lgb 2 I quels que soient g et b quels que soient g et b Lgbl O, quels que soient g et b Les lettres contenues dans les réceptacles sont transférées par piles dans un magasin d'approvisionnement de la machine de tri L'ordre des réceptacles et celui des lettres dans les réceptacles doivent être impérativement respectés. Seconde passe Chaque réceptacle est affecté à un numéro passe, on obtient: de grappe En fin de Réceptacle 1 Lgl, 1 Lgl, 2 Lgl, 3 1 Lgl, 10 Réceptacle 2 Lg 2,1 Lg 2,2 Lg 2,3 I Réceptacle 10 Lgl O,l Lgl O,2 Lgl O,3 I Lg 2,10 Lgl O, 10 et ce quel que soit g dans chaque réceptacle. Les lettres contenues dans les réceptacles sont tranférées par piles dans le magasin d'approvisionnement L'ordre des réceptacles et celui des lettres dans les réceptacles doivent être impérativement respectés.35 -5- Troisième passe Chaque réceptacle est affecté à un numéro de groupe Le tri est donc effectué sur 8 réceptacles, et l'on obtient, en fin de troisième passe 5 Réceptacle 1 Réceptacle 2 Réceptacle 8 L 1,1,1 L 211,1 L 8,1,1 L 1,1,2 L 2,1,2 L 8,1,2 Ll,1,3 L 2,1,3 L 8,1,3 | | l L 1,2,1 L 2,2,1 L 8,2,1 L 1,2,2 L 2,2,2 L 8,2,2 L,10,1 L 2,10,1 L 8,10,1 L 1,10,2 L 2,10,2 L 8,10,2 Ll,10,10 L 2,10,10 L 8,10,10 Les lettres contenues dans les réceptacles sont enfin dépilées puis rangées L'ordre des réceptacles et celui des lettres dans les réceptacles doivent être impérativement respectés. En pratique, plusieurs lettres peuvent être identifiées par un seul triplet (g, b, s) Toutefois, le procédé de tri en trois passes est indépendant de la quantité de lettres par point de distribution,25 et suppose a priori uniforme la répartition des lettres par point de distribution On comprend donc, et c'est ce qui a été constaté lors de simulations de ce procédé, qu'il peut y avoir débordement d'un ou de plusieurs réceptacles lors de l'une des passes Un débordement (ou overflow) dans l'une des passes conduit à l'échec du tri final, car,30 comme on l'a vu, le tri d'une passe est conditionné par le tri de la passe précédente. Le but de la présente invention est donc de réaliser un procédé de tri d'objets, et en particulier de tri d'objets en au moins deux passes dans des réceptacles de capacité limitée, permettant d'homogé-35 néiser la répartition des objets dans les réceptacles et donc d'éviter 6 - les débordements dans les réceptacles lors de l'une des passes. En particulier, la présente invention a pour objet de répartir équitablement le contenu du courrier dans les réceptacles de dernière passe. S La présente invention propose à cet effet un procédé de tri d'objets en N passes de distribution physique dans R réceptacles d'une machine de tri contrôlée par un moyen de contrôle, N étant au moins égal à deux, caractérisé en ce qu'il comprend les étapes suivantes lecture et mise en mémoire dans ledit moyen de contr 8 le d'informations codées portées par lesdits objets, lesdites informations comportant N critères distincts par objet, classement en mémoire dans ledit moyen de contrôle desdits objets dans un ordre donné de sorte que chacun desdits objets est affecté à une destination, 15 calcul, au sein dudit moyen de contr 8 le, de la répartition desdits objets dans lesdits réceptacles, lors d'une N-1 -ième passe canonique, c'est-à-dire telle que tous les objets qui ont la même valeur d'un premier desdits critères soient affectés à un même réceptacle, calcul, au sein dudit moyen de contrôle, de la répartition desdits objets dans lesdits réceptacles lors d'une N -ième passe canonique telle que tous lesdits objets qui ont la même valeur d'un deuxième desdits critères soient affectés à un même réceptacle et que leur ordre respecte ledit ordre donné, première modification par ledit moyen de contrôle de ladite répartition de ladite N -ième passe canonique, fournissant une répartition de N -ième passe modifiée, telle que le nombre d'objets dans chacun desdits réceptacles soit rendu au plus égal à P, P étant le nombre maximal d'objets que peut contenir chacun desdits réceptacles,30 détermination du contenu de chacun des réceptacles dans lesquels doivent se trouver lesdits objets à la fin d'une N-1 -ième passe provisoire, agencée de manière à permettre ladite répartition de N -ième passe modifiée, seconde modification de ladite répartition de N -ième passe modifiée, fournissant une répartition de N -ième passe définitive, si -7- le contenu de l'un desdits réceptacles dans lesquels doivent se trouver lesdits objets à la fin de ladite N-1 -ième passe provisoire dépasse P, de sorte que l'ordre desdits objets reste semblable audit ordre donné et que la répartition d'une N-1 -ième passe définitive agencée de manière à permettre ladite répartition de N -ième passe définitive conduise à des réceptacles contenant chacun au plus P objets, reprise de toutes les étapes précédentes en remplaçant N par N-1 et N-1 par N-2, et ainsi de suite jusqu'aux deux dernières des passes destinées à être modifiées, tri desdits objets par ladite machine selon les répartitions définitives déterminées. Grâce au procédé selon l'invention, aucun des réceptacles ne déborde lors des différentes passes effectuées. Si RN est strictement supérieur au nombre de destinations, la première modification comprend par exemple les étapes suivantes: sélection du réceptacle de N -ième passe canonique dont le contenu dépasse P et qui est plus rempli que tous les autres, affectation de l'un des objets de ce réceptacle au réceptacle suivant, sans modifier l'ordre donné des objets, réitération de la sélection et de l'affectation si le contenu de l'un des réceptacles de N -ième passe canonique dépasse P, attribution en mémoire, à chacun des réceptacles de la N -ième passe modifiée, d'un nombre d'objets dits réels, correspondant au nombre d'objets qu'il contient, et d'un nombre d'objets dits fictifs, correspondant à la différence entre P et le nombre d'objets réels, mise en oeuvre de l'étape de détermination si aucun des réceptacles de N -ième passe canonique n'a un contenu strictement supérieur à P. La seconde modification peut alors comprendre les étapes suivantes: une première étape de sélection du réceptacle de N-1 -ième passe provisoire dont le contenu dépasse P et qui est plus rempli que tous les autres, une seconde étape de sélection du réceptacle de N -ième passe modifiée le moins rempli et contenant le plus d'objets fictifs, -8 - considérés comme non traités, une troisième étape de recherche dans le réceptacle de N -ième passe modifiée sélectionné à la seconde étape, d'un objet fictif dit éventuel dont la position dans le réceptacle sélectionné indique qu'il provient dudit réceptacle de N -ième passe provisoire sélectionné à la première étape, une cinquième étape de sélection, si cet objet fictif éventuel existe, d'un réceptacle de N -ième passe modifiée le moins rempli contenant le plus d'objets fictifs considérés comme non traités, et distinct des réceptacles de N -ième passe modifiée les moins remplis et contenant le plus d'objets fictifs considérés comme non traités déjà sélectionnés lors de la seconde étape ou de la cinquième étape, la seconde modification reprenant à partir de la troisième étape s'il existe un réceptacle sélectionné à la cinquième étape, une sixième étape de sélection-, s'il n'existe pas de réceptacle sélectionné à la cinquième étape, d'un réceptacle de la N-1 - ième passe provisoire dont le contenu dépasse P, plus rempli que tous les autres et distinct des réceptacles de N-1 -ième passe provisoire dont le contenu dépasse P et les plus remplis déjà sélectionnés lors de la première étape ou de la sixième étape, puis reprise de la seconde modification à partir de la seconde étape, une septième étape, déclenchée si l'objet fictif éventuel n'existe pas, ce qui signifie qu'un un objet réel a une position dans le récep- tacle de N -ième passe modifiée sélectionné qui indique qu'il provient25 du réceptacle de N-1 -ième passe sélectionné à la première étape, de remplacement de cet objet réel par un objet fictif du réceptacle de N ième passe modifiée, en conservant l'ordre des objets réels, une huitième étape d'attribution de la qualité "traité" à l'objet fictif éventuel, réitération des étapes précédentes si la quantité d'objets fictifs "traités" est inférieure au nombre d'objets fictifs total initial. Grâce à l'artifice des objets fictifs utilisé lors des première et seconde modifications, tous les réceptacles sont utilisés lors de toutes les passes, ce qui permet d'utiliser au mieux la place35 disponible dans les réceptacles afin d'éviter tout débordement. -9- Selon une variante, l'étape de lecture peut avoir lieu pendant un premier passage des objets dans la machine, effectué selon un critère spécifique, les deux dernières passes destinées à être modifiées étant alors les troisièmes et seconde passes Le critère spécifique utilisé est par exemple un critère statistique Il peut être aussi l'un des N critères précédents. Dans un autre cas, les deux dernières passes destinées à être modifiées peuvent être les seconde et première passes. Dans une application possible du procédé selon l'invention, le tri est un tri en trois passes destiné au tri de L lettres d'un cour- rier, et l'étape de lecture est précédée par une répartition des L lettres en G groupes de B grappes chacun, chacune des grappes contenant S points de distribution des lettres, de sorte que chacune des lettres porte un numéro de groupe compris entre 1 et G, un numéro de grappe compris entre 1 et B et un numéro de point de distribution compris entre 1 et S, chacune des grappes constituant un objet, le premier critère correspondant à affecter à chaque réceptacle un des groupes et à attribuer à ce réceptacle toutes les grappes appartenant au groupe correspondant, et le second critère correspondant à affecter à chaque réceptable toutes les lettres portant le même numéro de grappe. Avantageusement si d'après la lecture, il s'avère que la répartition conduit à S points de distribution consécutifs ne contenant aucune lettre, ces S points de distribution sont regroupés pour être attribués à un objets fictif supplémentaire, et la répartition est effectuée de nouveau Ceci permet d'utiliser au mieux la place disponible dans les réceptacles. Enfin, selon un perfectionnement important, chacune des étapes de modification est suivie d'une étape d'optimisation du contenu de chacun des réceptacles Cette optimisation est obtenue en minimisant ou en maximisant une fonction dont l'extremum correspond à une répartition optimale du contenu des réceptacles Cette fonction est définie par exemple comme la somme, pour chacun des réceptacles, du carré de la différence entre le contenu d'un réceptacle et le contenu moyen des réceptacles. - Cette optimisation est par exemple un recuit simulé pour lequel les perturbations appliquées sont des déplacements des objets fictifs. Ce perfectionnement permet d'homogénéiser le contenu final des réceptacles de sorte que chaque réceptacle contienne environ le même nombre d'objets De plus, la méthode du recuit simulé s'applique particulièrement bien au traitement des nombres entiers. D'autres caractéristiques et avantages de la présente invention apparaîtront dans la description qui suit d'un procédé selon l'invention, donnée à titre illustratif et nullement limitatif. Dans les figures suivantes: la figure 1 est une vue schématique de dessus d'une machine automatique de tri de courrier, la figure 2 montre un schéma synoptique par blocs des principales étapes du procédé selon l'invention, la figure 3 montre un schéma synoptique par blocs des étapes successives constituant l'étape 70 de la figure 2, la figure 4 montre un schéma synoptique par blocs des étapes successives constituant l'étape 80 de la figure 2, les figures 5 à 9 représentent des tableaux explicatifs de certaines étapes du procédé selon l'invention. On a représenté à la figure 1 une machine automatique de tri de courrier 1 La machine 1 comprend les éléments suivants: un magasin d'approvisionnement 2 sur lequel l'opérateur installe le courrier à traiter Le courrier est alors pris en charge pour être présenté devant un dépileur 3, un dépileur 3 dont le rôle est de séparer les lettres les unes des autres pour les mener une à une sur un système de convoyage 4, une tête de lecture 5 associée à un microprocesseur (non représenté) de contrôle et de pilotage de la machine 1, et placée en regard du système de convoyage 4 pour identifier chaque lettre et lui affecter un réceptacle de rangement 6, une série de réceptacles 6: dix réceptacles de tri dont cinq seulement sont représentés, un réceptacle de rejet mécanique des lettres ne correspondant pas à un format standard, un réceptacle de35 rejet pour code illisible sur la lettre, et un réceptacle de il - débordement (ces trois derniers réceptacles ne sont pas représentés). On va maintenant s'attacher à décrire en détail les étapes successives du procédé selon l'invention. Pour illustrer les opérations effectuées selon ce procédé, on choisira l'exemple précédemment utilisé soit le tri d'environ 3000 lettres destinées à 800 points de distribution Ces 800 points de distribution sont répartis en grappes et en groupes Le tri est alors effectué par une machine à dix réceptacles, en trois passes. La figure 2 est un schéma synoptique global par blocs montrant les étapes principales successives du procédé selon l'invention Ce procédé consiste en un calcul effectué par un programme implanté au sein du microprocesseur de pilotage de la machine de tri Ce calcul détermine la répartition physique des lettres à exécuter par la machine.15 On appellera dans la suite passes canoniques les passes effectuées ou simulées suivant le procédé de tri de l'art antérieur. Les données connues au départ et fournies au programme pour le traitement sont: le nombre de lettres à trier L, le nombre de points de distribution S, le nombre de réceptacles de la machine de tri R. A partir de ces données, le traitement selon l'invention comprend les étapes successives suivantes qui consistent: dans une étape 10, à calculer le nombre de grappes B et de groupes nécessaires au tri en trois passes classiques, ainsi que l'affectation des points de distribution par grappes et des grappes par groupes. Dans l'exemple considéré, le résultat de l'étape 10 est la répartition des 800 points de distribution en huit groupes de dix grappes chacun, avec dix points de distribution par grappe,30 dans une étape 20, à effectuer au sein du microprocesseur, un classement des points de distribution selon un ordre à obtenir impérativement en fin de tri, dans une étape 30, à calculer la différence entre le nombre de grappes total pouvant être contenu dans tous les réceptacles et le nombre de grappes effectivement utilisé pour le tri lors de la passe 12 - canonique employant le moins de réceptacles; cette différence conduit à un nombre de grappes dites fictives BF Le nombre de grappes fictives peut être calculé selon la formule suivante BF = Rx BR B, o BR est le nombre de grappes que peut contenir un réceptacle. Dans l'exemple choisi, on a vu que seuls huit réceptacles sur dix sont utilisés en troisième passe canonique, soit 80 grappes dites réelles. Comme deux réceptacles, prévus pour contenir chacun 10 grappes, restent alors disponibles, on crée 20 grappes fictives de dix points de distribution chacune. L'utilisation de grappes fictives permet, comme cela sera expliqué plus en détail dans la suite, de répartir le courrier plus équitablement dans les réceptacles, afin d'éviter d'éventuels débordements, dans une étape 40, à piloter le tri de première passe canonique Pl et à enregistrer les informations portées par chaque objet afin de déterminer leur répartition La répartition des lettres par point de distribution étant inconnue avant la première passe canonique, cette dernière se déroule comme dans le procédé de l'art antérieur En fin de première passe canonique, chaque réceptacle contient donc toutes les lettres ayant le même numéro de point de distribution, et l'on suppose, pour simplifier, que la première passe ne conduit à aucun débordement de réceptacle Lors de cette passe, toutes les lettres défilent devant la tête de lecture pour être affectées à un25 réceptacle Ainsi, l'information contenant les trois critères de tri et présente sur chaque enveloppe ou sur chaque emballage (sous forme de code barre par exemple) est lue puis enregistrée et mise en mémoire dans le microprocesseur de pilotage, dans une étape 50, à calculer au sein du microprocesseur, la répartition des objets dans les réceptacles, lors des deuxième et troisième passes canoniques Ces répartitions sont calculées selon les deux critères que la première passe canonique n'a pas utilisés, c'est-à-dire les critères de grappe et de groupe, dans une étape 60, à déterminer d'après la répartition calculée à l'étape précédente, la quantité de lettres contenues dans les 13 - réceptacles de troisième passe canonique, dans une étape 70, à effectuer une première modification de la réparitition de troisième passe canonique, pour obtenir une répartition de troisième passe modifiée, de sorte qu'aucun réceptacle 5 ne se trouve en débordement, dans une étape 80, à déduire de la répartition calculée à l'étape 70 une répartition de deuxième et de troisième passes définitives telles qu'aucune de ces deux passes ne conduise à un débordement de réceptacles,10 dans une étape 90, à piloter la machine de tri pour qu'elle exécute la deuxième passe P 2 selon la répartition définitive calculée à l'étape 80, dans une étape 100, à piloter la machine de tri pour qu'elle exécute la troisième passe P 3 selon la répartition définitive calculée à l'étape 80. On va à présent détailler le fonctionnement des étapes 70 et 80, caractéristiques du traitement selon l'invention. La figure 3 est un schéma synoptique par blocs des opérations successives constituant l'étape 70 Le traitement de l'étape 70 utilise toutes les données précédentes ainsi que la donnée du contenu (en lettres) de chaque réceptacle de troisième passe canonique déterminé lors de l'étape 60 Ce traitement consiste: dans une étape 71, à affecter les grappes fictives aux réceptacles non utilisés lors du tri de troisième passe canonique, dans une étape 72, à sélectionner le réceptacle de troisième passe canonique le plus rempli (c'est-à-dire contenant le plus grand nombre de lettres), dans une étape 73, à affecter une grappe fictive à ce réceptacle, en la plaçant après les grappes réelles, ce qui revient à décaler toutes les grappes pour conserver leur ordre relatif, et à affecter l'une d'elles au premier réceptacle vide, dans une étape 74, à incrémenter la variable I correspondant au nombre de grappes fictives ainsi transférées, dans une étape 75, à comparer I au nombre de grappes fictives disponibles BF: si I est inférieur à BF, le traitement réitère les 14 - étapes 72 à 75; si I est égal à BF, le traitement passe à l'étape 80. Il est préférable, en effet, pour parvenir à éviter tous les débordements dans les deuxième et troisième passes, de déplacer toutes les grappes fictives Toutefois, il est également possible de passer au traitement de l'étape 80 dès que chacun des réceptacles de troisième passe contient soit uniquement des grappes réelles soit à la fois des grappes réelles et des grappes fictives, mais jamais uniquement des grappes fictives. Le traitement de l'étape 70 revient donc à répartir le contenu des réceptacles de troisième passe canonique dans tous les réceptacles disponibles, grâce à l'artifice des grappes fictives Chaque réceptacle contient alors le nombre maximal de grappes pour lequel il est prévu, ces grappes pouvant être des grappes réelles ou fictives. Cette opération n'affecte en rien l'ordonnancement impératif des grappes à respecter, car elle consiste en pratique à insérer des "vides" dans les réceptacles L'ordre des grappes prévu par le procédé de tri classique est donc conservé. Afin d'illustrer ce qui vient d'être décrit, on en revient à l'exemple choisi Le procédé classique prévoit, pour la troisième passe canonique, la répartition de 80 grappes réelles (que l'on note BO à B 79) dans les huit premiers réceptacles par exemple (RO à R 7) Le traitement selon l'invention part donc de la répartition de troisième passe canonique suivante (en notant BFI à BF 20 les 20 grappes fictives): RO Rl R 7 R 8 R 9 BO B 10 B 70 BF 1 BF 11 l l l I l B 9 B 19 B 79 BF 10 BF 20 Supposons que l'étape 72 sélectionne RO comme réceptacle de troisième passe canonique le plus rempli Le résultat de l'étape 73 est alors RO Rl R 2 R 7 R 8 R 9 BO B 9 B 19 B 69 B 79 BF 11 I I I I BF 2 B 8 I I I I I BF 1 B 18 B 28 B 78 BF 10 BF 20 - On a maintenant I= 1 Comme BF= 20, le traitement reprend à l'étape 72. Supposons que cette étape sélectionne encore le réceptacle RO comme étant le plus rempli Le résultat de l'étape 73 est maintenant RO Ri R 2 R 7 R 8 R 9 BO B 8 B 18 B 68 B 78 B Fll l l I I B 79 l B 7 I I | BF 3 l BF 1 l I I I I BF 2 B 17 B 27 B 77 BF 10 BF 20 On a I= 2 Le traitement reprend à l'étape 72. Une fois toutes les grappes fictives réparties, le dépilage des réceptacles de fin de troisième passe et leur rangement dans l'ordreconduit bien à respecter l'ordre impératif des grappes réelles On comprend donc que la position des grappes fictives à l'intérieur d'un réceptacle n'a aucune importance sur la position relative des grappes réelles dans ce réceptacle En revanche, elle entraîne une modification du contenu des réceptacles de la deuxième passe canonique. Le traitement de l'étape 80 est destiné à prévoir le contenu des réceptacles de deuxième passe, sachant qu'on ne modifie plus le contenu réel des réceptacles de troisième passe obtenu à la suite de l'étape 70. La figure 4 est un schéma synoptique par blocs des opérations successives constituant l'étape 80 Ce traitement consiste dans une étape 801, à déterminer le contenu de chacun des réceptacles dans lesquels doivent se trouver les grappes réelles et fictives à la fin d'une deuxième passe provisoire agencée de manière à permettre la répartition de troisième passe modifiée obtenue à l'étape , dans une étape 802, à sélectionner le réceptacle de deuxième passe provisoire le plus rempli et contenant plus de lettres que ne le permet sa contenance maximale,35 dans une étape 803, à sélectionner le réceptacle de troisième passe 16 - modifiée contenant le plus de grappes fictives non encore déplacées ou "traitées" par le traitement de l'étape 80 S'il existe plusieurs réceptacles répondant à ce critère, il est préférable de choisir celui qui, après le traitement de l'étape 807 (voir ci-dessous), permettra 5 la plus grande diminution du contenu du réceptacle de deuxième passe sélectionné, dans une étape 804, à chercher s'il existe, dans le réceptacle de troisième passe modifiée contenant le plus de grappes fictives non traitées, une grappe fictive dont la position dans ce réceptacle de troisième passe modifiée indique qu'elle provient du réceptacle de deuxième passe provisoire le plus rempli, dans une étape 805, déclenchée si la grappe fictive recherchée à l'étape 804 existe, à choisir, s'il existe, le réceptacle de troisième passe modifiée répondant au critère de l'étape 803 et différent de ceux précédemment trouvés à cette étape; si un tel réceptacle existe, le traitement est effectué de nouveau à partir de l'étape 804, dans une étape 806, déclenchée s'il n'existe plus de réceptacles de troisième passe modifiée répondant au critère de l'étape 803, à choisir un autre réceptacle de deuxième passe provisoire répondant au20 critère de l'étape 802 et différent de ceux précédemment choisis à cette étape, puis à effectuer de nouveau le traitement à partir de l'étape 803, dans une étape 807, déclenchée si la grappe fictive recherchée à l'étape 804 n'existe pas, à remplacer la grappe réelle du réceptacle de troisième passe modifiée sélectionné dont la position dans ce réceptacle indique qu'elle provient du réceptacle de deuxième passe provisoire le plus rempli, par une grappe fictive du réceptacle de troisième passe modifiée sélectionné, et à décaler toutes les autres grappes de ce réceptacle de troisième passe modifiée afin de conserver30 leur ordre relatif Cette opération revient donc à retirer au réceptacle de deuxième passe provisoire le plus rempli, une de ses grappes pour la remplacer par une grappe fictive, et donc à diminuer son contenu, dans une étape 808, à affecter à la grappe fictive déplacée à l'étape précédente une valeur (par exemple T= 1) indiquant que cette 17 - grappe a été "traitée" et que, par conséquent, elle ne sera plus déplacée dans la suite du traitement, dans une étape 809, à incrémenter la variable correspondant au nombre TT de grappes fictives traitées, c'est-à-dire affectées de la valeur T= 1, dans une étape 810, à comparer TT au nombre de grappes fictives disponibles BF: si ces deux nombres sont égaux, le traitement passe à l'étape 90; si TT est strictement inférieur à BF, le traitement reprend à partir de l'étape 802. Il est préférable à présent d'illustrer par un exemple le traitement effectué au cours de l'étape 80 Pour cela, on représente l'état des réceptacles de deuxième et troisième passe dans une matrice ou un tableau à deux entrées. Les figures 5 à 9 illustrent différents états d'un tel tableau. Chaque colonne, numérotée CO à C 9, représente un réceptacle de deuxième passe Chaque ligne, numérotée LO à L 9, représente un réceptacle de troisième passe, c'est-à-dire un groupe. A la figure 5, on a représenté le tableau figurant l'état des réceptacles de deuxième et troisième passes canoniques. Le tri de deuxième passe canonique conduit à affecter à chaque réceptacle un numéro de grappe; toutes les grappes correspondant par exemple à l'indice b=l dans les différents groupes sont regroupées dans le réceptacle RO (colonne CO) En pratique, les grappes indicées b=l sont par exemple BO, Bl O, B 20, B 30, B 70. Le tri de troisième passe canonique conduit à affecter à chaque réceptacle un numéro de groupe; ainsi, les dix grappes du premier groupe, par exemple, sont regroupées, dans l'ordre, dans le réceptacle RO (ligne LO). La figure 6 représente un tableau figurant un état possible des réceptacles de troisième passe modifiée calculé lors de l'étape 70. Dans cet exemple, on suppose que le réceptable R 3 (colonne C 3) est le réceptacle de deuxième passe provisoire le plus rempli Le résultat de l'étape 803 est le choix du réceptacle de troisième passe R 2 (ligne L 2), qui possède quatre grappes fictives BF 4, BF 5, BF 6, BF 735 alors que les autres réceptacles de troisième passe modifiée en 18 - possèdent trois au plus Dans le réceptacle de troisième passe modifiée R 2 (ligne L 2), aucune des quatre grappes fictives ne provient du réceptacle de deuxième passe provisoire R 3 (elles appartiennent aux réceptacles de deuxième passe provisoires respectifs R 6, R 7, R 8 et 5 R 9) On passe donc à l'étape 807 Elle conduit à mettre BF 4 dans la position de B 20 et à décaler B 20 et toutes les grappes suivantes pour conserver leur ordre relatif Le tableau de la figure 7 illustre le résultat obtenu après cette étape On comprend donc bien que l'ordre relatif des grappes dans le réceptacle de troisième passe modifiée10 choisi (R 2, ligne L 2) n'est pas modifié en pratique Après ce traitement, la grappe fictive BF 4 est "traitée": elle ne pourra plus être déplacée Après l'étape 809, la variable TT est égale à 1 et BF à Le traitement reprend donc à l'étape 802. Supposons qu'à présent, le réceptacle de deuxième passe provisoire le plus rempli soit RI (colonne Cl) Plusieurs réceptacles de troisième passe modifiée contiennent le même nombre de grappes fictives non encore traitées On choisira encore pour rendre l'exemple plus instructif, le réceptacle de troisième passe modifiée R 2 (ligne L 2) comme résultat de l'étape 803 Dans ce réceptacle de troisième passe modifiée R 2 (ligne L 2), aucune grappe fictive n'appartient déjà au réceptacle de deuxième passe provisoire RI (colonne Cl); on passe alors à l'étape 807 Elle conduit à placer BF 5 dans la position de B 18 et à décaler B 18 et toutes les grappes suivantes pouvant être décalées (c'est-à-dire à l'exception de BF 4),25 pour conserver leur ordre relatif Le tableau de la figure 8 illustre le résultat obtenu après cette étape. Le traitement se poursuit jusqu'à ce que toutes les grappes fictives soient "traitées". On va maintenant examiner le cas d'un autre état possible des réceptacles de troisième passe modifiée par l'étape 70 Le tableau illustrant cet état est toujours représenté en figure 6, mais à présent, on suppose que le réceptacle de deuxième passe provisoire le plus rempli est le réceptacle R 6 (colonne C 6) Le réceptacle de troisième passe modifiée contenant le plus grand nombre de grappes35 fictives est encore R 2 (ligne L 2), résultat de l'étape 803 Cette 19 - fois-ci dans le réceptacle de troisième passe modifiée R 2 (ligne L 2), une grappe fictive BF 4 appartient déjà au réceptacle de deuxième passe provisoire le plus rempli R 6 (colonne C 6) La suite de l'étape 804 est donc l'étape 805 Son résultat est le réceptacle de troisième passe modifiée Rl (ligne Ll), qui n'a pas encore été trouvé à l'étape 803. Ce réceptacle de troisième passe modifiée ne contient pas de grappe fictive appartenant au réceptacle de deuxième passe provisoire R 6 (colonne C 6) On peut donc passer à l'étape 807 qui conduit au résultat illustré par le tableau de la figure 9. Les répartitions définitives obtenues après le calcul de l'étape conditionnent les actions de la machine de tri lors des deuxième et troisième passes physiques, par un contr 8 le de ces passes lors des étapes 90 et 100. Ainsi, grâce au procédé de tri selon l'invention, aucun réceptacle ne déborde lors des deuxième et troisième passes Cet avantage important permet d'utiliser effectivement les machines de tri automatique en trois passes Ces machines ne sont en effet pas utilisées à l'heure actuelle étant donnés les problèmes de débordements engendrés par le procédé de tri en trois passes de l'art antérieur Le procédé selon l'invention représente ainsi un gain financier important Il représente également un gain de temps, car il permet d'utiliser une machine de tri rapide. En outre le calcul effectué entre les première et deuxième passes n'augmente pas le temps nécessaire aux autres opérations effectuées entre ces deux passses, c'est-à-dire le temps pendant lequel l'opérateur (ou la machine) transfère le contenu des réceptacles de première passe vers le magasin d'approvisionnement. Ainsi, le temps de transfert est d'environ 1 min 30 s, alors que le temps de calcul est d'au plus une quinzaine de secondes. Le procédé selon l'invention s'applique bien entendu tout particulièrement au tri postal en trois passes Toutefois, il n'est pas limité à ce tri, et peut concerner le tri d'objets quelconques en au moins deux passes selon au moins deux critères distincts (à chaque passe canonique est affecté un critère de tri), du moment que les35 réceptacles de la machine de tri sont en quantité inférieure au nombre - d'objets à trier et qu'il y a risque de débordement de ces réceptacles Afin de pouvoir appliquer le procédé selon l'invention il est ainsi nécessaire que le nombre d'objets à trier soit inférieur à la contenance totale de la machine de tri Ceci permet d'utiliser l'artifice d'ensembles des fictifs comme les grappes fictives Plus précisément, on peut appliquer le procédé selon l'invention si R > S pour le tri des lettres dans S points de distribution, en N passes dans une machine à R réceptacles. Pour un tri en N passes, on commence par effectuer le traitement selon l'invention aux N -ième et N-1 -ième passes, puis aux N-1 -ième et N-2 ième passes, et ainsi de suite jusqu'aux dernières passes que l'on désire modifier. Plusieurs cas se présentent en pratique pour la première passe. Dans un premier cas, une répartition statistique des lettres est connue, permettant d'établir l'affectation de chaque point de distribution en première passe (ou lors d'un premier passage des lettres en machine) En général, cette affectation n'entraîne pas de débordements, puisqu'elle prend en compte des résultats statistiques de tris précédents Si, toutefois, des débordements ont lieu pendant ce premier passage, il suffit de modifier l'affectation de manière à éviter ces débordements L'enregistrement des informations portées par les lettres est effectué pendant cette première passe. Dans un second cas, la première passe est effectuée selon le critère canonique mentionné dans le préambule C'est l'hypothèse choisie pour l'étape 40 précédemment décrite Si une telle passe conduit à des débordements, elle est effectuée de nouveau avec une modification des affectations qui dépend des informations enregistrées lors du premier passage. Enfin, dans un troisième cas, les informations portées par les lettres sont lues et enregistrées préalablement à toute passe Dès lors, le procédé selon l'invention est appliqué à toutes les passes en les considérant deux à deux à partir de la dernière Ceci conduit finalement à une répartition optimisée de toutes les passes physiques. On peut par exemple appliquer ce procédé au routage de pellicules photographiques dans un centre de développement. 21 - Bien évidemment, le procédé selon l'invention n'est pas limité à la description précédente. En particulier, si l'on constate, après la première passe physique, que dix points de distribution consécutifs ne contiennent aucune lettre, il est possible de supprimer ces dix points de distribution, en décalant la numérotation des suivants, pour en faire une grappe fictive supplémentaire. D'autre part, il est possible d'améliorer le traitement effectué aux opérations 70 et 80 En effet, ce traitement permet d'éviter les débordements Il est parfois souhaitable de surcroît que chaque réceptacle contienne des piles de tailles sensiblement équivalentes, car cela facilite le travail de l'opérateur devant les transférer dans le magasin d'approvisionnement Pour cela, on peut effectuer, après l'étape 70 et après l'étape 80, une opération d'optimisation par un15 procédé d'optimisation classiquement utilisé Le but de cette optimisation est par exemple de minimiser la fonction F dite fonction de coût définie par la somme, sur tous les réceptacles de deuxième ou de troisième passe, du carré de la différence entre le contenu d'un réceptacle et le contenu moyen de tous les réceptacles Pour minimiser20 la fonction F, on peut par exemple utiliser un procédé d'optimisation par recuit simulé, bien connu de l'homme de métier et décrit dans l'article intitulé:"Le recuit simulé", écrit par Ernesto Bonomi et Jean-Luc Lutton, paru dans Pour la Science N O 129 de juillet 1988, pages 68 à 77 Dans ce cas, on peut choisir comme perturbations les25 déplacements de grappes fictives, par exemple. Il est également possible d'utiliser tout autre procédé connu d'optimisation, comme par exemple la méthode du gradient Toutefois, le procédé de recuit simulé est mieux adapté au traitement des nombres entiers.30 22 - REVENDICATIONS 1/ Procédé de tri d'objets en N passes de distribution physique dans R réceptacles d'une machine de tri contr 8 lée par un moyen de contr 8 le, N étant au moins égal à deux, caractérisé en ce qu'il comprend les étapes suivantes: lecture et mise en mémoire dans ledit moyen de contrôle d'informations codées portées par lesdits objets, lesdites informations comportant N critères distincts par objet, classement en mémoire dans ledit moyen de contr 8 le desdits objets dans un ordre donné de sorte que chacun desdits objets est affecté à une destination, calcul, au sein dudit moyen de contr 8 le, de la répartition desdits objets dans lesdits réceptacles, lors d'une N-i -ième passe canonique, c'est-à-dire telle que tous les objets qui ont la même valeur d'un premier desdits critères soient affectés à un même réceptacle, calcul, au sein dudit moyen de contr 8 le, de la répartition desdits objets dans lesdits réceptacles lors d'une N -ième passe canonique telle que tous lesdits objets qui ont la même valeur d'un deuxième desdits critères soient affectés à un même réceptacle et que leur ordre respecte ledit ordre donné, première modification par ledit moyen de contr 8 le de ladite répartition de ladite N -ième passe canonique, fournissant une répartition de N -ième passe modifiée, telle que le nombre d'objets dans chacun desdits réceptacles soit rendu au plus égal à P, P étant25 le nombre maximal d'objets que peut contenir chacun desdits réceptacles, détermination du contenu de chacun des réceptacles dans lesquels doivent se trouver lesdits objets à la fin d'une N-1 -ième passe provisoire, agencée de manière à permettre ladite répartition de30 N -ième passe modifiée, seconde modification de ladite répartition de N ième passe modifiée, fournissant une répartition de N -ième passe définitive, si le contenu de l'un desdits réceptacles dans lesquels doivent se trouver lesdits objets à la fin de ladite N-1 -ième passe provisoire35 dépasse P, de sorte que l'ordre desdits objets reste semblable audit 23 - ordre donné et que la répartition d'une N-1 -ième passe définitive agencée de manière à permettre ladite répartition de N ième passe définitive conduise à des réceptacles contenant chacun au plus P objets, reprise de toutes les étapes précédentes en remplaçant N par N-1 et N-1 par N-2, et ainsi de suite jusqu'aux deux dernières des passes destinées à être modifiées, tri desdits objets par ladite machine selon les répartitions définitives déterminées. 2/ Procédé selon la revendication 1, caractérisé en ce que, si R est strictement supérieur au nombre desdites destinations, ladite première modification comprend les étapes suivantes: sélection du réceptacle de ladite N -ième passe canonique dont le contenu dépasse P et qui est plus rempli que tous les autres, affectation de l'un desdits objets de ce réceptacle au réceptacle suivant, sans modifier l'ordre donné desdits objets, réitération de ladite sélection et de ladite affectation si le contenu de l'un desdits réceptacles de ladite N -ième passe canonique dépasse P, attribution en mémoire, à chacun desdits réceptacles de ladite N -ième passe modifiée, d'un nombre d'objets dits réels, correspondant au nombre d'objets contenu dans chacun desdits réceptacles, et d'un nombre d'objets dits fictifs, correspondant à la différence entre P et ledit nombre d'objets réels,25 mise en oeuvre de ladite étape de détermination si aucun desdits réceptacles de ladite N -ième passe canonique n'a un contenu strictement supérieur à P. 3/ Procédé selon les revendications 1 et 2, caractérisé en ce que ladite seconde modification comprend les étapes suivantes: une première étape de sélection du réceptacle de ladite N-1 -ième passe provisoire dont le contenu dépasse P et qui est plus rempli que tous les autres, une seconde étape de sélection du réceptacle de ladite N -ième passe modifiée le moins rempli et contenant le plus d'objets fictifs, considérés comme non traités, A P 24 - une troisième étape de recherche dans ledit réceptacle de ladite N -ième passe modifiée sélectionné à ladite seconde étape, d'un objet fictif dit éventuel dont la position dans ledit réceptacle sélectionné indique qu'il provient dudit réceptacle de N -ième passe provisoire sélectionné à ladite première étape, une cinquième étape de sélection, si ledit objet fictif éventuel existe, d'un réceptacle de ladite N -ième passe modifiée le moins rempli contenant le plus d'objets fictifs considérés comme non traités, et distinct desdits réceptacles de ladite N -ième passe modifiée les moins remplis et contenant le plus d'objets fictifs considérés comme non traités déjà sélectionnés lors de ladite seconde étape ou de ladite cinquième étape, ladite seconde modification reprenant à partir de ladite troisième étape s'il existe un réceptacle sélectionné à ladite cinquième étape, une sixième étape de sélection, s'il n'existe pas de réceptacle sélectionné à ladite cinquième étape, d'un réceptacle de ladite N-1 -ième passe provisoire dont le contenu dépasse P, plus rempli que tous les autres et distinct desdits réceptacles de ladite N-i -ième passe provisoire dont le contenu dépasse P et les plus remplis déjà sélectionnés lors de ladite première étape ou de ladite sixième étape, puis reprise de ladite seconde modification à partir de ladite seconde étape, une septième étape, déclenchée si ledit objet fictif éventuel n'existe pas, ce qui signifie qu'un un objet réel a une position dans ledit réceptacle de N - ième passe modifiée sélectionné qui indique qu'il provient dudit réceptacle de N-1 -ième passe sélectionné à ladite première étape, de remplacement dudit objet réel par un objet fictif du réceptacle de ladite N -ième passe modifiée, en conservant l'ordre desdits objets réels, une huitième étape d'attribution de la qualité "traité" audit objet fictif éventuel, réitération desdites étapes précédentes si la quantité d'objets fictifs "traités" est inférieure au nombre d'objets fictifs total initial. 4/ Procédé selon l'une des revendications 1 à 3, caractérisé en ce que à ' w - ladite lecture a lieu pendant un premier passage desdits objets dans ladite machine, effectué effectuée selon un critère spécifique, lesdites deux dernières passes destinées à être modifiées étant alors les troisième et seconde passes. 5/ Procédé selon la revendication 4, caractérisé en ce que ledit critère spécifique est un critère statistique. 6/ Procédé selon la revendication 4, caractérisé en ce que ledit critère spécifique est l'un desdits N critères. 7/ Procédé selon l'une des revendications 1 à 3, caractérisé en ce que lesdites deux dernières passes destinées à être modifiées sont les seconde et première passes. 8/ Procédé selon l'une des revendications 1 à 7, caractérisé en ce que ledit tri est un tri en trois passes destiné au tri de L lettres d'un courrier, et en ce que ladite lecture est précédée par une répartition desdites L lettres en G groupes de B grappes chacun, chacune desdites grappes contenant S points de distribution desdites lettres, de sorte que chacune desdites lettres porte un numéro de groupe compris entre 1 et G, un numéro de grappe compris entre 1 et B et un numéro de point de distribution compris entre 1 et S, chacune desdites grappes20 constituant un desdits objets, ledit premier critère correspondant à affecter à chaque réceptacle un desdits groupes et à attribuer à ce réceptacle toutes les grappes appartenant au groupe correspondant, et ledit second critère correspondant à affecter à chaque réceptacle toutes les lettres portant le même numéro de grappe.25 9/ Procédé selon la revendication 8, caractérisé en ce que, si d'après ladite lecture, il s'avère que ladite répartition conduit à S points de distribution consécutifs ne contenant aucune lettre, lesdits S points de distribution sont regroupés pour être attribués à un objet fictif supplémentaire, et ladite répartition est effectuée de nouveau.30 10/ Procédé selon l'une des revendications 1 à 9, caractérisé en ce que chacune desdites modifications est suivie d'une étape d'optimisation du contenu de chacun desdits réceptacles. 11/ Procédé selon la revendication 10 caractérisé en ce que ladite optimisation est obtenue en minimisant ou en maximisant une fonction dont l'extremum correspond à une répartition optimale du contenu A ' r 26 - desdits réceptacles. 12/ Procédé selon la revendication 11 caractérisé en ce que ladite fonction est définie comme la somme, pour chacun desdits réceptacles, du carré de la différence entre le contenu d'un réceptacle et le 5 contenu moyen desdits réceptacles. 13/ Procédé selon l'une des revendications 10 à 12, caractérisé en ce que ladite optimisation est un recuit simulé. 14/ Procédé selon les revendications 10 à 13, caractérisé en ce que ladite optimisation est un recuit simulé pour lequel les perturbations appliquées sont des déplacements desdits objets fictifs.