Note: Descriptions are shown in the official language in which they were submitted.
2Q78468
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
5 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 l-^h;nes de tri pour de petits centres de
10 tri réalisant ce que l'on appelle le tri~ int -nt 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, le
5 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 r~chines~ une optimisation du nombre de destina-
tions de tri, et donc du nombre de réceptacles de la l~chine a été
20 effectuée. On a ainsi diminué le nombre de réceptacles de la -^hine,
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
30 courrier suivant un ordre à respecter scrupuleusement :
l'ordonnancement du courrier doit correspondre exactement au trajet
réellement suivi par le facteur, et cet ord~nn~ncement doit être
impérativement respecté tout au long du processus de tri.
Suivant le nombre de lettres à trier, le nombre de destinations,
35 la méthode de tri choisie, etc..., plusieurs passes de tri successives
*
2 0 7 8 q 6 8
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, lO, Valet, Dame, Roi,
- la valeur des couleurs, par exemple dans l'ordre suivant : Coeur,
Carreau, Pique, Trèfle.
10 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.
15 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 :
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
Roi Coeur Roi Carreau ............. ....Roi Trèfle
~Q78~68
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é.
S On comprend donc que deux exigences principales doivent 8tre
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
10 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,
15 - 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
20 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 ~ch;ne 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 à classer
25 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
30 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 de
35 la grappe b dans le groupe g.
2078468
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é tas6eur ou empileur car les
lettres y sont rangées les unes contre les autres en conætituant une
pile) est affecté à un numéro de ~top. En fin de passe, on obtient :
Réceptacle 1 : Lgbl , quels que soient g et b
Réceptacle 2 : Lgb2 , quels que soient g et b
Réceptacle 10 : LgblO , 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 de grappe. En fin de
passe, on obtient :
Réceptacle 1 Réceptacle 2 ............ Réceptacle 10
Lgl,1 Lg2,1 ................ .LglO,l
Lgl,2 Lg2,2 ................ .LglO,2
Lgl,3 Lg2,3 ................ .LglO,3
Lgl,10 Lg2,10 ............... .LglO,10
et ce quel que soit g dans chaque réceptacle.
Les lettres contenues dans les réceptacles sont transferees 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.
207~68
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 :
s
Réceptacle 1 Réceptacle 2 ............... Réceptacle 8
L1,1,1 L2,1,1 ................... L8,1,1
L1,1,2 L2,1,2 ................... L8,1,2
L1,1,3 L2,1,3 ................... L8,1,3
L1,2,1 L2,2,1 ................... L8,2,1
L1,2,2 L2,2,2 ................... L8,2,2
L1,10,1 L2,10,1 .................. L8,10,1
L1,10,2 L2,10,2 .................. L8,10,2
L1,10,10 L2,10,10 ................. L8,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
ne tient pas compte de la quantité de lettres par point de
distribution, 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, 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é-
néiser la répartition des objets dans les réceptacles et donc d'éviter
2078~68
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.
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ôle
10 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
~ans un ordre donné de sorte que chacun desdits objets est affecté à
une destination,
15 - calcul, au sein dudit moyen de contrôle, de la répartition desdits
objets dans lesdits réceptacles, lors d'une N-l -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
20 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 sYi -l 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-l -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
35 modifiée, fournissant une répartition de N -ième passe définitive, si
207~68
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 remplasant 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 ach; ne 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 - 2 0 7 8 ~t 6 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 quatrième étape de se~ection, si cet ob~et fictif éventuel
existe, d'un réceptacle de N -ième passe modifiée le moins rempli
contenant le plu6 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 quatrième étape,
la seconde modification reprenant à partir de la troisième étape s'il
existe un réceptacle sélectionné à la quatrième étape,
- une cinquième étape de sélection, s'il n~existe pas de réceptacle
sélectionné à la quatrième étape, d'un réceptacle de la N-l -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 cinquième étape, puis reprise de la seconde
modification à partir de la seconde étape,
- une sixième étape, déclenchée si l'objet fictif éventuel n'existe
pas, ce qui signifie qu'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 provient
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 septième étape d'attribution de la qualité "traité" à l'objet
fictif éventuel,
30 - 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 place
disponible dans les réceptacles afin d'éviter tout débordement.
2078468
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ème 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éceptacle 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 objet 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 ~x; ;sant 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.
~ 2078~8
-- 10 --
Cette optimisatlon 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,
15 - 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
20 é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
30 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 de
rejet pour code illisible sur la lettre, et un réceptacle de
2~78~68
11
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 implante au
sein du microprocesseur de pilotage de la machine de tri. Ce calcul
determine la répartition physique des lettres à exécuter par la
machine.
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,
20 - 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
2078468
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 = RxBR - 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,
15 - dans une étape 40, à piloter le tri de première passe canonique P1
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 à un
2S réceptacle. Ainsi, l'information contenant les trois critères de tri
et présente sur chaque enveloppe ou sur chaque emballage tsous 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 - 2 ~ 7 8 4 6 8
réceptacles de troisième passe canonique,
- dans une étape 70, à effectuer une première modification de la
~ w~-ition de troisième paæse canonique, pour obtenir une
répartition de troisième passe modifiée, de sorte qu'aucun réceptacle
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 P2 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 pasæe P3 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
20 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 conslcte :
- 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 tc'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
30 les grappes pour conserver leur ordre relatif, et à affecter l'une
d'elles au premier réceptacle vide,
- dan~ 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
207.~4~8
- 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 -Yil-l 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
15 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
B0 à B79) dans les huit premiers réceptacles par exemple (R0 à R7). Le
traitement selon l'invention part donc de la répartition de troisième
passe canonique suivante (en notant BFl à BF20 les 20 grappes
fictives) :
R0 Rl .......... R7 R8 R9
B0 B10 ......... B70 BFl BFll
I
B9 Bl9 ......... B79 BF10 BF20
Supposons que l'étape 72 sélectionne R0 comme réceptacle de troisième
passe canonique le plus rempli. Le résultat de l'étape 73 est alors :
R0 Rl R2 ......... R7 R8 R9
B0 B9 Bl9 ........ B69 B79 BFll
l l l l BF2
B8 l l l l
BFl B18 B28 ........ B78 BF10 BF20
2078468
_ 15 -
On a maintenant I=l. 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 Rl R2 ......... R7 R8 R9
BO B8 B18 ........ B68 B78 BFll
l l l l B79
B7 ¦ l BF3
BFl
10 BF2 B17 B27 ........ B77 BF10 BF20
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'ordre
15 conduit bien à respecter l'ordre impératif des grappes réelles. On
cc . end 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
20 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
70,
- 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 ~~ le,
- dans une étape 803, à sélectionner le réceptacle de troisième passe
~073468
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
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
10 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
15 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 au
20 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, à re pl~cer 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 conserver
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 r~ l~cer 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
2078468
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=l,
- 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.
15 Chaque colonne, numérotée C0 à C9, représente un réceptacle de
deuxième passe. Chaque ligne, numérotée L0 à L9, 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 R0 (colonne C0). En pratique, les grappes indicées
b=1 sont par exemple B0, B10, B20, B30,...B70.
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
R0 (ligne L0).
La figure 6 représente un tableau figurant un état possible des
30 réceptacles de troisième passe modifiée calculé lors de l'étape 70.
Dans cet exemple, on suppose que le réceptable R3 (colonne C3)
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
R2 (ligne L2), qui possède quatre grappes fictives BF4, BF5, BF6, BF7
alors que les autres réceptacles de troisième passe modifiée en
2078468
- 18 -
possèdent trois au plus. Dans le réceptacle de troisième passe
modifiée R2 (ligne L2), aucune des quatre grappes fictives ne provient
du réceptacle de deuxième passe provisoire R3 (elles appartiennent aux
réceptacles de deuxième passe provisoires respectifs R6, R7, R8 et
R9). On passe donc à l'étape 807. Elle conduit à mettre BF4 dans la
position de B20 et à décaler B20 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ée
10 choisi (R2, ligne L2) n'est pas modifié en pratique. Après ce
traitement, la grappe fictive BF4 est "traitée" : elle ne pourra plus
être déplacée. Après l'étape 809, la variable TT est égale à 1 et BF à
20. Le traitement reprend donc à l'étape 802.
Supposons qu'à présent, le réceptacle de deuxième passe
15 provisoire le plus rempli soit Rl (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 R2
(ligne L2) comme résultat de l'étape 803. Dans ce réceptacle de
20 troisième passe modifiée R2 (ligne L2), aucune~grappe fictive
n'appartient déjà au réceptacle de deuxième passe provisoire R1
(colonne Cl) ; on passe alors à l'étape 807. Elle conduit à placer BF5
dans la position de B18 et à décaler B18 et toutes les grappes
suivantes pouvant être décalées (c'est-à-dire à l'exception de BF4),
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 R6 (colonne C6). Le réceptacle de
troisième passe modifiée contenant le plus grand nombre de grappes
fictives est encore R2 (ligne L2), résultat de l'étape 803. Cette
21)~8~
-- 19 --
fois-ci dans le réceptacle de troisième passe modifiée R2 (ligne L2),
une grappe fictive BF4 appartient déjà au réceptacle de deuxième passe
provisoire le plus rempli R6 (colonne C6). 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 R6
(colonne C6). 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
80 conditionnent les actions de la machine de tri lors des deuxième et
troisième passes physiques, par un controle de ces passes lors des
étapes 90 et lOO.
Ainsi, grâce au procédé de tri selon l'invention, aucun
15 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
20 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 l min 30s, alors que le
temps de calcul est d'au plus une qli n~ ine 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 les
réceptacles de la machine de tri sont en quantité inférieure au nombre
- 2~468
- 20 -
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
10 selon l'invention aux N -ième et N-l -ième passes, puis aux N-l -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
15 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
20 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.
- 20~8~68
- 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
10 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 un
15 procédé d'optimisation classiquement utilisé. Le but de cette
optimisation est par eY~ .~e 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 I ini iser
20 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 129 de juillet 1988,
pages 68 à 77. Dans ce cas, on peut choisir comme perturbations les
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.
