(57)【要約】発送元、少なくとも１つの宛先、収集器（複数の連続するノードを備える）及び制御システム（注文を処理するように構成されている）を備える自動分配システムにおいてバッチを配列する方法である。少なくとも１つの解析されるノードについて、配置解析ステップが、指定された宛先の指定された宛先連続番号を有するバッチＣを収集器に配置することができるか否かを判定する次のステップ、すなわち、解析されるノードの下流の少なくとも１つのノードによって収集されるバッチの中で、指定された宛先連続番号よりも小さい宛先連続番号を有するバッチのリストＬＩ１と、リストＬＩ１のバッチと収集器との間にそれぞれ配置されたバッチのリストＬＩ２とを作成するステップ（Ａ１１）と、「リストＬＩ１が空である」及び「リストＬＩ１が空でなく、かつ、リストＬＩ２が空である」という条件のうちの一方が満たされているか否かを確認するステップ（Ｔ１３）と、２つの条件のうちの一方が満たされている場合に、バッチＣを配置するステップ（３０）とを含む。【選択図】図３
2019536713.tif 000002
【特許請求の範囲】
【請求項１】
自動分配システムにおいて荷物を配列する方法であって、
前記自動分配システムは、
発送元（Ｓ１〜Ｓ５）と、
少なくとも１つの宛先（Ｄ１〜Ｄ５）と、
前記発送元のうちの１つから出た荷物を収集する複数の連続したノード（Ｎ１〜Ｎ５）を有し、少なくとも１つの前記宛先へと荷物を運搬する収集器（７０）と、
前記発送元から取り出され、所与の宛先に対し宛先の所与の昇順で提供される荷物が列挙された顧客注文を処理し、前記顧客注文に列挙された荷物の全体的昇順を定め、発送元ごとに、出て行く荷物が前記全体的昇順と前記顧客注文に関連した宛先の昇順とを順守することを保証するように構成された制御システム（８０）と
を備え、
少なくとも１つの解析対象ノードについて、所与の宛先に関する所与の宛先順序番号を有する荷物Ｃを前記収集器内に投入することができるかどうかを判定する投入解析のステップを含み、
前記投入解析のステップは、
ａ）前記解析対象ノードの上流において、前記収集器上又は前記解析対象ノードの上流にある少なくとも１つのノードによって収集される荷物の中で、前記所与の宛先順序番号よりも小さい宛先順序番号を有する少なくとも１つの荷物が存在するか否かを判断する第１の投入テスト（Ｔ１２）のステップと、
ｂ）前記第１の投入テストに対する応答が肯定的である場合に、前記荷物Ｃを投入せず、さもなければ、
前記解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、前記所与の宛先順序番号よりも小さい宛先順序番号を有する荷物のリストＬＩ１と、前記リストＬＩ１の荷物と前記収集器との間にそれぞれ置かれる荷物のリストＬＩ２とを作成するステップ（Ａ１１）と、
前記リストＬＩ１が空であるという第１の投入条件と、前記リストＬＩ１が空ではなくかつ前記リストＬＩ２が空であるという第２の投入条件との一方の成立が確認されるかどうかを判定する第２の投入テストのステップ（Ｔ１３）と、
前記第１の投入条件及び前記第２の投入条件のうちの一方の成立が確認された場合に、前記荷物Ｃを投入するステップ（３０）と
を含むものである、方法。
【請求項２】
前記第１の投入条件の成立も前記第２の投入条件の成立も確認されない場合に、前記投入解析ステップは、
ａ’）前記解析対象ノードの上流において、前記収集器上又は前記解析対象ノードの上流にある少なくとも１つのノードによって収集される荷物の中で、前記リストＬＩ２からの荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である少なくとも１つの荷物が存在するかどうかを判定する第３の投入テストのステップ（Ｔ１４）と、
ｂ’）前記第３の投入テストに対する応答が肯定的である場合に、前記荷物Ｃを投入せず、さもなければ、
前記解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、前記リストＬＩ２の荷物が有する前記宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である荷物のリストＬＩ３と、前記リストＬＩ３の荷物と前記収集器との間にそれぞれ置かれる荷物のリストＬＩ４とを作成するステップ（Ａ２）と、
前記リストＬＩ３が空であることという第３の投入条件と、前記リストＬＩ３が空ではなくかつ前記リストＬＩ４が空であるという第４の投入条件との一方の成立が確認されるかどうかを判定する第４の投入テストのステップ（Ｔ１５）と、
前記第３の投入条件及び前記第４の投入条件のうちの一方の成立が確認された場合に、前記荷物Ｃを投入するステップ（３０）と
を含むものである、請求項１に記載の方法。
【請求項３】
前記第３の投入条件の成立も前記第４の投入条件の成立も確認されない場合に、前記投入解析のステップは、それまでの反復におけるリストＬＩ４を新たな各反復のリストＬＩ２として利用して、前記ステップａ’）及びｂ’）の少なくとも１回の新たな反復を行うステップを含むものである、請求項２に記載の方法。
【請求項４】
前記投入解析のステップは、前記宛先から最も遠い上流の第１のノードを除く前記ノードの各々について実行される、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記方法は、少なくとも１つの解析対象ノードについて、前記解析対象ノードの上流にあるノードから得られ、所与の宛先についての所与の宛先順序番号を有する荷物Ｃ’を前記収集器上で前進させることができるかどうかを判定する前進解析のステップを含み、
前記前進解析のステップは、
１）前記解析対象ノードによって収集される荷物の中で、前記所与の宛先順序番号よりも小さい宛先順序番号を有する少なくとも１つの荷物が存在するか否かを判定する第１の前進テストのステップ（Ｔ２２）と、
２）前記前進テストに対する応答が肯定的である場合に、前記荷物Ｃ’を前進させず、さもなければ、
前記解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、前記所与の宛先順序番号よりも小さい宛先順序番号を有する荷物のリストＬＡ１と、前記リストＬＡ１の荷物と前記収集器との間にそれぞれ置かれる荷物のリストＬＡ２と作成するステップ（Ａ２１）と、
前記リストＬＡ１が空であるという第１の前進条件と、前記リストＬＡ１が空ではなくかつ前記リストＬＡ２が空であるという第２の前進条件とのうちの一方の成立が確認されるかどうかを判定する第２の前進テストのステップ（Ｔ２３）と、
前記第１の前進条件及び前記第２の前進条件のうちの一方の成立が確認された場合に、前記荷物Ｃ’を前進させるステップ（４０）と
を含むものである、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記第１の前進条件の成立も前記第２の前進条件の成立も確認されない場合に、前記前進解析のステップは、
１’）前記解析対象ノードによって収集される荷物の中で、前記リストＬＡ２の荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である少なくとも１つの荷物が存在するかどうかを判定する第３の前進テストのステップ（Ｔ２４）と、
２’）前記第３の前進テストに対する応答が肯定的である場合に、前記荷物Ｃ’を前進させず、さもなければ、
前記解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、前記リストＬＡ２からの荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である荷物を含むリストＬＡ３と、前記リストＬＡ３の荷物と前記収集器との間にそれぞれ置かれる荷物を含むリストＬＡ４とを作成するステップ（Ａ２２）と、
前記リストＬＡ３が空であるという第３の前進条件と、前記リストＬＡ３が空ではなくかつ前記リストＬＡ４が空であるという第４の前進条件とのうちの一方の成立が確認されるかどうかを判定する第４の前進テストのステップ（Ｔ２５）と、
前記第３の前進条件及び前記第４の前進条件のうちの一方の成立が確認される場合に、前記荷物Ｃ’を前進させるステップ（４０）と
を含むものである、請求項５に記載の方法。
【請求項７】
前記第３の前進条件の成立も前記第４の前進条件の成立も確認されない場合に、前記前進解析のステップは、それまでの反復によるリストＬＡ４を新たな各反復におけるリストＬＡ２として利用して、前記ステップ１’）及び２’）の少なくとも１回の新たな反復を行うステップを含むものである、請求項６に記載の方法。
【請求項８】
前記前進解析のステップは、前記宛先の最も上流にある第１のノードを除く前記ノードのおのおのについて実行される、請求項５〜７のいずれか１項に記載の方法。
【請求項９】
コンピュータにおいて実行されると、請求項１〜８のいずれか１項に記載の方法を実施するプログラムコード命令を含むコンピュータプログラム製品の使用。
【請求項１０】
請求項９に記載のコンピュータプログラムを記憶する非一時的コンピュータ可読記憶媒体の使用。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は、ロジスティクスの分野である。具体的には、限定されるわけではないが、特に顧客からの注文の準備（小荷物の準備とも呼ばれる）のための自動分配システム（自動仕分けシステム）の分野である。
【０００２】
より具体的には、本発明は、かかる自動分配システムにおける荷物の配列方法に関する。
【背景技術】
【０００３】
自動分配システムは、発送元（ソース）と、少なくとも１つの宛先（destination）と、収集器（コレクタ）と、制御システムとを備えるものとする。収集器は、各宛先まで荷物を運搬するものであり、連続した複数のノードを有する。各ノードは、発送元から来た荷物を収集する。
【０００４】
制御システムは以下を行う。
・顧客注文を処理する。各顧客注文は、発送元から得られる荷物であって、所与の宛先に対して、宛先の昇順（rising sequential order）に提供される荷物をリストアップしたものである。
・顧客注文にリストアップされた荷物の全体的（overall）又は包括的（general）な昇順を定める。
・得られた荷物が全体的昇順とコマンドに関連した宛先の昇順とに従っていることを、発送元ごとに保証する。
【０００５】
駆動システム又は制御システム（ＷＣＳすなわち倉庫制御システム（warehouse control system）とも呼ばれる）は、自動分配システム全体の制御と顧客注文の管理とを担当するコンピュータ化された中央管理システムである。
【０００６】
所与の顧客注文の処理（又は管理）は、この顧客注文に列挙された全ての荷物が所望の宛先順序で所望の宛先に到達するように、（発送元を含む）自動分配システムを制御するよう制御システムによって実行される全ての動作を組み合わせるものである。
【０００７】
本発明は、限定されるわけではないが、特に、自動分配のシステムの各発送元が保管所（storage depot）の一部（保管所のこの部分は、本明細書において以下では保管ユニットとも呼ばれる）であり、自動分配のシステムの各宛先が顧客注文準備ステーション（ピッキングステーションとも呼ばれる）であるときに適用することができる。
【０００８】
ただし、本発明の枠組みから逸脱することなく多くの変形形態を想定することができることは明らかである。例えば、各発送元は、保管所とすることもできるし、幾つかの保管所を備えるユニットとすることもできるし、さらには、保管装置（保管所よりも複雑でない）とすることもできる。
【０００９】
本明細書において以下では、自動分配システムが小荷物の準備に用いられる特定の場合に存在する問題のより詳細な説明を試みる。もちろん、本発明は、この特定の用途に限定されるものではない。
【００１０】
小荷物準備システムは、より詳細には、小口の商品の通信注文の発送及び販売の商店において用いられる。これらの小荷物準備自動システムのユーザーの主な例は、事務機器、衣類、化粧品、エンジニアリング産業における工具及びスペア部品の供給業者である。これらのシステムは、顧客からの正確な顧客注文に対応する小荷物の準備を最小の労力によって短期間で正確な在庫追跡を用いて可能にする。この顧客注文は、種々の量の種々の商品に関係しており、その量を有する商品のそれぞれは、顧客注文のラインによって識別される（顧客注文の各ラインは、したがって、所望の商品が位置している保管容器を規定する）。
【００１１】
小荷物を準備するそのような自動システムの１つの例は、特に、本出願人によって出願された特許文献１に記載されている。これは、例えば、以下のものを含む。
・（上述した荷物に対応する）保管容器内の商品を収容する自動保管所。各保管容器は、単一の商品リファレンス（product reference）に関連付けられている（これらも、特定の顧客注文及び／又は商品が混合したものを収容する容器とすることができる）
・商品が配置された保管容器を保管所から顧客注文準備ステーション又は発送ステーションへ及びその逆へ搬送する一組のコンベア
・倉庫制御システム（ＷＣＳ）
【００１２】
自動保管所は、例えば、４つの保管ユニットを備える。各保管ユニットは、幾つかの重ねられた保管レベルを有する保管棚（又はシェルフユニット）を両側に提供するレーンによって構成される。各棚は、その長手方向に沿って保管場所（storage location）（セルとも呼ばれる）に分けられている。各保管場所は、保管容器を収容するためのものである。各保管レベルにおいて、各レーンは、保管容器を保管場所内に位置決めすることができるとともにこれらの場所から取り出すことができるように、保管容器をシフトさせる転送装置（収集移送トロリー又はシャトルとも呼ばれる）を移動させるトラックを受け入れる。トラックは、一般に、２つの平行なレールによって形成され、トロリーは、これらのレール上を移動するホイールを装備している。トロリーが、レーンの一方の端部又は両端部（又は中央部の場合もある）に配置されたエレベータ（アップ／ダウンエレベータ又は螺旋コンベア若しくはミニローダとも呼ばれる）によって保管容器を移送するとき又は移送しないとき、トロリーは、所与の保管レベルを水平に移動することができるだけでなく、あるレベルのレーンから別のレベルのレーンに移ることもできる。これらのエレベータによって、トロリーに配置された保管容器を一組のコンベアに向けて送ることが更に可能になる。
【００１３】
制御システムは、各小荷物（発送容器）に関連付けられ、保管所における保管容器の場所に従って保管容器（荷物）を列挙した顧客注文と、トロリー及び保管所エレベータの可用性と、これらの保管容器が顧客注文準備ステーションに対して相互に従わなければならない順序とを管理する。その目的は、全ての移動及び小荷物準備時間を最適化し、準備される小荷物の準備ステーションへの到着と、その準備されている小荷物に関連付けられた顧客注文に列挙された保管容器の準備ステーションへの到着との間の同期を確保することである。
【００１４】
次に、自動パッケージ準備システムの特定の状況（上記で提示された）において制御システムによって顧客注文を処理する（及び対応する荷物を配列する）従来の技法の図１Ａ、図１Ｂ及び図１Ｃに関するより詳細な説明をする。簡略にするため、自動分配のシステムの全ての構成要素がこれらの図に示されているわけではない。
【００１５】
図１Ａに、以下のものが示される。
・４つの保管ユニットＡ１〜Ａ４の端部。これらは、自動保管所の一部であり、４つの荷物保管元（load-storing source）を構成する。
・複数のＦＩＦＯ（先入れ先出し）型バッファ装置（符号１１〜１４）。各装置は、４つの保管ユニットＡ１〜Ａ４のうちの１つの直後の下流側に配置される。
・収集器１５（例えば、１つ以上のコンベアからなる）。これは、ソースバッファ装置１１〜１４から出て行く保管容器をノード２１〜２４により収集し、それらの保管容器を顧客注文準備ステーションまで運搬する。したがって、収集器１５は、自動保管所に対して、顧客注文準備ステーション１６を本来の場所から移すように機能する。実際は、建物内で、顧客注文準備ステーションを保管所のそばに配置することが常に可能とは限らない。
【００１６】
図１Ｃには以下のものが示されている。
・収集器１５
・荷物を受け取る宛先となる顧客注文準備ステーション１６（例えば、１つ以上のコンベアを備える）
・ＦＩＦＯ型の宛先バッファ装置１７。これは、注文準備ステーション１６の上流に配置され、ノード２５を通じて荷物を受け取る。
【００１７】
この例では、顧客注文は、これらの図において荷物が有する番号１〜８の昇順に対応する所与の順序で８つの荷物を列挙しているものとする。換言すれば、顧客注文準備ステーション１６は、これらの８つの荷物を１〜８の順に受け取らなければならない。
【００１８】
番号３及び６で示す荷物は発送元Ａ１に保管され、番号１及び２で示す荷物は発送元Ａ２に保管され、番号４及び７で示す荷物は発送元Ａ３に保管され、番号５及び８で示す荷物は発送元Ａ４に保管されているものとする。
【００１９】
上述した顧客注文を処理するために、制御システムは、保管された顧客注文の荷物が所与の宛先順序に従って出て行くように発送元Ａ１〜Ａ４のそれぞれに命令するときに第１の「発送元内（intra-source）」スケジューリング（発送元から出る前のスケジューリング）を実行する。そのため、図１Ａに示すように、ソースバッファ装置１１（発送元Ａ１の下流に配置されている）は、番号３及び６で参照される荷物を連続的に受け取る。ソースバッファ装置１２（発送元Ａ２の下流に配置されている）は、番号１及び２で参照される荷物を連続的に受け取る。ソースバッファ装置１３（発送元Ａ３の下流に配置されている）は、番号４及び７で参照される荷物を連続的に受け取る。ソースバッファ装置１４（保管ユニットＡ４の下流に配置されている）は、番号５及び８で参照される荷物を連続的に受け取る。
【００２０】
続いて制御システムは、収集器１５の出口において、注文に列挙された荷物が所望の宛先順序で収容されるようにバッファ発送元１１〜１４及びノード２１〜２４に命令することによって、第２の「発送元間（inter-source）」スケジューリング（発送元から出た後のスケジューリング）を実行する。このために、以下の判定ルール（投入（injection）及び前進（forward movement）のルール）が、ノード２１〜２４のそれぞれにおいて適用される。
●発送元Ａ１〜Ａ４のうちの１つから（ソースバッファ装置１１〜１４のうちの１つを介して）ノードに来る荷物の投入ルール
○当該ノードが宛先から最も遠い上流のノードである場合には、荷物はそのノードの下流の収集器１５内に投入される。
○宛先から最も遠い上流のノード以外のノードについては、より小さい宛先順序番号を有する他の荷物が、このノードの上流において、ソースバッファ装置のうちの１つ又は収集器にない場合、かつ、より小さい宛先順序番号を有する他の荷物が、このノードの下流において、この他のノードに接続されたソースバッファ装置のうちの１つにない場合に、当該荷物が投入される（その他の場合には、当該荷物は投入されない）。
○例えば、荷物がノード２３を介してソースバッファ装置１３から出て行く準備ができている場合であっても、番号１、２及び３で参照される荷物がノード２３の上流において、ソースバッファ装置２１及び２２のうちの一方又は収集器１５に位置している限り、番号４で参照される荷物は収集器１５内に投入されない。
●収集器１５に既にあり、ノードに提供される（別の上流ノードから来る）荷物の前進ルール
○より小さい宛先順序番号を有する他の荷物が、このノードに接続されたソースバッファ装置にない場合、当該荷物は前進する（さもなければ荷物は前進しない）。
○例えば、番号３で参照される荷物が収集器１５に配置（投入）されているとすると、この荷物は、ノード２２に提供される際、番号１及び２で参照されるノードが、このノード２２に接続されたソースバッファ装置１２にある限り、移動しない。
【００２１】
図１Ｂに、所望の宛先順序（１〜８）に配置された後、主な収集器１５によって移送されている番号１〜８で参照される荷物を示す。
【００２２】
最後に、図１Ｃに示すように、制御システムは、荷物（所望の宛先順序に既にソートされて宛先バッファ装置１７に入る）が、顧客注文準備ステーション１６に提供されるように所望の速度で出て行くことができるよう宛先バッファ装置１７に命令する。
【先行技術文献】
【特許文献】
【００２３】
【特許文献１】仏国特許出願公開第２９１５９７９号明細書
【発明の概要】
【発明が解決しようとする課題】
【００２４】
図１Ａ〜１Ｃに示すような手法（及びその投入及び前進のルール）の１つの欠点は、収集器の充填速度（したがって、この収集器からの出口における流速）が最適ではないということである。
【００２５】
したがって、一方では、荷物がノードを介して収集器内に投入されるまでの、他方では、荷物が（同じくノードを介して）収集器上を前進するまでの、荷物の待機時間を削減することが必要である。
【課題を解決するための手段】
【００２６】
本発明の１つの特定の実施の形態は、発送元と、少なくとも１つの宛先と、この少なくとも１つの宛先まで荷物を移送するように構成され、発送元のうちの１つから出て行く荷物を収集するようにそれぞれ構成された複数の連続するノードを備える収集器と、発送元から取り出されて、宛先の所与の昇順で所与の宛先に提供される荷物をそれぞれ列挙した顧客注文を処理し、顧客注文に列挙された荷物の全体的昇順を規定し、各発送元について、出て行く荷物が全体的昇順と顧客注文に関連した宛先の昇順とを順守することを保証するように構成された制御システムとを備える自動分配システムにおいて荷物を配列する方法であって、本方法は、少なくとも１つの解析されるノードについて、所与の宛先の所与の宛先順序番号を有する荷物Ｃを収集器内に投入することができるか否かを判定する投入解析のステップを含み、投入解析のステップは、以下のステップ、すなわち、
ａ）解析されるノードの上流において、収集器上又は解析されるノードの上流の少なくとも１つのノードによって収集される荷物の中で、所与の宛先順序番号よりも低い宛先順序番号を有する少なくとも１つの荷物が存在するか否かを判断する第１の投入テストのステップと、
ｂ）第１の投入テストに対する応答が肯定的である場合には、荷物Ｃを投入せず、そうでない場合には、
解析されるノードの下流の少なくとも１つのノードによって収集される荷物の中で、所与の宛先順序番号よりも低い宛先順序番号を有する荷物のリストＬＩ１と、リストＬＩ１の荷物と収集器との間にそれぞれ置かれる荷物のリストＬＩ２とを作成するステップと、
次の第１の投入条件及び第２の投入条件、すなわち、リストＬＩ１が空であることである第１の投入条件、及び、リストＬＩ１が空でなくかつリストＬＩ２が空であることである第２の投入条件のうちの一方の成立が確認されるか否かを判断する第２の投入テストのステップと、
第１の投入条件及び第２の投入条件のうちの一方の成立が確認された場合には、荷物Ｃを投入するステップと
を含むことを特徴とする、方法を提案する。
【００２７】
したがって、本発明の一般原理は、上述した既知の解決策よりも精細な解析を実行して、発送元から得られる荷物Ｃを解析されるノードのレベルにおいて投入することができる否かを判定することにある。提案された解決策を用いると、第１の投入テストに対する応答が否定的である場合には、リストＬＩ１が空でないことによって、荷物を投入されないことには系統的にはならない。実際は、提案された解決策は、リストＬＩ２も考慮して、荷物間に起こり得る相互ブロッキング（inter-blocking）を検出する完全に新規で進歩性のある手法に依拠している。このリストＬＩ２が空である場合、相互ブロッキングの危険はなく、荷物は投入される（このリストＬＩ２が空でない場合については、以下で詳細に説明される）。したがって、リストＬＩ１が空でないが、リストＬＩ２が空である場合、提案された解決策によれば、（相互ブロッキングの危険がないことを確保しながら）荷物は投入される一方、上述した既知の解決策によれば、荷物は投入されない。したがって、提案された解決策は、収集器の充填速度（したがって、この収集器からの出口の流速）を増加させる。これによって、荷物がノードを介して収集器内に投入されるまでの荷物の待機時間も削減される。
【００２８】
１つの特定の特徴によれば、第１の投入条件の成立も第２の投入条件の成立も確認されない場合には、投入解析ステップは、
ａ’）解析されるノードの上流において、収集器上又は解析されるノードの上流の少なくとも１つのノードによって収集される荷物の中で、リストＬＩ２からの荷物が有する宛先順序番号よりも低い宛先順序番号を有するとともに同じ宛先である少なくとも１つの荷物が存在するか否かを判断する第３の投入テストのステップと、
ｂ’）第３の投入テストに対する応答が肯定的である場合には、荷物Ｃを投入せず、そうでない場合には、
解析されるノードの下流の少なくとも１つのノードによって収集される荷物の中で、リストＬＩ２の荷物が有する宛先順序番号よりも低い宛先順序番号を有するとともに同じ宛先である荷物のリストＬＩ３と、リストＬＩ３の荷物と収集器との間にそれぞれ置かれる荷物のリストＬＩ４とを作成するステップと、
次の第３の投入条件及び第４の投入条件、すなわち、リストＬＩ３が空であることである第３の投入条件、及び、リストＬＩ３が空でなくかつリストＬＩ４が空であることである第４の投入条件のうちの一方の成立が確認されるか否かを判断する第４の投入テストのステップと、
第３の投入条件及び第４の投入条件のうちの一方の成立が確認された場合には、荷物Ｃを投入するステップと、
を含む。
【００２９】
したがって、リストＬＩ２が（したがって、リストＬＩ１も）空でない場合、解析が継続され、解析されるノードのレベルにおいて荷物Ｃを投入することができるか否かが判定される。第３の投入テストに対する応答が否定的である場合には、本発明は、荷物の間で起こり得る相互ブロッキングを検出するのにリストＬＩ３及びＬＩ４を考慮する。これらの２つのリストＬＩ３及びＬＩ４のうちの一方が空である場合、相互ブロッキングの危険はなく、荷物は投入される（リストＬＩ４が空でない場合については、以下で詳細に説明される）。これによって、収集器の充填速度（したがって、収集器からの出口の流速）が更に増加し、荷物がノードを介して収集器内に投入されるまでの荷物の待機時間が更に削減される。
【００３０】
１つの特定の特徴によれば、第３の投入条件の成立も第４の投入条件の成立も確認されない場合には、投入解析のステップは、以前の反復のリストＬＩ４を新たな各反復のリストＬＩ２として利用して、ステップａ’）及びｂ’）の少なくとも１つの新たな反復を行うことを含む。
【００３１】
したがって、リストＬＩ４が（したがって、リストＬＩ３も）空でない場合、解析は、ステップａ’）及びｂ’）の新たな反復によって継続され、解析されるノード内に荷物Ｃを投入することができるか否かが判定される。各反復において、第３の投入テストに対する応答が否定的である場合には、荷物の間で起こり得る相互ブロッキングを検出するのにリストＬＩ３及びＬＩ４が考慮され、２つのリストＬＩ３及びＬＩ４のうちの一方が空である場合、相互ブロッキングの危険はなく、荷物は投入される。これによって、収集器の充填速度（したがって、収集器からの出口の流速）が更に増加し、荷物がノードを介して収集器内に投入されるまでの荷物の待機時間が更に削減される。
【００３２】
１つの特定の特徴によれば、投入解析のステップは、宛先の上流の最も遠い第１のノードを除くノードのそれぞれについて実行される。
【００３３】
このように、ノードのレベルにおいて荷物を投入する提案された解決策は、多数のノードにおいて適用される。
【００３４】
１つの特定の特徴によれば、本方法は、少なくとも１つの解析されるノードについて、解析されるノードの上流のノードから得られ、所与の宛先の所与の宛先順序番号を有する荷物Ｃ’を収集器上で前進させることができるか否かを判定する前進解析のステップを含み、前進解析のステップは、以下のステップ、すなわち、
１）解析されるノードによって収集される荷物の中で、所与の宛先順序番号よりも低い宛先順序番号を有する少なくとも１つの荷物が存在するか否かを判断する第１の前進テストのステップと、
２）前進テストに対する応答が肯定的である場合には、荷物Ｃ’を前進させず、そうでない場合には、
解析されるノードの下流の少なくとも１つのノードによって収集される荷物の中で、所与の宛先順序番号よりも低い宛先順序番号を有する荷物のリストＬＡ１と、リストＬＡ１の荷物と収集器との間にそれぞれ置かれる荷物のリストＬＡ２とを作成するステップと、
次の第１の前進条件及び第２の前進条件、すなわち、リストＬＡ１が空であることである第１の前進条件、及び、リストＬＡ１が空でなくかつリストＬＡ２が空であることである第２の前進条件のうちの一方の成立が確認されるか否かを判断する第２の前進テストのステップと、
第１の前進条件及び第２の前進条件のうちの一方の成立が確認された場合には、荷物Ｃ’を前進させるステップと、
を含む。
【００３５】
したがって、ノードのレベルにおける荷物の投入について提案された解決策との相乗効果によって、解析されるノードのレベルにおいて収集器上で荷物Ｃを前進させることができるか否かを判定する、上述した既知の解決策よりも精細な解析を実行することも提案される。ノードにおける荷物の投入について提案された解決策を、ノードにおける荷物の前進について提案された解決策と組み合わせることによって、収集器の充填速度（したがって、この収集器からの出口の流速）が増加するとともに、相互ブロッキングの危険の全体的な管理が確保される。荷物の前進について提案された解決策を用いると、第１の前進テストに対する応答が否定的である場合に、荷物の前進が機械的に行われることはない。実際は、提案された解決策は、リストＬＡ１及びＬＡ２も考慮して、荷物の間で起こり得る相互ブロッキングを検出する完全に新規で進歩性のある手法に依拠している。リストＬＡ１及びＬＡ２のうちの一方が空である場合、相互ブロッキングの危険はなく、荷物は前進される（このリストＬＩ２が空でない場合については、以下で詳細に説明される）。
【００３６】
１つの特定の特徴によれば、第１の前進条件の成立も第２の前進条件の成立も確認されない場合には、前進解析のステップは、
１’）解析されるノードによって収集される荷物の中で、リストＬＡ２の荷物が有する宛先順序番号よりも低い宛先順序番号を有するとともに同じ宛先である少なくとも１つの荷物が存在するか否かを判断する第３の前進テストのステップと、
２’）第３の前進テストに対する応答が肯定的である場合には、荷物Ｃ’を前進させず、そうでない場合には、
解析されるノードの下流の少なくとも１つのノードによって収集される荷物の中で、リストＬＡ２からの荷物が有する宛先順序番号よりも低い宛先順序番号を有するとともに同じ宛先である荷物を含むリストＬＡ３と、リストＬＡ３の荷物と収集器との間にそれぞれ置かれる荷物を含むリストＬＡ４とを作成するステップと、
次の第３の前進条件及び第４の前進条件、すなわち、リストＬＡ３が空であることである第３の前進条件、及び、リストＬＡ３が空でなくかつリストＬＡ４が空であることである第４の前進条件のうちの一方の成立が確認されるか否かを判断する第４の前進テストのステップと、
第３の前進条件及び第４の前進条件のうちの一方の成立が確認される場合には、荷物Ｃ’を前進させるステップと、
を含む。
【００３７】
したがって、リストＬＡ２（又は、したがって、リストＬＡ１）が空でない場合、解析が継続され、解析されるノードのレベルにおいて荷物Ｃを前進させることができるか否かが判定される。第３の前進テストに対する応答が否定的である場合には、本発明は、荷物の間で起こり得る相互ブロッキングを検出するのにリストＩ３及びＬＩ４を考慮する。これらの２つのリストＬＡ３及びＬＡ４のうちの一方が空である場合、相互ブロッキングの危険はなく、荷物は前進する（リストＬＡ４が空でない場合については、以下で詳細に説明される）。
【００３８】
１つの特定の特徴によれば、第３の前進条件の成立も第４の前進条件の成立も確認されない場合には、前進解析のステップは、以前の反復のリストＬＡ４を新たな各反復のリストＬＡ２として利用して、ステップ１’）及び２’）の少なくとも１つの新たな反復を行うことを含む。
【００３９】
したがって、リストＬＡ４（又は、したがって、リストＬＡ３）が空でない場合、リストは、ステップａ’）及びｂ’）の新たな反復によって継続され、解析されるノードのレベルにおいて荷物Ｃを前進させることができるか否かが判定される。各反復において、第３の前進テストに対する応答が否定的である場合には、荷物の間で起こり得る相互ブロッキングを検出するのにリストＬＡ３及びＬＡ４が考慮され、２つのリストＬＡ３及びＬＡ４のうちの一方が空である場合、相互ブロッキングの危険はなく、荷物は前進する。
【００４０】
１つの特定の特徴によれば、前進解析のステップは、宛先の最も上流の上記第１のノードを除くノードのそれぞれについて実行される。
【００４１】
このように、ノードにおける荷物の前進について提案された解決策は、多数のノードにおいて適用される。
【００４２】
本発明の１つの特定の実施の形態は、コンピュータにおいて実行されると、上述した方法を（その種々の実施の形態のうちのいずれかにおいて）実施するプログラムコード命令を含むコンピュータプログラム製品の使用を提案する。
【００４３】
本発明の別の実施態様は、本明細書に上述したコンピュータプログラムを記憶する非一時的コンピュータ可読記憶媒体の使用を提案する。
【００４４】
本発明の別の実施の形態は、コンピュータにおいて実行されると、上述した方法を（その種々の実施の形態のうちのいずれかにおいて）実施するプログラムコード命令を含むコンピュータプログラム製品を提案する。
【００４５】
本発明の別の実施の形態は、上述した方法を（その種々の実施の形態のうちのいずれかにおいて）実施するコンピュータによって実行可能な一組の命令を含むコンピュータプログラムを記憶する非一時的コンピュータ可読記憶媒体を提案する。
【００４６】
本発明の他の特徴及び利点は、例示的で非網羅的な例として与えられた以下の説明及び添付図面から明らかになる。
【図面の簡単な説明】
【００４７】
【図１】図１Ａ〜図１Ｃは、従来技術に関して既に述べたとおり、従来の自動分配のシステムにおいて、制御システムによって顧客注文を処理する（及び対応する荷物を配列する）手法を示す図である。
【図２】本発明による荷物配列方法を実施することが可能な自動分配システムのブロック図である。
【図３】本発明の荷物配列方法の１つの特定の実施形態における荷物投入解析アルゴリズムのフローチャートである。
【図４】本発明の荷物配列方法の１つの特定の実施形態における荷物の前進の解析用のアルゴリズムのフローチャートである。
【図５】図３の投入解析アルゴリズムの（ノードＮ３における符号９６で参照される荷物に対する）実行と、図４の前進解析アルゴリズムの（ノードＮ２における２１０で参照される荷物に対する）実行との第１の状況例を示す図である。
【図６】図５の実行状況の荷物に関するミッション、宛先順序番号及び全体的順序番号の概念を図示及び説明する図である。
【図７】図４の前進解析アルゴリズムの（ノードＮ３における符号９６で参照される荷物に対する）第２の実行状況例を示す図である。
【図８】図４の前進解析アルゴリズムの（ノードＮ３における符号２１０で参照される荷物に対する）第３の実行状況例を示す図である。
【図９】本発明の１つの特定の実施形態による制御システムの構造を提示する図である。
【発明を実施するための形態】
【００４８】
本明細書の全ての図において、同一の要素及びステップには、同じ参照符号を付す。
【００４９】
図２は、本発明による荷物配列方法を実施することができる自動分配システム（自動仕分けシステム）のブロック図である。このシステムは、発送元Ｓ１〜Ｓ５（例えば、保管所の異なる部分（保管ユニット））と、宛先Ｄ１〜Ｄ５（例えば、顧客注文準備ステーション又はピッキングステーション）と、収集器１（例えば、幾つかのコンベアによって構成される）と、制御システム９０（例えば、ＷＣＳタイプのもの）とを備える。発送元及び宛先の数は、単なる例に過ぎない。
【００５０】
上記で既に説明したように、収集器１は、荷物を各宛先まで移送するように構成され、複数の連続するノードを備える。Ｎ１〜Ｎ５で参照されるノードはそれぞれ、発送元Ｓ１〜Ｓ５のうちの１つから得られる荷物を収集するように構成され、Ｎ１’〜Ｎ５’で参照されるノードはそれぞれ、荷物を宛先Ｄ１〜Ｄ５へと誘導するように構成されている。これらのノードのそれぞれは、例えば、９０度又は４５度における転送を行う転送装置を備える。
【００５１】
発送元Ｓ１〜Ｓ５のそれぞれは、例えば、ＦＩＦＯ型ソースバッファ装置Ｆ１〜Ｆ５によってノードＮ１〜Ｎ５のうちの１つに接続される。同様に、宛先Ｄ１〜Ｄ５のそれぞれも、例えば、ＦＩＦＯ型宛先バッファ装置Ｆ１’〜Ｆ５’によってノードＮ１’〜Ｎ５’のうちの１つに接続される。
【００５２】
制御システム９０は、発送元から取り出されて宛先の所与の昇順で所与の宛先に提供される荷物をそれぞれ列挙した顧客注文を処理する。制御システム９０は、顧客注文に列挙された荷物の全体的昇順を定めるようにも構成されている（以下の図６の説明参照）。最後に、制御システム９０は、出て行く荷物が全体的な昇順と顧客注文に関連した宛先の昇順とを順守することを発送元ごとに確保するように構成されている。
【００５３】
そのため、荷物は、以下の２つの順序番号に関連付けられている。
・一組の発送元から出て行く一組の荷物について定められた全体的な順序における全体的な順序番号
・所与の顧客注文に列挙された荷物について定められた宛先順序における宛先の順序番号
【００５４】
制御システム９０は、本発明の１つの特定の実施形態では、宛先から最も遠い上流のノードを除いて、発送元から得られる荷物を収集するノードのそれぞれ（すなわち、図２のシステムでは、ノードＮ１以外の、ノードＮ２〜Ｎ５のそれぞれ）について、以下のアルゴリズムを含む荷物配列方法を実施する。
・所与の宛先の所与の宛先順序番号を有する荷物Ｃを、解析されるノードの下流の収集器内に投入することができるか否かを判定する投入解析アルゴリズム（図３参照）
・解析されるノードの上流ノードから到来し、所与の宛先の所与の宛先順序を有する荷物Ｃ’を、解析されるノードの下流にある収集器にこのまま進めることができるか否かを判定する前進解析アルゴリズム（図４参照）
【００５５】
ノードＮ２〜Ｎ５のそれぞれについて、投入解析アルゴリズム及び前進解析アルゴリズムの実行の順序は、指定されない任意の順序である。ノードＮ２〜Ｎ５のそれぞれについて、制御システム９０は、例えば、定期的な時間間隔で及び／又はイベント（例えば、新たな荷物の到着）の検出時にこれらの２つのアルゴリズムのそれぞれを実行する。
【００５６】
ノードＮ１の場合、到着した（発送元Ｓ１から得られた）各荷物は、順序の条件なしで投入される。荷物の前進の問題は、ノードＮ１の場合、生じない（上流ノードが存在しない）。
【００５７】
図３に、本発明の荷物配列方法の１つの特定の実施形態における荷物投入解析アルゴリズムの詳細を示す。
【００５８】
ステップＴ１２において、制御システムは第１の投入テストを実行する。ここで、解析対象ノードの上流において、収集器上又は解析対象ノードの上流にある少なくとも１つのノードによって収集された荷物の中で、所与の宛先順序番号よりも小さい宛先順序番号を有する少なくとも１つの荷物が存在するか否かが判断される。
【００５９】
第１の投入テスト（Ｔ１２）に対する応答が肯定的であった場合、制御システムは、荷物Ｃを投入しないことを決定する（最終ステップ３１に直接進む）。さもなければ、制御システムは、以下のステップを実行する。
−解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、所与の宛先順序番号よりも小さい宛先順序番号を有する荷物のリストＬＩ１と、リストＬＩ１からの荷物と収集器との間にそれぞれ置かれる荷物のリストＬＩ２との作成（ステップＡ１１）
−次の第１の投入条件及び第２の投入条件のうちの一方の成立が確認されるか否かを判断する第２の投入テスト（ステップＴ１３）。第１の投入条件は、リストＬＩ１が空であることであり、第２の投入条件は、リストＬＩ１が空ではなく、かつ、リストＬＩ２が空であることである。
【００６０】
第１の投入条件及び第２の投入条件のうちの一方の成立が確認された（ステップＴ１３における応答が肯定的である）場合、制御システムは、荷物Ｃを投入する荷物投入ステップ３０に進み、その後、最終ステップ３１に進む。
【００６１】
その他の（すなわち、第１の投入条件及び第２の投入条件のいずれの成立も確認されない（ステップＴ１３における応答が否定的である））場合、制御システムは、ステップＴ１４に進む。このステップにおいて、制御システムは、解析対象ノードの上流において、収集器上又は解析対象ノードの上流にある少なくとも１つのノードによって収集される荷物の中で、リストＬＩ２の荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である少なくとも１つの荷物が存在するか否かを判断する第３の投入ステップを実行する。
【００６２】
第３の投入テスト（Ｔ１４）における応答が肯定的である場合には、制御システムは、荷物Ｃを投入しないことを決定する（最終ステップ３１に直接進む）。そうでない場合には、制御システムは、以下のステップを実行する。
−解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、リストＬＩ２の荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である荷物のリストＬＩ３と、リストＬＩ３の荷物と収集器との間にそれぞれ置かれる荷物のリストＬＩ４との作成（ステップＡ１２）
−次の第３の投入条件及び第４の投入条件のうちの一方の成立が確認されるか否かを判断する第４の投入テスト（ステップＴ１５）。第３の投入条件は、リストＬＩ３が空であることであり、第４の投入条件は、リストＬＩ３が空ではなく、かつ、リストＬＩ４が空であることである。
【００６３】
第３の投入条件及び第４の投入条件のうちの一方の成立が確認された（ステップＴ１５における応答が肯定的である）場合、制御システムは、荷物Ｃを投入する荷物投入ステップ３０に進み、その後、最終ステップ３１に進む。
【００６４】
その他の場合（すなわち、第３の投入条件の成立も第４の投入条件の成立も確認されない（ステップＴ１５における応答が否定的である））場合、制御システムは、新たな反復ごとに、リストＬＩ２として以前の反復のリストＬＩ４を利用して、ステップＴ１４、Ａ１２及びＴ１５の少なくとも１回の新たな反復を実行する。図３には、符号Ｔ１４’、Ａ１２’及びＴ１５’を用いた１回の新たな反復のみを示している。
【００６５】
性能は低下するものの必要な処理リソースが少なくなる図３の荷物投入解析アルゴリズムの以下の様々な可能な変形形態が存在する。
・第１の変形形態では、ステップＴ１３における応答が否定的である場合、制御システムが、荷物Ｃを投入しないことを直接決定する（最終ステップ３１に直接進む）。
・第２の変形形態では、ステップＴ１５における応答が否定的である場合、制御システムが、荷物Ｃを投入しないことを直接決定する（最終ステップ３１に直接進む）。
・第３の変形形態では、ステップＴ１５における応答が否定的である場合、制御システムが、新たな反復ごとに、リストＬＩ２として以前の反復のリストＬＩ４を利用して、ステップＴ１４、Ａ１２及びＴ１５の所定回数ｋ（例えば、ｋ＝１）の新たな反復を実行する。
【００６６】
次に、図４を参照して、本発明の荷物配列方法の１つの特定の実施形態における荷物前進解析アルゴリズムを詳細に説明する。
【００６７】
ステップＴ２２において、制御システムは、解析対象ノードによって収集される荷物の中で、所与の宛先順序番号よりも小さい宛先順序番号を有する少なくとも１つの荷物があるか否かを判断する第１の前進テストを実行する。
【００６８】
第１の前進テスト（Ｔ２２）における応答が肯定的である場合には、制御システムは、荷物Ｃ’を前進させないことを決定する（最終ステップ４１に直接進む）。さもなければ、制御システムは以下のステップを実行する。
−解析対象ノードの下流の少なくとも１つのノードによって収集される荷物の中で、所与の宛先順序番号よりも小さい宛先順序番号を有する荷物のリストＬＡ１と、リストＬＡ１の荷物と収集器との間にそれぞれ置かれる荷物のリストＬＡ２との作成（ステップＡ２１）
−次の第１の前進条件及び第２の前進条件のうちの一方の成立が確認されるか否かを判断する第２の前進テスト（ステップＴ２３）。第１の前進条件は、リストＬＡ１が空であることであり、第２の前進条件は、リストＬＡ１が空ではなく、かつ、リストＬＡ２が空であることである。
【００６９】
第１の前進条件及び第２の前進条件のうちの一方の成立が確認された（ステップＴ２３における応答が肯定的である）場合、制御システムは、荷物Ｃ’を前進させるステップ４０に進み、その後、最終ステップ３１に進む。
【００７０】
その他の（すなわち、第１の前進条件及び第２の前進条件のいずれの成立も確認されない）（ステップＴ２３における応答が否定的である）場合、制御システムは、ステップＴ２４に進む。このステップにおいて、制御システムは、解析対象ノードによって収集される荷物の中で、リストＬＡ２の荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である少なくとも１つの荷物が存在するか否かを判断する第３の前進テストを実行する。
【００７１】
第３の前進テスト（Ｔ２４）における応答が肯定的である場合には、制御システムは、荷物Ｃ’を前進させないことを決定する（最終ステップ４１に直接進む）。そうでない場合には、制御システムは以下のステップを実行する。
−解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、リストＬＡ２からの荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である荷物を含むリストＬＡ３と、リストＬＡ３の荷物と収集器との間にそれぞれ置かれる荷物を含むリストＬＡ４との作成（ステップＡ２２）
−次の第３の前進条件及び第４の前進条件のうちの一方の成立が確認されるか否かを判断する第４の前進テスト（ステップＴ２５）。第３の前進条件は、リストＬＡ３が空であることであり、第４の前進条件は、リストＬＡ３が空ではなく、かつ、リストＬＡ４が空であることである。
【００７２】
第３の前進条件及び第４の前進条件のうちの一方の成立が確認された（ステップＴ２５における応答が肯定的である）場合、制御システムは、荷物Ｃ’を前進させるステップ４０に進み、その後、最終ステップ４１に進む。
【００７３】
その他の場合（すなわち、第３の前進条件の成立も第４の前進条件の成立も確認されない（ステップＴ２５における応答が否定的である））場合、制御システムは、新たな反復ごとに、リストＬＡ２として以前の反復のリストＬＡ４を利用して、ステップＴ２４、Ａ２２及びＴ２５の少なくとも１回の新たな反復を実行する。図４には、符号Ｔ２４’、Ａ２２’及びＴ２５’を用いた１回の新たな反復のみを示している。
【００７４】
性能は低下するが、図４の荷物前進に必要なリソースが少なくなる様々な可能な代替アルゴリズムが存在する。
・第１の変形形態では、ステップＴ２３における応答が否定的である場合、制御システムが、荷物Ｃ’を前進させないことを直接決定する（最終ステップ４１に直接進む）。
・第２の変形形態では、ステップＴ２５における応答が否定的である場合には、制御システムが、荷物Ｃ’を前進させないことを直接決定する（最終ステップ４１に直接進む）。
・第３の変形形態では、ステップＴ２５に対する応答が否定的である場合には、制御システムが、新たな反復ごとに、リストＬＡ２として以前の反復のリストＬＡ４を利用して、ステップＴ２４、Ａ２２及びＴ２５の所定回数ｋ（例えば、ｋ＝１）の新たな反復を実行する。
【００７５】
図５に、図３の投入解析アルゴリズムの（ノードＮ２における符号９６で参照される荷物に対する）実行と、図４の前進解析アルゴリズムの（ノードＮ２における符号２１０で参照される荷物に対する）実行との第１の状況例を示す。図６は、図５の実行状況の荷物に関するミッション、宛先順序番号、全体的な順序番号の概念を図示及び説明している。
【００７６】
図５において、各荷物は、２つの数字（一方は、荷物の宛先順序番号である通常サイズの数字であり、他方の数字は、荷物の全体的な順序番号である下付き文字で示されている）がある「バックグラウンドの形状と色」の対によって表されている。各「形状／色バックグラウンド」の対は、（図６に示すように）宛先の１つに固有のものであり、宛先Ｄ１に対して「長方形／黒色背景」であり、宛先Ｄ２に対して「長方形／グレー背景」であり、宛先Ｄ３に対して「円形／グレー背景」であり、宛先Ｄ４に対して「三角形／グレー背景」であり、宛先Ｄ５に対して「長円形／グレー背景」である。
【００７７】
制御システムは、発送元から宛先までの荷物の移動の管理をそれぞれ目的としたミッションを開始する。ミッションの順序は、荷物の全体的な順序に対応する。図６に示すように、ミッションは、セクション単位で分かれていると仮定される。各セクションでは、ミッション開始コマンドが宛先に応じて予め定められ、宛先ごとに、ミッションの最大量が存在する。したがって、図５の例では、各セクションにおけるミッション開始コマンドは、次の宛先順序、すなわち、Ｄ２、Ｄ３、Ｄ４、Ｄ１及びＤ５に対応し、これらの宛先のそれぞれについて、最大で２つの荷物が存在する。全体的な荷物順序は以下のとおりである。
・第１のセクションについて：２１（Ｓ４からＤ２）、３２（Ｓ３からＤ２）、４３（Ｓ３からＤ３）、５４（Ｓ５からＤ３）、８５（Ｓ５からＤ４）、９６（Ｓ２からＤ４）、１７（Ｓ２からＤ１）、２８（Ｓ３からＤ１）、１９（Ｓ５からＤ５）及び２１０（Ｓ１からＤ５）
・第２のセクションについて：３１１（Ｓ４からＤ１）、４１２（Ｓ１からＤ１）、３１３（Ｓ５からＤ５）及び４１４（Ｓ４からＤ５）
【００７８】
次に、一例として、荷物９６（全体的な順序番号６と、宛先Ｄ４の宛先順序番号９とを有する）を、ノードＮ２の下流の収集器内に投入することができるか否かを判定する図３の投入解析アルゴリズムの実行について詳細に説明する。
・ステップＴ１２：応答は否定的であるため、ステップＡ１１に移動する。
・ステップＡ１：リストＬＩ１は荷物８５を含み、リストＬＩ２は荷物５４を含む。
・ステップＴ１３：応答は否定的であるため、ステップＴ１４に移動する。
・ステップＴ１４：応答は否定的であるため、ステップＡ１２に移動する。
・ステップＡ１２：リストＬＩ３は荷物４３を含み、リストＬＩ４は荷物３２を含む。
・ステップＴ１５：応答は否定的であるため、ステップＴ１４’に移動する。
・ステップＴ１４’：応答は否定的であるため、ステップＡ１２’に移動する。
・ステップＡ１２’：リストＬＩ３は荷物２１を含み、リストＬＩ４は空である。
・ステップＴ１５’：応答は肯定的であるため、荷物９６は（ノードＮ２の下流の）収集器内に投入される。
【００７９】
次に、一例として、荷物２１０（全体的な順序番号１０と、宛先Ｄ５の宛先順序番号２とを有する）を、ノードＮ２の下流の収集器上で前進させることができるか否かを判定する図４の前進解析アルゴリズムの実行について詳細に説明する。
・ステップＴ２２：応答は否定的であるため、ステップＡ２１に移動する。
・ステップＡ２１：リストＬＡ１は荷物１９を含み、リストＬＡ２は荷物８５及び５４を含む。
・ステップＴ２３：応答は否定的であるため、ステップＴ２４に移動する。
・ステップＴ２４：応答は否定的であるため、ステップＡ２２に移動する。
・ステップＡ２２：リストＬＡ３は荷物４３を含み、リストＬＡ４は荷物３２を含む。
・ステップＴ２５：応答は否定的であるため、ステップＴ２４’に移動する。
・ステップＴ２４’：応答は否定的であるため、ステップＡ２２’に移動する。
・ステップＡ２２’：リストＬＡ３は荷物２１を含み、リストＬＡ４は空である。
・ステップＴ２５’：応答は肯定的であるため、荷物２１０は（ノードＮ２の下流の）収集器内に投入される。
【００８０】
図７は、図４の前進解析アルゴリズムの（ノードＮ３における符号９６で参照される荷物に対する）第２の実行状況例を示している。図５と比較すると、この図は、荷物９６が（ノードＮ２から下流の）収集器内に投入されたことを前提として、その後の時点に位置しているものである。以下に、ノードＮ３の下流の収集器上で荷物９６を前進させることができるか否かを判定する図４の前進アルゴリズムの実行について詳細に説明する。
・ステップＴ２２：応答は否定的であり、ステップＡ２１に移動する。
・ステップＡ２１：リストＬＡ１は荷物８を含み、リストＬＡ２は荷物５４を含む。
・ステップＴ２３：応答は否定的であり、ステップＴ２４に移動する。
・ステップＴ２４：応答は肯定的であり（発送元Ｓ３から荷物４３が到着し、ノードＮ３によってまだ収集されていない）、荷物９６を収集器上で前進させることができない（荷物４３がノードＮ３の下流の収集器内に投入されない限り、前進が行われない）。
【００８１】
図８は、図４の前進解析アルゴリズムの（ノードＮ３における符号２１０で参照される荷物に対する）第３の実行状況例を示している。図５と比較すると、この図は、荷物２１０が（ノードＮ２から下流の）収集器に前進したことを前提として、その後の時点に位置しているものである。以下に、ノードＮ３の下流の収集器上で荷物２１０を前進させることができるか否かを判定する図４の前進アルゴリズムの実行について詳細に説明する。
・ステップＴ２２：応答は否定的であり、ステップＡ２１に移動する。
・ステップＡ２１：リストＬＡ１は荷物１９を含み、リストＬＡ２は荷物８５及び５４を含む。
・ステップＴ２３：応答は否定的であり、ステップＴ２４に移動する。
・ステップＴ２４：応答は肯定的であり（発送元Ｓ３から荷物４３が到着し、ノードＮ３によってまだ収集されていない）、荷物９６を収集器上で前進させることができない（荷物４３がノードＮ３の下流の収集器内に投入されない限り、前進が行われない）。
【００８２】
図９に、本発明の１つの特定の実施形態による制御システム９０の構造を示す。この装置は、ランダムアクセスメモリ９３（例えば、ＲＡＭ）と、例えば、プロセッサを有し、リードオンリーメモリ９２（例えば、ＲＯＭ又はハードディスクドライブ）に記憶されたコンピュータプログラムによって制御される処理ユニット９１とを備える。
【００８３】
まず、コンピュータプログラムのコード命令が、例えば、ランダムアクセスメモリ９３内にロードされ、その後、処理ユニット９１のプロセッサによって実行され、本発明の荷物配列方法が実施される。処理ユニット９１はコマンド９４を入力する。処理ユニット９１のプロセッサは、これらのコマンドを処理し、自動分配システムに含まれる異なる要素、特に、発送元Ｓ１〜Ｓ５、ＦＩＦＯタイプソースバッファ装置Ｆ１〜Ｆ５、収集器１、宛先Ｄ１〜Ｄ５及びＦＩＦＯタイプ宛先バッファ装置Ｆ１'〜Ｆ５'を制御（命令）する出力命令又は出力コマンドを生成する。
【００８４】
この図９は、本発明の実施形態の任意のものにおいて本発明の技法を実行する幾つかの可能な方法の中の１つの特定の方法のみを示している。実際は、制御システムは、命令シーケンスを含むプログラムを実行する再プログラミング可能なコンピューティングマシン（例えば、ＰＣコンピュータ、ＤＳＰプロセッサ、マイクロコントローラ等）、又は、専用計算マシン（例えば、ＦＰＧＡ若しくはＡＳＩＣ等の一組の論理ゲート又は他の任意のハードウェアモジュール）において同様に良好に実施することができる。
【００８５】
制御システムが、再プログラミング可能なコンピューティングマシンを用いて構成される場合、対応するプログラム（すなわち、命令シーケンス）は、着脱可能な記憶媒体（例えば、フロッピーディスク、ＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭ等）又は着脱不能な記憶媒体に記憶することができる。この記憶媒体は、コンピュータ又はプロセッサによって部分的又は全体的に可読である。
【図１】
2019536713.tif 000003
【図２】
2019536713.tif 000004
【図３】
2019536713.tif 000005
【図４】
2019536713.tif 000006
【図５】
2019536713.tif 000007
【図６】
2019536713.tif 000008
【図７】
2019536713.tif 000009
【図８】
2019536713.tif 000010
【図９】
2019536713.tif 000011
【手続補正書】
【提出日】令和1年8月15日(2019.8.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
自動分配システムにおいて制御システム（８０）により荷物を配列する方法であって、
前記自動分配システムは、
発送元（Ｓ１〜Ｓ５）と、
少なくとも１つの宛先（Ｄ１〜Ｄ５）と、
前記発送元のうちの１つから出た荷物を収集する複数の連続したノード（Ｎ１〜Ｎ５）を有し、少なくとも１つの前記宛先へと荷物を運搬する収集器（７０）と、
前記発送元から取り出され、所与の宛先に対し宛先の所与の昇順で提供される荷物が列挙された顧客注文を処理し、前記顧客注文に列挙された荷物の全体的昇順を定め、発送元ごとに、出て行く荷物が前記全体的昇順と前記顧客注文に関連した宛先の昇順とを順守することを保証するように構成された前記制御システム（８０）と
を備え、
前記制御システム（８０）は、少なくとも１つの解析対象ノードについて、所与の宛先に関する所与の宛先順序番号を有する荷物Ｃを前記収集器内に投入することができるかどうかを判定する投入解析のステップを実行し、
前記投入解析のステップは、
ａ）前記解析対象ノードの上流において、前記収集器上又は前記解析対象ノードの上流にある少なくとも１つのノードによって収集される荷物の中で、前記所与の宛先順序番号よりも小さい宛先順序番号を有する少なくとも１つの荷物が存在するか否かを判定する第１の投入テスト（Ｔ１２）のステップと、
ｂ）前記第１の投入テストの結果が肯定的である場合に、前記制御システム（８０）は前記解析対象ノードに対し前記解析対象ノードが前記収集器に前記荷物Ｃを投入しないよう命令し、さもなければ、前記制御システム（８０）は、
前記解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、前記所与の宛先順序番号よりも小さい宛先順序番号を有する荷物のリストＬＩ１と、前記リストＬＩ１の荷物と前記収集器との間にそれぞれ置かれる荷物のリストＬＩ２とを作成するステップ（Ａ１１）と、
前記リストＬＩ１が空であるという第１の投入条件と、前記リストＬＩ１が空ではなくかつ前記リストＬＩ２が空であるという第２の投入条件との一方の成立が確認されるかどうかを判定する第２の投入テストのステップ（Ｔ１３）と、
前記第１の投入条件及び前記第２の投入条件のうちの一方の成立が確認された場合に、前記制御システム（８０）は前記解析対象ノードに対し前記解析対象ノードが前記収集器に前記荷物Ｃを投入するよう命令するステップ（３０）と
を実行するステップと
を含むものである、方法。
【請求項２】
前記第１の投入条件の成立も前記第２の投入条件の成立も確認されない場合に、前記制御システム（８０）による前記投入解析のステップは、
ａ’）前記解析対象ノードの上流において、前記収集器上又は前記解析対象ノードの上流にある少なくとも１つのノードによって収集される荷物の中で、前記リストＬＩ２からの荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である少なくとも１つの荷物が存在するかどうかを判定する第３の投入テストのステップ（Ｔ１４）と、
ｂ’）前記第３の投入テストの結果が肯定的である場合に、前記制御システム（８０）は前記解析対象ノードに対し前記解析対象ノードが前記収集器に前記荷物Ｃを投入しないよう命令し、さもなければ、前記制御システム（８０）は、
前記解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、前記リストＬＩ２の荷物が有する前記宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である荷物のリストＬＩ３と、前記リストＬＩ３の荷物と前記収集器との間にそれぞれ置かれる荷物のリストＬＩ４とを作成するステップ（Ａ２）と、
前記リストＬＩ３が空であることという第３の投入条件と、前記リストＬＩ３が空ではなくかつ前記リストＬＩ４が空であるという第４の投入条件との一方の成立が確認されるかどうかを判定する第４の投入テストのステップ（Ｔ１５）と、
前記第３の投入条件及び前記第４の投入条件のうちの一方の成立が確認された場合に、前記制御システム（８０）は前記解析対象ノードに対し前記解析対象ノードが前記収集器に前記荷物Ｃを投入するよう命令するステップ（３０）と
を実行するステップと
を含むものである、請求項１に記載の方法。
【請求項３】
前記第３の投入条件の成立も前記第４の投入条件の成立も確認されない場合に、前記制御システム（８０）による前記投入解析のステップは、それまでの反復におけるリストＬＩ４を新たな各反復のリストＬＩ２として利用して、前記ステップａ’）及びｂ’）の少なくとも１回の新たな反復を行うステップを含むものである、請求項２に記載の方法。
【請求項４】
前記投入解析のステップは、前記制御システム（８０）により、前記宛先から最も遠い上流の第１のノードを除く前記ノードの各々について実行される、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記制御システム（８０）は、少なくとも１つの解析対象ノードについて、前記解析対象ノードの上流にあるノードから得られ、所与の宛先についての所与の宛先順序番号を有する荷物Ｃ’を前記収集器上で前進させることができるかどうかを判定する前進解析のステップを実行し、
前記前進解析のステップは、
１）前記解析対象ノードによって収集される荷物の中で、前記所与の宛先順序番号よりも小さい宛先順序番号を有する少なくとも１つの荷物が存在するか否かを判定する第１の前進テストのステップ（Ｔ２２）と、
２）前記前進テストの結果が肯定的である場合に、前記制御システム（８０）は前記解析対象ノードに対し前記解析対象ノードが前記収集器上で前記荷物Ｃ’を前進させないよう命令し、さもなければ、前記制御システム（８０）は、
前記解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、前記所与の宛先順序番号よりも小さい宛先順序番号を有する荷物のリストＬＡ１と、前記リストＬＡ１の荷物と前記収集器との間にそれぞれ置かれる荷物のリストＬＡ２と作成するステップ（Ａ２１）と、
前記リストＬＡ１が空であるという第１の前進条件と、前記リストＬＡ１が空ではなくかつ前記リストＬＡ２が空であるという第２の前進条件とのうちの一方の成立が確認されるかどうかを判定する第２の前進テストのステップ（Ｔ２３）と、
前記第１の前進条件及び前記第２の前進条件のうちの一方の成立が確認された場合に、前記制御システム（８０）は前記解析対象ノードに対し前記解析対象ノードが前記収集器上で前記荷物Ｃ’を前進させるよう命令するステップ（４０）と
を実行するステップと
を含むものである、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記第１の前進条件の成立も前記第２の前進条件の成立も確認されない場合に、前記制御システム（８０）による前記前進解析のステップは、
１’）前記解析対象ノードによって収集される荷物の中で、前記リストＬＡ２の荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である少なくとも１つの荷物が存在するかどうかを判定する第３の前進テストのステップ（Ｔ２４）と、
２’）前記第３の前進テストの結果が肯定的である場合に、前記制御システム（８０）は前記解析対象ノードに対し前記解析対象ノードが前記収集器上で前記荷物Ｃ’を前進させないよう命令し、さもなければ、前記制御システム（８０）は、
前記解析対象ノードの下流にある少なくとも１つのノードによって収集される荷物の中で、前記リストＬＡ２からの荷物が有する宛先順序番号よりも小さい宛先順序番号を有するとともに同じ宛先である荷物を含むリストＬＡ３と、前記リストＬＡ３の荷物と前記収集器との間にそれぞれ置かれる荷物を含むリストＬＡ４とを作成するステップ（Ａ２２）と、
前記リストＬＡ３が空であるという第３の前進条件と、前記リストＬＡ３が空ではなくかつ前記リストＬＡ４が空であるという第４の前進条件とのうちの一方の成立が確認されるかどうかを判定する第４の前進テストのステップ（Ｔ２５）と、
前記第３の前進条件及び前記第４の前進条件のうちの一方の成立が確認される場合に、前記制御システム（８０）は前記解析対象ノードに対し前記解析対象ノードが前記収集器上で前記荷物Ｃ’を前進させるよう命令するステップ（４０）と
を実行するステップと
を含むものである、請求項５に記載の方法。
【請求項７】
前記第３の前進条件の成立も前記第４の前進条件の成立も確認されない場合に、前記制御システム（８０）による前記前進解析のステップは、それまでの反復によるリストＬＡ４を新たな各反復におけるリストＬＡ２として利用して、前記ステップ１’）及び２’）の少なくとも１回の新たな反復を行うステップを含むものである、請求項６に記載の方法。
【請求項８】
前記前進解析のステップは、前記制御システム（８０）により、前記宛先の最も上流にある第１のノードを除く前記ノードの各々について実行される、請求項５〜７のいずれか１項に記載の方法。
【請求項９】
コンピュータにおいて実行されると、請求項１〜８のいずれか１項に記載の方法を前記制御システム（８０）に実行させるプログラムコード命令を含むコンピュータプログラム製品。
【請求項１０】
請求項９に記載のコンピュータプログラムを記憶する非一時的コンピュータ可読記憶媒体。
【国際調査報告】
2019536713.tif 000012
2019536713.tif 000013
2019536713.tif 000014
2019536713.tif 000015