JP4915302B2 - Route search system and method, transport system, and computer program - Google Patents
Route search system and method, transport system, and computer program Download PDFInfo
- Publication number
- JP4915302B2 JP4915302B2 JP2007183903A JP2007183903A JP4915302B2 JP 4915302 B2 JP4915302 B2 JP 4915302B2 JP 2007183903 A JP2007183903 A JP 2007183903A JP 2007183903 A JP2007183903 A JP 2007183903A JP 4915302 B2 JP4915302 B2 JP 4915302B2
- Authority
- JP
- Japan
- Prior art keywords
- route
- cost
- sets
- route search
- transport vehicle
- 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
Links
- 238000000034 method Methods 0.000 title claims description 40
- 238000004590 computer program Methods 0.000 title claims description 11
- 238000004364 calculation method Methods 0.000 claims description 37
- 238000003860 storage Methods 0.000 claims description 27
- 238000001514 detection method Methods 0.000 claims description 19
- 230000008569 process Effects 0.000 claims description 16
- 230000006870 function Effects 0.000 claims description 5
- 230000037361 pathway Effects 0.000 claims 1
- 230000032258 transport Effects 0.000 description 74
- 238000004519 manufacturing process Methods 0.000 description 70
- 101000798007 Homo sapiens RAC-gamma serine/threonine-protein kinase Proteins 0.000 description 11
- 102100032314 RAC-gamma serine/threonine-protein kinase Human genes 0.000 description 11
- 208000027744 congestion Diseases 0.000 description 11
- 101000652133 Homo sapiens STE20-like serine/threonine-protein kinase Proteins 0.000 description 10
- 101000880431 Homo sapiens Serine/threonine-protein kinase 4 Proteins 0.000 description 10
- 101000601460 Homo sapiens Serine/threonine-protein kinase Nek4 Proteins 0.000 description 10
- 102100030571 STE20-like serine/threonine-protein kinase Human genes 0.000 description 10
- 102100037629 Serine/threonine-protein kinase 4 Human genes 0.000 description 10
- 239000004065 semiconductor Substances 0.000 description 10
- 102100032306 Aurora kinase B Human genes 0.000 description 9
- 108090000749 Aurora kinase B Proteins 0.000 description 9
- 101000628647 Homo sapiens Serine/threonine-protein kinase 24 Proteins 0.000 description 9
- 101000880439 Homo sapiens Serine/threonine-protein kinase 3 Proteins 0.000 description 9
- 102100026764 Serine/threonine-protein kinase 24 Human genes 0.000 description 9
- 230000008859 change Effects 0.000 description 9
- 238000012546 transfer Methods 0.000 description 7
- 238000003745 diagnosis Methods 0.000 description 6
- 230000005856 abnormality Effects 0.000 description 5
- 230000009467 reduction Effects 0.000 description 4
- 238000012545 processing Methods 0.000 description 3
- 230000004044 response Effects 0.000 description 3
- 239000000758 substrate Substances 0.000 description 3
- 238000012937 correction Methods 0.000 description 2
- 238000010586 diagram Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000012423 maintenance Methods 0.000 description 2
- 230000015572 biosynthetic process Effects 0.000 description 1
- 239000000969 carrier Substances 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 238000005530 etching Methods 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 238000010438 heat treatment Methods 0.000 description 1
- 238000011031 large-scale manufacturing process Methods 0.000 description 1
- 230000007246 mechanism Effects 0.000 description 1
- 238000011084 recovery Methods 0.000 description 1
- 238000005096 rolling process Methods 0.000 description 1
Images
Landscapes
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
Description
本発明は、例えば、半導体装置製造用の各種基板などの被搬送物を、工場内に敷設された軌道上を移動するビークル等の搬送車で搬送する搬送システムにおいて、最適経路を探索する経路探索システム及び方法の技術分野に関する。本発明は更に、かかる搬送システム及びコンピュータをこのような経路探索システムとして機能させるコンピュータプログラムの技術分野に関する。 The present invention provides, for example, a route search that searches for an optimum route in a transport system that transports an object to be transported such as various substrates for manufacturing a semiconductor device with a transport vehicle such as a vehicle that moves on a track laid in a factory. It relates to the technical field of systems and methods. The present invention further relates to the technical field of a computer program that causes such a transport system and a computer to function as such a route search system.
この種の経路探索システムとして、例えば特許文献1には、複数の分岐や合流を含んで張り巡らされた軌道上で出発地点から目的地点までの最適な経路を探索するのに、所謂“ダイクストラ法”を利用した技術が開示されている。この技術では、全経路の各々が、最適経路の候補とされる。該各々の候補を構成するリンクにおける移動コスト(即ち、分岐点や合流点に相当するノード間を走行するのにかかる時間或いは時間に対応する評価値)が、出発地点から目標地点までについて積算される。その後、候補のうち出発地点から目的地点までの移動コストが最小となるものが、最適経路として決定される。
As this type of route search system, for example,
しかしながら、上述の背景技術によれば、作業装置を夫々ノードとし且つ作業装置間に位置する経路部分を夫々リンクとして、移動コストが設定されている。このため、経路探索において取り扱うデータ数が膨大となり、特に近時における経路の複雑高度化或いは作業装置数の増大に伴って、コンピュータにかかる負荷は膨大となるという技術的問題点がある。 However, according to the background art described above, the movement cost is set with the working devices as nodes and the path portions located between the working devices as links. For this reason, the number of data handled in the route search becomes enormous, and there is a technical problem that the load on the computer becomes enormous especially as the route becomes more sophisticated and the number of working devices has increased recently.
本発明は、例えば、上述した問題点に鑑みなされたものであり、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索可能である経路探索システム及び方法、これを備えた搬送システム、並びにコンピュータをこのような経路探索システムとして機能させるコンピュータプログラムを提供することを課題とする。 The present invention has been made in view of the above-described problems, for example, a route search system and method capable of searching for an optimum route while reducing the number of data to be handled and a calculation load, a transport system including the same, and It is an object of the present invention to provide a computer program that causes a computer to function as such a route search system.
本発明の経路探索システムは上記課題を解決するために、被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムであって、前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段とを備える。 In order to solve the above problems, the route search system of the present invention searches for an optimum route when moving a transport vehicle for transporting an object to be transported from a starting point to a target point on the route of the transport vehicle. In the system, each of a plurality of sets including at least one set including a plurality of work devices that perform various processes on the object to be conveyed and are arranged along the route is set as a node. Storage means for storing the movement cost of the transport vehicle, which is defined as a link between the two sets, and connecting the plurality of sets with at least a part of the optimum route based on the stored movement cost. The route search means for searching in units, at least a part of the searched, and the one or a plurality of sets included in the searched at least a part of the plurality of sets By integrating a portion of the road, and a path identifying means for identifying the optimum path.
本発明の経路探索システムによれば、実際の経路探索の動作に先立って、例えばデータベース、メモリ等の格納手段に、経路上における搬送車の移動コストが格納される。ここに「経路」とは、例えばレールなど、被搬送物が搭載された又はされない状態で搬送車が移動可能である、経路を意味する。「搬送車」とは、例えばビークル等の経路上を移動すると共に被搬送物を積載可能に構成された台車等の車を意味する。 According to the route search system of the present invention, prior to the actual route search operation, the moving cost of the transport vehicle on the route is stored in storage means such as a database or a memory. Here, the “route” means a route on which the transport vehicle can move with or without a transported object such as a rail mounted thereon. The “conveyor vehicle” means a vehicle such as a carriage configured to move on a route such as a vehicle and to be loaded with an object to be conveyed.
本発明では特に、移動コストは、複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される。ここに「作業装置」とは、例えば半導体基板などの被搬送物に対して、成膜、加熱、配線、エッチング等を行う製造装置や、被搬送物の一時的な格納を行うストッカを含む、被搬送物に対して各種処理を施す装置を意味する。作業装置は、経路の脇に並んでいるか、又は経路の一部をなすように並んでいる。経路の一部をなす場合としては、例えば、単一の作業装置における搬入口と搬出口との経路における位置が相互に異なることで、経路の一部をなすように並ぶ場合がある。本発明に係る「集合」は、このような作業装置を複数含んで構成される集合を含む。但し、作業装置の一つから構成される集合を含んでもよい。集合の間には、搬送車が移動される経路(以下適宜「集合間経路」と呼ぶ)が存在し、集合の内部にも、搬送車が移動される経路(以下適宜「集合内経路」)が存在する。例えば、個々の集合は、個々の製造ラインに対応してもよいし、複数の集合が単一の製造ラインの中に存在していてもよい。 Particularly in the present invention, the movement cost is defined as a node in each of a plurality of sets including at least one set including a plurality of work devices, and a link between the plurality of sets. Here, the “working apparatus” includes, for example, a manufacturing apparatus that performs film formation, heating, wiring, etching, and the like on a transferred object such as a semiconductor substrate, and a stocker that temporarily stores the transferred object. It means an apparatus that performs various types of processing on a conveyed object. The working devices are arranged alongside the route or arranged to form a part of the route. As a case of forming a part of the route, for example, there are cases where the positions of the carry-in port and the carry-out port in a single work device are different from each other so as to form a part of the route. The “set” according to the present invention includes a set including a plurality of such work devices. However, a set composed of one of the work devices may be included. Between the sets, there is a route along which the transport vehicle is moved (hereinafter referred to as “inter-set route” as appropriate), and within the set, a route along which the transport vehicle is moved (hereinafter referred to as “in-set route” as appropriate). Exists. For example, an individual set may correspond to an individual production line, or a plurality of sets may exist in a single production line.
本発明に係る「移動コスト」は、このように複数の作業装置を含んでなる集合の相互間の経路部分が夫々リンクとされると共に集合が夫々ノードとされた上で、規定されている。「リンク」は、経路において、分岐点、合流点、交差点などの間を直接結んでおり、移動の仕方について単純に進むことしか選択枝がない、一本の直線又は曲線状若しくは屈曲状の経路部分に対応する。「ノード」は、経路において、リンクの端に位置しており、典型的には、分岐点、合流点、交差点、行き止り点、更にはストッカの搬出搬入箇所など、搬送経路における移動の仕方についての選択枝が複数存在する点或いは箇所に対応する。「移動コスト」とは、このような集合をノードとし且つ集合間をリンクとする経路探索を行う際に、一つのノードからこれに隣接するノードまで一つのリンクを介して移動するのにかかる時間若しくは時間に比例する指標であるコストを意味する。例えば、同一の距離でも、混雑等により移動時間が長ければ、移動コストの値は大きくなる。このような移動コストを用いれば、次に説明するように、典型的には、上述の如く集合に対応した移動コストを用いてのダイクストラ法によって、複数の集合を結ぶ単位での経路探索を行える。 The “movement cost” according to the present invention is defined in such a manner that the path portions between the sets including a plurality of work devices are each a link and each set is a node. A “link” is a straight, curved, or curved path that directly connects between branching points, merge points, intersections, etc. in the path, and has only a choice as to how to move. Corresponds to the part. The “node” is located at the end of the link in the route. Typically, the “node” is a branching point, a junction point, an intersection, a dead end point, and a moving method in the conveying route such as a stocker loading / unloading point. This corresponds to a point or location where there are a plurality of selected branches. “Movement cost” is the time taken to move from one node to a node adjacent to it when performing a route search with such a set as a node and a link between sets. Or it means the cost which is an index proportional to time. For example, even if the distance is the same, if the movement time is long due to congestion or the like, the value of the movement cost increases. If such a movement cost is used, as will be described below, typically, a route search in units connecting a plurality of sets can be performed by the Dijkstra method using the movement cost corresponding to the set as described above. .
特に、このように複数の作業装置を含んでなる集合をノードとして、移動コストが規定されるので、作業装置をノードとする場合と比較して、複数の作業装置を集合にまとめた分だけ、経路探索に供される移動コストの総数は、削減される。即ち、格納手段に格納される移動コストのデータ量は、先ず低減される。また、作業装置等の設備が新規に設置される場合に、その新規設備は何れかのノードに設置される。この何れかのノードを含んでなる経路における移動コストの修正では、その新規設備が設置されたノードのみにおいて、移動コストが算出されればよく、既に使用されている規定済みの移動コストは、該経路において流用可能である。このため、新規設備を立ち上げる時間を短縮することができる。 In particular, since the set including a plurality of work devices as a node and the movement cost is defined, compared to the case where the work device is a node, the amount of the work devices collected in a set is as follows: The total number of travel costs used for route search is reduced. That is, the data amount of the movement cost stored in the storage means is first reduced. Further, when a facility such as a work apparatus is newly installed, the new facility is installed at any node. In the correction of the movement cost in the route including any one of the nodes, it is only necessary to calculate the movement cost only in the node where the new equipment is installed. Can be diverted in the route. For this reason, the time to start up a new facility can be shortened.
尚、以上のような移動コストは、例えば過去における各集合に関しての平均移動時間から予め特定して、格納手段に格納してもよい。或いは、実際の経路探索の動作を行う際に先ず、経路における混雑状況等を考慮して、かかる移動コストを検出或いは算出し、格納手段に新たに格納したり、その格納内容を更新してもよい。或いは、搬送作業の際に、搬送車が各集合を移動するのに要した移動時間が実測され、搬送作業が終了されると直ちに、その経路についてのコスト計算が実行或いは再実行されることで、格納手段の格納内容が新設或いは更新されてもよい。この場合に、移動コストは、最新の経路の混雑状況を反映させたものとなる。 The travel cost as described above may be specified in advance from the average travel time for each set in the past and stored in the storage means. Alternatively, when performing an actual route search operation, it is necessary to first detect or calculate the travel cost in consideration of the congestion situation on the route, and store it in the storage means or update the stored content. Good. Alternatively, during the transport operation, the travel time required for the transport vehicle to move through each set is measured, and immediately after the transport operation is completed, the cost calculation for the route is executed or re-executed. The stored contents of the storage means may be newly established or updated. In this case, the movement cost reflects the congestion status of the latest route.
その後、実際の経路探索の動作時には、例えばプロセッサ、メモリ等を備えてなる経路探索手段によって、上述の如く格納手段に格納された移動コストに基づいて、最適経路の少なくとも一部が、複数の集合を結ぶ単位で探索される。例えば、複数の集合のうち出発地点を含む出発集合から、複数の集合のうち目的地点を含む目標集合までの経路が、出発集合から目標集合まで複数の集合を結ぶ形で探索される。言い換えれば、先ずは、少なくとも最適経路の一部について、経路探索手段によって、例えば製造ライン単位など、集合を結ぶ単位での大まかな経路探索が行われる。 Thereafter, at the time of the actual route search operation, at least a part of the optimum route is set to a plurality of sets based on the movement cost stored in the storage unit as described above by the route search unit including, for example, a processor and a memory. It is searched in the unit connecting. For example, a route from a starting set including a starting point among a plurality of sets to a target set including a destination point among the plurality of sets is searched in a form connecting the plurality of sets from the starting set to the target set. In other words, first, at least a part of the optimum route is subjected to a rough route search by a unit for connecting a set such as a production line unit by the route search means.
このように経路探索手段による経路探索では、少なくとも最適経路の一部について、集合の内部において個々の作業装置間を結ぶ経路部分が、夫々リンクとして扱われるのではなく、集合の相互間を結ぶ経路部分が夫々リンクとして扱われる。これと共に、個々の作業装置が夫々ノードとして扱われるのではなく、集合が夫々ノードとして扱われる。従って、個々の作業装置間を結ぶ経路部分が夫々リンクとして扱われ、個々の作業装置が夫々ノードとして扱われる場合における、経路探索と比べて、データ量及び演算量が飛躍的に低減される。特に、格納手段に格納される移動コストの総数の削減に対して、移動コストに基づく経路探索におけるデータ量及び演算量の削減は、極めて顕著となる。経路探索で用いる移動コストの総数の小規模な削減であっても、経路探索においては大規模なデータ量及び演算量の削減に繋がる。 As described above, in the route search by the route search means, at least a part of the optimal route, the route portion connecting the individual work devices within the set is not treated as a link, but a route connecting the sets to each other. Each part is treated as a link. At the same time, each work device is not treated as a node, but a set is treated as a node. Accordingly, the amount of data and the amount of calculation are drastically reduced as compared to the route search in the case where the route portions connecting the individual work devices are each treated as a link and each work device is treated as a node. In particular, the reduction in the amount of data and the amount of calculation in the route search based on the movement cost is extremely remarkable, as compared with the reduction in the total number of movement costs stored in the storage means. Even a small reduction in the total number of travel costs used in route search leads to a large amount of data and computation reduction in route search.
このような経路探索手段による探索と相前後して又は並列に、例えばプロセッサ、メモリ等を備えてなる経路特定手段によって、探索された最適経路の少なくとも一部と、この少なくとも一部に含まれる一又は複数の集合の内部に存在する経路の部分とが統合されることで、最適経路の全体が特定される。ここに「統合する」とは、探索された集合を結ぶ集合間経路と、探索された集合の各々の内部に存在する集合内経路とを、一本の道筋に結び合わせて最適経路とすることを意味する。例えば、経路探索手段による探索の後に、探索された集合の内部の夫々について、経路特定手段によってダイクストラ法による集合内経路の探索が行われる。或いは、経路探索手段による探索の以前に、任意の集合の内部の夫々について、経路特定手段によってダイクストラ法による集合内経路の探索が行われて、探索された集合内経路が集合に対応付けられて格納手段等に格納され、その後、経路探索手段により探索された集合に対応する集合内経路が格納手段等から呼び出されてもよい。 At least a part of the optimum route searched for by the route specifying means including, for example, a processor, a memory, etc., in parallel with or in parallel with the search by the route search means, and one included in this at least part Alternatively, the whole of the optimum route is specified by integrating the route portions existing in the plurality of sets. Here, “integrate” means that an inter-set route connecting the searched sets and an intra-set route existing inside each searched set are combined into a single route to be an optimum route. Means. For example, after the search by the route search means, the search for the route within the set by the Dijkstra method is performed by the route specifying means for each of the inside of the searched set. Alternatively, before the search by the route search means, the route specifying means searches for the route in the set by the Dijkstra method for each of the inside of the set, and the searched route in the set is associated with the set. The intra-set route corresponding to the set stored in the storage means or the like and then searched by the route search means may be called from the storage means or the like.
ここで特に、本願発明者の研究によれば、全体として複雑高度化された経路であっても、一つの集合についてみれば、その内部における経路及び経路を介しての移動は、相対的に単純であり、移動にかかる時間は、短時間であることが判明している。言い換えれば、同一集合内であれば、目標地点がどの作業装置であったとしても、時間的に或いはコスト的に大差がないことが判明している。よって、上述の経路特定手段による集合内経路の探索或いは決定は、例えば同一製造ライン内における経路の探索であれば、複数の製造ラインに跨る経路の探索或いは決定と比べて、飛躍的に単純なもので足りる。例えば、ダイクストラ法を用いても、個々の集合についてみれば、リンク及びノードの構成は単純なものであり、経路探索にかかるデータ量及び演算処理も、飛躍的に低減されることになる。従って、先ず集合を結ぶ単位で大まかな経路探索を行って、最適経路をなす集合及び集合間経路を決定した上で、各集合内における集合内経路を特定し、これらを結んで得られる最適経路は、初めから経路を最大限に細かく見てダイクストラ法により経路探索を行った場合に得られる最適経路と比べて、実践上は殆ど又は全く遜色のないものとなる。 Here, in particular, according to the study of the present inventor, even if the route is complicated and sophisticated as a whole, the route and the movement through the route are relatively simple in terms of one set. It has been found that the time required for movement is short. In other words, it has been found that there is no significant difference in time or cost regardless of which work device the target point is within the same set. Therefore, the search or determination of the route in the set by the route specifying means described above is dramatically simpler than the search or determination of a route across a plurality of production lines, for example, when searching for a route within the same production line. Things are enough. For example, even if the Dijkstra method is used, the structure of links and nodes is simple when viewed for each set, and the amount of data and calculation processing for route search are drastically reduced. Therefore, first, a rough route search is performed in units of connecting sets, and after determining the sets and inter-set routes that form the optimal route, the intra-set routes within each set are identified, and the optimal route obtained by connecting these routes Compared with the optimum route obtained when the route is searched by the Dijkstra method by looking at the route to the maximum detail from the beginning, it is practically inferior or not inferior.
そこで本発明において、経路探索手段により、集合を結ぶ単位で大まかな経路探索を行うと共に、経路特定手段により、集合内での経路探索或いは経路の決定を行えば、決定される最適経路は、実践上は、理論上における真の最適経路と殆ど又は全く同じ経路となる。或いは、少なくとも、真の最適経路に相当に近いものとなる。他方で、このような適切な経路を求める際に、集合単位で経路探索するのに必要なデータ量及び演算量と集合内で経路探索或いは決定を行うのに必要なデータ量及び演算量との合算は、一段階で真の最適経路を探索する場合と比べて飛躍的に低減されている。 Therefore, in the present invention, when the route search unit performs a rough route search in units of connecting sets, and the route specifying unit performs route search or route determination within the set, the optimum route to be determined is practiced. The above is almost or exactly the same as the true optimum path in theory. Or, at least, it is very close to the true optimum route. On the other hand, when obtaining such an appropriate route, the amount of data and the amount of computation required to search for a route in a set unit and the amount of data and the amount of computation required to perform a route search or determination within the set The summation is drastically reduced compared to the case of searching for the true optimum route in one step.
以上の結果、取り扱うデータ数及び演算負荷を低減しつつ、最適経路或いは実践的な意味での最適経路を探索できる。従って、リアルタイム或いはそれに近い形で経路探索を行うことも容易となり、搬送システムにおいて迅速な搬送が可能となる。更に、これらを実践するために、経済性に見合わないような高性能のコンピュータを用いることも効果的に回避できる。 As a result, the optimum route or the optimum route in a practical sense can be searched while reducing the number of data to be handled and the calculation load. Therefore, it is easy to search for a route in real time or in a form close to that, and quick transportation is possible in the transportation system. Furthermore, it is possible to effectively avoid the use of a high-performance computer that does not match the economic efficiency in order to implement these.
尚、本発明で探索される最適経路の精度を高める観点からは、一集合にまとめられる複数の作業装置は、経路探索上で同一ノードとして扱っても、最終的に探索される経路に差がでないような関係にある、典型的に近くに横並びになっているような複数の作業装置とするのがよい。例えば、小規模な製造ラインであって、その製造ライン内における移動が短時間で行われ得るような製造ラインであれば、一つの集合と一つの製造ラインとを対応させるのがよい。他方、大規模な製造ラインであって、その製造ライン内における移動が長時間で行われ得るような製造ラインであれば、複数の集合と一つの製造ラインとを対応させるのがよい。 Note that, from the viewpoint of improving the accuracy of the optimum route searched for in the present invention, a plurality of working devices grouped together as one set have a difference in the finally searched route even if they are treated as the same node on the route search. It is better to have a plurality of working devices that are not closely related, typically side by side. For example, if the production line is a small-scale production line that can be moved within the production line in a short time, it is preferable that one set corresponds to one production line. On the other hand, if the production line is a large-scale production line that can be moved in the production line for a long time, it is preferable to associate a plurality of sets with one production line.
他方で、複数の作業装置を集合にまとめる箇所が多い程、移動コストの総数は低減され、よって経路探索時におけるデータ量及び演算量の削減の効果は、より顕著に得られる。但し、集合にまとめる箇所が一箇所だけであっても、経路探索時におけるデータ量及び演算量の削減の効果は、相応に得られる。 On the other hand, the greater the number of locations where a plurality of work devices are grouped together, the lower the total number of travel costs. Therefore, the effect of reducing the amount of data and the amount of computation during route search can be obtained more significantly. However, even if there is only one place to be collected in the set, the effect of reducing the amount of data and the amount of calculation during route search can be obtained accordingly.
加えて、集合間の経路と集合との接続点、即ち、各集合の搬出口及び搬入口は、一つの集合に対して複数個所存在してもよい。一つの集合を一つのノードとして扱えば、上述の如き移動時間又は移動コストを用いた経路探索は、極めて単純化できる。或いは、搬出口及び搬入口の少なくとも一方が複数ある場合、搬出口又は搬入口別に複数の集合として扱って、即ち複数のノードであるものとして扱っても(従って、リンクもそれに応じて増えても)、移動時間又は移動コストを用いた経路探索は、全ての作業装置の各々をノードとして扱う場合と比べれば、なお顕著に単純化できる。 In addition, there may be a plurality of connection points between the paths between the sets and the sets, that is, the exits and the entrances of each set. If one set is treated as one node, the route search using the travel time or travel cost as described above can be greatly simplified. Alternatively, when there are a plurality of at least one of the carry-out port and the carry-in port, they can be treated as a plurality of sets according to the carry-out port or the carry-in port, that is, treated as a plurality of nodes (therefore, links are increased accordingly). ), Route search using travel time or travel cost can still be significantly simplified as compared to the case where all work devices are treated as nodes.
本発明の経路探索システムの一態様では、前記経路特定手段は、前記複数の作業装置間を夫々結ぶ前記経路の部分を夫々リンクとすると共に前記複数の作業装置を夫々ノードとする前記搬送車の移動コストに基づいて、前記経路の部分を探索し、前記探索された少なくとも一部と前記探索された経路の部分とを統合することで、最適経路を特定する。 In one aspect of the route search system of the present invention, the route specifying unit includes a link of each part of the route connecting the plurality of work devices, respectively, and the transport vehicle having the plurality of work devices as nodes. Based on the movement cost, the route portion is searched, and the optimum route is specified by integrating at least the searched portion and the searched route portion.
この態様によれば、各集合内における経路探索は、作業装置をノードとし且つ作業装置間をリンクとする移動コストを用いて、典型的にはダイクストラ法によって行われるが、例えば同一製造ラインなど、同一集合の内部での経路の探索である。このため、経路特定手段による経路探索に必要なデータ量及び演算負荷が、過度に増大することはない。 According to this aspect, the route search in each set is typically performed by the Dijkstra method using the movement cost with the working device as a node and between the working devices as a link. Searching for routes within the same set. For this reason, the data amount and calculation load required for the route search by the route specifying means do not increase excessively.
或いは本発明の経路探索システムの他の態様では、前記格納手段は、前記ノード及び前記リンクに対応付けて、前記集合の内部における前記経路の部分を示す集合内経路情報を更に格納しており、前記経路特定手段は、前記格納された集合内経路情報を参照することで、前記探索された少なくとも一部に接続される経路の部分を決定し、前記探索された少なくとも一部と前記決定された経路の部分とを統合することで、最適経路を特定する。 Alternatively, in another aspect of the route search system of the present invention, the storage means further stores in-set route information indicating a portion of the route in the set in association with the node and the link, The route specifying means determines a portion of a route connected to the searched at least part by referring to the stored intra-set route information, and determined as the searched at least part. The optimal route is specified by integrating the route portion.
この態様によれば、各集合内における経路の決定は、格納手段に格納された集合内経路情報を参照することで行われるが、例えば同一製造ラインなど、同一集合の内部での経路の決定である。このため、経路特定手段による経路の決定に必要なデータ量及び演算負荷が、過度に増大することはない。 According to this aspect, the route in each set is determined by referring to the in-set route information stored in the storage means. For example, the route in the same set such as the same manufacturing line is determined. is there. For this reason, the amount of data and the calculation load required for determining the route by the route specifying means do not increase excessively.
本発明の経路探索システムの他の態様では、前記搬送車が移動する際の移動状況を検出する状態検出手段を更に備え、前記経路探索手段は、前記検出された移動状況に対応して、前記経路を再探索する。 In another aspect of the route search system of the present invention, the route search system further includes state detection means for detecting a movement situation when the transport vehicle moves, the route search means corresponding to the detected movement situation, Search the route again.
この態様によれば、例えばプロセッサ、センサ等を有する状態検出手段によって、例えば各集合内を移動する際の平均移動速度、混雑状態や、集合間を移動する際の平均移動速度、混雑状態などの、搬送車が移動する際の移動状況が検出される。すると、経路探索手段によって、検出された移動状況に対応して、経路が再探索される。従って、特定の集合で或いは特定の集合間で平均移動速度が変化したり、故障や搬送量の過多に起因して混雑やデッドロックが発生したり、回復や搬送量の低下に起因して混雑やデッドロックが解消した場合に、最適経路が探索され直される。従って、リアルタイム的に各時点に見合った最適経路が探索されることとなり、実践上極めて便利である。特に、演算負荷が低減されているので、このように再探索を行う場合に特に有利である。仮に頻繁に再探索を行っても特に問題は生じない。 According to this aspect, for example, the state detection means having a processor, a sensor, etc., for example, the average movement speed when moving in each set, the congestion state, the average movement speed when moving between sets, the congestion state, etc. The movement status when the transport vehicle moves is detected. Then, the route is searched again by the route search means corresponding to the detected movement situation. Therefore, the average moving speed changes in a specific set or between specific sets, congestion or deadlock occurs due to failure or excessive transport amount, and congestion occurs due to recovery or decrease in transport amount. When the deadlock is resolved, the optimum route is searched again. Therefore, an optimum route suitable for each time point is searched in real time, which is extremely convenient in practice. In particular, since the calculation load is reduced, this is particularly advantageous when performing a re-search. Even if re-searching is performed frequently, no particular problem occurs.
尚、このような経路探索手段による再探索に加えて又は代えて、経路特定手段による最適経路による再特定が、状態検出手段により検出された移動状況に対応して、行われてもよい。 In addition to or instead of such re-searching by the route searching means, re-specification by the optimum route by the route specifying means may be performed in accordance with the movement status detected by the state detecting means.
本発明の経路探索システムの他の態様では、前記経路の一部を、前記経路探索手段により前記最適経路を探索する上で、使用不可能に設定する設定手段を更に備え、前記経路探索手段は、前記使用不可能に設定された一部を除外して、前記経路を探索する。 In another aspect of the route search system of the present invention, the route search unit further includes setting means for setting a part of the route to be unusable when searching for the optimum route by the route search means. The route is searched by excluding a part set as unusable.
この態様によれば、例えばキーボード、マウス、プロセッサ等を備えてなる設定手段によって、経路の一部が、ユーザによって、経路探索手段により最適経路を探索する上で、使用不可能に設定される。或いは、経路の一部が、故障診断を行う手段若しくは混雑診断を行う手段による診断結果に応じて、又はメンテナンスが行われている箇所を特定する手段による特定結果に応じて、経路探索手段により最適経路を探索する上で、使用不可能に設定される。例えば、前述の状況検出手段の検出結果により、移動状況の異常が検出された場合に、これに対応する経路に使用不可能フラグを立てることで、実質的に使用不可能に設定されてもよい。すると、経路探索手段によって、このように実質的に使用不可能に設定された一部が除外された上で、経路が探索される。或いは、既に経路が設定されていた場合に、設定手段によって、経路の一部がこのように実質的に使用不可能に設定されると、経路探索手段によって、このように実質的に使用不可能に設定された一部が除外された上で、経路が再探索される。従って、経路探索におけるデータ量及び演算負荷は、経路の一部を除外して計算する分だけ、飛躍的に低減されると共に、使用不可能な一部を含む最適経路が決定されるのを未然防止できる。 According to this aspect, a part of the route is set to be unusable when the user searches for the optimum route by the route search unit by the setting unit including a keyboard, a mouse, a processor, and the like. Alternatively, a part of the route is optimized by the route search means according to the diagnosis result by the means for performing the failure diagnosis or the means for performing the congestion diagnosis, or according to the specification result by the means for specifying the place where the maintenance is performed. When searching for a route, it is set to be unusable. For example, when an abnormality in the movement situation is detected based on the detection result of the above-described situation detection unit, the flag may be set to be substantially unusable by setting an unusable flag on the corresponding route. . Then, the route search unit searches for a route after excluding a part that has been set to be substantially unusable in this way. Alternatively, when a route has already been set and a part of the route is set to be substantially unusable by the setting means, the route search means is thus substantially unusable. The route is re-searched after a part set to is excluded. Therefore, the amount of data and the calculation load in route search are drastically reduced by the amount calculated by excluding a part of the route, and the optimum route including the unusable part can be determined in advance. Can be prevented.
尚、このような経路探索手段による、使用不可能に設定された一部を除外しての経路探索に加えて又は代えて、経路特定手段による、使用不可能に設定された一部を除外しての最適経路の特定が、行われてもよい。 In addition to or instead of the route search that excludes a part that is set to be unusable by such a route search unit, a part that is set to be unusable by a route specifying unit is excluded. All the optimum routes may be identified.
或いは本発明の経路探索システムの他の態様では、前記経路の一部を使用可能に設定する又は前記経路に対して使用可能な一部を追加する設定手段を更に備え、前記経路探索手段は、前記使用可能に設定された又は追加された一部を入れて、前記経路を探索する。 Alternatively, in another aspect of the route search system of the present invention, the route search unit further includes a setting unit that sets a part of the route to be usable or adds a part that can be used to the route. The route is searched with the part set to be usable or added.
この態様によれば、例えばキーボード、マウス、プロセッサ等を備えてなる設定手段によって、経路の一部が、ユーザによって使用可能に設定される。或いは、経路の一部が、故障診断を行う手段若しくは混雑診断を行う手段による診断結果に応じて、又はメンテナンスが行われている箇所を特定する手段による特定結果に応じて、使用可能に設定される。例えば、前述の状況検出手段の検出結果に応じて、使用可能に設定されてもよい。すると、経路探索手段によって、このように使用可能に設定された又は追加された一部が入れられた上で、経路が探索される。或いは、既に経路が設定されていた場合に、設定手段によって、経路の一部が使用可能に設定される又は追加されると、経路探索手段によって、使用可能に設定された又は追加された一部が入れられた上で、経路が再探索される。従って、使用可能な一部を除外するが故に、不適切な経路(即ち、コストが最小でない経路)が、最適経路として決定されるのを未然防止できる。 According to this aspect, for example, a part of the route is set to be usable by the user by the setting unit including a keyboard, a mouse, a processor, and the like. Alternatively, a part of the route is set to be usable according to a diagnosis result by a means for performing a failure diagnosis or a means for performing a congestion diagnosis, or according to a specification result by a means for specifying a place where maintenance is performed. The For example, it may be set to be usable according to the detection result of the above-described situation detection means. Then, the route is searched by the route search means after the part that has been set to be usable or added in this way is entered. Alternatively, when a route has already been set, if a part of the route is set to be usable or added by the setting unit, the part that has been set to be usable or added by the route search unit Is entered, and the route is searched again. Therefore, since a part that can be used is excluded, it is possible to prevent an inappropriate route (that is, a route with a minimum cost) from being determined as the optimum route.
尚、このような経路探索手段による、使用可能に設定された一部を入れての経路探索に加えて又は代えて、経路特定手段による、使用可能に設定された一部を入れての最適経路の特定が、行われてもよい。 In addition to or instead of the route search that includes a part that is set to be usable by such a route search unit, an optimum route that includes a part that is set to be usable by a route specifying unit. Identification may be performed.
本発明の経路探索システムの他の態様では、前記移動コストを前記リンク毎に算出するコスト算出手段を更に備え、前記格納手段は、前記算出された移動コストを格納する。 In another aspect of the route search system of the present invention, the route search system further includes cost calculation means for calculating the movement cost for each link, and the storage means stores the calculated movement cost.
この態様によれば、経路探索手段による経路探索に先立って、例えばプロセッサ、メモリ等を備えてなるコスト算出手段によって、移動コストが、算出され、例えばデータベース等の格納手段に格納される。 According to this aspect, prior to the route search by the route search means, the movement cost is calculated by the cost calculation means including, for example, a processor, a memory, etc., and stored in the storage means such as a database.
この態様では、前記コスト算出手段は、前記搬送車が実際の搬送作業に要した実績時間データから前記搬送車が実際に搬送した前記経路について前記移動コストを算出し、前記格納手段は、前記算出された移動コストで格納内容を更新するように構成してもよい。 In this aspect, the cost calculation means calculates the travel cost for the route actually transported by the transport vehicle from actual time data required for the transport vehicle for actual transport work, and the storage means calculates the calculation The stored contents may be updated at the travel cost.
このように構成すれば、コスト算出手段によって、例えば搬送車が経路上の目標地点に到達すると直ちに、搬送車が実際の搬送作業に要した実績時間データから搬送車が実際に搬送した経路について移動コストが算出される。更に、この算出された移動コストで、格納手段の格納内容が更新される。このため、経路における混雑の状況等が変化した場合に、経路探索に必要な移動コストを最新のものに更新でき、よりリアルタイム的に実際の経路状況に合致した最適経路を探索可能となる。 If comprised in this way, as soon as a conveyance vehicle arrives at the target point on a path | route for example by a cost calculation means, a conveyance vehicle will move about the path | route which the conveyance vehicle actually conveyed from the performance time data required for the actual conveyance work. Cost is calculated. Further, the stored contents of the storage means are updated with the calculated movement cost. For this reason, when the congestion status of the route changes, the travel cost necessary for the route search can be updated to the latest one, and the optimum route that matches the actual route status can be searched in real time.
本発明の搬送システムは上述の課題を解決するために、上述した本発明に係る経路探索システム(但し、その各種態様を含む)と、前記経路と、前記搬送車と、前記搬送車を前記経路上で移動させる移動手段とを備える。 In order to solve the above-described problems, the transport system of the present invention includes the above-described route search system according to the present invention (including various aspects thereof), the route, the transport vehicle, and the transport vehicle. And moving means for moving above.
本発明の搬送システムによれば、上述した本発明に係る経路探索システムを含むので、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索でき、リアルタイム或いはそれに近い形で経路探索を行うことも容易となる。これにより、例えばビークルの推進装置、レールなどを含んでなる移動手段によって、搬送車が、例えば同一の製造ライン内で或いは異なる製造ライン間で、迅速に移動可能となる。例えば、複数の作業装置から一つの製造ラインが構成されており、複数の製造ラインに対応して複数の搬送ラインが設けられ、更に複数の搬送ラインの相互間にも、搬送ラインが設けられている搬送システムにおいて、最適な経路を経由して移動可能にできる。 According to the transport system of the present invention, since the route search system according to the present invention described above is included, the optimum route can be searched while reducing the number of data to be handled and the calculation load, and the route search is performed in real time or close to it. Is also easier. As a result, for example, the moving means including a vehicle propulsion device, rails, and the like enables the transport vehicle to quickly move within, for example, the same production line or between different production lines. For example, a single production line is composed of a plurality of work devices, a plurality of conveyance lines are provided corresponding to the plurality of production lines, and a conveyance line is also provided between the plurality of conveyance lines. Can be moved via an optimal route.
尚、本発明の搬送システムにおいても、上述した本発明の経路探索システムにおける各種態様と同様の各種態様を採ることが可能である。 The transport system of the present invention can also adopt various aspects similar to the various aspects of the above-described route search system of the present invention.
本発明の経路探索方法は上記課題を解決するために、被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索方法であって、前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段に格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する探索工程と、前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定工程とを備える。 In order to solve the above problems, the route search method of the present invention searches for an optimum route when moving a transport vehicle for transporting a transported object from a starting point to a target point on the route of the transport vehicle. A method of performing a variety of processes on the object to be conveyed and including each of a plurality of sets including at least one set including a plurality of work devices arranged along the path as a node. Based on the movement cost stored in the storage means for storing the movement cost of the transport vehicle, which is defined as a link between the sets of the plurality of sets, at least a part of the optimum route is a unit connecting the plurality of sets. Integrating a search step for searching, at least a part of the searched part, and a part of the route existing inside one or a plurality of sets included in the searched at least part of the plurality of sets In Rukoto, and a path specifying step of specifying the optimum path.
本発明の経路探索方法によれば、上述した本発明に係る経路探索システムの場合と同様に、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索でき、リアルタイム或いはそれに近い形で経路探索を行うことも容易となる。 According to the route search method of the present invention, as in the case of the route search system according to the present invention described above, the optimum route can be searched while reducing the number of data to be handled and the calculation load, and the route search can be performed in real time or close to it. It is also easy to perform.
尚、本発明の経路探索方法においても、上述した本発明の経路探索システムにおける各種態様と同様の各種態様を採ることが可能である。 In the route search method of the present invention, various aspects similar to the various aspects of the above-described route search system of the present invention can be employed.
本発明のコンピュータプログラムは上記課題を解決するために、被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムに備えられるコンピュータを、前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段として機能させる。 In order to solve the above problems, a computer program according to the present invention searches for an optimum route for moving a transport vehicle for transporting an object to be transported from a starting point to a target point on the route of the transport vehicle. The computer included in the computer is configured to process each of the objects to be conveyed and each of a plurality of sets including at least one set including a plurality of work devices arranged along the path as a node, and Storage means for storing the movement cost of the transport vehicle defined as a link between a plurality of sets, and at least a part of the optimum route based on the stored movement cost, A route searching means for searching by a unit to be connected, at least a part of the searched, and one or a plurality of parts included in the searched at least part of the plurality of sets By integrating a portion of the path that exists inside the case, to function as a route identifying means for identifying the optimum path.
本実施形態のコンピュータプログラムによれば、当該コンピュータプログラムを格納するCD−ROM、DVD−ROM等の記録媒体から、当該コンピュータプログラムを、経路探索システムに備えられたコンピュータに読み込んで実行させれば、或いは、当該コンピュータプログラムを通信手段を介してダウンロードさせた後に実行させれば、上述した本発明に係る経路探索システムを比較的簡単に構築できる。これにより、上述した本発明に係る経路探索システムの場合と同様に、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索でき、リアルタイム或いはそれに近い形で経路探索を行うことも容易となる。 According to the computer program of the present embodiment, if the computer program is read from a recording medium such as a CD-ROM or DVD-ROM storing the computer program into a computer provided in the route search system and executed, Alternatively, the route search system according to the present invention described above can be constructed relatively easily if the computer program is executed after being downloaded via communication means. As a result, as in the case of the route search system according to the present invention described above, the optimum route can be searched while reducing the number of data to be handled and the calculation load, and the route search can be easily performed in real time or in a form close thereto. .
尚、本発明のコンピュータプログラムにおいても、上述した本発明の経路探索システムにおける各種態様と同様の各種態様を採ることが可能である。 Note that the computer program of the present invention can also adopt various aspects similar to the various aspects of the above-described route search system of the present invention.
本発明の作用及び他の利得は次に説明する実施するための最良の形態から明らかにされる。 The operation and other advantages of the present invention will become apparent from the best mode for carrying out the invention described below.
以下、本発明の実施形態について図を参照しつつ説明する。 Hereinafter, embodiments of the present invention will be described with reference to the drawings.
先ず、本実施形態に係る経路探索システムを含む製造システムの構成について説明する。ここに図1は、本実施形態に係る経路探索システムを含む製造システムのブロック図であり、図2は、図1の経路探索システムの搬送路を製造装置と共に示す概略平面図である。 First, the configuration of a manufacturing system including a route search system according to the present embodiment will be described. FIG. 1 is a block diagram of a manufacturing system including the route search system according to the present embodiment, and FIG. 2 is a schematic plan view showing a conveyance path of the route search system of FIG.
図1及び図2において、製造システム200は、主に、製造指示部1、ビークル2、CPU10、及び移動装置11を備えている。本実施形態に係る経路探索システム100は、CPU10として、製造システム200に組み込まれている。CPU10は、経路設定部3、走行検出部4、コスト算出部5、第1経路探索部6、経路特定部7、搬送コントローラ8、及びメモリ9を含む。移動装置11は、ビークル2を所望の製造装置21及びストッカ21bへと搬送可能に構成されている。
1 and 2, the
図2において、移動装置11は、本発明に係る「移動手段」の一例であって、搬送路12の他、例えばリニアモータの制御ライン及び電源装置などの、ビークル2をリニアモータ方式で移動させるための機械的及び電気的な機構一式を有する。より具体的には、搬送路12は、搬送方向に延びると共にビークル2の車輪が転動する転動面を夫々有する一対のレールを有し、更に該一対のレールの間に搬送方向に複数配列された永久磁石を有する。搬送路12は、ビークル2側に設けられたリニアモータが、その上を走行するための走行路でもあり、ビークル2が走行するための電源信号やその走行を制御するための各種信号がやりとりされる有線の制御線としての機能も有する。
In FIG. 2, the moving device 11 is an example of the “moving means” according to the present invention, and moves the
移動装置11は、モジュールM1からM4を搬送路12によって接続している。ここに「モジュール」とは、一つ又は複数のベイによって構成されたOHT(工程内搬送機器)システムが搬送制御管理するための単位を意味し、「ベイ」とは、OHTシステムで搬送可能な一又は複数の製造装置の集まりである。モジュールM1からM4は、大規模OHTを構成している。大規模OHTでは、大規模OHTを構成する移動装置11の部分によって、モジュールM1からM4の各々の内部で、ビークル2が走行可能である。更に、移動装置11は、搬送路12によって、四方に配置されるモジュールM1からM4を、ストッカSTK1からSTK4を介して、相互に接続している。このモジュールM1からM4の間の搬送制御が、OHS(工程間搬送機器)システムによって管理される。OHSでは、OHSを構成する移動装置11の部分によって、モジュールM1からM4の間で、ビークル2が走行可能である。
The moving device 11 connects the modules M1 to M4 by the
ビークル2は、本発明に係る「搬送車」の一例として、リニアモータにより搬送路12に沿って走行し、半導体装置製造における各種基板等の被搬送物が格納されたキャリアを搬送する。ビークル2には、図示しない、個々のビークルを独立制御するためのコントローラ、及び位置情報を発信するための位置情報発信部が内蔵されている。
As an example of the “transport vehicle” according to the present invention, the
製造装置21は、本発明に係る「作業装置」の一例として、製造装置コントローラ22による制御下で、ビークル2により搬送された被搬送物に対して、製品に至る各種処理を行う。
As an example of the “working apparatus” according to the present invention, the
ストッカ21bは、本発明に係る「作業装置」の一例として、ストッカコントローラ23による制御下で、ビークル2により搬送されたキャリア(例えば、搬送用の容器)或いは被搬送物に対して一部処理が実施されたキャリアを、内部の収容庫へ搬入する又は外部へ搬出するように構成されている。ストッカ21bは、搬送路12の一部から搬入すると共に搬送路12の他部へ搬出することで、移動装置11と共に搬送手段の一部を構成してもよい。
As an example of the “working apparatus” according to the present invention, the stocker 21b performs a partial process on a carrier (for example, a container for transport) or a transported object transported by the
ストッカ21bの各々には、キャリアの搬入又は搬出を行うために、OHTに対する搬入出口STK−1、及びOHSに対する搬入出口STK−2が夫々備えられている。これらの2つの搬入出口STK−1及びSTK−2は、OHTからOHSに、或いはその逆にOHSからOHTに移動手段を切り替えるために備えられている。ストッカ21bには、図示しない、ストッカロボットも備えられている。ストッカロボットは、ストッカ21bの内部で、キャリアを移動させ、所望の搬入出口STK−1又はSTK−2からキャリアを搬出することで、OHT及びOHSの移動手段を切り替える。具体的に、OHTによって移動されるビークル2がグループG3のストッカ21b(STK1)に差し掛かると、ビークル2によって搬送されるキャリアが、ストッカロボットによって、ストッカSTK1の内部に、搬入出口STK−1から搬入された後、搬入出口STK−2から搬出される。これにより、ビークル2の移動手段がOHTからOHSに切り替えられ、ビークル2は、OHSによって移動されることになる。
Each of the stockers 21b is provided with a loading / unloading port STK-1 for the OHT and a loading / unloading port STK-2 for the OHS in order to load or unload the carrier. These two loading / unloading ports STK-1 and STK-2 are provided for switching the moving means from OHT to OHS or vice versa. The stocker 21b is also provided with a stocker robot (not shown). The stocker robot moves the carrier inside the stocker 21b, and carries out the carrier from the desired loading / unloading port STK-1 or STK-2, thereby switching the OHT and OHS moving means. Specifically, when the
図2に示すように、搬送路12には、複数の製造装置21やストッカ21bからなるグループG1からG10が設定されている。モジュールM1からM4の各々は、グループG3及びG4、グループG5及びG6、グループG7及びG8、グループG9及びG10に夫々対応している。モジュールM1のストッカSTK1及びモジュールM2のストッカSTK2は、グループG1に対応し、モジュールM3のストッカSTK3及びモジュールM4のストッカSTK4は、グループG2に対応している。このようなグループG1からG10の各々が、本発明に係る「集合」の一例とされた場合、グループG1からG10の各々が「ノード」として扱われ、グループG1からG10の相互間が「リンク」として扱われて、リンク毎にコストが算出される。コストは、本発明に係る「移動コスト」の一例として、各グループG1からG10において、例えば過去に測定された移動時間の平均値から算出される。或いは、この平均値に対して、経路の現状に応じた修正が施されることで設定される。
As shown in FIG. 2, groups G1 to G10 including a plurality of
各グループG1からG10は、グループを結ぶ単位での大まかな最適経路を、探索する際の区分けとなる。更に、そのように大まかな最適経路が決定された後のグループ内部における最適経路を決定する際の範囲となる。即ち、各グループG1からG10は、2段階で経路探索を行う際に、段階を隔てる基本的な区分けである。 Each of the groups G1 to G10 serves as a division when searching for a rough optimum route in a unit connecting the groups. Further, this is a range for determining the optimum route within the group after such a rough optimum route is determined. That is, each group G1 to G10 is a basic division that separates stages when performing route search in two stages.
再び図1において、製造指示部1は、製造工程のスケジュールに従って、製造を指示する旨の製造指示データを、CPU10、製造装置コントローラ22及びストッカコントローラ23に入力することで、半導体装置製造の指示を行う。
Referring again to FIG. 1, the
CPU10は、製造指示部1によって入力される製造指示データに対応して、半導体装置製造の処理を実行しつつ、ビークル2を、例えば後に詳述する最適経路を介して目標地点に到達させるように、各部を制御する。
The
経路設定部3は、本発明に係る「設定手段」の一例であって、半導体装置製造が開始されるよりも前に、製造指示部1及び走行検出部4の指示により、搬送路12の部分、即ち部分経路のいずれかを使用可能又は使用不可能に設定する。具体的に、経路設定部3は、該設定を行う部分経路に対して、予め設定されているフラグを、使用可能及び使用不可能のどちらかに変更する。この部分経路の設定変更のデータは、コスト算出部5に入力される。
The
走行検出部4は、本発明に係る「状態検出手段」の一例として、経路設定部3と同様に、半導体装置製造が開始されるよりも前に、製造指示部1の指示により、搬送路12を走行する複数のビークル2から発信される位置情報に基づいて、ビークル2の走行状況を検出する。具体的に、走行検出部4は、該位置情報に基づいて、例えばビークル2の走行が異常に遅いことや、走行すべき搬送路12で走行が止まっていることを検出する。この検出のデータは、経路設定部3及びコスト算出部5に入力される。
As an example of the “state detection unit” according to the present invention, the
コスト算出部5は、本発明に係る「コスト算出手段」の一例として、基本的に、半導体装置製造が開始されるよりも前に、製造指示部1の指示により、グループG1からG10の相互間の経路、即ちリンク毎のコストを算出する。
As an example of the “cost calculation unit” according to the present invention, the cost calculation unit 5 basically includes the groups G1 to G10 according to instructions from the
図2に示すように、グループG1は、ストッカSTK1及びストッカSTK2、グループG2は、ストッカSTK3及びストッカSTK4から夫々構成される。グループG3は、ビークル2が走行する順に、製造装置EQ11,EQ12、ストッカSTK1、グループG4は、製造装置EQ14,EQ13、グループG5は、製造装置EQ21,EQ22、ストッカSTK2、グループG6は、製造装置EQ24,EQ23、グループG7は、ストッカSTK3、製造装置EQ31,EQ32、グループG8は、製造装置EQ34,EQ33、グループG9は、ストッカSTK4、製造装置EQ41,EQ42、グループG10は、製造装置EQ44,EQ43から夫々構成される。 As shown in FIG. 2, the group G1 includes a stocker STK1 and a stocker STK2, and the group G2 includes a stocker STK3 and a stocker STK4. In the group G3, the manufacturing apparatuses EQ11 and EQ12 and the stocker STK1, the group G4, the manufacturing apparatuses EQ14 and EQ13, the group G5, the manufacturing apparatuses EQ21 and EQ22, the stocker STK2, and the group G6, the manufacturing apparatus EQ24 , EQ23, group G7 is stocker STK3, manufacturing equipment EQ31, EQ32, group G8 is manufacturing equipment EQ34, EQ33, group G9 is stocker STK4, manufacturing equipment EQ41, EQ42, and group G10 is from manufacturing equipment EQ44, EQ43, respectively. Composed.
具体的には、コスト算出部5は、移動装置11によって、コスト算出用の所定のビークル2を、グループG1からG10の相互間において所定回数移動させる。この移動に要した時間の平均値が、コストとして算出され、予めメモリ9に格納される。或いは、過去に搬送作業を行った一又は複数のビークル2がグループG1からG10の相互間の夫々で移動する際に要した移動時間の平均値が、コストとして算出されて、予めメモリ9に格納される。或いは、経験的な又は理論計算に基づくデフォールトの値が、コストとして、予めメモリ9に格納される。
Specifically, the cost calculation unit 5 causes the moving device 11 to move the
コスト算出部5は、半導体装置製造が開始されてからも、経路設定部3から入力される部分経路の設定変更、及び走行検出部4から入力される走行状況の検出結果に応じて、リンク毎のコストを再度算出し、メモリ9に格納されているコストのデータを更新する。
Even after the semiconductor device manufacturing is started, the cost calculation unit 5 is set for each link according to the partial route setting change input from the
最適経路の探索方法について、本実施形態では、第1経路探索部6及び第2経路探索部7aによる2段階の探索が行われる。 Regarding the optimum route search method, in this embodiment, a two-step search is performed by the first route search unit 6 and the second route search unit 7a.
第1経路探索部6は、半導体装置製造が開始されると、製造指示部1の指示により、ビークル2が出発地点から目標地点までキャリアを搬送するための、グループを結ぶ単位での最適経路を探索する。ここでは先ず、かかるグループを結ぶ単位での最適経路の複数の候補として、搬送元を含むグループから搬送先を含むグループに至るものが複数特定される。更に、第1経路探索部6は、これら複数の候補のうち、合計コスト(即ち、総コスト)が小さいものを、グループを結ぶ単位での最適経路として決定する。このため、第1経路探索部6は、メモリ9から、各候補に相当するグループ単位のコストを読み出し、読み出した複数のコストを合計して、各候補の合計コストを算出する。経路特定部7は、算出された合計コストのうち最小のものを有する候補を選択する。ここでの合計コストは、図2に示した各候補を構成する一連のグループのコストを合計或いは積算したものであり、各候補を経路として採用した場合における、搬送元を含むグループから搬送先を含むグループまで移動するのにかかる時間の概ねの指標となる。
When the semiconductor device manufacture is started, the first route search unit 6 determines an optimum route in units of connecting groups for the
本実施形態では特に、第1経路探索部6は、コスト算出部5によるコストデータの更新に応答して、グループを結ぶ単位での最適経路を再度探索する。具体的には、第1経路探索部6は、経路設定部3によって部分経路のいずれかが使用不可能に設定された場合に、その使用不可能に設定された経路を除いて、グループを結ぶ単位での最適経路を再度探索する。また、経路設定部3によって部分経路のいずれかが使用可能に設定されたり、使用可能な部分経路が追加された場合に、その使用可能に設定された、又は追加された部分経路を含めて、グループを結ぶ単位での最適経路を再度探索する。更に、走行検出部4によって検出される走行状況に応じて、グループを結ぶ単位での最適経路を再度探索する。
In the present embodiment, in particular, the first route search unit 6 searches again for the optimum route in units connecting groups in response to the update of the cost data by the cost calculation unit 5. Specifically, when one of the partial routes is set to be unusable by the
次に、経路特定部7は、第1経路探索部6から入力されたグループを結ぶ単位での最適経路における各グループの内部を通過する経路を特定する。このため、経路特定部7は、第2経路探索部7aを備える。第2経路探索部7aは、グループ内を結ぶ単位の最適経路を構成するグループG1からG10のうちいずれか複数のグループの各々の内部を、短時間で通過する経路(即ち、グループ内最適経路)を、第1経路探索部6と同様のダイクストラ法を、グループ内部の移動に係るコスト(即ち、グループ内部に存在する製造装置やストッカをノードとし且つこれらの間をリンクとして定義されるコスト)を用いて行うことで、探索される。この結果、個々のグループの内部に存在する複数の製造装置21又はストッカ21bを結ぶグループ内最適経路が特定される。
Next, the route specifying unit 7 specifies a route that passes through each group in the optimum route in a unit connecting the groups input from the first route searching unit 6. For this reason, the route specifying unit 7 includes a second route searching unit 7a. The second route search unit 7a is a route that passes through each of a plurality of groups among the groups G1 to G10 constituting the optimum route of the unit connecting the groups in a short time (that is, the optimum route within the group). The same Dijkstra method as that of the first route search unit 6 is used to calculate the cost related to movement within the group (that is, the cost defined as a link between the manufacturing apparatus and stocker existing in the group as nodes). It is searched by using. As a result, an optimum intra-group route that connects a plurality of
尚、グループ内の経路は、単純な場合もある。よって、このようなグループ内最適経路は、コスト計算による探索を行わなくても、例えば、予め設定された製造装置間やポート間を素直に連絡する順路として特定されてもよい。或いはコストに代えて単純に経路長や、右回り又は左回りなどの単純なルールに従って、特定されてもよい。 Note that the route within the group may be simple. Therefore, such an intra-group optimum route may be specified as a normal route that communicates between preset manufacturing apparatuses or between ports without performing a search by cost calculation. Alternatively, it may be specified in accordance with a simple rule such as a route length or clockwise or counterclockwise instead of cost.
経路特定部7は、このように第2経路探索部7aによって探索された個々のグループの内部にあるグループ内最適経路と、第1経路探索部6から入力されたグループを結ぶ単位での最適経路とを統合することで得られる一筋の経路を、最終的に最適経路として特定し、これを示す最適経路データを、搬送コントローラ8に入力する。 In this way, the route specifying unit 7 is configured to connect the optimum route in a group within each group searched by the second route search unit 7a and the optimum route in units connecting the groups input from the first route search unit 6. Finally, a single route obtained by integrating the two is specified as the optimum route, and optimum route data indicating this is input to the transport controller 8.
搬送コントローラ8は、経路特定部7から入力された最適経路データに基づいて、ビークル2を制御する。この制御により、ビークル2に搬送されるキャリアが、最短時間で目標地点に到達する。
The transport controller 8 controls the
メモリ9は、本発明に係る「格納手段」の一例として、グループ別のコスト及びグループ内経路情報を格納している。コストは、コスト算出部5によって、グループを結ぶリンク毎に予め算出されると共に、経路設定部3による設定変更、及び走行検出部4により検出される走行状況に応じて、更新される。グループ内経路情報は、グループG1からG10の各々の内部におけるグループ内経路を示し、第2経路探索部7aにより適宜参照される。
The
次に、最適経路を特定する動作処理について説明する。ここに図3は、本実施形態に係る経路探索システムを含む製造システムのグループ別のコスト表の一具体例であり、図4は、図3の経路探索システムにおける最適経路の合計コストの対比表の一具体例である。 Next, an operation process for specifying the optimum route will be described. FIG. 3 is a specific example of the cost table for each group of the manufacturing system including the route search system according to this embodiment, and FIG. 4 is a comparison table of the total cost of the optimum route in the route search system of FIG. Is a specific example.
図3において、グループ別のコストが示されている。各コストは、1つの製造装置21、ストッカ21b、OHT、及びOHS別に設定される、搬送元(即ち、搬送当初の出発地点又は搬送途中の中継地点)及び搬送先(即ち、搬送途中の中継地点又は最終的な目標地点)の組み合わせに対応している。即ち、搬送元及び搬送先を夫々ノードとして、これらにより結ばれるリンクに対応する形で、各コストは定義されている。具体的には、作業装置がストッカSTK1である場合に、搬送元として、搬送されるキャリアがストッカSTK1の内部にあることを示す「SHELF」、キャリアがOHSの搬入出口STK−2にあることを示す「OHSin」、及びキャリアがOHTの搬入出口STK−1にあることを示す「OHTin」が示されている。この搬送元に対する搬送先として、搬送されるキャリアがOHSに向かうことを示す「OHSout」、キャリアがOHTに向かうことを示す「OHTout」、及びキャリアがストッカSTK1の内部に向かうことを示す「SHELF」が示されている。例えば、ストッカSTK1の内部にあるキャリアがOHTに向かう場合に、搬送元として「SHELF」、搬送先として「OHTout」が選択され、図3に示すように、コストが「10」となる。
In FIG. 3, the cost for each group is shown. Each cost is set for each
更に、作業装置が移動手段であるOHT及びOHSである場合に、搬送元及び搬送先として、グループG1からG10のいずれかが示されている。即ち、OHT及びOHSの場合には特に、グループを夫々ノードとして、これらにより結ばれるリンクに対応する形で、各コストは定義されている。例えば、OHSに対するグループG1とグループG2との間を、キャリアが搬送される場合に、搬送元として「G1」、搬送先として「G2」が選択され、コストが「40」となる。経路網上における移動時間に大差がないような隣接した又は近接した複数の作業装置は、同一グループに属するように、ここでのグループ分けは行われる。 Furthermore, when the working device is OHT and OHS which are moving means, any one of groups G1 to G10 is shown as the transfer source and transfer destination. That is, particularly in the case of OHT and OHS, each group is defined as a node, and each cost is defined in a form corresponding to a link connected by these groups. For example, when a carrier is transported between the group G1 and the group G2 for OHS, “G1” is selected as the transport source, “G2” is selected as the transport destination, and the cost is “40”. Here, grouping is performed so that a plurality of adjacent or adjacent work devices that do not have a large difference in travel time on the route network belong to the same group.
再び図2において、製造指示部1によって、ストッカ21b(STK1)内部に収容されているキャリアを、製造装置21(EQ44)に搬送する指示がなされると、第1経路探索部6は、ストッカSTK1から製造装置EQ44までの最適経路の探索を行う。この探索では、グループを結ぶ単位での最適経路の候補として4つの候補TRである、第1候補(図4における搬送経路No.1)〜第4候補(図4における搬送経路No.4)についての、コスト比較が行われる。図3では、第4の最適経路の候補TR4を構成するグループのコストが示される。
In FIG. 2 again, when the
第1候補は、先ず、ストッカSTK1の搬入出口STK−1を出発し、OHTを介して、グループG10の製造装置EQ44に到達する経路を示す。この第1候補は、グループG3に対応するグループ間経路(STK1:SHELF → STK1:OHTout)、及びOHTにおけるグループG3からグループG10のグループ間のグループ間経路(STK1:OHTout → EQ44)の2つのグループ間経路から構成されている。 The first candidate first indicates a route that starts from the loading / unloading exit STK-1 of the stocker STK1 and reaches the manufacturing apparatus EQ44 of the group G10 via the OHT. This first candidate includes two groups of an inter-group route (STK1: SHELF → STK1: OHTout) corresponding to the group G3 and an inter-group route (STK1: OHTout → EQ44) between the groups G3 to G10 in the OHT. It consists of an inter-path.
第2候補は、先ず、ストッカSTK1の搬入出口STK−2を出発し、OHSにおけるグループG1を介して、ストッカSTK2の搬入出口STK−2に達した後、その内部を経て、ストッカSTK2の搬入出口STK−1から、OHTを介して、グループG10の製造装置EQ44に到達する経路を示す。この第2候補は、グループG3に対応するグループ間経路(STK1:SHELF → STK1:OHSout)、OHSにおけるグループG1に対応するグループ間経路(STK1:OHSout → STK2:OHSin)、グループG5に対応するグループ間経路(STK2:OHSin → STK2:OHTout)、及びOHTにおけるグループG5からグループG10のグループ間のグループ間経路(STK2:OHTout → EQ44)の4つのグループ間経路から構成されている。 First, the second candidate starts from the loading / unloading port STK-2 of the stocker STK1, reaches the loading / unloading port STK-2 of the stocker STK2 via the group G1 in the OHS, and then passes through the loading / unloading port STK2 of the stocker STK2. The path | route which reaches | attains the manufacturing apparatus EQ44 of group G10 via OHT from STK-1 is shown. The second candidate is an inter-group route corresponding to the group G3 (STK1: SHELF → STK1: OHSout), an inter-group route corresponding to the group G1 in the OHS (STK1: OHSout → STK2: OHSin), and a group corresponding to the group G5. The inter-group path (STK2: OHSin → STK2: OHTout) and the inter-group path (STK2: OHTout → EQ44) between the groups G5 to G10 in the OHT are configured.
第3候補は、先ず、ストッカSTK1の搬入出口STK−2を出発し、OHSにおけるグループG1及びG2を介して、ストッカSTK3の搬入出口STK−2に達した後、その内部を経て、ストッカSTK3の搬入出口STK−1から、OHTを介して、グループG7を経て、グループG10の製造装置EQ44に到達する経路を示す。この第3候補は、グループG3に対応するグループ間経路(STK1:SHELF → STK1:OHSout)、OHSにおけるグループG1及びG2に対応するグループ間経路(STK1:OHSout → STK3:OHSin)、グループG7に対応するグループ間経路(STK3:OHSin → STK3:OHTout)、及びOHTにおけるグループG7からG10のグループ間のグループ間経路(STK3:OHTout → EQ44)の4つのグループ間経路から構成されている。 The third candidate first departs from the loading / unloading port STK-2 of the stocker STK1, reaches the loading / unloading port STK-2 of the stocker STK3 via the groups G1 and G2 in the OHS, and then passes through the inside of the loading / unloading port STK3. The path | route which reaches | attains the manufacturing apparatus EQ44 of the group G10 through the group G7 from the loading / unloading exit STK-1 is shown. This third candidate corresponds to the inter-group route corresponding to the group G3 (STK1: SHELF → STK1: OHSout), the inter-group route corresponding to the groups G1 and G2 in the OHS (STK1: OHSout → STK3: OHSin), and the group G7. The inter-group route (STK3: OHSin → STK3: OHTout) and the inter-group route (STK3: OHTout → EQ44) between the groups G7 to G10 in the OHT are configured.
第4候補は、先ず、ストッカSTK1の搬入出口STK−2を出発し、OHSにおけるグループG1及びG2を介して、ストッカSTK4の搬入出口STK−2に達した後、その内部を経て、ストッカSTK4の搬入出口STK−1から、OHTを介して、グループG10の製造装置EQ44に到達する経路を示す。この第4候補は、グループG3のグループ間経路(STK1:SHELF → STK1:OHSout)、OHSにおけるグループG1及びG2に対応するグループ間経路(STK1:OHSout → STK4:OHSin)、グループG9に対応するグループ間経路(STK4:OHSin → STK4:OHTout)、及びOHTにおけるグループG9からG10のグループ間のグループ間経路(STK4:OHTout → EQ44)の4つのグループ間経路から構成されている。 First, the fourth candidate starts from the loading / unloading port STK-2 of the stocker STK1, reaches the loading / unloading port STK-2 of the stocker STK4 via the groups G1 and G2 in the OHS, and then passes through the inside of the loading / unloading port STK4. The path | route which reaches | attains the manufacturing apparatus EQ44 of the group G10 from the loading / unloading exit STK-1 via OHT is shown. The fourth candidate is an inter-group route (STK1: SHELF → STK1: OHSout) of the group G3, an inter-group route (STK1: OHSout → STK4: OHSin) corresponding to the groups G1 and G2 in the OHS, and a group corresponding to the group G9. The inter-group route (STK4: OHSin → STK4: OHTout) and the inter-group route (STK4: OHTout → EQ44) between the groups G9 to G10 in the OHT are configured.
こうして、4つの候補についてのグループを結ぶ単位での合計コストは、メモリ9から読み取られたグループ別のコストが積算されることで算出される。第1候補から第4候補の合計コストは夫々、図4に「合計コスト」として示したように、「125」、「205」、「185」、「95」となる。これにより、合計コストが、最小値「95」となる第4候補が、最適経路TR4として選択される。
In this way, the total cost in the unit connecting the groups for the four candidates is calculated by integrating the cost for each group read from the
このようにグループを結ぶ単位での最適経路TR4が特定されると、これを構成するグループの各々の内部に存在するグループ内経路とが結び合わされて、一本の道筋になることで、最終的に、最適経路が特定される。 When the optimum route TR4 in the unit connecting the groups is specified in this way, the intra-group routes existing inside each of the groups constituting the group are combined to form a single route. The optimum route is identified.
次に、本実施形態に係る経路探索システムの動作処理である経路特定処理について、図5を参照して説明する。
(経路特定処理)
図5は、本実施形態に係る経路探索システムの経路特定処理を示すフローチャートである。
Next, a route specifying process that is an operation process of the route search system according to the present embodiment will be described with reference to FIG.
(Route identification process)
FIG. 5 is a flowchart showing route specifying processing of the route search system according to the present embodiment.
具体的には、図5において、先ず、第1経路探索部6によって、グループを結ぶ単位で、最適経路の複数の候補が探索される(ステップS11)。続いて、探索された複数の候補を構成する、部分経路のいずれかについて、経路設定部3によって使用可能又は使用不可能とする経路変更、或いは走行検出部5によってビークル2の故障等の走行異常があったか否かが判定される(ステップS12)。
Specifically, in FIG. 5, first, the first route searching unit 6 searches for a plurality of candidates for the optimum route in units of connecting groups (step S11). Subsequently, for any of the partial routes constituting the plurality of searched candidates, the
ここで、経路変更及び走行異常のいずれかがあったと判定された場合には(ステップS12:YES)、経路変更の対象となる部分経路、及び走行異常とされるビークル2が存在するために通過できないと想定される部分経路が、使用不可能に設定される(ステップS13)。具体的には、この実質的に使用不可能な部分経路を含む候補については、次に行われる候補毎のコスト算出の対象から除外される。或いは、この使用不可能な部分経路に対する移動コストについては、非常に高い値に設定される。これにより、次に行われる候補毎のコスト算出における合計コストが大きくなるが故に、早期に候補から除外される。
Here, if it is determined that either a route change or a running abnormality has occurred (step S12: YES), the vehicle passes because there is a partial route that is subject to a route change and the
他方で、経路変更及び走行異常のいずれもないと判定された場合には(ステップS12:NO)、ステップS13における部分経路を使用不可能とする設定が行われることなく、次の処理へ進む。 On the other hand, when it is determined that there is neither a route change nor a running abnormality (step S12: NO), the process proceeds to the next process without setting the partial route to be unusable in step S13.
続いて、コスト算出部5によって、グループ単位でのコストが算出され、メモリ9に格納されているコストデータが更新される(ステップS14)。続いて、第1経路探索部6によって、更新後における合計コストが最小となる候補が、選択される。即ち、グループ単位での最適経路が、この段階で完了する。
Subsequently, the cost in the group unit is calculated by the cost calculation unit 5, and the cost data stored in the
続いて、この特定されたグループ単位での最適経路を構成するグループの各々の内部のグループ内経路情報がメモリ9から読み出され、読み出されたグループ内経路情報に基づくグループ内経路が特定される。更に、これらの特定されたグループ内経路とグループを結ぶ単位での最適経路とが統合されることで、最終的に最適経路が特定される(ステップS15)。
Subsequently, the intra-group route information inside each of the groups constituting the optimum route in the specified group unit is read from the
その後、搬送コントローラ8によって、特定された最適経路に沿って、ビークル2が制御され、ビークル2に搬送されるキャリアが目標地点に到達される(ステップS16)。これにより、一連の経路特定処理が終了される。
Thereafter, the transport controller 8 controls the
尚、ステップS16で実際にビークル2が目標地点に到達すると直ちに、走行した最適経路を構成するリンクを搬送するのにかかった時間から、これら各リンクについての移動コストが、算出される。更に、この算出された移動コストで、メモリ9内の格納内容が更新されて、その後における最適経路探索に利用される。
Note that as soon as the
このように、実施形態の経路特定システムによれば、グループを結ぶ単位でコストが算出されるので、コストを用いての経路探索に必要とされるデータ数が極端に少なくなる。これにより、取り扱うデータ数及び演算負荷を低減しつつ、最適経路或いは実践的な意味での最適経路を探索できる。 As described above, according to the route specifying system of the embodiment, since the cost is calculated in units of connecting groups, the number of data required for the route search using the cost is extremely reduced. This makes it possible to search for the optimum route or the optimum route in a practical sense while reducing the number of data to be handled and the calculation load.
また、搬送経路の変更や、ビークル2の走行異常に対応して、再度、リンク毎にコストを算出するので、常に最新のコストに基づいて最適経路が選択される。このため、搬送車の故障や、搬送経路の混雑を要因とする搬送時間のロスを無くすことができ、パフォーマンスを更に向上させることができる。
Further, since the cost is calculated again for each link in response to the change of the transport route or the traveling abnormality of the
本発明は、上述した実施形態に限られるものではなく、請求の範囲及び明細書全体から読み取れる発明の要旨或いは思想に反しない範囲で適宜変更可能であり、そのような変更を伴う経路探索システム及び方法、搬送システム、並びにコンピュータプログラムもまた本発明の技術的範囲に含まれるものである。 The present invention is not limited to the above-described embodiment, and can be appropriately changed without departing from the spirit or idea of the invention that can be read from the claims and the entire specification, and a route search system with such a change and Methods, transport systems, and computer programs are also within the scope of the present invention.
1…搬送路、2…ビークル、3…経路設定部、4…走行検出部、5…コスト算出部、6…第1経路特定部、7…経路特定部、7a…第2経路探索部、8…搬送コントローラ、11…移動装置、21…製造装置、21b…ストッカ、100…経路探索システム、200…製造システム
DESCRIPTION OF
Claims (11)
前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、
前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、
前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段と
を備えることを特徴とする経路探索システム。 A route search system for searching for an optimum route when moving a transport vehicle for transporting an object to be transported from a departure point to a target point on the route of the transport vehicle,
Each of a plurality of sets including at least one set that includes a plurality of work devices that perform various processes on the transported object and that are arranged along the path is a node between the plurality of sets. Storage means for storing the movement cost of the transport vehicle,
Route search means for searching for at least a part of the optimum route in units of connecting the plurality of sets based on the stored travel cost;
The optimal route is obtained by integrating the searched at least part and the part of the route existing inside one or a plurality of sets included in the searched at least part of the plurality of sets. A route search system comprising: a route specifying means for specifying.
前記経路特定手段は、前記格納された集合内経路情報を参照することで、前記探索された少なくとも一部に接続される経路の部分を決定し、前記探索された少なくとも一部と前記決定された経路の部分とを統合することで、前記最適経路を特定することを特徴とする請求項1に記載の経路探索システム。 The storage means further stores in-set route information indicating the portion of the route in the set in association with the node and the link,
The route specifying means determines a portion of a route connected to the searched at least part by referring to the stored intra-set route information, and determined as the searched at least part. The route search system according to claim 1, wherein the optimum route is specified by integrating a route portion.
前記経路探索手段は、前記検出された移動状況に対応して、前記経路を再探索する
ことを特徴とする請求項1から3のいずれか一項に記載の経路探索システム。 It further comprises a state detection means for detecting a movement situation when the transport vehicle moves,
The route search system according to any one of claims 1 to 3, wherein the route search means re-searches the route according to the detected movement state.
前記経路探索手段は、前記使用不可能に設定された一部を除外して、前記経路を探索することを特徴とする請求項1から4のいずれか一項に記載の経路探索システム。 A setting unit that sets a part of the route to be unusable when searching for the optimum route by the route searching unit;
5. The route search system according to claim 1, wherein the route search unit searches for the route by excluding a part of the route that is set to be unusable. 6.
前記経路探索手段は、前記使用可能に設定された又は追加された一部を入れて、前記経路を探索することを特徴とする請求項1から4のいずれか一項に記載の経路探索システム。 Setting means for setting a part of the route to be usable or adding a usable part to the route;
5. The route search system according to claim 1, wherein the route search unit searches the route by including the part that is set to be usable or added. 5.
前記格納手段は、前記算出された移動コストを格納することを特徴とする請求項1から6のいずれか一項に記載の経路探索システム。 A cost calculation means for calculating the movement cost for each link;
The route search system according to claim 1, wherein the storage unit stores the calculated travel cost.
前記格納手段は、前記算出された移動コストで格納内容を更新する
ことを特徴とする請求項7に記載の経路探索システム。 The cost calculating means calculates the travel cost for the route actually transported by the transport vehicle from actual time data required by the transport vehicle for actual transport work,
The route search system according to claim 7, wherein the storage unit updates storage contents with the calculated travel cost.
前記経路と、
前記搬送車と、
前記搬送車を前記経路上で移動させる移動手段と
を備えることを特徴とする搬送システム。 A route search system according to any one of claims 1 to 8,
The pathway;
The transport vehicle;
And a moving means for moving the transport vehicle on the route.
前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段に格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する探索工程と、
前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定工程と
を備えることを特徴とする経路探索方法。 A route search method for searching for an optimal route when moving a transport vehicle for transporting an object to be transported from a departure point to a target point on the route of the transport vehicle,
Each of a plurality of sets including at least one set that includes a plurality of work devices that perform various processes on the transported object and that are arranged along the path is a node between the plurality of sets. A search step for searching for at least a part of the optimum route by a unit connecting the plurality of sets, based on the movement cost stored in the storage means for storing the movement cost of the transport vehicle. ,
The optimal route is obtained by integrating the searched at least part and the part of the route existing inside one or a plurality of sets included in the searched at least part of the plurality of sets. A route search method comprising: a route specifying step for specifying.
前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、
前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、
前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段と
として機能させることを特徴とするコンピュータプログラム。 A computer provided in a route search system for searching for an optimum route when moving a transport vehicle for transporting an object to be transported from a starting point to a target point on the route of the transport vehicle;
Each of a plurality of sets including at least one set that includes a plurality of work devices that perform various processes on the transported object and that are arranged along the path is a node between the plurality of sets. Storage means for storing the movement cost of the transport vehicle,
Route search means for searching for at least a part of the optimum route in units of connecting the plurality of sets based on the stored travel cost;
The optimal route is obtained by integrating the searched at least part and the part of the route existing inside one or a plurality of sets included in the searched at least part of the plurality of sets. A computer program that functions as a path specifying means for specifying.
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2007183903A JP4915302B2 (en) | 2007-07-13 | 2007-07-13 | Route search system and method, transport system, and computer program |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2007183903A JP4915302B2 (en) | 2007-07-13 | 2007-07-13 | Route search system and method, transport system, and computer program |
Publications (2)
Publication Number | Publication Date |
---|---|
JP2009020773A JP2009020773A (en) | 2009-01-29 |
JP4915302B2 true JP4915302B2 (en) | 2012-04-11 |
Family
ID=40360351
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP2007183903A Active JP4915302B2 (en) | 2007-07-13 | 2007-07-13 | Route search system and method, transport system, and computer program |
Country Status (1)
Country | Link |
---|---|
JP (1) | JP4915302B2 (en) |
Cited By (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP2020030724A (en) * | 2018-08-24 | 2020-02-27 | 村田機械株式会社 | Running car control apparatus, running car system, and running car control method |
US10726170B2 (en) | 2015-12-25 | 2020-07-28 | Kabushiki Kaisha Toshiba | Simulation machine and simulation method |
JP2021076970A (en) * | 2019-11-06 | 2021-05-20 | 株式会社ダイフク | Article conveyance facility |
Families Citing this family (5)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN105446342B (en) * | 2016-01-04 | 2019-02-05 | 杭州亚美利嘉科技有限公司 | Method and apparatus for the reflux of robot terminal place |
KR102404695B1 (en) * | 2020-04-28 | 2022-06-02 | 한국과학기술원 | Dynamic Routing Method and Apparatus for Overhead Hoist Transport System |
KR102265604B1 (en) * | 2020-10-30 | 2021-06-17 | 주식회사 세미티에스 | Method for searching optimal transfer path in transfer system of wafer container used in semiconductor manufacturing process and central control device using the same |
KR102635999B1 (en) * | 2020-12-03 | 2024-02-13 | 세메스 주식회사 | Article storage device and control method thereod |
JP7426672B2 (en) | 2021-03-24 | 2024-02-02 | 株式会社豊田自動織機 | sorting equipment |
Family Cites Families (7)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP2001153671A (en) * | 1999-11-24 | 2001-06-08 | Clarion Co Ltd | Navigation device and method and recording medium storing navigation software |
JP2003345439A (en) * | 2002-05-30 | 2003-12-05 | Asyst Shinko Inc | Automatic transportation system and method for searching path for transport vehicle |
JP2004110288A (en) * | 2002-09-17 | 2004-04-08 | Mitsubishi Heavy Ind Ltd | Agv route searching method and its program |
AU2002357627A1 (en) * | 2002-12-20 | 2004-07-14 | Jicoux Datasystems, Inc. | Route search apparatus, route search system, program, and route search method |
JP4138541B2 (en) * | 2003-03-13 | 2008-08-27 | 独立行政法人科学技術振興機構 | Distributed path planning apparatus and method, and distributed path planning program |
JP4339714B2 (en) * | 2004-02-12 | 2009-10-07 | ジクー・データシステムズ株式会社 | Route calculation device, route calculation method, and program |
JP4172465B2 (en) * | 2005-05-09 | 2008-10-29 | 村田機械株式会社 | Conveyor cart system |
-
2007
- 2007-07-13 JP JP2007183903A patent/JP4915302B2/en active Active
Cited By (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US10726170B2 (en) | 2015-12-25 | 2020-07-28 | Kabushiki Kaisha Toshiba | Simulation machine and simulation method |
JP2020030724A (en) * | 2018-08-24 | 2020-02-27 | 村田機械株式会社 | Running car control apparatus, running car system, and running car control method |
WO2020039699A1 (en) * | 2018-08-24 | 2020-02-27 | 村田機械株式会社 | Traveling vehicle control device, traveling vehicle system, and traveling vehicle control method |
JP2021076970A (en) * | 2019-11-06 | 2021-05-20 | 株式会社ダイフク | Article conveyance facility |
JP7059999B2 (en) | 2019-11-06 | 2022-04-26 | 株式会社ダイフク | Goods transport equipment |
US11312578B2 (en) | 2019-11-06 | 2022-04-26 | Daifuku Co., Ltd. | Article transport facility |
Also Published As
Publication number | Publication date |
---|---|
JP2009020773A (en) | 2009-01-29 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
JP4915302B2 (en) | Route search system and method, transport system, and computer program | |
TWI485537B (en) | Method of carrying the trolley system and the walking path of the van | |
US9415934B2 (en) | Transport system and transport method | |
JP5119762B2 (en) | Route search system and method, transport system, and computer program | |
US7577517B2 (en) | Guided vehicle system and teaching method in the guided vehicle system | |
JP4977644B2 (en) | Automatic conveyance system and method for setting standby position of conveyance vehicle in automatic conveyance system | |
US7809466B2 (en) | Transportation system and transportation method | |
JP2011102166A (en) | Conveying route determining method and automatic conveyance system | |
KR102431740B1 (en) | Driving vehicle controller and driving vehicle system | |
TW202014356A (en) | Traveling vehicle control device, traveling vehicle system, and traveling vehicle control method | |
TWI489238B (en) | Running the car system | |
JPWO2019067837A5 (en) | ||
TW202246076A (en) | Article transport facility, route setting method, route setting program | |
TWI402643B (en) | Unmanned delivery device and method for determining delivery path thereof | |
JP4441931B2 (en) | Conveyor cart system | |
CN108394672B (en) | Article carrying apparatus | |
TW200410883A (en) | Control device for transfer system | |
JP2013237562A (en) | Article transfer equipment | |
TW202014981A (en) | Running vehicle control device, running vehicle system, and running vehicle control method | |
KR20240116769A (en) | return system | |
TWI380942B (en) | Unattended transporting apparatus and transporting route determining method for the same | |
JP2012162096A (en) | System for rail guided truck | |
JPH04340607A (en) | Optimum route determining device | |
JP2005206272A (en) | Article carrying method and article carrying system | |
JP2022178183A (en) | Travel route setting device, autonomous mobile robot control system including the same, travel route setting method, and travel route setting program |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
A711 | Notification of change in applicant |
Free format text: JAPANESE INTERMEDIATE CODE: A711 Effective date: 20091022 |
|
RD03 | Notification of appointment of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7423 Effective date: 20091120 |
|
A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20100108 |
|
A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20100628 |
|
A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20111207 |
|
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: 20111227 |
|
A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20120109 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20150203 Year of fee payment: 3 |
|
R150 | Certificate of patent or registration of utility model |
Ref document number: 4915302 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20150203 Year of fee payment: 3 |
|
S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313111 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20150203 Year of fee payment: 3 |
|
R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |