[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP7426672B2 - sorting equipment - Google Patents

sorting equipment Download PDF

Info

Publication number
JP7426672B2
JP7426672B2 JP2021049715A JP2021049715A JP7426672B2 JP 7426672 B2 JP7426672 B2 JP 7426672B2 JP 2021049715 A JP2021049715 A JP 2021049715A JP 2021049715 A JP2021049715 A JP 2021049715A JP 7426672 B2 JP7426672 B2 JP 7426672B2
Authority
JP
Japan
Prior art keywords
route search
objects
transported
state
value
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2021049715A
Other languages
Japanese (ja)
Other versions
JP2022148146A (en
Inventor
昭徳 若林
賢司 橋本
秀生 柳澤
生光 小原
五十樹 野田
紀彦 加藤
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Toyota Industries Corp
National Institute of Advanced Industrial Science and Technology AIST
Original Assignee
Toyota Industries Corp
National Institute of Advanced Industrial Science and Technology AIST
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Toyota Industries Corp, National Institute of Advanced Industrial Science and Technology AIST filed Critical Toyota Industries Corp
Priority to JP2021049715A priority Critical patent/JP7426672B2/en
Publication of JP2022148146A publication Critical patent/JP2022148146A/en
Application granted granted Critical
Publication of JP7426672B2 publication Critical patent/JP7426672B2/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Landscapes

  • Discharge Of Articles From Conveyors (AREA)

Description

本発明は、仕分け装置に関する。 The present invention relates to a sorting device.

従来、搬送物を搬送するシステムとして、例えば特許文献1に記載されたものが知られている。このシステムは、搬送物を搬入して、所定の階数の棚に仕分ける。仕分けられた搬送物は、各階にて、保管されて、出庫のタイミングになったら、搬送されて出庫される。 BACKGROUND ART Conventionally, as a system for conveying objects, the system described in Patent Document 1, for example, is known. This system brings in items to be transported and sorts them into shelves of a predetermined number of floors. The sorted items are stored on each floor, and when the time comes to take them out, they are transported and taken out.

特開2018-81008号公報JP 2018-81008 Publication

ここで、搬入コンベアから搬入した搬送物を仕分ける場合、仕分け装置が、搬送機を用いて、複数の搬送物を同時に仕分けることで、作業効率を向上させることがある。しかしながら、このような仕分け装置においては、搬送機の動作上の制約、その他の制約などが存在することによって、適切な経路で搬送を行わなくては、仕分け時間が長くなる場合がある。 Here, when sorting the conveyance items carried in from the carry-in conveyor, the sorting device may improve work efficiency by simultaneously sorting the plurality of conveyance articles using a conveyor. However, in such a sorting device, there are operating restrictions and other restrictions on the conveyor, so if the items are not conveyed along an appropriate route, the sorting time may become longer.

従って、本発明は、適切な経路にて搬送物の仕分けを行うことができる仕分け装置を提供することを目的とする。 Therefore, an object of the present invention is to provide a sorting device that can sort conveyed items along appropriate routes.

本発明の一態様に係る仕分け装置は、搬入手段における搬入口と、水平方向移動手段を有する搬送機を少なくとも含む仕分け部と、搬出手段における搬出口と、搬入口から搬入された搬送物を仕分け部で仕分けして搬出口から搬出する制御を行う制御部と、を備える仕分け装置であって、制御部は、所定個数の搬送物を前記仕分け部で仕分けをするときに、少なくとも搬入口、及び仕分け部の各部位を探索ノードとして、最短経路探索手法を用いて各搬送物の経路を探索する、経路探索部を備え、経路探索部は、他の搬送物による影響がないと仮定した場合における、各搬送物が目的地へ移動するのに必要なコストをそれぞれ演算し、所定個数の搬送物の中から、コストが最も大きくなる搬送物を選択すると共に当該搬送物のコストを基準値とし、選択した搬送物以外についても、基準値を適用して経路探索を行う。 A sorting device according to one aspect of the present invention includes an inlet in an inlet, a sorting section including at least a carrier having a horizontal movement means, an outlet in an outlet, and a sorter for sorting articles brought in from the inlet. a control section that performs control to sort the articles at the section and carry them out from the carry-out port, and the control section controls at least the carry-in port and It is equipped with a route search section that uses each part of the sorting section as a search node to search the route of each conveyed object using the shortest route search method, and the route search section searches for the route of each conveyed object, assuming that there is no influence from other conveyed objects. , calculates the cost required for each transported object to move to its destination, selects the transported object with the largest cost from among a predetermined number of transported objects, and uses the cost of the transported object as a reference value, The route search is also performed for items other than the selected conveyance items by applying the reference value.

制御部の経路探索部は、所定個数の搬送物を仕分け部で仕分けをするときに、少なくとも搬入口、及び仕分け部の各部位を探索ノードとして、最短経路探索手法を用いて各搬送物の経路を探索する。このように、経路探索部が、最短経路探索手法を用いて各搬送物の経路を探索することで、適切な経路を設定することが可能になる。ここで、経路探索部は、他の搬送物による影響がないと仮定した場合における、各搬送物が目的地へ移動するのに必要なコストをそれぞれ演算する。これにより、経路探索部は、複数の搬送物を同時に仕分ける場合に、どの搬送物が目的地まで遠いかを把握することが可能となる。そして、経路探索部は、所定個数の搬送物の中から、コストが最も大きくなる搬送物を選択すると共に当該搬送物のコストを基準値とし、選択した搬送物以外についても、基準値を適用して経路探索を行う。これにより、経路探索部は、複数の搬送物を同時に仕分ける上で、時間を短縮できる経路を設定することができる。以上より、適切な経路にて搬送物の仕分けを行うことができる。 When a predetermined number of transported objects are sorted in the sorting section, the route search section of the control section uses at least the entrance and each part of the sorting section as search nodes to determine the route of each transported object using a shortest route search method. Explore. In this way, the route search unit searches for the route of each conveyance object using the shortest route search method, thereby making it possible to set an appropriate route. Here, the route search unit calculates the cost required for each transport object to move to its destination, assuming that there is no influence from other transport objects. Thereby, when sorting a plurality of conveyance items at the same time, the route search section can grasp which conveyance article is far from the destination. Then, the route search unit selects the item with the highest cost from among the predetermined number of items, uses the cost of the item as a reference value, and applies the standard value to items other than the selected items. route search. Thereby, the route search unit can set a route that can save time when sorting a plurality of conveyed items at the same time. As described above, it is possible to sort the conveyed items along appropriate routes.

経路探索部は、最短経路探索手法としてエースターアルゴリズムを用い、コストとして、各搬送物が目的地に到達するまでにかかるステップ数に基づく推定コストを演算し、所定個数の搬送物の中から、推定コストが最も大きくなる搬送物を選択すると共に当該搬送物の推定コストをヒューリスティック関数の値とし、選択した搬送物以外についても、ヒューリスティック関数の値を適用して経路探索を行ってよい。エースターアルゴリズムは、最適解が必ず見つかる最短経路探索方法として、経路探索において有効に用いられている方法である。経路探索部が、このようなエースターアルゴリズムを用いことで、最適な経路を探索することができる。 The route search unit uses the Aster algorithm as the shortest route search method, calculates the estimated cost based on the number of steps it takes for each transported object to reach its destination, and calculates the cost from among a predetermined number of transported objects. The transport object with the largest estimated cost may be selected, and the estimated cost of the transport object may be set as the value of the heuristic function, and the route search may be performed by applying the value of the heuristic function to objects other than the selected transport object. The Aster algorithm is a method that is effectively used in route searching as a method for searching for the shortest route that always finds the optimal solution. The route search unit can search for an optimal route by using such an Aster algorithm.

経路探索部は、所定タイミングにおける各搬送物の配置状態から、次のタイミングに発生し得る各搬送物の次状態候補を複数演算し、複数の次状態候補に対して、動作ステップ数と基準値との和による状態評価値を演算し、複数の次状態候補の中から、状態評価値が最も小さくなるものを経路探索に採用してよい。この場合、経路探索部は、状態評価値を比較することで、複数の次状態候補の中から、適切なものを採用することができる。 The route search unit calculates multiple next state candidates for each transported object that may occur at the next timing from the arrangement state of each transported object at a predetermined timing, and calculates the number of operation steps and a reference value for the multiple next state candidates. The state evaluation value may be calculated by the sum of the next state candidates, and the one with the smallest state evaluation value may be selected from among the plurality of next state candidates for the route search. In this case, the route search unit can select an appropriate next state candidate from among the plurality of next state candidates by comparing the state evaluation values.

経路探索において、所定個数の搬送物の配置状態の候補として同率に評価される候補が複数表れた場合、経路探索部は、仕分け部中の搬送物が少ない方の候補を優先してよい。先に目的地に搬送物が到達した候補を選ぶことで、その後の経路の探索がやりやすくなるため、経路探索部は、そのような候補を優先することができる。 In the route search, if a plurality of candidates that are equally evaluated as candidates for the arrangement state of the predetermined number of transported objects appear, the route searching section may prioritize the candidate with fewer transported objects in the sorting section. By selecting a candidate whose conveyed object reaches its destination first, it becomes easier to search for a subsequent route, so the route search unit can give priority to such candidates.

経路探索において、所定個数の搬送物の配置状態の候補として同率に評価される候補が複数表れた場合、経路探索部は、各搬送物が前記目的地へ到達するまでの見積値の合計値を演算し、合計値が少ない候補を優先してよい。この場合、経路探索部は、複数の搬送物の目的地までの遠さを全体的に考慮した候補を優先することができる。 In the route search, if multiple candidates that are equally evaluated as candidates for the arrangement state of a predetermined number of transported objects appear, the route search section calculates the total value of the estimated value until each transported object reaches the destination. Candidates with a smaller total value may be given priority. In this case, the route search unit can give priority to candidates that take into consideration the overall distance to the destination of the plurality of conveyance items.

制御部は、搬送物の配置状態に対する最適な経路探索情報が予め準備された最適化テーブルを取得する最適化テーブル取得部を備え、経路探索部は、搬送物の配置状態を最適化テーブルへ問い合わせ、当該最適化テーブルから返送された最適解に基づいて、経路探索を行ってよい。この場合、経路探索部は、準備された最適化テーブルを用いることで、速やかに経路を探索できる。 The control unit includes an optimization table acquisition unit that acquires an optimization table in which optimal route search information for the arrangement state of the transported object is prepared in advance, and the route search unit queries the optimization table about the arrangement state of the transported object. , the route search may be performed based on the optimal solution returned from the optimization table. In this case, the route search unit can quickly search for a route by using the prepared optimization table.

最適化テーブルは、搬送物の搬送状態に対して予め規則化された添え字値が紐付けられたハッシュテーブルを有し、経路探索部は、搬送物の配置状態に対応する添え字値を演算し、演算した添え字値を用いてハッシュテーブルを参照してよい。この場合、経路探索部は、添え字値を用いることで、処理時間を短縮して最適化テーブルから、適切な経路を取得できる。 The optimization table has a hash table in which subscript values that are regularized in advance are linked to the transportation state of the transported object, and the route search unit calculates the subscript value that corresponds to the arrangement state of the transported object. Then, the hash table may be referenced using the calculated subscript value. In this case, by using the subscript value, the route search unit can shorten the processing time and obtain an appropriate route from the optimization table.

経路探索部が、搬出口側の範囲において、設定値以下の個数の搬送物の配置状態を最適化テーブルへ問い合わせる場合、搬入口からの新たな搬送物の搬入に制限を設けてよい。この場合、経路探索部は、搬入手段から新たな搬送物が搬入されてても、問い合わせ対象の搬送物の個数を設定値以下に抑制できるので、最適化テーブルを利用することができる。 When the route search unit inquires of the optimization table about the arrangement state of objects to be transported whose number is equal to or less than a set value in the area on the exit side, a limit may be set on the introduction of new objects to be transported from the entrance. In this case, even if a new object is brought in from the loading means, the route search section can suppress the number of objects to be queried to below the set value, and thus can utilize the optimization table.

本発明によれば、適切な経路にて搬送物の仕分けを行うことができる仕分け装置を提供することができる。 According to the present invention, it is possible to provide a sorting device that can sort conveyed items along appropriate routes.

本発明の実施形態に係る仕分け装置が適用される倉庫システムを示す概略側面図である。1 is a schematic side view showing a warehouse system to which a sorting device according to an embodiment of the present invention is applied. 本発明の実施形態に係る仕分け装置の構成を示す概略構成図である。1 is a schematic configuration diagram showing the configuration of a sorting device according to an embodiment of the present invention. 搬送系をモデル化した図である。It is a diagram modeling a transport system. 本実施形態に係る仕分け装置のブロック構成図である。FIG. 1 is a block configuration diagram of a sorting device according to the present embodiment. 仕分け部における経路を示す概念図である。It is a conceptual diagram showing the route in a sorting part. 経路探索部の処理内容を示す概念図である。FIG. 3 is a conceptual diagram showing processing contents of a route search unit. 見積値について説明する概念図である。It is a conceptual diagram explaining an estimated value. 最適化テーブルについて説明する概念図である。It is a conceptual diagram explaining an optimization table. 最適化テーブルについて説明する概念図である。It is a conceptual diagram explaining an optimization table. 最適化テーブルの一例である。This is an example of an optimization table. 添え時値を説明するための概念図である。FIG. 2 is a conceptual diagram for explaining a value at the time of attachment. 添え字値を用いた処理内容を示す概念図である。FIG. 2 is a conceptual diagram showing the content of processing using subscript values. 最適化テーブルに保存される残りステップを説明する概念図である。FIG. 7 is a conceptual diagram illustrating remaining steps saved in an optimization table. 搬入される搬送物を規制する様子を示す概念図である。FIG. 2 is a conceptual diagram illustrating how transported objects are regulated. 経路探索部の処理内容を示すフローチャートである。It is a flowchart which shows the processing content of a route search part.

以下、本発明の実施形態について、図面を参照して詳細に説明する。 Embodiments of the present invention will be described in detail below with reference to the drawings.

図1は、本発明の実施形態に係る仕分け装置1が適用される倉庫システム100を示す概略側面図である。図1に示すように、倉庫システム100は、複数の搬送物150を入庫して保管し、保管された各搬送物150のうち、出庫すべきものを出庫可能なシステムである。倉庫システム100は、倉庫本体部101と、入庫渡り通路103と、出庫渡り通路102と、入庫エレベータ105と、出庫エレベータ104と、を備える。倉庫本体部101は、複数段の棚110を有している。棚110は、倉庫本体部101の一方側の端部から他方側の端部へ延在している。棚110では、移載装置111にて、入庫経路から出庫経路への搬送物の移載動作が行われる。入庫渡り通路103は、倉庫本体部101の一方側の端部に設けられ、各段の棚110に対して搬送物150を入庫する機構である。出庫渡り通路102は、倉庫本体部101の他方側の端部に設けられ、各段の棚110から搬送物150を出庫する機構である。入庫エレベータ105は、搬入コンベア21から入庫される搬送物150を上下させて、所望の棚110に対応する段の入庫渡り通路103へ搬送物150を供給する。出庫エレベータ104は、出庫対象となる搬送物150を棚110及び出庫渡り通路102から受け取り、図示しない出庫口へ昇降させる。出庫エレベータ104から出庫された搬送物150は、搬出コンベア121へ搬出される。このうち、入庫エレベータ105付近に、本実施形態に係る仕分け装置1が適用される。 FIG. 1 is a schematic side view showing a warehouse system 100 to which a sorting device 1 according to an embodiment of the present invention is applied. As shown in FIG. 1, the warehouse system 100 is a system that can store and store a plurality of transported objects 150 and take out the stored objects 150 that should be taken out of the warehouse. The warehouse system 100 includes a warehouse main body 101, a warehousing crossing passage 103, a warehousing crossing passage 102, a warehousing elevator 105, and a warehousing elevator 104. The warehouse main body 101 has multiple shelves 110. The shelves 110 extend from one end of the warehouse main body 101 to the other end. On the shelf 110, a transfer device 111 performs a transfer operation of the transported object from the warehousing route to the warehousing route. The warehousing passageway 103 is provided at one end of the warehouse main body 101 and is a mechanism for warehousing articles 150 onto the shelves 110 at each stage. The unloading passageway 102 is provided at the other end of the warehouse main body 101, and is a mechanism for unloading articles 150 from the shelves 110 at each stage. The warehousing elevator 105 moves up and down the goods 150 that are stored from the carry-in conveyor 21 and supplies the goods 150 to the warehousing crossover passageway 103 of the stage corresponding to the desired shelf 110 . The unloading elevator 104 receives a conveyance object 150 to be unloaded from the shelf 110 and the unloading passageway 102, and moves it up and down to an unillustrated exit exit. The conveyed object 150 that has been unloaded from the unloading elevator 104 is transported to the unloading conveyor 121 . Of these, the sorting device 1 according to this embodiment is applied near the warehousing elevator 105.

図2は、本発明の実施形態に係る仕分け装置1の構成を示す概略構成図である。図2に示すように、仕分け装置1は、搬送物150を搬送する搬送系2と、搬送系2を制御する制御部10と、を備える。搬送系2は、搬入コンベア21(搬入手段)と、搬送機22と、搬出コンベア23(搬出手段)と、を備える。このうち、搬送機22は、前述の入庫エレベータ105を構成する機器である。搬入コンベア21は、搬送機22に搬入される搬送物150を当該搬送機22側へ水平に搬送する装置である。搬入コンベア21は、搬送機22の所定の段に対して設けられている。搬出コンベア23は、搬送機22から搬出される搬送物150を水平に搬送する装置である。搬出コンベア23は、入庫渡り通路103の各階(ここでは四階)に設けられる。 FIG. 2 is a schematic configuration diagram showing the configuration of the sorting device 1 according to the embodiment of the present invention. As shown in FIG. 2, the sorting device 1 includes a transport system 2 that transports objects 150, and a control unit 10 that controls the transport system 2. The conveyance system 2 includes a carry-in conveyor 21 (carry-in means), a conveyor 22, and a carry-out conveyor 23 (carry-out means). Among these, the transport machine 22 is a device that constitutes the above-mentioned warehousing elevator 105. The carry-in conveyor 21 is a device that horizontally conveys the conveyance object 150 carried into the conveyor 22 to the conveyor 22 side. The carry-in conveyor 21 is provided for a predetermined stage of the conveyor 22. The carry-out conveyor 23 is a device that horizontally conveys the object 150 carried out from the conveyor 22. The carry-out conveyor 23 is provided on each floor (here, the fourth floor) of the warehousing crossing passageway 103.

搬送機22は、水平方向移動手段(例えばコンベア)と、上下移動手段と、を備え、搬送物150を上下方向及び水平方向に移動させる装置である。これにより、搬送機22は、各搬送物150を入庫渡り通路103における目的階へ移動させる。なお、図では、「n階」を目的地とした搬送物150に対して、「n」の数字が付されている。以降の図においても同様である。また、以降の説明では、n階を目的値とした搬送物150を「n階への搬送物」と称する場合がある。 The conveyance machine 22 is a device that includes a horizontal movement means (for example, a conveyor) and a vertical movement means, and moves the conveyed object 150 in the vertical direction and the horizontal direction. Thereby, the transport machine 22 moves each transported object 150 to the destination floor in the warehousing passageway 103. In addition, in the figure, the number "n" is attached to the transported object 150 whose destination is "nth floor". The same applies to subsequent figures. Furthermore, in the following description, the transported object 150 with the nth floor as the target value may be referred to as "the transported object to the nth floor."

。搬送機22は、交互動作式の昇降装置であり、搬入コンベア21側の搬送棚22Aと、搬出コンベア23側の搬送棚22Bを有している。搬送棚22A、22Bは、それぞれ「仕分けの階数+一階」分の段数の収容可能エリアCEを有している。そして、「仕分けの階数」分の段数(ここでは四段)で連続した搬送箱22aを有している。連続した搬送箱22aは、同時に上下移動する。連続した搬送箱22aが下側へ移動すると、下から順に一段目から四段目の収容可能エリアCEに各搬送箱22aが配置される。連続した搬送箱22aが上側へ移動すると、下から順に二段目から五段目の収容可能エリアCEに各搬送箱22aが配置される。なお、以降の説明において、単に段数について述べた場合、特に注意が無い限り、下からカウントした段数を示すものとする。また、搬送棚22Aの搬送箱22aと搬送棚22Bの搬送箱22aは、交互に上下移動する。すなわち、搬送棚22Aの搬送箱22aが上側へ移動すると、搬送棚22Bの搬送箱22aが下側へ移動し、搬送棚22Aの搬送箱22aが下側へ移動すると、搬送棚22Bの搬送箱22aが上側へ移動する。また、同じ段数において、搬送棚22Aの搬送箱22aと搬送棚22Bの搬送箱22aとの間にて、搬送物150を水平方向に移動させることができ、相互に搬送物150の受け渡しと受け取りを行うことができる。 . The conveyance machine 22 is an alternating operation type lifting device, and has a conveyance shelf 22A on the carry-in conveyor 21 side and a conveyance shelf 22B on the carry-out conveyor 23 side. Each of the transport shelves 22A and 22B has an accommodating area CE with a number of stages equal to "the number of floors for sorting + the first floor". The transport box 22a has continuous transport boxes 22a with a number of stages corresponding to the "number of floors for sorting" (here, four stages). The continuous transport boxes 22a move up and down simultaneously. When the continuous transport boxes 22a move downward, each transport box 22a is arranged in the accommodating areas CE of the first to fourth stages from the bottom. When the continuous transport boxes 22a move upward, each transport box 22a is arranged in the accommodating areas CE of the second to fifth stages from the bottom. In the following description, when simply referring to the number of stages, unless otherwise noted, the number of stages counted from the bottom is meant. Further, the transport box 22a of the transport shelf 22A and the transport box 22a of the transport shelf 22B are alternately moved up and down. That is, when the transport box 22a of the transport shelf 22A moves upward, the transport box 22a of the transport shelf 22B moves downward, and when the transport box 22a of the transport shelf 22A moves downward, the transport box 22a of the transport shelf 22B moves downward. moves upward. Moreover, in the same number of stages, the transported object 150 can be moved in the horizontal direction between the transport box 22a of the transport shelf 22A and the transport box 22a of the transport shelf 22B, and the mutual delivery and receipt of the transported object 150 is possible. It can be carried out.

本実施形態では、下から二段目の収容可能エリアCEに対して搬入コンベア21が設けられ、下から二段目~五段目の収容可能エリアCEに対して四つの搬出コンベア23が設けられる。なお、図2において収容可能エリアCEの中で「L」「R」と示された箇所は、搬送棚22A,22Bが昇降動作をするために設けられたスペースである。ただし、収容可能エリアCE、搬入コンベア21、及び搬出コンベア23との位置関係は特に限定されるものではなく、倉庫システム100の構成に応じて、適宜設定されてよい。 In this embodiment, an incoming conveyor 21 is provided for the second tier from the bottom of the accommodating area CE, and four outgoing conveyors 23 are provided for the accommodating areas CE of the second to fifth tiers from the bottom. . In addition, in FIG. 2, the locations indicated by "L" and "R" in the accommodating area CE are spaces provided for the transport shelves 22A, 22B to move up and down. However, the positional relationship among the accommodating area CE, the carry-in conveyor 21, and the carry-out conveyor 23 is not particularly limited, and may be appropriately set according to the configuration of the warehouse system 100.

上述のような装置構成により、仕分け装置1の搬送系2は、搬入口30と、仕分け部31と、搬出口32と、を備える。搬入口30は、搬入コンベア21のうち、搬送方向の最も下流側の搬送物配置エリアに設定される。搬出口32は、各階の搬出コンベア23のうち、搬送方向の最も上流側の搬送物配置エリアに設定される。仕分け部31は、搬送機22を少なくとも含む。更に、三階分の搬出コンベア23のうち、搬送方向の最も上流側の搬送物配置エリアは、搬送物150の仕分けに用いることができる。例えば、一階の搬出コンベア23は、一階への搬送物150にとっては目的地であるが、三階への搬送物150にとっては目的地ではない。従って、三階の搬送物150を一階の搬出コンベア23に一時的に配置してよい。このようなエリアは、仕分け部31の一部である一時配置エリア34となる。なお一時配置エリア34は、搬入口30に設けられていてもよい。 With the device configuration as described above, the conveyance system 2 of the sorting device 1 includes an inlet 30, a sorting section 31, and an outlet 32. The carry-in port 30 is set in the conveyance object placement area of the carry-in conveyor 21 on the most downstream side in the conveyance direction. The carry-out port 32 is set in the most upstream conveyed article arrangement area in the conveyance direction among the carry-out conveyors 23 on each floor. The sorting section 31 includes at least the conveyor 22. Further, among the three floors of the carry-out conveyor 23, the most upstream conveyance object placement area in the conveyance direction can be used for sorting the conveyance objects 150. For example, the discharge conveyor 23 on the first floor is the destination for the goods 150 to be transported to the first floor, but not the destination for the goods 150 to be transported to the third floor. Therefore, the third floor conveyed article 150 may be temporarily placed on the first floor discharge conveyor 23. Such an area becomes a temporary placement area 34 that is a part of the sorting section 31. Note that the temporary placement area 34 may be provided at the loading entrance 30.

上述のような搬送系2の動作の一例について説明する。ここでは、搬送棚22Aが下がった状態(搬送棚22Bが上がった状態)で、搬送物150を四階の搬出コンベア23へ移動させる場合の動作の一例について説明する。まず、搬送棚22Aは、二段目の収容可能エリアCEにて、二段目の搬送箱22aで搬送物150を受容する(M1)。搬送棚22Aは、搬送箱22aと共に搬送物150を一段上昇させる(M2)。搬送棚22Aの二段目の搬送箱22aは、三段目の収容可能エリアCEにて搬送棚22Bの三段目の搬送箱22aへ搬送物150を受け渡す(M3)。搬送棚22Bは、搬送箱22aと共に搬送物150を一段上昇させる(M4)。搬送棚22Bの三段目の搬送箱22aは、三段目の一時配置エリア34へ搬送物150を受け渡して(M5)、一段下がる。三段目の搬出コンベア23は、搬送棚22Bの四段目の搬送箱22aへ搬送物150を受け渡す(M6)。搬送棚22Bは、搬送箱22aと共に搬送物150を一段上昇させる(M7)。搬送棚22Bの四段目の搬送箱22aは、五段目の収容可能エリアCEにて、四階の搬出コンベア23の搬出口32へ搬送物150を受け渡す(M8)。これにより、四階の搬送物150が目的地に到達する。なお、搬送物150を移動させる際に、搬送棚22A,22Bの状態と搬送物150の目的地によっては、一時配置エリア34へ搬送物150を受け渡さず、搬送棚22A,22Bのやり取りだけで目的地に搬送する場合もある。 An example of the operation of the transport system 2 as described above will be explained. Here, an example of the operation in the case where the conveyed object 150 is moved to the carry-out conveyor 23 on the fourth floor with the conveying shelf 22A in a lowered state (the conveying shelf 22B in a raised state) will be described. First, the transport shelf 22A receives the transported object 150 in the second stage transport box 22a in the second stage storage area CE (M1). The transport shelf 22A raises the transported object 150 one step higher together with the transport box 22a (M2). The second-stage transport box 22a of the transport shelf 22A delivers the object 150 to the third-stage transport box 22a of the transport shelf 22B in the third-stage accommodation area CE (M3). The transport shelf 22B raises the transported object 150 one step higher together with the transport box 22a (M4). The transport box 22a on the third stage of the transport shelf 22B delivers the transported object 150 to the temporary placement area 34 on the third stage (M5), and then moves down one stage. The third-stage delivery conveyor 23 delivers the article 150 to the fourth-stage transport box 22a of the transport shelf 22B (M6). The transport shelf 22B raises the transported object 150 one step higher together with the transport box 22a (M7). The transport box 22a on the fourth stage of the transport shelf 22B delivers the transported object 150 to the exit 32 of the transport conveyor 23 on the fourth floor in the accommodation area CE on the fifth stage (M8). As a result, the transported object 150 on the fourth floor reaches its destination. Note that when moving the transported object 150, depending on the state of the transport shelves 22A, 22B and the destination of the transported object 150, the transported object 150 may not be delivered to the temporary placement area 34, but may only be exchanged between the transport shelves 22A, 22B. It may also be transported to the destination.

以降の説明においては、仕分け装置1の搬送系2を図3のようにモデル化して示す場合がある。一つの搬送物150を配置可能なエリアが、一つの四角形で示されている。なお、各搬送物150は、干渉物がないかぎり、水平方向に同時動作が可能である。垂直動作としては、搬送機22の搬送棚の垂直動作中は、搬送機22内の搬送物150は動作不可である。搬送機22の垂直動作中は、搬入コンベア21及び搬出コンベア23は水平動作可能である。動作速度は特に限定されないが、水平動作は約1.0秒に設定され、垂直動作は約1.75秒に設定されてよい。 In the following description, the transport system 2 of the sorting device 1 may be shown as a model as shown in FIG. An area where one conveyance object 150 can be placed is shown as one square. Note that each conveyance object 150 can be operated simultaneously in the horizontal direction unless there is an interfering object. Regarding the vertical movement, during the vertical movement of the transport shelf of the transport machine 22, the transported object 150 in the transport machine 22 cannot be moved. While the conveyance machine 22 is operating vertically, the carry-in conveyor 21 and the carry-out conveyor 23 can be operated horizontally. Although the operation speed is not particularly limited, the horizontal operation may be set to approximately 1.0 seconds, and the vertical operation may be set to approximately 1.75 seconds.

次に、図4を参照して、仕分け装置1のブロック構成について説明する。図4は、本実施形態に係る仕分け装置1のブロック構成図である。制御部10は、搬送系2を制御するユニットである。制御部10は、搬入口30から搬入された搬送物150を仕分け部31で仕分けして搬出口32から搬出する。制御部10は、仕分け装置1を統括的に管理するECU[ElectronicControl Unit]を備えている。ECUは、CPU[Central Processing Unit]、ROM[Read Only Memory]、RAM[Random Access Memory]、CAN[Controller Area Network]、通信回路等を有する電子制御ユニットである。ECUでは、例えば、ROMに記憶されているプログラムをRAMにロードし、RAMにロードされたプログラムをCPUで実行することにより各種の機能を実現する。制御部10は、動作制御部11、経路探索部12と、最適化テーブル取得部13と、を備える。 Next, the block configuration of the sorting device 1 will be explained with reference to FIG. 4. FIG. 4 is a block diagram of the sorting device 1 according to this embodiment. The control section 10 is a unit that controls the transport system 2. The control unit 10 uses the sorting unit 31 to sort the objects 150 carried in from the carry-in port 30 and carries them out from the carry-out port 32. The control unit 10 includes an ECU (Electronic Control Unit) that comprehensively manages the sorting device 1. The ECU is an electronic control unit that includes a CPU [Central Processing Unit], a ROM [Read Only Memory], a RAM [Random Access Memory], a CAN [Controller Area Network], a communication circuit, and the like. The ECU realizes various functions by, for example, loading a program stored in a ROM into a RAM and executing the program loaded into the RAM by a CPU. The control unit 10 includes an operation control unit 11, a route search unit 12, and an optimization table acquisition unit 13.

動作制御部11は、経路探索部12で探索した経路に従って各搬送物150が搬送されるように、搬送系2の動作を制御するユニットである。動作制御部11は、搬送系2の搬入コンベア21、搬送機22、及び搬出コンベア23の各駆動部へ制御信号を送信することで、各駆動部を動作させる。 The operation control section 11 is a unit that controls the operation of the conveyance system 2 so that each article 150 is conveyed according to the route searched by the route search section 12. The operation control unit 11 operates each drive unit of the carry-in conveyor 21, the transport machine 22, and the carry-out conveyor 23 of the transport system 2 by transmitting a control signal to each drive unit.

経路探索部12は、搬送系2の仕分け部31における、各搬送物150の経路を探索するユニットである。ここで、仕分け部31における経路について図5を参照して説明する。例えば、図5の左上に示す状態をスタート状態とし、図5の右下に示すように、全ての搬送物150が状態をゴール状態とする。スタート状態とゴール状態との間では、仕分け装置1は、各搬送物の水平移動、及び垂直移動を同時に行い、各動作を組み合わせることによって、各搬送物150の目的地まで搬送する。このとき、仕分け装置1は、複数の搬送物150を仕分け部31によって、搬送機22の動作的制限下において、互いの搬送物150が干渉しないように、且つ、速やかに仕分けできるように、搬送物150を移動させる。この際、経路探索部12は、各搬送物150が仕分け部31内にてどのような経路を通って、目的地まで到達するかを演算する。 The route search unit 12 is a unit that searches for a route for each transported object 150 in the sorting unit 31 of the transport system 2. Here, the route in the sorting section 31 will be explained with reference to FIG. For example, the state shown in the upper left of FIG. 5 is the start state, and as shown in the lower right of FIG. 5, the state of all conveyed objects 150 is the goal state. Between the start state and the goal state, the sorting device 1 simultaneously moves each conveyed object horizontally and vertically, and conveys each conveyed object 150 to its destination by combining each operation. At this time, the sorting device 1 uses the sorting unit 31 to sort the plurality of conveyed objects 150 under the operational limitations of the conveyor 22 so that the objects 150 do not interfere with each other and can be sorted quickly. Move the object 150. At this time, the route search section 12 calculates what route each conveyance object 150 takes within the sorting section 31 to reach the destination.

経路探索部12は、所定個数の搬送物150を仕分け部31で仕分けをするときに、少なくとも搬入口30、及び仕分け部31の各部位を探索ノードとして、最短経路探索手法を用いて各搬送物150の経路を探索する。図3のモデルでは、仕分け部31の収容可能エリアCEや、搬入口30、搬出口32、すなわち一つ当たりの四角形を、一つの探索ノードとして取り扱うことができる。経路探索部12は、他の搬送物150による影響がないと仮定した場合における、各搬送物150が目的地へ移動するのに必要なコストをそれぞれ演算する。なお、コストを示す値の単位は特に限定されず、時間、または距離などで示されてよい。コストは、ある搬送物150が、目的地へ到達するために、最低限必要になる条件(時間的条件、距離的条件)を示す。ここで、一つの移動物が、一つの目的地へ到達するための経路を探索するときは、一つの移動物のコストだけを考慮して経路を探索すればよい。しかし、仕分け装置1では、複数の搬送物150が、複数の目的地へ到達し、且つ、同じ候補経路の中で複数の搬送物150が同時に存在する。そこで、経路探索部12は、所定個数の搬送物150の中から、コストが最も大きくなる搬送物150を選択すると共に当該搬送物のコストを基準値とし、選択した搬送物以外についても、基準値を適用して経路探索を行う。すなわち、経路探索部12は、最も距離が遠い搬送物150の最短経路のコストの下限値を、搬送物150すべてのコストに適用することで経路探索を行う。例えば、図7の例では、経路探索部12は、最も距離が遠い「見積値10」の搬送物150の最短経路のコストの下限値(見積値10)を、他の搬送物150の全てのコストに適用して、経路検索を行う。 When sorting a predetermined number of transported objects 150 in the sorting section 31, the route searching section 12 uses a shortest route search method to sort each transported object by using at least the loading port 30 and each part of the sorting section 31 as search nodes. Search 150 routes. In the model of FIG. 3, the accommodating area CE of the sorting section 31, the loading port 30, and the loading port 32, that is, each square can be handled as one search node. The route search unit 12 calculates the cost required for each transport object 150 to move to its destination, assuming that there is no influence from other transport objects 150. Note that the unit of the value indicating the cost is not particularly limited, and may be expressed in time, distance, or the like. The cost indicates the minimum necessary conditions (time conditions, distance conditions) for a certain transported object 150 to reach its destination. Here, when searching for a route for one moving object to reach one destination, it is sufficient to search for the route by considering only the cost of the one moving object. However, in the sorting device 1, a plurality of objects 150 arrive at a plurality of destinations, and a plurality of objects 150 exist simultaneously on the same candidate route. Therefore, the route search unit 12 selects the transported object 150 with the largest cost from among the predetermined number of transported objects 150, uses the cost of the concerned transported object as a reference value, and sets other transported objects other than the selected transported objects to the reference value. Route search is performed by applying . That is, the route search unit 12 performs route searching by applying the lower limit of the cost of the shortest route of the object 150 having the farthest distance to the cost of all the objects 150. For example, in the example of FIG. 7, the route search unit 12 determines the lower limit cost (estimated value 10) of the shortest route for the farthest transported object 150 with the "estimated value 10", for all other transported objects 150. Route search is performed by applying the cost.

具体的に、経路探索部12は、最短経路探索手法としてエースターアルゴリズム(A*アルゴリズム)を用いる。エースターアルゴリズムは、グラフ上でスタートからゴールまでの道を見つけるという、グラフ探索の場面において、ヒューリスティック関数と称される探索の道標となる関数を用いて探索を行うアルゴリズムである。ヒューリスティック関数は、各探索ノードから目的値までのコストのある妥当な推定値を返す関数である。ここでは、コストとして、各搬送物150が目的地に到達するまでにかかるステップ数に基づく推定コストが採用される。 Specifically, the route search unit 12 uses the Aster algorithm (A* algorithm) as the shortest route search method. The Aster algorithm is an algorithm that performs a search using a function called a heuristic function that serves as a guidepost for the search in the graph search scene of finding a path from a start to a goal on a graph. A heuristic function is a function that returns a reasonable estimate of the cost from each search node to the target value. Here, as the cost, an estimated cost based on the number of steps required for each transported object 150 to reach its destination is employed.

仕分け装置1では、ある搬送物150に対する推定コストは、搬送物150が仕分け部31を通過するまでに要すると見積もられるステップ数で示される。このステップ数は、搬送物150が、寄り道することなく仕分け部31内の探索ノードを移動し、最短で仕分け部31を通過するのに要するステップ数で与えられる。なお、推定コストは、このようなステップ数を移動するのに要する時間で示されてもよく、当該ステップ数を移動する距離などで示されてもよい。例えば、図6の「現在状態」で示す図では、一階への搬送物150は、三回のステップ数で仕分け部31を通過する。従って、「現在状態」の一階への搬送物150の推定コストは、「3」となる。二階への搬送物150は、二回のステップ数で仕分け部31を通過する。従って、「現在状態」の二階への搬送物150の推定コストは、「2」となる。なお、図6では、矢印一つ分が一ステップを示している。なお、前述の図2の例においても、M1~M8の矢印の一つが一ステップを示している。 In the sorting device 1, the estimated cost for a certain transported object 150 is indicated by the estimated number of steps required for the transported object 150 to pass through the sorting section 31. This number of steps is given by the number of steps required for the conveyed article 150 to move through the search nodes in the sorting section 31 without making a detour and to pass through the sorting section 31 in the shortest possible time. Note that the estimated cost may be expressed as the time required to move the number of steps, or may be expressed as the distance traveled through the number of steps. For example, in the diagram shown in "Current State" in FIG. 6, the article 150 to be transported to the first floor passes through the sorting section 31 in three steps. Therefore, the estimated cost of the object 150 to be transported to the first floor in the "current state" is "3". The article 150 to be transported to the second floor passes through the sorting section 31 in two steps. Therefore, the estimated cost of the item 150 to be transported to the second floor in the "current state" is "2". Note that in FIG. 6, each arrow represents one step. Note that in the example of FIG. 2 described above, one of the arrows M1 to M8 indicates one step.

これに対し、経路探索部12は、所定個数の搬送物150の中から、推定コストが最も大きくなる搬送物150を選択すると共に当該搬送物の推定コストをヒューリスティック関数の値とする。そして、経路探索部12は、選択した搬送物以外についても、ヒューリスティック関数の値を適用して経路探索を行う。図6の「現在状態」では、一階への搬送物150が、推定コストが最も大きくなる搬送物150に該当する。経路探索部12は、一階への搬送物150の推定コストである「3」をヒューリスティック関数の値(コストの基準値)とする。経路探索部12は、選択した搬送物150以外の二階への搬送物150についても、ヒューリスティック関数の値である「3」を適用して経路探索を行う。このとき、経路探索部12は、各状態における評価を行うために、状態評価値を演算する。状態評価値は、基準から演算時における状態に至るまでの動作ステップ数と、ヒューリスティック関数の値との和によって求められる。図6に示す「現在状態」は、ステップ数の基準となる状態であるため、「ステップ数:0」である。前述のように「ヒューリスティック関数の値:3」である。従って、「状態評価値:3」となる。 On the other hand, the route search unit 12 selects the transport object 150 with the largest estimated cost from among the predetermined number of transport objects 150, and uses the estimated cost of the transport object as the value of the heuristic function. Then, the route searching unit 12 performs route searching for objects other than the selected transport object by applying the value of the heuristic function. In the "current state" of FIG. 6, the object 150 to be transported to the first floor corresponds to the object 150 with the highest estimated cost. The route search unit 12 sets "3", which is the estimated cost of transporting the object 150 to the first floor, as the value of the heuristic function (cost reference value). The route search unit 12 performs route search for objects 150 to be transported to the second floor other than the selected object 150 by applying the heuristic function value "3". At this time, the route search unit 12 calculates a state evaluation value in order to perform evaluation in each state. The state evaluation value is determined by the sum of the number of operation steps from the reference to the state at the time of calculation and the value of the heuristic function. The "current state" shown in FIG. 6 is the state that serves as the reference for the number of steps, so the "number of steps: 0". As mentioned above, the value of the heuristic function is 3. Therefore, "state evaluation value: 3" is obtained.

経路探索部12は、所定タイミングにおける各搬送物150の配置状態から、次のタイミングに発生し得る各搬送物150の次状態候補を複数演算する。経路探索部12は、複数の次状態候補に対して、状態評価値を演算する。そして、経路探索部12は、複数の次状態候補の中から、状態評価値が最も小さくなるものを経路探索に採用する。具体的に、図6には、「現在状態」から一ステップ進んだ状態として、「次状態」の欄に記載された状態候補A1~A3などが例示される。経路探索部12は、各状態候補A1~A3についての状態評価値を演算する。なお、経路探索部12は、各状態候補A1~A3について、ヒューリスティック関数の値を再び演算する。このとき、二階への搬送物150の推定コストが最も大きくなる場合、二階への搬送物150の推定コストがヒューリスティック関数の値となってよい。ここでは、状態候補A3の状態評価値が最も小さくなる。よって、経路探索部12は、各搬送物150について、「現在状態」の探索ノードから状態候補A3の探索ノードへ向かう経路を採用する。 The route search unit 12 calculates a plurality of next state candidates for each transported object 150 that may occur at the next timing from the arrangement state of each transported object 150 at a predetermined timing. The route search unit 12 calculates state evaluation values for a plurality of next state candidates. Then, the route search unit 12 selects, from among the plurality of next state candidates, the one with the smallest state evaluation value for route searching. Specifically, FIG. 6 shows state candidates A1 to A3 listed in the "Next state" column as states that are one step ahead of the "current state". The route search unit 12 calculates state evaluation values for each of the state candidates A1 to A3. Note that the route search unit 12 calculates the value of the heuristic function again for each state candidate A1 to A3. At this time, if the estimated cost of the object 150 to be transported to the second floor is the largest, the estimated cost of the object 150 to be transported to the second floor may be the value of the heuristic function. Here, the state evaluation value of state candidate A3 is the smallest. Therefore, the route search unit 12 adopts a route from the "current state" search node to the state candidate A3 search node for each conveyance object 150.

図6には、「次状態」から一ステップ進んだ状態として、「次々状態」の欄に記載された状態候補B1~B4などが例示される。経路探索部12は、各状態候補B1~B4についての状態評価値を演算する。なお、経路探索部12は、各状態候補B1~B3について、ヒューリスティック関数の値を再び演算する。ここでは、状態候補B3,B4の状態評価値が最も小さくなる。経路探索部12は、状態評価値が同率になった場合は、例えば後述のような方法によって優先順位を設け、一つの状態を選ぶ。このように、経路探索部12は、複数の次状態候補の演算と、採用する状態候補の選択をゴール状態に至るまで繰り返すことで、各搬送物150の経路を設定する。以上のようにエースターアルゴリズムを用いる場合、前述のコストは各搬送物150の推定コストで示される。 FIG. 6 illustrates state candidates B1 to B4 listed in the "Successive state" column as states that are one step ahead of the "next state." The route search unit 12 calculates state evaluation values for each state candidate B1 to B4. Note that the route search unit 12 calculates the value of the heuristic function again for each state candidate B1 to B3. Here, the state evaluation values of state candidates B3 and B4 are the smallest. If the state evaluation values are the same, the route search unit 12 sets priorities and selects one state, for example, by the method described below. In this manner, the route search unit 12 sets the route for each transported object 150 by repeating the calculation of a plurality of next state candidates and the selection of the adopted state candidate until the goal state is reached. When using the Aster algorithm as described above, the above-mentioned cost is represented by the estimated cost of each conveyed object 150.

ここで、経路探索において、所定個数の搬送物150の配置状態の候補として同率に評価される候補が複数表れた場合、経路探索部12は、仕分け部31中の搬送物150が少ない方の候補を優先する。上述のように、最小の状態評価値が、複数の状態候補に表れた場合、経路探索部12は、当該優先順位付けの処理を行う。図6の「次々状態」に示す例では、状態候補B3,B4の状態評価値が採用となる。このうち、状態候補B3では、一階への搬送物150及び二階への搬送物150は両方とも目的地へ到達していない。すなわち、仕分け部31に搬送物150が二つ存在する。一方、状態候補B4では、二階への搬送物150は目的地へ到達している。すなわち、仕分け部31に搬送物150が一つだけ存在している。この場合、経路探索部12は、仕分け部31内の搬送物150が少ない方の状態候補B4を優先して選択する。 Here, in the route search, if a plurality of candidates that are equally evaluated as candidates for the arrangement state of the predetermined number of transported objects 150 appear, the route searching section 12 selects the candidate with fewer transported objects 150 in the sorting section 31. Prioritize. As described above, when the minimum state evaluation value appears in a plurality of state candidates, the route search unit 12 performs the priority ranking process. In the example shown in "one state after another" in FIG. 6, the state evaluation values of state candidates B3 and B4 are adopted. Among these, in state candidate B3, both the transported object 150 to the first floor and the transported object 150 to the second floor have not reached their destinations. That is, there are two conveyance items 150 in the sorting section 31. On the other hand, in state candidate B4, the object 150 to be transported to the second floor has reached its destination. That is, only one conveyed object 150 exists in the sorting section 31. In this case, the route search unit 12 preferentially selects the state candidate B4 in which the number of transported objects 150 in the sorting unit 31 is smaller.

また、経路探索において、所定個数の搬送物150の配置状態の候補として同率に評価される候補が複数表れた場合、各搬送物150が目的地へ到達するまでの見積値の合計値を演算し、合計値が少ない候補を優先してよい。例えば、図7に示すように、経路探索部12は、探索対象となる搬送物150の全てについて、見積値を演算する。図7には、各搬送物150の見積値が示されている。なお、図7に示される例では、見積値として、搬送物150が目的地まで到達するのに必要なステップ数が採用される。ここでは、搬出コンベア23の探索ノードのうち、搬出口32より更に一段進んだ探索ノードまで到達するまでのステップ数が見積値として採用される。 In addition, in the route search, if multiple candidates that are equally evaluated as candidates for the arrangement state of a predetermined number of transported objects 150 appear, the total value of the estimated value until each transported object 150 reaches the destination is calculated. , candidates with a smaller total value may be prioritized. For example, as shown in FIG. 7, the route search unit 12 calculates estimated values for all the objects 150 to be searched. FIG. 7 shows the estimated value of each transported object 150. Note that in the example shown in FIG. 7, the number of steps required for the transported object 150 to reach the destination is used as the estimated value. Here, among the search nodes of the carry-out conveyor 23, the number of steps required to reach a search node that is one step further from the carry-out exit 32 is employed as the estimated value.

図4に戻り、最適化テーブル取得部13は、搬送物150の配置状態に対する最適な経路探索情報が予め準備された最適化テーブルを取得するユニットである。このような最適化テーブルは、記憶部3に記憶されている。従って、最適化テーブル取得部13は、記憶部3から最適化テーブルを読み出して取得する。 Returning to FIG. 4, the optimization table acquisition unit 13 is a unit that acquires an optimization table in which optimal route search information for the arrangement state of the transported object 150 is prepared in advance. Such an optimization table is stored in the storage unit 3. Therefore, the optimization table acquisition unit 13 reads and acquires the optimization table from the storage unit 3.

例えば、図8の上段側に示すように、仕分け装置1は、事前処理として、配置状態S1に示すような配列の搬送物150を、前述のようなエースターアルゴリズムを用いた探索方法によって、最適な経路を探索する。仕分け装置1は、このような最適な経路を最適解AS1として最適化テーブルに保存する。仕分け装置1は、その他にも様々な配置状態に対する最適解を求めると共に、最適化テーブルに保存する。そして、図8の下段側に示すように、経路探索部12は、搬送物150の配置状態を最適化テーブルへ問い合わせ、当該最適化テーブルから返送された最適解に基づいて、経路探索を行う。すなわち、経路探索部12が、運用時において配置状態S1に対する経路を探索する場合、配置状態S1に対応する最適解がないかを最適化テーブルに問い合わせる。最適化テーブルには、配置状態S1に対応する最適解AS1が保存されている。従って、最適化テーブルは、保存しておいた最適解AS1を返送する。 For example, as shown in the upper part of FIG. 8, the sorting device 1, as a pre-processing, optimally stores the items 150 arranged in the arrangement state S1 using the search method using the Aster algorithm as described above. Search for a route. The sorting device 1 stores such an optimal route as the optimal solution AS1 in the optimization table. The sorting device 1 also finds optimal solutions for various other arrangement states and stores them in an optimization table. Then, as shown in the lower part of FIG. 8, the route search unit 12 queries the optimization table about the arrangement state of the transported object 150, and performs route search based on the optimal solution returned from the optimization table. That is, when the route search unit 12 searches for a route for the placement state S1 during operation, it queries the optimization table as to whether there is an optimal solution corresponding to the placement state S1. The optimization table stores an optimal solution AS1 corresponding to the placement state S1. Therefore, the optimization table returns the saved optimal solution AS1.

最適化テーブルは、図9に示すように、スタート状態からゴール状態の全ての経路をまとまったパターン情報として保存してもよいが、図9に示すように、ある配置状態に対して一ステップ先の最適経路を保存してもよい。この場合、経路探索部12は、スタート状態からゴール状態に至るまでの間、最適化テーブル(逆順テーブル)に再帰的に問い合わせをしてよい。例えば、経路探索部12が配置状態S1について最適化テーブルに問い合わせたら、最適化テーブルは、一ステップ先の配置状態S2を最適解AS1として返送する。次に、経路探索部12は配置状態S1について最適化テーブルに問い合わせ、最適化テーブルは、一ステップ先の配置状態S3を最適解AS2として返送する。経路探索部12は、このような問い合わせを繰り返すことで、ゴール状態までの経路を取得する。 The optimization table may store all routes from the start state to the goal state as a set of pattern information, as shown in FIG. 9, but as shown in FIG. The optimal route may be saved. In this case, the route search unit 12 may recursively inquire of the optimization table (reverse order table) from the start state to the goal state. For example, when the route search unit 12 inquires of the optimization table regarding the placement state S1, the optimization table returns the placement state S2 one step ahead as the optimal solution AS1. Next, the route search unit 12 queries the optimization table regarding the placement state S1, and the optimization table returns the placement state S3 one step ahead as the optimal solution AS2. The route search unit 12 obtains a route to the goal state by repeating such inquiries.

上述のような一ステップ先の配置状態を保存したデータとして、図10のようなデータベースが例示される。図10の最適化テーブルは、経路探索の範囲内に最大四つ(n=4)の搬送物150が存在する配置状態のパターンに対し、一ステップ先の最適解に係る配置状態が保存されている。このようなパターンとして、760600個のパターンのデータが保存されている。 A database as shown in FIG. 10 is exemplified as data storing the arrangement state one step ahead as described above. The optimization table in FIG. 10 stores the placement state related to the optimal solution one step ahead for a placement state pattern in which there are a maximum of four (n = 4) transported objects 150 within the route search range. There is. As such patterns, data of 760,600 patterns are stored.

ここで、図10の最適化テーブルには、「添え字値」の項目にて、各配置状態に対して添え字値が紐付けられている。このように、最適化テーブルは、搬送物150の搬送状態に対して予め規則化された添え字値が紐付けられたハッシュテーブルを有していてよい。例えば、図11に示すように、経路探索の対象範囲となる探索ノードに対して、探索ノード番号を設定する(1~15)。また、16番目の探索ノード番号として、垂直搬送機の昇降状態(搬送棚22Aが下がった状態である、搬送棚22Bが下がった状態であるか)が割り当てられている。探索ノード番号と各探索ノードに存在する搬送物150の目的地の階数とに基づき、数字の列Xが設定される。探索ノード番号は、列Xの列数に対応する。また、搬送物150の目的地の階数は列Xに挿入される数字に対応する。例えば、探索ノード番号1,2,3,4に対して、「目標階数1,3,4,2」の搬送物150が存在している。従って、列Xの1,2,3,4列目には、「1,3,4,2」という数字が挿入される。なお、搬送物150が存在していない場合は「0」が挿入される。経路探索部12は、このような列Xに対して任意の行を掛け合わせることで、添え字値を算出する。なお、添え字値をどのように計算するかは特に限定されず、所定の規則に従って算出可能であればよい。 Here, in the optimization table of FIG. 10, a subscript value is associated with each arrangement state in the "subscript value" item. In this way, the optimization table may include a hash table in which subscript values that are regularized in advance are linked to the conveyance state of the conveyed object 150. For example, as shown in FIG. 11, search node numbers are set for the search nodes that are the target range of route search (1 to 15). Further, as the 16th search node number, the ascending and descending state of the vertical transport machine (whether the transport shelf 22A is in a lowered state or the transport shelf 22B is in a lowered state) is assigned. A string of numbers X is set based on the search node number and the floor number of the destination of the transported object 150 existing at each search node. The search node number corresponds to the number of columns in column X. Further, the floor number of the destination of the transported object 150 corresponds to the number inserted in column X. For example, for search node numbers 1, 2, 3, and 4, objects 150 with "target floors 1, 3, 4, and 2" exist. Therefore, the numbers "1, 3, 4, 2" are inserted in the 1st, 2nd, 3rd, and 4th columns of column X. Note that if the conveyed object 150 does not exist, "0" is inserted. The route search unit 12 calculates a subscript value by multiplying such a column X by an arbitrary row. Note that there is no particular limitation on how to calculate the subscript value, as long as it can be calculated according to predetermined rules.

例えば、図12に示すように、経路探索部12は、現在の配置状態に対応する添え字値を演算し、演算した添え字値を用いてハッシュテーブルを参照する。これにより、経路探索部12は、最適解に係る配置状態に対応する添え字値をハッシュテーブルから取得する。そして、経路探索部12は、取得した添え字値を逆算することで、最適解としての配置状態を算出する。 For example, as shown in FIG. 12, the route search unit 12 calculates a subscript value corresponding to the current arrangement state, and refers to a hash table using the calculated subscript value. Thereby, the route search unit 12 obtains the subscript value corresponding to the arrangement state related to the optimal solution from the hash table. Then, the route search unit 12 calculates the arrangement state as the optimal solution by back-calculating the obtained subscript value.

図10に示すように、最適化テーブルには、ゴール状態へ到達するまでの残りステップ数も保存されている。この残りステップは、上述のヒューリスティック関数の値として用いることができる。この場合、経路探索部12は、ある配置状態から次の配置状態の経路探索を行うときに、最適解を最適化テーブルから取得すると共に、残りステップヒューリスティック関数の値として取得することができる。例えば、図13に示すように、経路探索部12は、最適化テーブルから残りステップを取得できなかった場合は、残りのステップをカウントして、ヒューリスティック関数の値を「4」と算出する。しかし、探索の演算をそのまま継続すると、実際には「4」でゴールに到達できないことが分かり、実際のヒューリスティック関数の値は「5」が正しいということが事後的に分かることもある。一方、最適化テーブルは、実際の経路探索に基づいて作成されたものであるので、このような正しい残りステップを保存することができる。従って、経路探索部12は、最適化テーブルに問い合わせることで、正しいヒューリスティック関数の値「5」を直ちに取得することができる。 As shown in FIG. 10, the optimization table also stores the number of remaining steps until reaching the goal state. This remaining step can be used as the value of the heuristic function described above. In this case, when performing a route search from one placement state to the next placement state, the route search unit 12 can obtain the optimal solution from the optimization table and also obtain it as the value of the remaining step heuristic function. For example, as shown in FIG. 13, if the route search unit 12 cannot obtain the remaining steps from the optimization table, it counts the remaining steps and calculates the value of the heuristic function as "4". However, if the search operation is continued as it is, it may be found that the goal cannot actually be reached with "4", and it may be found ex post that the actual value of the heuristic function is "5". On the other hand, since the optimization table is created based on actual route searching, it is possible to store such correct remaining steps. Therefore, the route search unit 12 can immediately obtain the correct heuristic function value "5" by querying the optimization table.

ここで、図10に示す例では、経路探索の対象範囲内において、最大四つの搬送物150の配置状態について、最適解が保存されていた。これに対し、経路探索部12が四つより多い搬送物150の経路を探索しようとすると、最適化テーブルを用いて経路探索ができなくなってしまう。一方、搬入コンベアからは、連続的に新しい搬送物150が搬入される場合もある。従って、図14に示すように、経路探索部12は、搬出口32側の領域にて、設定値(n=4)以下の個数の搬送物150の配置状態を最適化テーブルへ問い合わせる場合、搬入口30からの新たな搬送物150の搬入に制限を設けてよい。図14(a)に示すように、経路探索部12は、搬出口32に近い順から四個のみの搬送物150(領域E1参照)についての配置状態を取り出し、最適化テーブルに問い合わせる。このとき、五個目の搬送物150(領域E2参照)は考慮されない。図14(b)に示すように、一つステップが進むと、経路探索部12は、四個のみの搬送物150(領域E1参照)の新しい配置状態について、最適化テーブルに問い合わせる。このとき、五個目の搬送物150は、配置状態として考慮はしないが、搬入コンベア21上の位置は進めてもよい。しかし、図14(c)に示すように、制御部10は、五個目の搬送物150が、搬入コンベア21の最下流の探索ノードに配置されないように、搬入を制限する。当該位置における検索ノードは、四個の配置状態の最適解として、搬送物150が配置される可能性がある位置であるためである。一方、一つの搬送物150が目的地に到達したら、図14(d)に示すように、経路探索部12は、最適化テーブルの問い合わせ対象となる四個の搬送物150の組み合わせを更新する(領域E1参照)。 Here, in the example shown in FIG. 10, optimal solutions are stored for the arrangement states of up to four conveyance objects 150 within the route search target range. On the other hand, if the route search unit 12 tries to search for routes for more than four objects 150, the route search cannot be performed using the optimization table. On the other hand, new objects 150 may be continuously carried in from the carry-in conveyor. Therefore, as shown in FIG. 14, when the route search unit 12 inquires of the optimization table about the arrangement state of the transported objects 150 whose number is equal to or less than the set value (n=4) in the region on the side of the transport exit 32, the route search unit 12 Restrictions may be placed on the introduction of new objects 150 from the port 30. As shown in FIG. 14A, the route search unit 12 extracts the arrangement state of only four transported objects 150 (see area E1) in the order of their proximity to the exit 32, and queries the optimization table. At this time, the fifth conveyed object 150 (see area E2) is not considered. As shown in FIG. 14(b), when one step progresses, the route search unit 12 queries the optimization table regarding the new arrangement state of only four conveyed objects 150 (see area E1). At this time, although the fifth conveyance object 150 is not considered as an arrangement state, its position on the carry-in conveyor 21 may be advanced. However, as shown in FIG. 14C, the control unit 10 restricts the carry-in so that the fifth conveyed object 150 is not placed at the most downstream search node of the carry-in conveyor 21. This is because the search node at this position is a position where the transported object 150 may be placed as the optimal solution among the four placement states. On the other hand, when one transported object 150 reaches its destination, as shown in FIG. (see area E1).

図15を参照して、仕分け装置1の制御部10の処理内容の一例について説明する。図15に示すように、経路探索部12は、経路探索対象物として、搬出口32付近の所定個数の搬送物150を特定する(ステップS10)。次に、経路探索部12は、次の状態候補を複数演算する(ステップS20)。次に、経路探索部12は、各状態候補について、所定個数の搬送物150の推定コストを演算して比較することで、ヒューリスティック関数の値を設定する(ステップS30)。そして、経路探索部12は、ヒューリスティック関数の値を用いて各状態候補の評価を行うと共に、優先順位が最も高いものを経路として採用する(ステップS40)。次に、経路探索部12は、特定した搬送物150が全て目的地に到達したか判定する(ステップS50)。S50において、到達していないと判定したら、ステップS20から処理が繰り返される。S50において、到達したと判定されたら、図15に示す処理を終了する。次の搬送物150が搬入されたら、再び図15の処理が実行される。 An example of the processing content of the control unit 10 of the sorting device 1 will be described with reference to FIG. 15. As shown in FIG. 15, the route search unit 12 identifies a predetermined number of transported objects 150 near the exit 32 as route search objects (step S10). Next, the route search unit 12 calculates a plurality of next state candidates (step S20). Next, the route search unit 12 sets the value of the heuristic function by calculating and comparing the estimated costs of a predetermined number of objects 150 for each state candidate (step S30). Then, the route search unit 12 evaluates each state candidate using the value of the heuristic function, and selects the one with the highest priority as the route (step S40). Next, the route search unit 12 determines whether all of the identified conveyed objects 150 have reached their destinations (step S50). If it is determined in S50 that it has not been reached, the process is repeated from step S20. If it is determined in S50 that the point has been reached, the process shown in FIG. 15 is ended. When the next conveyed object 150 is carried in, the process of FIG. 15 is executed again.

次に、本実施形態に係る仕分け装置1の作用・効果について説明する。 Next, the functions and effects of the sorting device 1 according to this embodiment will be explained.

制御部10の経路探索部12は、所定個数の搬送物を仕分け部31で仕分けをするときに、少なくとも搬入口30、及び仕分け部31の各部位を探索ノードとして、最短経路探索手法を用いて各搬送物の経路を探索する。このように、経路探索部12が、最短経路探索手法を用いて各搬送物の経路を探索することで、適切な経路を設定することが可能になる。ここで、経路探索部12は、他の搬送物による影響がないと仮定した場合における、各搬送物が目的地へ移動するのに必要なコストをそれぞれ演算する。これにより、経路探索部12は、複数の搬送物を同時に仕分ける場合に、どの搬送物が目的地まで遠いかを把握することが可能となる。そして、経路探索部12は、所定個数の搬送物の中から、コストが最も大きくなる搬送物を選択すると共に当該搬送物のコストを基準値とし、選択した搬送物以外についても、基準値を適用して経路探索を行う。これにより、経路探索部12は、複数の搬送物を同時に仕分ける上で、時間を短縮できる経路を設定することができる。以上より、適切な経路にて搬送物の仕分けを行うことができる。 The route search unit 12 of the control unit 10 uses a shortest route search method using at least the loading port 30 and each part of the sorting unit 31 as search nodes when sorting a predetermined number of conveyed items in the sorting unit 31. Search the route of each conveyed item. In this way, the route search unit 12 searches for the route of each conveyance object using the shortest route search method, thereby making it possible to set an appropriate route. Here, the route search unit 12 calculates the cost required for each transported object to move to its destination, assuming that there is no influence from other transported objects. This makes it possible for the route search unit 12 to know which object is far from the destination when sorting a plurality of objects at the same time. Then, the route search unit 12 selects the transport item with the highest cost from among the predetermined number of transport items, uses the cost of the transport item as a reference value, and applies the reference value to other transport items than the selected transport items. to search for a route. Thereby, the route search unit 12 can set a route that can save time when sorting a plurality of conveyed items at the same time. As described above, it is possible to sort the conveyed items along appropriate routes.

経路探索部12は、最短経路探索手法としてエースターアルゴリズムを用い、コストとして、各搬送物が目的地まで到達するまでにかかるステップ数に基づく推定コストを演算し、所定個数の搬送物の中から、推定コストが最も大きくなる搬送物を選択すると共に当該搬送物の推定コストをヒューリスティック関数の値とし、選択した搬送物以外についても、ヒューリスティック関数の値を適用して経路探索を行ってよい。エースターアルゴリズムは、最適解が必ず見つかる最短経路探索方法として、経路探索において有効に用いられている方法である。経路探索部12が、このようなエースターアルゴリズムを用いことで、最適な経路を探索することができる。 The route search unit 12 uses the Aster algorithm as the shortest route search method, calculates the estimated cost based on the number of steps it takes for each transported object to reach its destination, and selects a route from among a predetermined number of transported objects. , the transport object with the largest estimated cost may be selected, the estimated cost of the transport object may be set as the value of the heuristic function, and the route search may be performed by applying the value of the heuristic function to objects other than the selected transport object. The Aster algorithm is a method that is effectively used in route searching as a method for searching for the shortest route that always finds the optimal solution. The route search unit 12 can search for an optimal route by using such an Aster algorithm.

なお、ヒューリスティック関数の値を0とすることでも最適解が求まる。これは幅優先探索と同じであり、短いステップで動作できるパターンを優先して調べていくため、莫大な時間がかかるが、初めに見つけた解が最短ステップの解、すなわち最適解となる。最適解を求めるために寄与するのはコストを真の値より低く見積もることである。一方で、本実施形態のように、最も大きなコストを基準値に選ぶことは最適解導出時間に寄与する。真の値より低くかつ近い値を求めていくことがエースターアルゴリズムでは重要となる。その中で、本実施形態では、この条件を満たす単純で強力な知識であると言える。 Note that the optimal solution can also be found by setting the value of the heuristic function to 0. This is the same as breadth-first search, and it takes a huge amount of time because it prioritizes and examines patterns that can operate in short steps, but the solution found first becomes the solution with the shortest steps, that is, the optimal solution. What contributes to finding the optimal solution is to estimate the cost below its true value. On the other hand, selecting the largest cost as the reference value as in this embodiment contributes to the optimal solution derivation time. In the Aster algorithm, it is important to find a value that is lower and closer to the true value. Among them, this embodiment can be said to be simple and powerful knowledge that satisfies this condition.

経路探索部12は、所定タイミングにおける各搬送物の配置状態から、次のタイミングに発生し得る各搬送物の次状態候補を複数演算し、複数の次状態候補に対して、動作ステップ数と基準値との和による状態評価値を演算し、複数の次状態候補の中から、状態評価値が最も小さくなるものを経路探索に採用してよい。この場合、経路探索部12は、状態評価値を比較することで、複数の次状態候補の中から、適切なものを採用することができる。 The route search unit 12 calculates a plurality of next state candidates for each conveyed object that may occur at the next timing from the arrangement state of each conveyed object at a predetermined timing, and calculates the number of operation steps and criteria for the plurality of next state candidates. A state evaluation value may be calculated based on the sum of the state evaluation value and the next state candidate, and the one with the smallest state evaluation value may be selected from among the plurality of next state candidates for the route search. In this case, the route search unit 12 can select an appropriate next state candidate from among the plurality of next state candidates by comparing the state evaluation values.

経路探索において、所定個数の搬送物の配置状態の候補として同率に評価される候補が複数表れた場合、経路探索部12は、仕分け部中の搬送物が少ない方の候補を優先してよい。先に目的地に搬送物が到達した候補を選ぶことで、その後の経路の探索がやりやすくなるため、経路探索部12は、そのような候補を優先することができる。 In the route search, if a plurality of candidates that are equally evaluated as candidates for the arrangement state of the predetermined number of transported objects appear, the route search section 12 may prioritize the candidate with fewer transported objects in the sorting section. By selecting a candidate whose conveyed object reaches its destination first, it becomes easier to search for a subsequent route, so the route search unit 12 can give priority to such candidates.

経路探索において、所定個数の搬送物の配置状態の候補として同率に評価される候補が複数表れた場合、経路探索部12は、各搬送物が前記目的地へ到達するまでの見積値の合計値を演算し、合計値が少ない候補を優先してよい。この場合、経路探索部12は、複数の搬送物の目的地までの遠さを全体的に考慮した候補を優先することができる。 In the route search, if a plurality of candidates are evaluated at the same rate as candidates for the arrangement state of the predetermined number of transported objects, the route search unit 12 calculates the total value of the estimated value until each transported object reaches the destination. , and give priority to candidates with a smaller total value. In this case, the route search unit 12 can give priority to candidates that take into consideration overall distances to the destinations of the plurality of conveyance items.

制御部は、搬送物の配置状態に対する最適な経路探索情報が予め準備された最適化テーブルを取得する最適化テーブル取得部を備え、経路探索部12は、搬送物の配置状態を最適化テーブルへ問い合わせ、当該最適化テーブルから返送された最適解に基づいて、経路探索を行ってよい。この場合、経路探索部12は、準備された最適化テーブルを用いることで、速やかに経路を探索できる。 The control unit includes an optimization table acquisition unit that acquires an optimization table in which optimal route search information for the arrangement state of the transported object is prepared in advance, and the route search unit 12 inputs the arrangement state of the transported object into the optimization table. A route search may be performed based on the inquiry and the optimal solution returned from the optimization table. In this case, the route search unit 12 can quickly search for a route by using the prepared optimization table.

最適化テーブルは、搬送物の搬送状態に対して予め規則化された添え字値が紐付けられたハッシュテーブルを有し、経路探索部12は、搬送物の配置状態に対応する添え字値を演算し、演算した添え字値を用いてハッシュテーブルを参照してよい。この場合、経路探索部12は、添え字値を用いることで、処理時間を短縮して最適化テーブルから、適切な経路を取得できる。 The optimization table has a hash table in which subscript values that are regularized in advance are linked to the transportation state of the transported object, and the route search unit 12 calculates the subscript value that corresponds to the arrangement state of the transported object. The hash table may be referenced using the calculated subscript value. In this case, by using the subscript value, the route search unit 12 can shorten the processing time and obtain an appropriate route from the optimization table.

経路探索部12が、搬出口側の範囲において、設定値以下の個数の搬送物の配置状態を最適化テーブルへ問い合わせる場合、搬入口からの新たな搬送物の搬入に制限を設けてよい。この場合、経路探索部12は、搬入手段から新たな搬送物が搬入されてても、問い合わせ対象の搬送物の個数を設定値以下に抑制できるので、最適化テーブルを利用することができる。 When the route search unit 12 inquires of the optimization table about the arrangement state of objects to be transported whose number is equal to or less than a set value in the area on the exit side, a restriction may be set on the introduction of new objects to be transported from the entrance. In this case, the route search unit 12 can use the optimization table because it can suppress the number of objects to be queried to below the set value even if a new object is brought in from the carrying means.

本発明は、上述の実施形態に限定されない。 The invention is not limited to the embodiments described above.

例えば、仕分け装置が適用されるシステムは、図1に示す倉庫システムに限定されない。また、仕分け部の搬送機は、図2に示すような交互に上下動するような一対の収容棚を有するタイプのものでなくてよい。例えば、ロータリー式の搬送機(収容棚が一段ずつ一定方向に周回移動するとともに、収容棚が周回移動しない際には、搬送物が収容棚間で移動可能な搬送機)を採用してよい。 For example, the system to which the sorting device is applied is not limited to the warehouse system shown in FIG. Furthermore, the conveyance machine in the sorting section does not have to be of the type shown in FIG. 2, which has a pair of storage shelves that move up and down alternately. For example, a rotary type conveyance machine (a conveyance machine in which each storage shelf rotates one stage at a time in a fixed direction, and when the storage shelf does not rotate, the transported object can be moved between the storage shelves) may be used.

また、最短経路探索手法としてエースターアルゴリズムを用いたが、手法は限定されず、例えば、ダイクストラ法に代表される様々な探索アルゴリズムを用いてよい。 Further, although the Aster algorithm is used as the shortest route search method, the method is not limited, and various search algorithms such as Dijkstra's algorithm may be used.

本実施形態では、搬入コンベア21から入庫される搬送物150を各階の搬出コンベア23に移動させる形態に関して説明したが、各階のコンベアから出庫される搬送物150を搬出コンベア121に移動させる形態に、本発明の仕分け装置の処理が適用されてもよい。 In the present embodiment, the embodiment has been described in which the conveyed objects 150 that are stored from the carry-in conveyor 21 are moved to the carry-out conveyor 23 on each floor. The processing of the sorting device of the present invention may be applied.

また、搬出コンベアや搬出口は4段に限らず、2段や3段、5段より多くてもよい。また搬入口も1つではなく複数設けられていてもよい。 In addition, the number of delivery conveyors and delivery ports is not limited to four stages, and may be more than two, three, or five stages. Moreover, there may be a plurality of entrances instead of one.

1…仕分け装置、10…制御部、12…経路探索部、21…搬入コンベア(搬入手段)、22…搬送機、23…搬出コンベア(搬出手段)、30…搬入口、31・・仕分け部、32…搬出口。 DESCRIPTION OF SYMBOLS 1... Sorting device, 10... Control unit, 12... Route search unit, 21... Carrying-in conveyor (carrying-in means), 22... Conveying machine, 23... Carrying-out conveyor (carrying-out means), 30... Carrying-in entrance, 31... Sorting part, 32...Export exit.

Claims (8)

搬入手段における搬入口と、
水平方向移動手段を有する搬送機を少なくとも含む仕分け部と、
搬出手段における搬出口と、
前記搬入口から搬入された搬送物を前記仕分け部で仕分けして前記搬出口から搬出する制御を行う制御部と、を備える仕分け装置であって、
前記制御部は、所定個数の前記搬送物を前記仕分け部で仕分けをするときに、少なくとも前記搬入口、及び前記仕分け部の各部位を探索ノードとして、最短経路探索手法を用いて各搬送物の経路を探索する、経路探索部を備え、
前記経路探索部は、
他の搬送物による影響がないと仮定した場合における、各搬送物が目的地へ移動するのに必要なコストをそれぞれ演算し、
所定個数の前記搬送物の中から、前記コストが最も大きくなる搬送物を選択すると共に当該搬送物のコストを基準値とし、選択した搬送物以外についても、前記基準値を適用して経路探索を行う、仕分け装置。
A loading port in the loading means;
a sorting section including at least a conveyor having a horizontal movement means;
an exit in the transport means;
A sorting device comprising: a control unit that controls the sorting unit to sort conveyed items brought in from the carry-in port and carry them out from the carry-out port,
When the predetermined number of the objects to be transported are sorted by the sorting section, the control section uses a shortest path search method to sort each object by using at least the entrance and each part of the sorting section as search nodes. Equipped with a route search section that searches for routes,
The route search unit includes:
Calculate the cost required for each conveyance object to move to its destination, assuming that there is no influence from other conveyance objects,
From among the predetermined number of transported objects, the transported object with the highest cost is selected, and the cost of the transported object is used as a reference value, and the route search is performed for other transported objects by applying the reference value. sorting equipment.
前記経路探索部は、前記最短経路探索手法としてエースターアルゴリズムを用い、
前記コストとして、各搬送物が前記目的地に到達するまでにかかるステップ数に基づく推定コストを演算し、
所定個数の前記搬送物の中から、前記推定コストが最も大きくなる搬送物を選択すると共に当該搬送物の前記推定コストをヒューリスティック関数の値とし、選択した搬送物以外についても、前記ヒューリスティック関数の値を適用して経路探索を行う、請求項1に記載の仕分け装置。
The route search unit uses an Aster algorithm as the shortest route search method,
As the cost, calculate an estimated cost based on the number of steps it takes for each conveyed object to reach the destination,
From among the predetermined number of transported objects, the transported object with the largest estimated cost is selected, and the estimated cost of the transported object is set as the value of a heuristic function, and the value of the heuristic function is also calculated for other transported objects than the selected transported objects. The sorting device according to claim 1, wherein the sorting device performs route searching by applying.
前記経路探索部は、
所定タイミングにおける各前記搬送物の配置状態から、次のタイミングに発生し得る各前記搬送物の次状態候補を複数演算し、
複数の前記次状態候補に対して、動作ステップ数と前記基準値との和による状態評価値を演算し、
複数の前記次状態候補の中から、前記状態評価値が最も小さくなるものを経路探索に採用する、請求項1又は2に記載の仕分け装置。
The route search unit includes:
calculating a plurality of candidates for the next state of each of the conveyed objects that may occur at the next timing from the arrangement state of each of the conveyed objects at a predetermined timing;
calculating a state evaluation value based on the sum of the number of motion steps and the reference value for the plurality of next state candidates;
The sorting device according to claim 1 or 2, wherein, from among the plurality of next state candidates, the one with the smallest state evaluation value is adopted for route searching.
経路探索において、所定個数の前記搬送物の配置状態の候補として同率に評価される候補が複数表れた場合、前記経路探索部は、前記仕分け部中の前記搬送物が少ない方の候補を優先する、請求項1~3の何れか一項に記載の仕分け装置。 In the route search, if a plurality of candidates that are equally evaluated as candidates for the arrangement state of the predetermined number of the objects to be transported appear, the route search section gives priority to the candidate with fewer objects in the sorting section. , the sorting device according to any one of claims 1 to 3. 経路探索において、所定個数の前記搬送物の配置状態の候補として同率に評価される候補が複数表れた場合、前記経路探索部は、各前記搬送物が前記目的地へ到達するまでの見積値の合計値を演算し、前記合計値が少ない候補を優先する、請求項1~4の何れか一項に記載の仕分け装置。 In the route search, if a plurality of candidates are evaluated at the same rate as candidates for the arrangement state of the predetermined number of the conveyed objects, the route search section calculates the estimated value of the time it will take for each of the conveyed objects to reach the destination. The sorting device according to any one of claims 1 to 4, which calculates a total value and prioritizes candidates with a smaller total value. 前記制御部は、前記搬送物の配置状態に対する最適な経路探索情報が予め準備された最適化テーブルを取得する最適化テーブル取得部を備え、
前記経路探索部は、前記搬送物の配置状態を前記最適化テーブルへ問い合わせ、当該最適化テーブルから返送された最適解に基づいて、経路探索を行う、請求項1~5の何れか一項に記載の仕分け装置。
The control unit includes an optimization table acquisition unit that acquires an optimization table in which optimal route search information for the arrangement state of the transported object is prepared in advance,
According to any one of claims 1 to 5, the route search unit queries the optimization table about the arrangement state of the conveyed object and performs the route search based on the optimal solution returned from the optimization table. Sorting equipment as described.
前記最適化テーブルは、前記搬送物の搬送状態に対して予め規則化された添え字値が紐付けられたハッシュテーブルを有し、
前記経路探索部は、前記搬送物の配置状態に対応する添え字値を演算し、演算した添え字値を用いて前記ハッシュテーブルを参照する、請求項6に記載の仕分け装置。
The optimization table has a hash table in which subscript values that are regularized in advance are linked to the conveyance state of the conveyed object,
7. The sorting device according to claim 6, wherein the route search unit calculates a subscript value corresponding to the arrangement state of the conveyed items, and refers to the hash table using the calculated subscript value.
前記経路探索部が、前記搬出口側の範囲において、設定値以下の個数の前記搬送物の配置状態を前記最適化テーブルへ問い合わせる場合、前記搬入口からの新たな搬送物の搬入に制限を設ける、請求項6または7に記載の仕分け装置。 When the route search unit inquires of the optimization table about the arrangement state of the objects to be transported, the number of which is equal to or less than a set value in the range on the carry-out port side, a limit is placed on the introduction of new objects from the carry-in port. , The sorting device according to claim 6 or 7.
JP2021049715A 2021-03-24 2021-03-24 sorting equipment Active JP7426672B2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2021049715A JP7426672B2 (en) 2021-03-24 2021-03-24 sorting equipment

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2021049715A JP7426672B2 (en) 2021-03-24 2021-03-24 sorting equipment

Publications (2)

Publication Number Publication Date
JP2022148146A JP2022148146A (en) 2022-10-06
JP7426672B2 true JP7426672B2 (en) 2024-02-02

Family

ID=83463503

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2021049715A Active JP7426672B2 (en) 2021-03-24 2021-03-24 sorting equipment

Country Status (1)

Country Link
JP (1) JP7426672B2 (en)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2019013432A (en) * 2017-07-06 2019-01-31 株式会社三洋物産 Game machine
JP2019013433A (en) * 2017-07-06 2019-01-31 株式会社三洋物産 Game machine

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001241959A (en) 2000-03-02 2001-09-07 Sumitomo Electric Ind Ltd Decision method for route search condition in road map
JP2009020773A (en) 2007-07-13 2009-01-29 Asyst Technologies Japan Inc Route searching system and method, transportation system, and computer program
JP2015059872A (en) 2013-09-19 2015-03-30 ヤフー株式会社 Route search device, route search method, route search system, and route search program
JP2016166078A (en) 2015-03-10 2016-09-15 村田機械株式会社 Elevating conveying device
JP2020060563A (en) 2018-10-12 2020-04-16 株式会社日立製作所 Plural vehicle route planning method and plural vehicle route planning system
WO2020090323A1 (en) 2018-11-02 2020-05-07 村田機械株式会社 Conveyor system
CN111126705A (en) 2019-12-25 2020-05-08 北京旷视机器人技术有限公司 Transport path generation method and device for dense warehousing and electronic equipment
US20200338597A1 (en) 2019-04-29 2020-10-29 Amazon Technologies, Inc. Automated Modular System For Sorting Items

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001241959A (en) 2000-03-02 2001-09-07 Sumitomo Electric Ind Ltd Decision method for route search condition in road map
JP2009020773A (en) 2007-07-13 2009-01-29 Asyst Technologies Japan Inc Route searching system and method, transportation system, and computer program
JP2015059872A (en) 2013-09-19 2015-03-30 ヤフー株式会社 Route search device, route search method, route search system, and route search program
JP2016166078A (en) 2015-03-10 2016-09-15 村田機械株式会社 Elevating conveying device
JP2020060563A (en) 2018-10-12 2020-04-16 株式会社日立製作所 Plural vehicle route planning method and plural vehicle route planning system
WO2020090323A1 (en) 2018-11-02 2020-05-07 村田機械株式会社 Conveyor system
US20200338597A1 (en) 2019-04-29 2020-10-29 Amazon Technologies, Inc. Automated Modular System For Sorting Items
CN111126705A (en) 2019-12-25 2020-05-08 北京旷视机器人技术有限公司 Transport path generation method and device for dense warehousing and electronic equipment

Also Published As

Publication number Publication date
JP2022148146A (en) 2022-10-06

Similar Documents

Publication Publication Date Title
CN110182527B (en) Warehouse-in and warehouse-out control method and conveying system for shelf array
CN105836356B (en) A kind of intensive warehousing system hybrid optimization dispatching method
US7221998B2 (en) Determining pallet case configurations for placement by a robot
JP7426672B2 (en) sorting equipment
JP6650508B2 (en) Warehouse management system and warehouse management method
CN110182529B (en) Warehouse-in and warehouse-out control method and conveying system for shelf array
CN110182528B (en) Warehouse-in and warehouse-out control method and conveying system for shelf array
US8851818B2 (en) Automatic warehouse and control method thereof
CN110888903B (en) Method and system for automatic continuous carrying operation of crane
Khojasteh et al. A travel time model for order picking systems in automated warehouses
Manda et al. Recent advances in the design and analysis of material handling systems
JP2021165926A (en) Three-dimensional automated warehouse in logistics
JP7521470B2 (en) Sorting device
Öztürkoğlu Effects of varying input and output points on new aisle designs in warehouses
JP7424957B2 (en) Transport vehicle control system, operation management device, and transport route generation method
JP7416287B2 (en) Picking system and picking system control method
US20230092793A1 (en) Article search device and article search method
Kang An order picking algorithm for vertically stacked and top-retrieval storage systems
Öztürkoğlu Investigating the robustness of aisles in a non-traditional unit-load warehouse design: Leverage
WO2023033160A1 (en) Control device for distribution warehouse and control method for distribution warehouse
Shi et al. Travel time analysis of the single and dual command of AS/RS
JP2024104832A (en) Learning device for sorting device, learning method for sorting device, and sorting device
JP2022178587A (en) Logistics warehouse
JP7466152B2 (en) Logistics Warehouse
CN110888904A (en) Intelligent optimization method and system for automatic loading sequence of crane cargos

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20230421

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20231226

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20240109

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20240115

R150 Certificate of patent or registration of utility model

Ref document number: 7426672

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150