• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    A method of sequencing charges in an automated dispensing system comprising sources, at least one destination, a collector (comprising a plurality of successive nodes) and a control system (configured to process commands). For at least one analyzed node, an injection analysis step comprises the following steps, to decide whether a load C having a given destination sequence number for a given destination can be injected on the collector: creation (Ail) among charges to be collected by at least one node downstream of the analyzed node, from a list LI1 of charges having a destination order number less than the given destination order number and a list LI2 of charges which are each interposed between a load of the list LI1 and the collector; test (T 13) to determine if a condition is checked among "the list LI1 is empty" and "the list LI1 is not empty and the list LI2 is empty"; if one of the two conditions is satisfied, injection (30) of the charge C.
    公开号:FR3058708A1
    申请号:FR1661103
    申请日:2016-11-16
    公开日:2018-05-18
    发明作者:Jean-Michel Collin
    申请人:Savoye SA；
    IPC主号:
    专利说明:

    1. TECHNICAL AREA
    The field of the invention is that of logistics, and in particular that of automated distribution systems, in particular, but not exclusively, for the preparation of orders (also called "package preparation").
    More specifically, the invention relates to a method of sequencing charges in such an automated distribution system.
    It is assumed that the automated distribution system comprises sources, at least one destination, a collector and a control system. The collector is configured to transport loads to each destination and includes a plurality of successive nodes each configured to collect loads coming from one of the sources.
    The control system is configured to:
    • process orders listing each of the charges to be extracted from the sources and to be supplied in an increasing order of destination given to a given destination;
    • define an increasing global order for the loads listed in the orders; and • guarantee for each source that outgoing loads respect the increasing global order and the increasing destination orders associated with the orders.
    The control system (also called SGE, for “Warehouse Management System”, or WCS, for “Warehouse Control System” in English) is a central management IT system, responsible for steering the entire system automated distribution, as well as order management.
    The processing (or management) of a given order brings together all the actions carried out by the control system to control the automated distribution system (including the sources) so that all the loads listed in this given order arrive at the desired destination in the desired destination order.
    The invention applies in particular, but not exclusively, in the case where each source of the automated distribution system is a part of a storage warehouse (this part is also called “storage assembly” in the following description) and each destination of the automated distribution system is an order preparation station (also called a "picking station").
    It is clear, however, that many variants can be envisaged without departing from the scope of the present invention: for example, each source can be defined as a storage magazine, or even as an assembly comprising several storage magazines, or even as a storage device. storage (less complex than a storage store).
    2. TECHNOLOGICAL BACKGROUND
    In the remainder of this document, we will endeavor to describe the problem existing in the particular case where the automated distribution system is used for the preparation of packages. The invention is of course not limited to this particular application.
    Package preparation systems are more particularly used in shipping and distance selling businesses for small volume products. The main examples of users of these automated package preparation systems are suppliers of office equipment, clothing, cosmetics, tools or spare parts in the mechanical industry. These systems make it possible to prepare, with a minimum of manpower, within a short time and with precise monitoring of stocks, a package corresponding to a precise order from a customer, this order relating to several products in different quantities, each products with its quantity being identified by a line of the order (each line of the order defines a storage container in which the desired product is located).
    An example of such an automated package preparation system is described in particular in patent LR 2,915,979 filed by the applicant . It includes for example:
    • an automated storage store containing the products in storage containers (corresponding to the aforementioned charges), each storage container being associated with a unique product reference (it may also be containers containing a specific order or a mixture of products) ;
    • an order preparation station, where the products are picked up and placed by an operator in a package (shipping container);
    • a set of conveyors bringing the storage containers, in which the products are located, from the storage store to the order preparation or dispatch station and vice versa; and • a piloting system (WCS).
    The automated storage magazine comprises, for example, four storage units, each storage unit being formed by an aisle serving on either side a storage shelf (or shelving) with several levels of superimposed storage, each shelf being subdivided on its length in storage locations (also called cells) each intended to accommodate a storage container. Each aisle receives, at each storage level, ways for the movement of a transfer device (also called collection and transport cart or shuttle) which moves the storage containers, for their installation at the inside the storage locations and for their removal from these locations. A track is generally formed of two parallel rails and the carriage is equipped with wheels to move on these rails. Carts can not only move horizontally to a given level of storage, but also can be brought from one level to another of an aisle, whether or not they are carrying a storage container, by elevators (also called elevators / descenders, spiral conveyors, mini-stacker cranes (“mini-loads” in English), which are arranged at one or both ends of the aisles (or even in the middle). These elevators also allow the transfer of a storage container placed on a trolley to the set of conveyors.
    The control system manages the order associated with each package (shipping container) and lists storage containers (loads), depending on the location of these storage containers in the storage store, the availability of trolleys and of the storage warehouse elevators, as well as of the destination order (also called "station order") in which these storage containers must follow one another at the order preparation station. The purpose of this is to optimize all movements and times for preparing packages and to ensure synchronization between the arrival, at the preparation station, of a package in preparation and the storage containers listed in the order associated with this package in preparation.
    We now present in more detail, in relation to FIGS. IA, IB and IC, a current technique for processing an order (and sequencing the corresponding charges) by the control system, in the particular context (presented above) d '' an automated package preparation system. For the sake of simplification, all the constituent elements of the automated distribution system are not shown in these figures.
    Figure IA only shows:
    • the ends of four storage units A1 to A4, which form part of the automated storage warehouse and constitute four sources storing charges;
    • a plurality of source buffer devices 11 to 14, of the FIFO type (for “First In First Out” in English, or “first entered first out” in French) and each placed immediately downstream from one of four sources A1 to A4 ; and • a collector 15 (composed for example of one or more conveyors), collecting, via nodes 21 to 24, the charges leaving the source buffer devices 11 to 14 and transporting them to the order preparation station 16 (destination ). The collector 15 therefore serves to relocate the order preparation station 16 relative to the automated storage store. In fact, buildings do not always allow the order preparation station to be located next to the storage store.
    Figure IC only shows:
    • the collector 15;
    • the order preparation station 16 (composed for example of one or more conveyors) and constituting a destination receiving loads; and a destination buffer device 17, of the FIFO type and placed upstream of the order preparation station 16, for receiving loads via a node 25.
    In this example, we assume that the command lists eight charges in a given destination order, corresponding to the ascending order of references 1 to 8 that these charges bear in the figures. In other words, the order preparation station 16 must receive these eight loads in the order of 1 to 8.
    It is also assumed that the charges referenced 3 and 6 are stored in the source Al, the charges referenced 1 and 2 are stored in the source A2, the charges referenced 4 and 7 are stored in the source A3, and the charges referenced 5 and 8 are stored in source A4.
    To process the aforementioned order, the control system performs a first “intra-source” scheduling (scheduling before the sources exit), by controlling each of the sources A1 to A4 so that the loads of the order which are stored there exit in accordance to the given destination order. Thus, as illustrated in FIG. 1A, the source buffer device 11 (placed downstream of the source Al) successively receives the loads referenced 3 and 6. The source buffer device 12 (placed downstream of the source A2) successively receives the loads referenced 1 and 2. The source buffer device 13 (placed downstream of the source A3) successively receives the charges referenced 4 and 7. The source buffer device 14 (placed downstream of the source A4) successively receives the charges referenced 5 and 8 .
    Then, the control system performs a second “intersource” scheduling (scheduling after the sources exit), by controlling the source buffer devices 11 to 14 and the nodes 21 to 24 so that at the output of the collector 15 the loads listed in the order are arranged in the desired destination order. For this, decision rules (injection and advance rules) are applied at each of the nodes 21 to 24:
    • injection rules, for a load occurring at a node coming from one of the sources A1 to A4 (via one of the source buffer devices 11 to 14):
    o the load is injected on the collector 15, downstream of this node, if this node is the one most upstream of the destinations;
    o for a node other than the one most upstream from the destinations, the load is injected if no other load with a lower destination order number is present upstream of this node, in one of the source buffer devices or on the collector, and if no other load having a lower destination order number is present downstream of this node, in one of the source buffer devices connected to the other nodes (otherwise it is not injected);
    o for example, even if it is ready to leave the source buffer device 13 via the node 23, the load referenced 4 is not injected on the collector 15 as long as the loads referenced 1, 2 and 3 are located upstream of the node 23, in one of the source buffer devices 21 and 22 or on the collector 15; and • advance rule, for a load already present on the collector 15 and appearing at a node (coming from another node upstream):
    o the load advances if no other load with a lower destination order number is present in the source buffer device connected to this node (otherwise it does not advance);
    o for example, if it is assumed that the load referenced 3 has been placed (injected) on the collector 15, then when it will appear at node 22 it will not advance as long as the loads referenced 1 and 2 are located in the device source buffer 12 connected to this node 22.
    FIG. 1B illustrates the loads referenced 1 to 8 during transport by the collector 15, after having been placed there in the desired destination order (from 1 to 8).
    Finally, as illustrated in FIG. 1C, the control system controls the destination buffer device 17 so that the charges (which enter there, via the node referenced 25, already sorted according to the desired destination order) come out at the desired rate for be presented at the order preparation station 16.
    A drawback of the known technique illustrated in FIGS. 1A to 1C (and of its injection and advance rules) is that the filling rate of the collector (and therefore the flow leaving it) is not optimal.
    It would therefore be advisable to reduce the waiting times of the charges, on the one hand before their injection on the collector via the nodes and on the other hand before their advance on the collector (also via the nodes).
    3.
    ABSTRACT
    In a particular embodiment of the invention, there is provided a method for sequencing charges in an automated distribution system comprising: sources; at least one destination; a collector configured to transport charges to said at least one destination and comprising a plurality of successive nodes each configured to collect charges leaving one of the sources; and a control system configured to process commands listing each of the charges to be extracted from the sources and to be supplied in a given increasing order of destination to a given destination, to define an increasing global order for the charges listed in the commands and to guarantee for each source that outgoing loads respect the increasing global order and the increasing destination orders associated with the commands, characterized in that it comprises, for at least one node analyzed, an injection analysis step comprising the following steps, for deciding if a load C having a given destination serial number for a given destination can be injected into the collector:
    a) first injection test to determine whether there is, upstream of the analyzed node, on the collector or among charges to be collected by at least one node upstream of the analyzed node, at least one charge having a serial number destination less than the given destination serial number;
    b) in the event of a positive response to the first injection test, non-injection of the load C, otherwise:
    - creation, among charges to be collected by at least one node downstream of the analyzed node, of a list LU of charges having a destination order number lower than the given destination order number and of a list LI2 of charges which are each interposed between a charge from the LU list and the collector;
    - second injection test to determine whether one of the first and second following injection conditions is satisfied: the first injection condition being that the LU list is empty; the second injection condition being that the list Ll 1 is not empty and that the list LI2 is empty;
    - if one of the first and second injection conditions is satisfied, injection of charge C.
    The general principle of the invention therefore consists in carrying out a more detailed analysis than in the aforementioned known solution, in order to decide whether a charge C originating from a source can be injected at the level of an analyzed node. With the proposed solution, in the event of a negative response to the first injection test, the fact that the LU list is not empty does not systematically lead to a non-injection of the charge. Indeed, the proposed solution is based on a completely new and inventive approach consisting in also taking account of the list LI2, to detect a possible inter-blocking between charges. If this LI2 list is empty, there is no risk of inter-blocking and the load is injected (the case where this LI2 list is not empty is detailed below). Thus, if the list LU is not empty but the list LI2 is empty, the proposed solution results in an injection of the charge (while guaranteeing that there is no risk of inter-blocking), while that the aforementioned known solution results in a non-injection of the charge. Therefore, the proposed solution makes it possible to increase the filling rate of the collector (and therefore the flow leaving it). This also allows a reduction in the waiting times of the charges before their injection on the collector, via the nodes.]
    According to a particular characteristic, if none of the first and second injection conditions is verified, the injection analysis step comprises:
    a ') third injection test to determine whether there is, upstream of the analyzed node, on the collector or among charges to be collected by at least one node upstream of the analyzed node, at least one charge having a number of destination order lower than a destination order number owned by a load from the list LI2 and for the same destination;
    b ’) in the event of a positive response to the third injection test, non-injection of load C, otherwise:
    * creation, among charges to be collected by at least one node downstream of the node analyzed, of a list LI3 of charges having a destination order number less than a destination order number possessed by a charge from the list LI2 and for the same destination, and a list LI4 of charges which are each interposed between a charge from the list LI3 and the collector;
    * fourth injection test to determine whether one of the third and fourth following injection conditions is satisfied: the third injection condition being that the list LI3 is empty; the fourth injection condition being that the list LI3 is not empty and that the list LI4 is empty;
    * if one of the third and fourth injection conditions is satisfied, injection of charge C.
    Thus, in the case where the list LI2 is not empty (nor consequently the list LU), the analysis is continued to decide if the load C can be injected at the level of the node analyzed. In the event of a negative response to the third injection test, the LI3 and LI4 lists are taken into account to detect any inter-blocking between charges. If one of these two lists LI3 and LI4 is empty, there is no risk of inter-blocking and the charge is injected (the case where the list LI4 is not empty is detailed below). This makes it possible to further increase the filling rate of the collector (and therefore the flow leaving it) and to further reduce the waiting times of the charges before their injection onto the collector, via the nodes.
    According to a particular characteristic, if none of the third and fourth injection conditions is satisfied, the injection analysis step comprises at least one new iteration of steps a ') and b'), taking LI2 as a list for each new iteration the list LI4 of the previous iteration.
    Thus, in the case where the list LI4 is not empty (nor consequently the list LI3), the analysis is continued, by a new iteration of steps a ') and b'), to decide if the charge C can be injected at the node analyzed. At each iteration, in the event of a negative response to the third injection test, the LI3 and LI4 lists are taken into account to detect any inter-blocking between charges, and if one of these two lists LI3 and LI4 is empty, there is no there is no risk of interlocking and the charge is injected. This makes it possible to further increase the filling rate of the collector (and therefore the flow leaving it) and to further reduce the waiting times of the charges before their injection onto the collector, via the nodes.
    According to a particular characteristic, the injection analysis step is performed for each of the nodes except a first node furthest upstream from the destinations.
    In this way, we apply in a large number of nodes the solution proposed for the injection of the charges at the level of the nodes.
    ίο
    According to a particular characteristic, the method comprises, for at least one node analyzed, a step of analysis in advance comprising the following steps, to decide whether a load C ′, originating from a node upstream of the node analyzed and having a destination order number given for a given destination, can be advanced on the collector:
    1) first advance test to determine whether there is, among charges to be collected by the analyzed node, at least one charge having a destination order number lower than the given destination order number;
    2) in the event of a positive response to the first advance test, no advance of the load C ’, otherwise:
    - creation, among charges to be collected by at least one node downstream of the analyzed node, of a list LAI of charges having a destination order number lower than the given destination order number, and of a list LA2 loads which are each inserted between a load from the LAI list and the collector;
    - second advance test to determine whether one of the first and second following advance conditions is satisfied: the first advance condition being that the LAI list is empty; the second advance condition being that the LAI list is not empty and that the LA2 list is empty;
    - if one of the first and second advance conditions is satisfied, advance of the load C ’.
    Thus, in synergy with the solution proposed for the injection of the charges at the level of the nodes, it is also proposed to make a finer analysis than in the aforementioned known solution, to decide if a charge C can advance on the collector, at the level of an analyzed node. The combination of the solution proposed for the injection of the charges at the nodes with the solution proposed for the advance of the charges at the nodes makes it possible to increase the rate of filling of the collector (and therefore the flow at the outlet of it- ci) while guaranteeing a global management of deadlock risks. With the solution proposed for the advance of the charges, a negative response to the first advance test does not systematically lead to an advance of the charge. Indeed, the proposed solution is based on a completely new and inventive approach consisting in also taking into account the LAI and LA2 lists, to detect a possible π
    inter-blocking between charges. If one of the LAI and LA2 lists is empty, there is no risk of inter-blocking and the load is advanced (the case where the LA2 list is not empty is detailed below).
    According to a particular characteristic, if none of the first and second advance conditions is verified, the advance analysis step comprises:
    Γ) third advance test to determine whether there is, among charges to be collected by the analyzed node, at least one charge having a destination order number lower than a destination order number possessed by a charge of the LA2 list and for the same destination;
    2 '') in the event of a positive response to the third advance test, no advance of the load C ', otherwise:
    * creation, among charges to be collected by at least one node downstream of the node analyzed, of a list LA3 containing charges having a destination order number less than a destination order number possessed by a charge of the list LA2 and for the same destination, and a list LA4 containing charges which are each interposed between a charge from list LA3 and the collector;
    * fourth advance test to determine if one of the third and fourth following advance conditions is satisfied: the third advance condition being that the list LA3 is empty; the fourth advance condition being that the list LA3 is not empty and that the list LA4 is empty;
    * if one of the third and fourth advance conditions is satisfied, advance of the charge C ’.
    Thus, in the case where the list LA2 is not empty (nor consequently the list LAI), one continues the analysis to decide if the load C can be advanced at the level of the node analyzed. In the event of a negative response to the third advance test, the LI3 and LI4 lists are taken into account to detect any inter-blocking between charges. If one of these two lists LA3 and LA4 is empty, there is no risk of inter-blocking and the load is advanced (the case where the list LA4 is not empty is detailed below).
    According to a particular characteristic, if none of the third and fourth advance conditions is verified, the advance analysis step comprises at least one new iteration of steps Γ) and 2 '), taking as list LA2 for each new iteration the list LA4 of the previous iteration.
    Thus, in the case where the list LA4 is not empty (nor consequently the list LA3), the analysis is continued, by a new iteration of steps Γ) and 2 '), to decide whether the charge C can be advanced at the node analyzed. At each iteration, in the event of a negative response to the third advance test, the LA3 and LA4 lists are taken into account to detect any inter-blocking between charges, and if one of these two lists LA3 and LA4 is empty, there is no there is no risk of interlocking and the charge is advanced.
    According to a particular characteristic, the advance analysis step is performed for each of the nodes except said first node furthest upstream from the destinations.
    In this way, we apply in a large number of nodes the solution proposed for the advance of the charges at the level of the nodes.
    In a particular embodiment of the invention, use is made of a computer program product comprising program code instructions for implementing the aforementioned method (in any one of its embodiments ), when said program is run on a computer.
    In a particular embodiment of the invention, use is made of a computer-readable and non-transient storage medium, storing a computer program product as mentioned above.
    In another embodiment of the invention, there is provided a computer program product which includes program code instructions for implementing the aforementioned method (in any one of its various embodiments), when said program is executed on a computer.
    In another embodiment of the invention, there is proposed a computer-readable and non-transient storage medium, storing a computer program comprising a set of instructions executable by a computer to implement the above-mentioned method (in any of its different embodiments).
    4.
    LIST OF FIGURES
    Other characteristics and advantages of the invention will appear on reading the following description, given by way of non-limiting example, and the attached drawings, in which:
    Figures IA to IC, already described in relation to the prior art, present a technique for processing an order (and sequencing the corresponding loads) by a control system, in a conventional automated distribution system;
    Figure 2 shows a block diagram of an automated distribution system in which a method of sequencing loads according to the invention can be implemented;
    FIG. 3 presents a flowchart of a charge injection analysis algorithm, in a particular embodiment of the charge sequencing method of the invention;
    FIG. 4 presents a flowchart of a charge advance analysis algorithm, in a particular embodiment of the charge sequencing method of the invention;
    FIG. 5 illustrates a first example of the execution context of the injection analysis algorithm of FIG. 3 (at node N2 for the load referenced 9 6 ) and of the advance analysis algorithm of the Figure 4 (at node N2 for the load referenced 2 10 );
    FIG. 6 illustrates and explains the concepts of mission, destination sequence number and global sequence number, in relation to the charges of the execution context of FIG. 5;
    FIG. 7 illustrates a second example of the execution context of the advance analysis algorithm of FIG. 4 (at node N3 for the load referenced 9 6 ); FIG. 8 illustrates a third example of the execution context of the advance analysis algorithm of FIG. 4 (at node N3 for the load referenced 2 10 ); and FIG. 9 shows the structure of a control system according to a particular embodiment of the invention.
    5.
    DETAILED DESCRIPTION
    In all the figures in this document, identical elements and steps are designated by the same reference numeral.
    FIG. 2 presents a block diagram of an automated distribution system in which a method of sequencing loads according to the invention can be implemented.
    The system comprises sources St to S5 (for example different parts (storage units) of a storage store), destinations D1 to D5 (for example order picking stations), a collector 1 (for example composed of one or more conveyors) and a control system 90 (for example of the WCS type). The number of sources and destinations is purely illustrative.
    As already explained above, the collector 1 is configured to transport charges to each destination and includes a plurality of successive nodes, those referenced NI to N5 are each configured to collect charges leaving one of the sources St to S5, and those referenced NI 'to N5' are each configured to direct loads to one of the destinations D1 to D5. Each of these nodes includes, for example, a 90 ° or 45 ° transfer device
    Each of the sources St to S5 is for example connected to one of the nodes NI to N5 by a source buffer device of the FIFO type L1 to L5. Likewise, each of the destinations D1 to D5 is for example connected to one of the nodes NI ’to N5’ by a destination buffer device of the LILO type L1 ’to F5’.
    The control system 90 is configured to process commands listing each of the loads to be extracted from the sources and to be supplied in a given increasing order of destination to a given destination. It is also configured to define an increasing global order for the loads listed in the commands (see description of Figure 6 below). Finally, it is configured to guarantee, for each source, that outgoing loads respect the increasing global order and the increasing destination orders associated with the orders.
    A charge is therefore associated with two order numbers:
    • a global order number, within the global order defined for all charges leaving all sources, and • a destination order number, within a destination order defined for loads listed in a given order.
    The control system 90 implements a charge sequencing method which, in a particular embodiment of the invention, includes the following algorithms for each of the nodes collecting charges leaving the sources, except that most upstream of the destinations (that is to say, in the system of FIG. 2, for each of the nodes N2 to N5, but not for the node NI):
    • an injection analysis algorithm (see FIG. 3), to decide whether a load C having a given destination sequence number for a given destination can be injected on the collector downstream of the analyzed node; and • an advance analysis algorithm (see FIG. 4), to decide whether a load C ′, originating from a node upstream from the node analyzed and having a given destination sequence number for a given destination, can be advanced on the collector downstream of the node analyzed.
    For each of the nodes N2 to N5, the order of execution of the injection analysis and advance analysis algorithms is arbitrary. For each of the nodes N2 to N5, the control system 90 executes for example each of these two algorithms at regular time intervals and / or upon detection of an event (for example the arrival of a new load).
    For the NI node, each load that occurs (from the SI source) is injected without order condition. Furthermore, the question of the advance of a load does not arise for the NI node (no upstream node).
    We now present, in relation to FIG. 3, the detail of the charge injection analysis algorithm, in a particular embodiment of the charge sequencing method of the invention.
    In a step T12, the control system performs a first injection test to determine whether there exists, upstream of the analyzed node, on the collector or among charges to be collected by at least one node upstream of the analyzed node, at minus a load with a destination serial number lower than the given destination serial number.
    In the event of a positive response to the first injection test (T 12), the control system decides that the load C is not injected (direct passage to an end step 31), otherwise it performs the following steps:
    - creation (step Alt), among charges to be collected by at least one node downstream of the node analyzed, of a list Lit of charges having a destination order number lower than the given destination order number and a list LI2 of charges which are each interposed between a charge from the list Lit and the collector; and
    - second injection test (step T13) to determine whether one of the first and second following injection conditions is verified: the first injection condition being that the list LI1 is empty; the second injection condition being that the Lit list is not empty and that the LI2 list is empty.
    If one of the first and second injection conditions is verified (positive response in step T13), the control system goes to a step 30 of injecting the load C then to an end step 31.
    Otherwise (that is to say if none of the first and second injection conditions is verified) (negative response in step T13), the control system goes to step T14 in which it performs a third test injection to determine whether there is, upstream of the analyzed node, on the collector or among charges to be collected by at least one node upstream of the analyzed node, at least one charge having a destination order number less than a destination serial number owned by a load from the LI2 list and for the same destination.
    In the event of a positive response to the third injection test (T14), the control system decides not to inject the load C (direct passage to the end step 31), otherwise it performs the following steps:
    - creation (step A12), among charges to be collected by at least one node downstream of the node analyzed, of a list LI3 of charges having a destination order number less than a destination order number possessed by a load from the list LI2 and for the same destination, and from a list LI4 of loads which are each interposed between a load from the list LI3 and the collector; and
    - fourth injection test (step T15) to determine whether one of the third and fourth following injection conditions is verified: the third injection condition being that the list LI3 is empty; the fourth injection condition being that the LI3 list is not empty and that the LI4 list is empty.
    If one of the third and fourth injection conditions is verified (positive response in step T15), the control system proceeds to step 30 of injection of the charge C and then to the end step 31.
    Otherwise (that is to say if none of the third and fourth injection conditions are verified) (negative response in step T15), the control system performs at least one new iteration of steps T14, A12 and T15, taking as list LI2 for each new iteration the list LI4 of the previous iteration. In FIG. 3, only one new iteration is represented, with the notations T14 ’, A12’ and T15 ’.
    Various variants of the charge injection analysis algorithm of FIG. 3 are possible, which are less efficient but require less processing resources:
    • in a first variant, in the event of a negative response to step T13, the control system directly decides that the load C is not injected (direct passage to the end step 31);
    • in a second variant, in the event of a negative response to step T15, the control system directly decides that the load C is not injected (direct passage to the end step 31);
    • in a third variant, in the event of a negative response to step T15, the control system performs a predetermined number k (for example k = l) of new iteration of steps T14, A12 and T15, taking LI2 as the list for each new iteration the list LI4 of the previous iteration.
    We now present, in relation to FIG. 4, the detail of the charge advance analysis algorithm, in a particular embodiment of the charge sequencing method of the invention.
    In a step T22, the control system performs a first advance test to determine whether there is, among charges to be collected by the analyzed node, at least one charge having a destination order number lower than the number of destination order given.
    In the event of a positive response to the first advance test (T22), the control system decides that the load C ’does not advance (direct passage to the end step 41), otherwise it performs the following steps:
    creation (step A21), among charges to be collected by at least one node downstream of the analyzed node, of a list LAI of charges having a destination order number lower than the given destination order number, and d 'a list LA2 of loads which are each interposed between a load of the list LAI and the collector; and
    - second advance test (step T23) to determine whether one of the first and second following advance conditions is verified: the first advance condition being that the list LAI is empty; the second advance condition being that the LAI list is not empty and that the LA2 list is empty.
    If one of the first and second advance conditions is verified (positive response to step T23), the control system goes to a step 40 for advancing the load C ’then to an end step 31.
    Otherwise (i.e. if none of the first and second advance conditions are verified) (negative response in step T23), the control system goes to step T24 in which it performs a third test in advance to determine whether there is, among charges to be collected by the analyzed node, at least one charge having a destination order number less than a destination order number possessed by a charge from the list LA2 and for the same destination.
    In the event of a positive response to the third advance test (T24), the control system decides that the charge C ’does not advance (direct passage to the end step 41), otherwise it performs the following steps:
    creation (step A22), among charges to be collected by at least one node downstream of the node analyzed, of a list LA3 containing charges having a destination order number less than a destination order number owned by a charge from the list LA2 and for the same destination, and from a list LA4 containing charges which are each interposed between a charge from the list LA3 and the collector;
    - fourth advance test (step T25) to determine whether one of the third and fourth following advance conditions is verified: the third advance condition being that the list LA3 is empty; the fourth advance condition being that the LA3 list is not empty and that the LA4 list is empty.
    If one of the third and fourth advance conditions is verified (positive response at step T25), the control system proceeds to step 40 of advance of the load C ’then to the end step 41.
    Otherwise (that is to say if none of the third and fourth advance conditions are verified) (negative response in step T25), the control system performs at least one new iteration of steps T24, A22 and T25, taking as list LA2 for each new iteration the list LA4 of the previous iteration. In FIG. 4, only one new iteration is represented, with the notations T24 ’, A22’ and T25 ’.
    Various variants of the charge advance analysis algorithm of FIG. 4 are possible, which are less efficient but require less processing resources:
    • in a first variant, in the event of a negative response to step T23, the control system directly decides that the load C ’does not advance (direct passage to the end step 41);
    • in a second variant, in the event of a negative response to step T25, the control system directly decides that the load C ’does not advance (direct passage to the end step 41);
    • in a third variant, in the event of a negative response to step T25, the control system performs a predetermined number k (for example k = l) of new iteration of steps T24, A22 and T25, taking as list LA2 for each new iteration the list LA4 of the previous iteration.
    FIG. 5 illustrates a first example of the execution context of the injection analysis algorithm of FIG. 3 (at node N2 for the load referenced 9 6 ) and of the advance analysis algorithm of the figure 4 (at node N2 for the load referenced
    2 10 ). FIG. 6 illustrates and explains the concepts of mission, destination serial number and global serial number, in relation to the charges of the execution context of FIG. 5.
    In FIG. 5, each charge is represented by a “shape / background color” pair in which two figures appear (one in normal size, which is the order number of the destination of the charge, and the other in index, which is the overall serial number of the load). Each “background shape / color” pair is specific to one of the destinations (as illustrated in FIG. 6): “rectangle / black background” for the destination D1; "Rectangle / gray background" for destination D2; "Circle / gray background" for destination D3; "Triangle / gray background" for destination D4; and "oval / gray background" for destination D5.
    The piloting system launches missions each aiming to manage the movement of a load from a source to a destination. The order of the missions corresponds to the overall order of the charges. As illustrated in FIG. 6, it is assumed that the missions are distributed by tranche. In each tranche, the order of launching of the missions is predetermined according to the destinations, and for each destination there is a maximum quantity of missions. Thus, in the example of FIG. 5, the order of launching of the missions in each tranche corresponds to the following order of the destinations: D2, D3, D4, Dl and D5, and for each destination there are at most two charges. The overall order of charges is as follows:
    • for the first tranche: 2 X (from S4 to D2), 3 2 (from S3 to D2), 4 3 (from S3 to
    D3), 5 4 (from S5 to D3), 8 S (from S5 to D4), 9 6 (from S2 to D4), 1 7 (from S2 to
    Dl), 2 8 (from S3 to Dl), 1 9 (from S5 to D5) and 2 10 (from SI to D5);
    • for the second tranche: 3 n (from S4 to Dl), 4 12 (from SI to Dl), 3 13 (from S5 to D5) and 4 14 (from S4 to D5).
    By way of example, we now detail the execution of the injection analysis algorithm of FIG. 3, to decide whether the load 9 6 (having the global order number 6 and the order number of destination 9 for destination D4) can be injected on the collector, downstream of node N2:
    • step T12: negative response, therefore passing to step Al 1;
    • step Ail: the list LU includes the load 8 S and the list LI2 includes the load
    5 4 , • step T13: negative response, therefore go to step T14;
    • step T14: negative response, therefore go to step A12;
    • step A12: the list LI3 includes the load 4 3 and the list LI4 includes the load
    3 2 ;
    • step T15: negative response, therefore go to step T14 ’;
    • step T14 ’: negative response, therefore go to step A12’;
    • step A12 ': the list LI3 includes the load 2 X and the list LI4 is empty;
    • step T15 ': positive response, therefore the load 9 6 is injected into the collector (downstream of the node N2).
    By way of example, we now detail the execution of the advance algorithm of FIG. 4, in order to decide whether the load 2 10 (having the global order number 10 and the destination order number 2 for destination D5) can be advanced on the collector, downstream of node N2:
    • step T22: negative response, therefore passing to step A21;
    • step A21: the list LAI includes the load 1 9 and the list LA2 includes the loads 8 S and 5 4 ;
    • step T23: negative response, therefore go to step T24;
    • step T24: negative response, therefore go to step A22;
    • step A22: the list LA3 includes the load 4 3 and the list LA4 includes the load 3 2 ;
    • step T25: negative response, therefore go to step T24 ’;
    • step T24 ’: negative response, therefore go to step A22’;
    • step A22 ': the list LA3 includes the load 2 X and the list LA4 is empty;
    • step T25 ': positive response, therefore the load 2 10 is advanced on the collector (downstream of the node N2).
    FIG. 7 illustrates a second example of the context for executing the advance analysis algorithm of FIG. 4 (at node N3 for the load referenced
    9 6 ). Compared to FIG. 5, we place ourselves at a later time, assuming that the load 9 6 has been injected on the collector (downstream of the node N2). We now detail the execution of the advance algorithm of Figure 4, to decide if the load 9 6 can be advanced on the collector, downstream of the node N3:
    • step T22: negative response, therefore passing to step A21;
    • step A21: the list LAI includes the load 8 S and the list LA2 includes the load 5 4 ;
    • step T23: negative response, therefore go to step T24;
    • step T24: positive response (there is the load 4 3 which arrives from the source S3 and which has not yet been collected by the node N3), therefore the load 9 6 cannot be advanced on the collector (not in advance as long as the load 4 3 has not been injected on the collector, downstream of the node N3).
    FIG. 8 illustrates a third example of an execution context for the advance analysis algorithm of FIG. 4 (at node N3 for the load referenced 2 10 ). Compared to FIG. 5, we place ourselves at a later instant, assuming that the load 2 10 has been advanced on the collector (downstream of the node N2). We now detail the execution of the advance algorithm of FIG. 4, to decide if the load 2 10 can be advanced on the collector, downstream of the node N3:
    • step T22: negative response, therefore passing to step A21;
    • step A21: the list LAI includes the load 1 9 and the list LA2 includes the loads 8 S and 5 4 ;
    • step T23: negative response, therefore go to step T24;
    • step T24: positive response (there is the load 4 3 which arrives from the source S3 and which has not yet been collected by the node N3), therefore the load 2 10 cannot be advanced on the collector (not in advance as long as the load 4 3 has not been injected on the collector, downstream of the node N3).
    FIG. 9 shows the structure of the control system 90 according to a particular embodiment of the invention. This control system comprises a random access memory 93 (for example a RAM memory), a processing unit 91, equipped for example with a processor, and controlled by a computer program stored in a read-only memory 92 (for example a memory ROM or hard drive).
    On initialization, the code instructions of the computer program are for example loaded into the random access memory 93 before being executed by the processor of the processing unit 91, in order to implement the method of sequencing the loads of the invention. The processing unit 91 receives commands 94 at the input. The processor of the processing unit 91 processes the commands and generates, at the output, instructions or commands 95 making it possible to control (command) various elements included in the automated distribution system, in particular the sources SI to S5, the source buffer devices of the LILO L1 to L5 type, the collector 1, the destinations Dl to D5 and the destination buffer devices of the LILO L1 type L1 to L5 '.
    This FIG. 9 illustrates only one particular way, among several possible, of carrying out the technique of the invention, in any one of its embodiments. Indeed, the control system is carried out indifferently on a reprogrammable calculation machine (for example a PC computer, a DSP processor, a microcontroller, etc.) executing a program comprising a sequence of instructions, or on a dedicated calculation machine (for example a set of logic gates such as an FPGA or an ASIC, or any other hardware module).
    In the case where the control system is implemented with a reprogrammable calculating machine, the corresponding program (i.e. the sequence of instructions) can be stored in a removable storage medium (such as for example a floppy disk , a CD-ROM or a DVD-ROM) or not, this storage medium being partially or totally readable by a computer or a processor.
    权利要求:
    Claims (2)
    [1" id="c-fr-0001]
    1. Method for sequencing charges in an automated distribution system comprising: sources (SI -S5); at least one destination (D1-D5); a collector (70) configured to transport charges to said at least one destination and comprising a plurality of successive nodes (N1-N5) each configured to collect charges leaving one of the sources; and a control system (80) configured to process orders listing each of the loads to be extracted from the sources and to be supplied in a given increasing order of destination to a given destination, to define an increasing global order for the loads listed in the orders and to guarantee for each source that outgoing loads respect the increasing global order and the increasing destination orders associated with the commands, characterized in that it comprises, for at least one node analyzed, an injection analysis step comprising the following steps , to decide whether a load C having a given destination order number for a given destination can be injected on the collector:
    a) first injection test (T12) to determine whether there is, upstream of the analyzed node, on the collector or among charges to be collected by at least one node upstream of the analyzed node, at least one charge having a number destination order less than the given destination order number;
    b) in the event of a positive response to the first injection test, non-injection of the load C, otherwise:
    - creation (Ail), among charges to be collected by at least one node downstream of the analyzed node, of a list LU of charges having a destination order number lower than the given destination order number and a list LI2 of loads which are each interposed between a load of the list LU and the collector;
    - second injection test (T13) to determine if one of the first and second following injection conditions is satisfied: the first injection condition being that the LU list is empty; the second injection condition being that the LU list is not empty and that the LI2 list is empty;
    - if one of the first and second injection conditions is satisfied, injection (30) of the load C.
    2. Method according to claim 1, characterized in that, if none of the first and second injection conditions is verified, the injection analysis step comprises:
    a ') third injection test (T14) to determine whether there is, upstream of the analyzed node, on the collector or among charges to be collected by at least one node upstream of the analyzed node, at least one charge having a destination serial number lower than a destination serial number owned by a load from the LI2 list and for the same destination;
    b ’) in the event of a positive response to the third injection test, non-injection of load C, otherwise:
    * creation (A 12), among charges to be collected by at least one node downstream of the node analyzed, of a list LI3 of charges having a destination order number less than a destination order number possessed by a load from the list LI2 and for the same destination, and from a list LI4 of loads which are each interposed between a load from the list LI3 and the collector;
    * fourth injection test (T 15) to determine if one of the third and fourth following injection conditions is satisfied: the third injection condition being that the list LI3 is empty; the fourth injection condition being that the list LI3 is not empty and that the list LI4 is empty;
    * if one of the third and fourth injection conditions is satisfied, injection (30) of the load C.
    3. Method according to claim 2, characterized in that, if none of the third and fourth injection conditions is verified, the injection analysis step comprises at least one new iteration of steps a ') and b '), taking as list LI2 for each new iteration the list LI4 of the previous iteration.
    4. Method according to any one of claims 1 to 3, characterized in that the injection analysis step is carried out for each of the nodes except a first node furthest upstream from the destinations.
    5. Method according to any one of claims 1 to 4, characterized in that it comprises, for at least one node analyzed, a step of analysis in advance comprising the following steps, to decide whether a load C ', coming from a node upstream of the analyzed node and having a given destination serial number for a given destination, can be advanced on the collector:
    1) first advance test (T22) to determine whether there are, among charges to be collected by the analyzed node, at least one charge having a destination order number lower than the given destination order number;
    [2" id="c-fr-0002]
    2) in the event of a positive response to the first advance test, no advance of the load C ’, otherwise:
    - creation (A21), among charges to be collected by at least one node downstream of the analyzed node, of a list LAI of charges having a destination order number lower than the given destination order number, and a list LA2 of charges which are each interposed between a charge from the list LAI and the collector;
    - second advance test (T23) to determine whether one of the first and second following advance conditions is satisfied: the first advance condition being that the LAI list is empty; the second advance condition being that the LAI list is not empty and that the LA2 list is empty;
    - if one of the first and second advance conditions is satisfied, advance (40) of the load C ’.
    6. Method according to claim 5, characterized in that, if none of the first and second advance conditions is verified, the advance analysis step comprises:
    Γ) third advance test (T24) to determine whether there is, among charges to be collected by the analyzed node, at least one charge having a destination sequence number lower than a destination sequence number owned by a charge from the LA2 list and for the same destination;
    2 '') in the event of a positive response to the third advance test, no advance of the load C ', otherwise:
    * creation (A22), among charges to be collected by at least one node downstream of the analyzed node, of a list LA3 containing charges having a destination order number less than a destination order number possessed by a charge from the list LA2 and for the same destination, and from a list LA4 containing charges which are each interposed between a charge from the list LA3 and the collector;
    * fourth advance test (T25) to determine whether one of the third and fourth following advance conditions is satisfied: the third advance condition being that the list LA3 is empty; the fourth advance condition being that the list LA3 is not empty and that the list LA4 is empty;
    * if one of the third and fourth advance conditions is satisfied, advance (40) of the charge C ’.
    7. Method according to claim 6, characterized in that, if none of the third and fourth advance conditions are verified, the advance analysis step comprises at least one new iteration of steps Γ) and 2 ' ), taking as list LA2 for each new iteration the list LA4 of previous iteration.
    8. Method according to any one of claims 5 to 7, characterized in that the advance analysis step is carried out for each of the nodes except said first node most upstream of the destinations.
    9. A computer program product comprising program code instructions for implementing the method according to any one of claims 1 to 8, when said program is executed on a computer.
    10. A computer readable, non-transient storage medium storing a computer program product according to claim 9.
    类似技术:
    公开号 | 公开日 | 专利标题
    EP3324349A1|2018-05-23|Method for sequencing loads in an automated timing system
    EP2834172B1|2017-03-15|System and method for processing a command, use of a computer program product and of a storage medium in such a system
    FR3025908B1|2019-07-12|MECHANISM AND METHOD FOR ACCESSING DATA IN A SHARED MEMORY
    Gutiérrez-Jarpa et al.2010|A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows
    WO2017207152A1|2017-12-07|A system for buffer storage and sequencing of items comprising two elevators
    EP2979996B1|2017-11-01|Automated storage/picking system comprising an elevator engaging with a transfer device and a sequencer
    EP3693901A1|2020-08-12|Method for sequencing loads in an automated timing system, with reduction of a disturbance during a load collection on a manifold
    Zainuddin et al.2007|A perturbation-based heuristic for the capacitated multisource Weber problem
    EP3648026A1|2020-05-06|Method for controlling the flow mode of a buffer storage system and for sequencing loads, and corresponding control unit
    EP3693902A1|2020-08-12|Method for sequencing loads in an automated timing system, with reduction of a disturbance during a load collection on a manifold
    CA3080655C|2021-11-30|Process for handling a command list in a command preparation system, and corresponding command preparation system
    EP3648025A1|2020-05-06|Method for controlling the sorting mode of a buffer storage system and for sequencing loads, and corresponding control unit
    CA3068358A1|2019-01-10|System for conveying loads between a plurality of storage units and a plurality of preparation stations, via a horizontal load conveyor network
    Becker et al.2015|A hybrid reactive tabu search for liner shipping fleet repositioning
    FR3068682A1|2019-01-11|SYSTEM FOR DELIVERING LOADS BETWEEN A PLURALITY OF STORAGE UNITS AND A PLURALITY OF PREPARATION STATIONS, VIA A LOAD DRAINAGE NETWORK DISTRIBUTED ON TWO HORIZONTAL PLANS
    EP3816896A1|2021-05-05|Method for merging, in a logistics warehouse, k incoming flows of payloads in one outgoing flow
    Dridi et al.2010|Approche Multicritere pour le Probleme de Ramassage et de Livraison avec Fen^ etres de Tempsa Plusieurs V'ehicules
    Côté et al.2015|The value of integrating loading and routing
    Rieck et al.2007|A sampling procedure for real-life rich vehicle routing problems
    同族专利:
    公开号 | 公开日
    WO2018091428A1|2018-05-24|
    FR3058708B1|2019-01-25|
    US11117745B2|2021-09-14|
    CA3040382A1|2018-05-24|
    RU2743124C2|2021-02-15|
    EP3324349A1|2018-05-23|
    HK1253344A1|2019-06-14|
    RU2019116390A3|2020-12-17|
    JP2019536713A|2019-12-19|
    US20200102146A1|2020-04-02|
    CN110140139A|2019-08-16|
    RU2019116390A|2020-12-17|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    FR2915979A1|2007-05-11|2008-11-14|Savoye Sa|AUTOMATED PACK PREPARATION SYSTEM|EP3693901A1|2019-02-08|2020-08-12|Savoye|Method for sequencing loads in an automated timing system, with reduction of a disturbance during a load collection on a manifold|
    EP3693902A1|2019-02-08|2020-08-12|Savoye|Method for sequencing loads in an automated timing system, with reduction of a disturbance during a load collection on a manifold|JP4415671B2|2003-12-24|2010-02-17|株式会社豊田自動織機|Delivery method and distribution system in distribution system|
    JP2008105827A|2006-10-27|2008-05-08|Aisin Seiki Co Ltd|Automatic warehouse system|
    JP5194447B2|2006-12-20|2013-05-08|株式会社ダイフク|Sorting method of goods|
    FR2989070B1|2012-04-04|2015-04-24|Savoye|METHOD FOR PROCESSING A CONTROL BY A CONTROL SYSTEM OF AN AUTOMATED DELIVERY SYSTEM|
    JP6040893B2|2013-08-30|2016-12-07|株式会社ダイフク|Sequential transport system|
    US10947060B2|2018-06-26|2021-03-16|Symbolic Llc|Vertical sequencer for product order fulfillment|CN113213051B|2021-06-16|2021-12-14|浙江云洁仓储设备有限公司|Large-scale storage cabinet body with electronic mechanism that snatchs|
    法律状态:
    2017-11-28| PLFP| Fee payment|Year of fee payment: 2 |
    2018-05-18| PLSC| Publication of the preliminary search report|Effective date: 20180518 |
    2019-11-26| PLFP| Fee payment|Year of fee payment: 4 |
    2020-11-27| PLFP| Fee payment|Year of fee payment: 5 |
    2021-11-25| PLFP| Fee payment|Year of fee payment: 6 |
    优先权:
    申请号 | 申请日 | 专利标题
    FR1661103|2016-11-16|
    FR1661103A|FR3058708B1|2016-11-16|2016-11-16|METHOD FOR SEQUENCING LOADS IN AN AUTOMATED DELIVERY SYSTEM|FR1661103A| FR3058708B1|2016-11-16|2016-11-16|METHOD FOR SEQUENCING LOADS IN AN AUTOMATED DELIVERY SYSTEM|
    US16/461,166| US11117745B2|2016-11-16|2017-11-14|Method for sequencing loads in an automated distribution system|
    RU2019116390A| RU2743124C2|2016-11-16|2017-11-14|Method for setting the sequence of cargo movement in the automated distribution system|
    EP17201507.5A| EP3324349A1|2016-11-16|2017-11-14|Method for sequencing loads in an automated timing system|
    PCT/EP2017/079114| WO2018091428A1|2016-11-16|2017-11-14|Method for sequencing batches in an automated distribution system|
    CA3040382A| CA3040382A1|2016-11-16|2017-11-14|Method for sequencing loads in an automated distribution system|
    JP2019525781A| JP2019536713A|2016-11-16|2017-11-14|Package arrangement method in automatic distribution system|
    CN201780070434.0A| CN110140139A|2016-11-16|2017-11-14|Method for being ranked up in automatic distribution system to loading|
    HK18112638.3A| HK1253344A1|2016-11-16|2018-10-03|Method for sequencing loads in an automated timing system|
    [返回顶部]