(57)【特許請求の範囲】
【請求項１】
格子状に設けられた複数の搬送路上の互いに異なる複数の搬送開始位置にそれぞれ配置された被搬送物をいずれかの搬送路上に設定された搬送目的位置へ、各搬送路上を移動し得る複数の搬送機によって各別に搬送する計画を策定する場合、
各搬送機をそれが搬送すべき被搬送物にそれぞれ割り付け、
各搬送機別にそれぞれ、当該搬送開始位置から搬送目的位置までの各搬送路がそれぞれ交差する複数の交差位置間の通行による搬送目的位置までの搬送のし易さを示す値を、各交差位置間の距離を用いて求め、求めた各値に基づいて、相対的に搬送し易い交差位置を順次選択して最適搬送経路を生成し、生成した最適搬送経路の方向及び前記値に基づいて、前記最適搬送経路を構成する交差位置とは異なる交差位置を含み、相対的に搬送し易い交差位置を選択して前記最適搬送経路とは異なる１又は複数の次善搬送経路を生成して、前記最適搬送経路及び１又は複数の次善搬送経路を含む複数の搬送機別搬送経路群を得、
各搬送機別搬送経路群からそれぞれ、そこに含まれる最適搬送経路及び次善搬送経路の内の任意の搬送経路を選択し、任意の搬送経路を選択する都度、当該搬送経路を構成する各交差位置間で搬送機を待機させるべく予め設定された複数の待機時間から任意の待機時間を選択し、選択した待機時間を当該搬送経路を構成する１又は複数の交差位置間に設定して搬送計画候補を生成する操作を繰り返して搬送計画候補群とし、
これらの操作を複数回行って、待機時間及び／又は待機時間を設定した交差位置間が異なる複数の搬送計画候補群を得、
得られた各搬送計画候補群それぞれについて、同じ時刻に同じ交差位置間に複数の搬送機が存在する回数、及び、搬送開始位置から搬送目的位置まで被搬送物を搬送するに要する時間に基づいて適合度を算出するに当たって、前記回数が少ないほど、また前記時間が短いほど高い値の適合度を算出し、算出された各適合度の値を比較し、その比較結果に基づいて、前記複数の搬送計画候補群からより適合度が高い至適な搬送計画候補群を選択し、選択した搬送計画候補群を構成する各搬送計画候補をそれぞれ搬送計画とする
ことを特徴とする搬送計画策定方法。
【請求項２】
前記各搬送路上の複数位置にはそれぞれ、前記交差位置であるノードが設定されており、相隣るノード間にそれぞれ両ノード間の距離に応じて、両ノード間における搬送機の通り易さである重みを予め設定しておき、
これら重みを次の（１）式及び（２）式に適用して、搬送目的位置から位置を隔てる順に、相隣るノード間の通行による搬送目的位置までの搬送のし易さの値であって、その値が小さいほど搬送し易いと判断されるＱ値をそれぞれ算出し、
次善搬送経路を生成する場合、当該次善搬送経路を構成すべき候補ノードに相隣る１又は複数のノードから任意のノードを選択して第１のノードとし、前記候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであるか否かを判断し、同じ方向でない場合、候補ノードと第１のノードとの間のＱ値を特定し、第１のノードに相隣る１又は複数のノードから任意のノードを指定して第２のノードとし、第１のノードと第２のノードとの間のＱ値を特定し、前者のＱ値より後者のＱ値の方が小さい場合、第１のノードを候補ノードとする
請求項１記載の搬送計画策定方法。
【数３】
0006695653.tif 000005
【請求項３】
第１のノードと第２のノードとの間のＱ値を特定するに先立って、
前記第２のノードが第１のノードを選択した際の候補ノードと同じ位置であるか否かを判断し、同じ位置である場合、第１のノードと第２のノードとの間のＱ値を特定することなく、第１のノードに相隣る他のノードを指定する
請求項２記載の搬送計画策定方法。
【請求項４】
前記候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じである場合、候補ノードと第１のノードとの間のＱ値を特定することなく、第１のノードを候補ノードとする請求項２又は３記載の搬送計画策定方法。
【請求項５】
至適な搬送計画候補群を選択する場合、
得られた各搬送計画候補群をその適合度の値に応じて順位付けし、
予め定めた順位より低い順位の各搬送計画候補群に対して、各搬送計画候補群に含まれる各搬送経路を２つのグループに分け、両グループから任意の搬送機に係る搬送計画候補をそれぞれ選択して対とし、両搬送計画候補をそれぞれ構成する複数の交差位置間である搬送経路を入れ替える交叉を、予め設定された交叉頻度回数に至るまで互いに交叉させる操作を全ての搬送機について行って、新しい搬送計画候補群をそれぞれ生成し、及び／又は、各搬送計画候補群から任意の搬送計画候補を選択し、各搬送計画候補群の各搬送経路を、選択した搬送計画候補に含まれる各搬送経路に更新した後、各搬送経路に設定された待機時間に遺伝的アルゴリズムを適用して、予め設定された突然変異確率で異なる待機時間を生成し、生成した待機時間に更新することによって、新しい搬送計画候補群をそれぞれ生成し、
予め定めた順位より高い順位の各搬送計画候補群及び生成した新しい各搬送計画候補群についてその適合度の値に応じて順位付けする操作を、予め定めた回数だけ繰り返した後、より高い順位の搬送計画候補群を至適な搬送計画候補群とする
請求項１から４のいずれかに記載の搬送計画策定方法。
【請求項６】
前記適合度は、次の（３）式を用いて算出する請求項１から５のいずれかに記載の搬送計画策定方法。
【数４】
0006695653.tif 000006
【請求項７】
格子状に設けられた複数の搬送路上の互いに異なる複数の搬送開始位置にそれぞれ配置された被搬送物をいずれかの搬送路上に設定された搬送目的位置へ、各搬送路上を移動し得る複数の搬送機によって各別に搬送する計画を策定する場合、
各搬送機をそれが搬送すべき被搬送物にそれぞれ割り付ける手段と、
各搬送機別にそれぞれ、当該搬送開始位置から搬送目的位置までの各搬送路がそれぞれ交差する複数の交差位置間の通行による搬送目的位置までの搬送のし易さを示す値を、各交差位置間の距離を用いて求め、求めた各値に基づいて、相対的に搬送し易い交差位置を順次選択して最適搬送経路を生成する手段と、生成した最適搬送経路の方向及び前記値に基づいて、前記最適搬送経路を構成する交差位置とは異なる交差位置を含み、相対的に搬送し易い交差位置を選択して前記最適搬送経路とは異なる１又は複数の次善搬送経路を生成して、前記最適搬送経路及び１又は複数の次善搬送経路を含む複数の搬送機別搬送経路群を得る手段と、
各搬送機別搬送経路群からそれぞれ、そこに含まれる最適搬送経路及び次善搬送経路の内の任意の搬送経路を選択する搬送経路選択手段と、任意の搬送経路を選択する都度、当該搬送経路を構成する各交差位置間で搬送機を待機させるべく予め設定された複数の待機時間から任意の待機時間を選択し、選択した待機時間を当該搬送経路を構成する１又は複数の交差位置間に設定して搬送計画候補を生成する搬送計画候補生成手段とを備え、
前記搬送経路選択手段が任意の搬送経路を選択する都度、搬送計画候補生成手段が搬送計画候補を生成する動作を繰り返して搬送計画候補群とし、これらの動作を複数回行って、待機時間及び／又は待機時間を設定した交差位置間が異なる複数の搬送計画候補群を得るようになしてあり、
更に、得られた各搬送計画候補群それぞれについて、同じ時刻に同じ交差位置間に複数の搬送機が存在する回数、及び、搬送開始位置から搬送目的位置まで被搬送物を搬送するに要する時間に基づいて適合度を算出するに当たって、前記回数が少ないほど、また前記時間が短いほど高い値の適合度を算出し、算出された各適合度の値を比較し、その比較結果に基づいて、前記複数の搬送計画候補群からより適合度が高い至適な搬送計画候補群を選択する至適搬送計画候補群選択手段と、選択された搬送計画候補群を構成する各搬送計画候補をそれぞれ搬送計画とする手段と
を備えることを特徴とする搬送計画策定装置。
【請求項８】
前記各搬送路上の複数位置にはそれぞれ、前記交差位置であるノードが設定されており、相隣るノード間にそれぞれ両ノード間の距離に応じて、両ノード間における搬送機の通り易さである重みが予め設定されており、
これら重みを予め設定された次の（１）式及び（２）式に適用して、搬送目的位置から位置を隔てる順に、相隣るノード間の通行による搬送目的位置までの搬送のし易さの値であって、その値が小さいほど搬送し易いと判断されるＱ値をそれぞれ算出する手段を備え、
前記次善搬送経路生成手段は、
当該次善搬送経路を構成すべき候補ノードに相隣る１又は複数のノードから任意のノードを選択して第１のノードとする手段と、前記候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであるか否かを判断する方向判断手段と、
同じ方向でない場合、候補ノードと第１のノードとの間のＱ値を特定する現在ノードＱ値特定手段と、
第１のノードに相隣る１又は複数のノードから任意のノードを指定して第２のノードとするノード指定手段と、
第１のノードと第２のノードとの間のＱ値を特定する指定ノードＱ値特定手段と、
前者のＱ値より後者のＱ値の方が小さい場合、第１のノードを候補ノードとする候補ノード決定手段とを具備する
請求項７記載の搬送計画策定装置。
【数５】
0006695653.tif 000007
【請求項９】
更に、前記指定ノードＱ値特定手段が、第１のノードと第２のノードとの間のＱ値を特定するに先立って、前記第２のノードが第１のノードを選択した際の候補ノードと同じ位置であるか否かを判断する手段を備え、
同じ位置である場合、前記指定ノードＱ値特定手段は第１のノードと第２のノードとの間のＱ値を特定することなく、前記ノード指定手段は第１のノードに相隣る他のノードを指定するようになしてある
請求項８記載の搬送計画策定装置。
【請求項１０】
前記方向判断手段が候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであると判断した場合、前記現在ノードＱ値特定手段が候補ノードと第１のノードとの間のＱ値を特定することなく、前記候補ノード決定手段は第１のノードを候補ノードとするようになしてある請求項８又は９記載の搬送計画策定装置。
【請求項１１】
前記至適搬送計画候補群選択手段は、
得られた各搬送計画候補群をその適合度の値に応じて順位付けする順位付手段と、
予め定めた順位より低い順位の各搬送計画候補群に対して、各搬送計画候補群に含まれる各搬送経路を２つのグループに分け、両グループから任意の搬送機に係る搬送計画候補をそれぞれ選択して対とし、両搬送計画候補をそれぞれ構成する複数の交差位置間である搬送経路を入れ替える交叉を、予め設定された交叉頻度回数に至るまで互いに交叉させる操作を全ての搬送機について行って、新しい搬送計画候補群をそれぞれ生成し、及び／又は、各搬送計画候補群から任意の搬送計画候補を選択し、各搬送計画候補群の各搬送経路を、選択した搬送計画候補に含まれる各搬送経路に更新した後、各搬送経路に設定された待機時間に遺伝的アルゴリズムを適用して、予め設定された突然変異確率で異なる待機時間を生成し、生成した待機時間に更新することによって、新しい搬送計画候補群をそれぞれ生成する新搬送計画候補群生成手段とを具備し、
前記順位付手段は、予め定めた順位より高い順位の各搬送計画候補群及び生成した新しい各搬送計画候補群についてその適合度の値に応じて順位付けするようになしてあり、
前記新搬送計画候補群生成手段が新しい搬送計画候補群をそれぞれ生成し、前記順位付手段が順位付けする動作を予め定めた回数だけ繰り返した後、より高い順位の搬送計画候補群を至適な搬送計画候補群とする手段を具備する
請求項７から１０のいずれかに記載の搬送計画策定装置。
【請求項１２】
前記適合度算出手段は、予め設定された次の（３）式に基づいて適合度を算出するようになしてある請求項７から１１のいずれかに記載の搬送計画策定装置。
【数６】
0006695653.tif 000008
【請求項１３】
複数の搬送路と、各搬送路上を移動し得る複数の搬送機と、請求項７から１２のいずれかに記載の搬送計画策定装置と、該搬送計画策定装置が作成した搬送計画を各搬送機へ送信する送信器と
を備えることを特徴とする搬送システム。
【請求項１４】
コンピュータに、格子状に設けられた複数の搬送路上の互いに異なる複数の搬送開始位置にそれぞれ配置された被搬送物をいずれかの搬送路上に設定された搬送目的位置へ、各搬送路上を移動し得る複数の搬送機によって各別に搬送する計画を策定させるプログラムであって、
コンピュータに、
各搬送機をそれが搬送すべき被搬送物にそれぞれ割り付けさせるステップと、
各搬送機別にそれぞれ、当該搬送開始位置から搬送目的位置までの各搬送路がそれぞれ交差する複数の交差位置間の通行による搬送目的位置までの搬送のし易さを示す値を、各交差位置間の距離を用いて求め、求めた各値に基づいて、相対的に搬送し易い交差位置を順次選択して最適搬送経路を生成させるステップと、生成された最適搬送経路の方向及び前記値に基づいて、前記最適搬送経路を構成する交差位置とは異なる交差位置を含み、相対的に搬送し易い交差位置を選択して前記最適搬送経路とは異なる１又は複数の次善搬送経路を生成させる次善搬送経路生成ステップと、生成された最適搬送経路及び１又は複数の次善搬送経路を含む複数の搬送機別搬送経路群を得させるステップと、
各搬送機別搬送経路群からそれぞれ、そこに含まれる最適搬送経路及び次善搬送経路の内の任意の搬送経路を選択させる搬送経路選択ステップと、任意の搬送経路が選択される都度、当該搬送経路を構成する各交差位置間で搬送機を待機させるべく予め設定された複数の待機時間から任意の待機時間を選択し、選択した待機時間を当該搬送経路を構成する１又は複数の交差位置間に設定させて搬送計画候補を生成させる搬送計画候補生成ステップとを備え、
前記搬送経路選択ステップで任意の搬送経路が選択される都度、搬送計画候補生成ステップが搬送計画候補を生成させる操作を繰り返させて搬送計画候補群とし、これらの操作を複数回行わせて、待機時間及び／又は待機時間を設定した交差位置間が異なる複数の搬送計画候補群を得させるようになしてあり、
更に、得られた各搬送計画候補群それぞれについて、同じ時刻に同じ交差位置間に複数の搬送機が存在する回数、及び、搬送開始位置から搬送目的位置まで被搬送物を搬送するに要する時間に基づいて適合度を算出させるに当たって、前記回数が少ないほど、また前記時間が短いほど高い値の適合度を算出させる適合度算出ステップと、算出された各適合度の値を比較し、その比較結果に基づいて、前記複数の搬送計画候補群からより適合度が高い至適な搬送計画候補群を選択させる至適搬送計画候補群選択ステップと、選択された搬送計画候補群を構成する各搬送計画候補をそれぞれ搬送計画とさせるステップと
を備え、コンピュータに搬送計画を策定させることを特徴とするコンピュータプログラム。
【請求項１５】
前記各搬送路上の複数位置にはそれぞれ、前記交差位置であるノードが設定されており、相隣るノード間にそれぞれ両ノード間の距離に応じて、両ノード間における搬送機の通り易さである重みが予め設定されており、
コンピュータに、
これら重みを次の（１）式及び（２）式に適用して、搬送目的位置から位置を隔てる順に、相隣るノード間の通行による搬送目的位置までの搬送のし易さの値であって、その値が小さいほど搬送し易いと判断されるＱ値をそれぞれ算出させるステップを備え、
前記次善搬送経路生成ステップは、
当該次善搬送経路を構成すべき候補ノードに相隣る１又は複数のノードから任意のノードを選択させて第１のノードとさせるステップと、前記候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであるか否かを判断させる方向判断ステップと、同じ方向でない場合、候補ノードと第１のノードとの間のＱ値を特定させる現在ノードＱ値特定ステップと、第１のノードに相隣る１又は複数のノードから任意のノードを指定させて第２のノードとさせるノード指定ステップと、第１のノードと第２のノードとの間のＱ値を特定させる指定ノードＱ値特定ステップと、前者のＱ値より後者のＱ値の方が小さい場合、第１のノードを候補ノードとさせる候補ノード決定ステップと
を具備する
請求項１４記載のコンピュータプログラム。
【数７】
0006695653.tif 000009
【請求項１６】
コンピュータに、
更に、前記指定ノードＱ値特定ステップにて、第１のノードと第２のノードとの間のＱ値を特定させるに先立って、前記第２のノードが第１のノードを選択させた際の候補ノードと同じ位置であるか否かを判断させるステップを備え、
同じ位置である場合、前記指定ノードＱ値特定ステップは第１のノードと第２のノードとの間のＱ値を特定させることなく、前記ノード指定ステップは第１のノードに相隣る他のノードを指定させるようになしてある
請求項１５記載のコンピュータプログラム。
【請求項１７】
コンピュータに、
前記方向判断ステップにて候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであると判断された場合、前記現在ノードＱ値特定ステップが候補ノードと第１のノードとの間のＱ値を特定させることなく、前記候補ノード決定ステップは第１のノードを候補ノードとさせるようになしてある請求項１５又は１６記載のコンピュータプログラム。
【請求項１８】
前記至適搬送計画候補群選択ステップは、
コンピュータに、
得られた各搬送計画候補群をその適合度の値に応じて順位付けさせる順位付ステップと、予め定めた順位より低い順位の各搬送計画候補群に対して、各搬送計画候補群に含まれる各搬送経路を２つのグループに分け、両グループから任意の搬送機に係る搬送計画候補をそれぞれ選択させて対とし、両搬送計画候補をそれぞれ構成する複数の交差位置間である搬送経路を入れ替えさせる交叉を、予め設定された交叉頻度回数に至るまで互いに交叉させる操作を全ての搬送機について行わせて、新しい搬送計画候補群をそれぞれ生成させ、及び／又は、各搬送計画候補群から任意の搬送計画候補を選択させ、各搬送計画候補群の各搬送経路を、選択させた搬送計画候補に含まれる各搬送経路に更新させた後、各搬送経路に設定された待機時間に遺伝的アルゴリズムを適用させて、予め設定された突然変異確率で異なる待機時間を生成させ、生成させた待機時間に更新させることによって、新しい搬送計画候補群をそれぞれ生成させる新搬送計画候補群生成ステップとを具備し、
前記順位付ステップは、予め定めた順位より高い順位の各搬送計画候補群及び生成された新しい各搬送計画候補群についてその適合度の値に応じて順位付けさせるようになしてあり、
前記新搬送計画候補群生成ステップが新しい搬送計画候補群をそれぞれ生成させ、前記順位付ステップが順位付けさせる操作を予め定めた回数だけ繰り返した後、より高い順位の搬送計画候補群を至適な搬送計画候補群とさせるステップを具備する
請求項１４から１７のいずれかに記載のコンピュータプログラム。
【請求項１９】
前記適合度算出ステップは、コンピュータに、次の（３）式に基づいて適合度を算出させるようになしてある請求項１４から１８のいずれかに記載のコンピュータプログラム。
【数８】
0006695653.tif 000010
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の搬送開始位置から目的位置へそれぞれ被搬送物を搬送するに際して、各搬送開始位置から目的位置への搬送計画を策定する方法、そのような搬送計画を策定する装置、及び該搬送計画策定装置を備え、策定された搬送計画に基づいて複数の搬送開始位置から目的位置へそれぞれ被搬送物を搬送する搬送システム、並びにコンピュータに搬送計画の策定を実行させるコンピュータプログラムに関する。
【背景技術】
【０００２】
物流の拠点として機能している物流倉庫にあっては、入庫する複数の被搬送物に対応して柔軟に、かつ効率良く再配置して出庫させることが要求されている。この要求に応えるため、自律走行可能な複数の搬送機を導入して、各搬送機によって物流倉庫内の複数の搬送開始位置から再配置先である目的位置へ被搬送物をそれぞれ搬送することが検討されているが、かかる物流倉庫においては各搬送開始位置及び目的位置が共に変動するため、高効率な搬送計画を短時間で策定することが重要である。そのため、後記する特許文献１には次のような方法が開示されている。
【０００３】
すなわち、各搬送開始位置と目的位置との間に複数のノードを予め定めておき、相隣るノード間を結んでなる複数の搬送経路候補をそれぞれ作成して初期解集団を得る。このとき、時間制約の無いノードを時間制約のあるノードより優先させて搬送経路候補を作成する。そして、得られた初期解集団の各搬送経路候補について遺伝的アルゴリズムを適用して改良をくり返すことによって、時間制約を充足し、かつ総距離がより短い搬送経路を作成する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００３−１５７３１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、このような従来の方法にあっては、作成された各搬送経路上において、共通する２つのノード間に複数の搬送機が重畳する、所謂渋滞が生じた場合に、これに対応することができないため、全体として搬送効率が低下していた。
【０００６】
本発明は斯かる事情に鑑みてなされたものであって、搬送経路上で複数の搬送機間による渋滞が生じる場合であっても、各搬送機が全体としてより高い効率で被搬送物を搬送することができる搬送計画を策定する方法、そのような搬送計画を策定する装置、及び該搬送計画策定装置を備え、策定された搬送計画に基づいて複数の搬送開始位置から搬送目的位置へ搬送機にてそれぞれ被搬送物を搬送する搬送システム、並びにコンピュータに搬送計画の策定を実行させるコンピュータプログラムを提供する。
【課題を解決するための手段】
【０００７】
（１）本発明に係る搬送計画策定方法は、複数の搬送路上の互いに異なる複数の搬送開始位置にそれぞれ配置された被搬送物をいずれかの搬送路上に設定された搬送目的位置へ、各搬送路上を移動し得る複数の搬送機によって各別に搬送する計画を策定する場合、各搬送機をそれが搬送すべき被搬送物にそれぞれ割り付け、各搬送機別にそれぞれ、当該搬送開始位置から搬送目的位置までの距離に基づいて最適搬送経路を生成し、生成した最適搬送経路の方向及び搬送経路における搬送のし易さを示す値に基づいて、前記最適搬送経路とは異なる１又は複数の次善搬送経路を生成して、前記最適搬送経路及び１又は複数の次善搬送経路を含む複数の搬送機別搬送経路群を得、各搬送機別搬送経路群からそれぞれ、そこに含まれる最適搬送経路及び次善搬送経路の内の任意の搬送経路を選択し、任意の搬送経路を選択する都度、当該搬送経路上の中途位置で搬送機を待機させるべく予め定めた複数の待機時間から任意の待機時間を選択し、選択した待機時間を当該搬送経路上の１又は複数の中途位置に設定して搬送計画候補を生成する操作を繰り返して搬送計画候補群とし、これらの操作を複数回行って、待機時間の設定が異なる複数の搬送計画候補群を得、得られた各搬送計画候補群それぞれについて、同じ時刻に同じ搬送経路上に複数の搬送機が存在するか否か、及び搬送開始位置から搬送目的位置まで被搬送物を搬送するに要する時間に基づいて適合度を算出し、算出された各適合度の値を比較し、その比較結果に基づいて、前記複数の搬送計画候補群から至適な搬送計画候補群を選択し、選択した搬送計画候補群を構成する各搬送計画候補をそれぞれ搬送計画とすることを特徴とする。
【０００８】
（２）また、本発明に係る搬送計画策定方法は、前記各搬送路上の複数位置にはそれぞれノードが設定されており、相隣るノード間にそれぞれ両ノード間の距離に応じた重みを予め設定しておき、これら重みを後述する（１）式及び（２）式に適用して、搬送目的位置から位置を隔てる順に相隣るノード間における通行による搬送目的位置までの搬送のし易さを示すＱ値をそれぞれ算出し、次善搬送経路を生成する場合、当該次善搬送経路を構成すべき候補ノードに相隣る１又は複数のノードから任意のノードを選択して第１のノードとし、前記候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであるか否かを判断し、同じ方向でない場合、候補ノードと第１のノードとの間のＱ値を特定し、第１のノードに相隣る１又は複数のノードから任意のノードを指定して第２のノードとし、第１のノードと第２のノードとの間のＱ値を特定し、前者のＱ値より後者のＱ値の方が小さい場合、第１のノードを候補ノードとすることを特徴とする。
【０００９】
（３）更に、本発明に係る搬送計画策定方法は、第１のノードと第２のノードとの間のＱ値を特定するに先立って、前記第２のノードが第１のノードを選択した際の候補ノードと同じ位置であるか否かを判断し、同じ位置である場合、第１のノードと第２のノードとの間のＱ値を特定することなく、第１のノードに相隣る他のノードを指定することを特徴とする。
【００１０】
（４）一方、本発明に係る搬送計画策定方法は、前記候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じである場合、候補ノードと第１のノードとの間のＱ値を特定することなく、第１のノードを候補ノードとすることを特徴とする。
【００１１】
（５）また、本発明に係る搬送計画策定方法は、至適な搬送計画候補群を選択する場合、得られた各搬送計画候補群をその適合度の値に応じて順位付けし、予め定めた順位より低い順位の各搬送計画候補群に対して、各搬送計画候補群に含まれる各搬送経路を、予め設定された交叉頻度回数に至るまで互いに交叉させて、新しい搬送計画候補群をそれぞれ生成し、及び／又は、各搬送計画候補群から任意の搬送計画候補を選択し、各搬送計画候補群の各搬送経路を、選択した搬送計画候補に含まれる各搬送経路に更新した後、各搬送経路に設定された待機時間を予め定めた突然変異確率で更新して、新しい搬送計画候補群をそれぞれ生成し、予め定めた順位より高い順位の各搬送計画候補群及び生成した新しい各搬送計画候補群についてその適合度の値に応じて順位付けする操作を、予め定めた回数だけ繰り返した後、より高い順位の搬送計画候補群を至適な搬送計画候補群とすることを特徴とする。
【００１２】
（６）ところで、本発明に係る搬送計画策定方法は、前記適合度は、後述する（３）式を用いて算出することを特徴とする。
【００１３】
（７）本発明に係る搬送計画策定装置は、複数の搬送路上の互いに異なる複数の搬送開始位置にそれぞれ配置された被搬送物をいずれかの搬送路上に設定された搬送目的位置へ、各搬送路上を移動し得る複数の搬送機によって各別に搬送する計画を策定する場合、各搬送機をそれが搬送すべき被搬送物にそれぞれ割り付ける手段と、各搬送機別にそれぞれ、当該搬送開始位置から搬送目的位置までの距離に基づいて最適搬送経路を生成する手段と、生成した最適搬送経路の方向及び搬送経路における搬送のし易さを示す値に基づいて、前記最適搬送経路とは異なる１又は複数の次善搬送経路を生成して、前記最適搬送経路及び１又は複数の次善搬送経路を含む複数の搬送機別搬送経路群を得る手段と、各搬送機別搬送経路群からそれぞれ、そこに含まれる最適搬送経路及び次善搬送経路の内の任意の搬送経路を選択する搬送経路選択手段と、任意の搬送経路を選択する都度、当該搬送経路上の中途位置で搬送機を待機させるべく予め定めた複数の待機時間から任意の待機時間を選択し、選択した待機時間を当該搬送経路上の１又は複数の中途位置に設定して搬送計画候補を生成する搬送計画候補生成手段とを備え、前記搬送経路選択手段が任意の搬送経路を選択する都度、搬送計画候補生成手段が搬送計画候補を生成する動作を繰り返して搬送計画候補群とし、これらの動作を複数回行って、待機時間の設定が異なる複数の搬送計画候補群を得るようになしてあり、更に、得られた各搬送計画候補群それぞれについて、同じ時刻に同じ搬送経路上に複数の搬送機が存在するか否か、及び搬送開始位置から搬送目的位置まで被搬送物を搬送するに要する時間に基づいて適合度を算出する適合度算出手段と、算出された各適合度の値を比較し、その比較結果に基づいて、前記複数の搬送計画候補群から至適な搬送計画候補群を選択する至適搬送計画候補群選択手段と、選択された搬送計画候補群を構成する各搬送計画候補をそれぞれ搬送計画とする手段とを備えることを特徴とする。
【００１４】
（８）また、本発明に係る搬送計画策定装置は、前記各搬送路上の複数位置にはそれぞれノードが設定されており、相隣るノード間にそれぞれ両ノード間の距離に応じた重みが予め設定されており、これら重みを予め設定された後述する（１）式及び（２）式に適用して、搬送目的位置から位置を隔てる順に相隣るノード間における通行による搬送目的位置までの搬送のし易さを示すＱ値をそれぞれ算出する手段を備え、前記次善搬送経路生成手段は、当該次善搬送経路を構成すべき候補ノードに相隣る１又は複数のノードから任意のノードを選択して第１のノードとする手段と、前記候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであるか否かを判断する方向判断手段と、同じ方向でない場合、候補ノードと第１のノードとの間のＱ値を特定する現在ノードＱ値特定手段と、第１のノードに相隣る１又は複数のノードから任意のノードを指定して第２のノードとするノード指定手段と、第１のノードと第２のノードとの間のＱ値を特定する指定ノードＱ値特定手段と、前者のＱ値より後者のＱ値の方が小さい場合、第１のノードを候補ノードとする候補ノード決定手段とを具備することを特徴とする。
【００１５】
（９）本発明に係る搬送計画策定装置は、更に、前記指定ノードＱ値特定手段が、第１のノードと第２のノードとの間のＱ値を特定するに先立って、前記第２のノードが第１のノードを選択した際の候補ノードと同じ位置であるか否かを判断する手段を備え、同じ位置である場合、前記指定ノードＱ値特定手段は第１のノードと第２のノードとの間のＱ値を特定することなく、前記ノード指定手段は第１のノードに相隣る他のノードを指定するようになしてあることを特徴とする。
【００１６】
（１０）一方、本発明に係る搬送計画策定装置は、前記方向判断手段が候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであると判断した場合、前記現在ノードＱ値特定手段が候補ノードと第１のノードとの間のＱ値を特定することなく、前記候補ノード決定手段は第１のノードを候補ノードとするようになしてあることを特徴とする。
【００１７】
（１１）ところで、本発明に係る搬送計画策定装置は、前記至適搬送計画候補群選択手段は、得られた各搬送計画候補群をその適合度の値に応じて順位付けする順位付手段と、予め定めた順位より低い順位の各搬送計画候補群に対して、各搬送計画候補群に含まれる各搬送経路を、予め設定された交叉頻度回数に至るまで互いに交叉させて、新しい搬送計画候補群をそれぞれ生成し、及び／又は、各搬送計画候補群から任意の搬送計画候補を選択し、各搬送計画候補群の各搬送経路を、選択した搬送計画候補に含まれる各搬送経路に更新した後、各搬送経路に設定された待機時間を予め定めた突然変異確率で更新して、新しい搬送計画候補群をそれぞれ生成する新搬送計画候補群生成手段とを具備し、前記順位付手段は、予め定めた順位より高い順位の各搬送計画候補群及び生成した新しい各搬送計画候補群についてその適合度の値に応じて順位付けするようになしてあり、前記新搬送計画候補群生成手段が新しい搬送計画候補群をそれぞれ生成し、前記順位付手段が順位付けする動作を予め定めた回数だけ繰り返した後、より高い順位の搬送計画候補群を至適な搬送計画候補群とする手段を具備することを特徴とする。
【００１８】
（１２）また、本発明に係る搬送計画策定装置は、前記適合度算出手段は、予め設定された後述する（３）式に基づいて適合度を算出するようになしてあることを特徴とする。
【００１９】
（１３）本発明に係る搬送システムは、複数の搬送路と、各搬送路上を移動し得る複数の搬送機と、前記（７）から（１２）のいずれかに記載の搬送計画策定装置と、該搬送計画策定装置が作成した搬送計画を各搬送機へ送信する送信器とを備えることを特徴とする。
【００２０】
（１４）本発明に係るコンピュータプログラムは、コンピュータに、複数の搬送路上の互いに異なる複数の搬送開始位置にそれぞれ配置された被搬送物をいずれかの搬送路上に設定された搬送目的位置へ、各搬送路上を移動し得る複数の搬送機によって各別に搬送する計画を策定させるプログラムであって、コンピュータに、各搬送機をそれが搬送すべき被搬送物にそれぞれ割り付けさせるステップと、各搬送機別にそれぞれ、当該搬送開始位置から搬送目的位置までの距離に基づいて最適搬送経路を生成させるステップと、生成された最適搬送経路の方向及び搬送経路における搬送のし易さを示す値に基づいて、前記最適搬送経路とは異なる１又は複数の次善搬送経路を生成させる次善搬送経路生成ステップと、生成された最適搬送経路及び１又は複数の次善搬送経路を含む複数の搬送機別搬送経路群を得させるステップと、各搬送機別搬送経路群からそれぞれ、そこに含まれる最適搬送経路及び次善搬送経路の内の任意の搬送経路を選択させる搬送経路選択ステップと、任意の搬送経路が選択される都度、当該搬送経路上の中途位置で搬送機を待機させるべく予め定めた複数の待機時間から任意の待機時間を選択し、選択した待機時間を当該搬送経路上の１又は複数の中途位置に設定させて搬送計画候補を生成させる搬送計画候補生成ステップとを備え、前記搬送経路選択ステップで任意の搬送経路が選択される都度、搬送計画候補生成ステップが搬送計画候補を生成させる操作を繰り返させて搬送計画候補群とし、これらの操作を複数回行わせて、待機時間の設定が異なる複数の搬送計画候補群を得させるようになしてあり、更に、得られた各搬送計画候補群それぞれについて、同じ時刻に同じ搬送経路上に複数の搬送機が存在するか否か、及び搬送開始位置から搬送目的位置まで被搬送物を搬送するに要する時間に基づいて適合度を算出させる適合度算出ステップと、算出された各適合度の値を比較し、その比較結果に基づいて、前記複数の搬送計画候補群から至適な搬送計画候補群を選択させる至適搬送計画候補群選択ステップと、選択された搬送計画候補群を構成する各搬送計画候補をそれぞれ搬送計画とさせるステップとを備え、コンピュータに搬送計画を策定させることを特徴とする。
【００２１】
（１５）また、本発明に係るコンピュータプログラムは、前記各搬送路上の複数位置にはそれぞれノードが設定されており、相隣るノード間にそれぞれ両ノード間の距離に応じた重みが予め設定されており、コンピュータに、これら重みを後述する（１）式及び（２）式に適用して、搬送目的位置から位置を隔てる順に相隣るノード間における通行による搬送目的位置までの搬送のし易さを示すＱ値をそれぞれ算出させるステップを備え、前記次善搬送経路生成ステップは、当該次善搬送経路を構成すべき候補ノードに相隣る１又は複数のノードから任意のノードを選択させて第１のノードとさせるステップと、前記候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであるか否かを判断させる方向判断ステップと、同じ方向でない場合、候補ノードと第１のノードとの間のＱ値を特定させる現在ノードＱ値特定ステップと、第１のノードに相隣る１又は複数のノードから任意のノードを指定させて第２のノードとさせるノード指定ステップと、第１のノードと第２のノードとの間のＱ値を特定させる指定ノードＱ値特定ステップと、前者のＱ値より後者のＱ値の方が小さい場合、第１のノードを候補ノードとさせる候補ノード決定ステップとを具備することを特徴とする。
【００２２】
（１６）本発明に係るコンピュータプログラムは、コンピュータに、更に、前記指定ノードＱ値特定ステップにて、第１のノードと第２のノードとの間のＱ値を特定させるに先立って、前記第２のノードが第１のノードを選択させた際の候補ノードと同じ位置であるか否かを判断させるステップを備え、同じ位置である場合、前記指定ノードＱ値特定ステップは第１のノードと第２のノードとの間のＱ値を特定させることなく、前記ノード指定ステップは第１のノードに相隣る他のノードを指定させるようになしてあることを特徴とする。
【００２３】
（１７）一方、本発明に係るコンピュータプログラムは、コンピュータに、前記方向判断ステップにて候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであると判断された場合、前記現在ノードＱ値特定ステップが候補ノードと第１のノードとの間のＱ値を特定させることなく、前記候補ノード決定ステップは第１のノードを候補ノードとさせるようになしてあることを特徴とする。
【００２４】
（１８）ところで、本発明に係るコンピュータプログラムは、前記至適搬送計画候補群選択ステップは、コンピュータに、得られた各搬送計画候補群をその適合度の値に応じて順位付けさせる順位付ステップと、予め定めた順位より低い順位の各搬送計画候補群に対して、各搬送計画候補群に含まれる各搬送経路を、予め設定された交叉頻度回数に至るまで互いに交叉させて、新しい搬送計画候補群をそれぞれ生成させ、及び／又は、各搬送計画候補群から任意の搬送計画候補を選択させ、各搬送計画候補群の各搬送経路を、選択された搬送計画候補に含まれる各搬送経路に更新させた後、各搬送経路に設定された待機時間を予め定めた突然変異確率で更新させて、新しい搬送計画候補群をそれぞれ生成させる新搬送計画候補群生成ステップとを具備し、前記順位付ステップは、予め定めた順位より高い順位の各搬送計画候補群及び生成された新しい各搬送計画候補群についてその適合度の値に応じて順位付けさせるようになしてあり、前記新搬送計画候補群生成ステップが新しい搬送計画候補群をそれぞれ生成させ、前記順位付ステップが順位付けさせる操作を予め定めた回数だけ繰り返した後、より高い順位の搬送計画候補群を至適な搬送計画候補群とさせるステップを具備することを特徴とする。
【００２５】
（１９）本発明に係るコンピュータプログラムは、前記適合度算出ステップは、コンピュータに、後述する（３）式に基づいて適合度を算出させるようになしてあることを特徴とする。
【００２６】
（１）、（７）、（１３）及び（１４）の発明にあっては、複数の搬送路上の互いに異なる複数の搬送開始位置にそれぞれ配置された被搬送物をいずれかの搬送路上に設定された搬送目的位置へ、各搬送路上を移動し得る複数の搬送機によって各別に搬送する計画を策定する場合、各搬送機をそれが搬送すべき被搬送物にそれぞれ割り付け、各搬送機別にそれぞれ、当該搬送開始位置から搬送目的位置までの最適搬送経路を生成する。ここで、最適搬送経路は搬送開始位置から搬送目的位置までの最短経路とすることができる。
【００２７】
また、生成した最適搬送経路に基づいて１又は複数の次善搬送経路を生成する。次善搬送経路は、搬送開始位置から搬送目的位置までの最短経路ではないが、搬送開始位置と搬送目的位置との間に設定することができる複数の経路の内、例えば距離といった基準及び対応する最適搬送経路の方向等に基づいて、より通行し易い経路を求めることによって定めることができる。このように各搬送機別に最適搬送路及び１又は複数の次善搬送経路を生成することによって、複数の搬送機別搬送経路群を得る。
【００２８】
次に、各搬送機別搬送経路群からそれぞれ最適搬送経路又は次善搬送経路を選択し、最適搬送経路又は次善搬送経路を選択する都度、当該搬送経路である最適搬送経路又は次善搬送経路上の１又は複数の中途位置に待機時間を設定して搬送計画候補を生成する操作を繰り返して搬送計画候補群とする。これらの操作を複数回行って複数の搬送計画候補群を得る。即ち、１つの搬送計画候補群は、各搬送機にそれぞれ対応する各搬送計画候補によって構成されており、搬送計画候補は当該搬送機に対応する最適搬送経路又は次善搬送経路と、当該最適搬送経路又は次善搬送経路上の１又は複数の中途位置に設定された待機時間によって構成されている。
【００２９】
このようにして得られた各搬送計画候補群それぞれについて、予め定めた基準に対する適合度を算出し、算出された適合度を用いて各搬送計画候補群から至適な搬送計画候補群を探索する。そして、探索された搬送計画候補群を構成する各搬送計画候補をそれぞれ搬送計画とする。
【００３０】
このように搬送計画候補群を構成する各搬送計画候補は、最適搬送経路以外に１又は複数の次善搬送経路が含まれ、更に最適搬送経路及び次善搬送経路上の１又は複数の中途位置に待機時間が設定してあり、かかる複数の搬送計画候補群から至適な搬送計画候補群を選択するため、搬送経路上で複数の搬送機間による渋滞が生じる場合であっても、各搬送機が全体としてより高い効率で被搬送物を搬送することができる搬送計画を策定することができる。ここで、同じ時刻に同じ搬送経路上に複数の搬送機が存在する場合は適合度を低くし、逆に、同じ時刻に同じ搬送経路上に複数の搬送機が存在する場合は適合度を高くする。また、搬送開始位置から搬送目的位置まで被搬送物を搬送するに要する時間が短い程、適合度を高くするようになっている。従って、搬送経路上で複数の搬送機間による渋滞が生じる場合であっても、各搬送機が全体としてより短い時間で被搬送物を搬送し得る搬送計画を策定することができる。
【００３１】
（２）、（８）、（１３）及び（１５）の発明にあっては、前述した各搬送路上の複数位置にはそれぞれノードが設定されており、搬送機はいずれかのノードを経由して搬送開始位置から搬送目的位置まで移動するようになっている。
【００３２】
相隣るノード間にそれぞれ両ノード間の距離に応じた重みを予め設定しておき、これら重みを用いて、搬送目的位置から位置を隔てる順に相隣るノード間における通行による搬送目的位置までの搬送のし易さを示すＱ値をそれぞれ算出する。これによって、搬送目的位置に応じたＱ値が求められる。このＱ値を用いて次善搬送経路を次のように生成する。
【００３３】
当該次善搬送経路を構成すべき候補ノードに相隣る１又は複数のノードから任意のノードを選択して第１のノードとし、前記候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じであるか否かを判断する。候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と異なる場合、候補ノードと第１のノードとの間のＱ値を特定した後、第１のノードに相隣る１又は複数のノードから任意のノードを指定して第２のノードとする。そして、第１のノードと第２のノードとの間のＱ値を特定し、前者のＱ値より後者のＱ値の方が小さい場合、第１のノードを候補ノードとする。かかる操作を搬送開始位置から搬送目的位置に達するまで繰り返し実施し、各候補ノードを結ぶことによって次善搬送経路が生成される。
【００３４】
候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と異なる場合、当該搬送経路は最短経路に比べて冗長な経路であるが、前述したように候補ノードと第１のノードとの間のＱ値より第１のノードと第２のノードとの間のＱ値の方が小さい場合に、第１のノードを候補ノードとするため、更に冗長な経路が生成されることが回避され、従ってより適正な次善搬送経路を効率良く生成することができる。
【００３５】
（３）、（９）、（１３）及び（１６）の発明にあっては、第１のノードと第２のノードとの間のＱ値を特定するに先立って、前述したように第２のノードが第１のノードを選択した際の候補ノードと同じ位置であるか否かを判断する。即ち、候補ノードから第１のノードを経て、再び前記候補ノードへ戻る経路であるか否かを判断するのである。そして、同じ位置である場合はそのような経路を破棄すべく、第１のノードと第２のノードとの間のＱ値を特定することなく、第１のノードに相隣る他のノードを指定するのである。これによって、同じノード間を往復するような低効率の次善搬送経路が生成されることを回避することができる。
【００３６】
（４）、（１０）、（１３）及び（１７）の発明にあっては、前述した候補ノードから第１のノードへの方向が、対応する最適搬送経路の方向と同じである場合は、搬送効率が高い最適搬送経路に対応する経路が生成されるため、候補ノードと第１のノードとの間のＱ値を特定することなく、第１のノードを候補ノードとするのである。これによって、次善搬送経路を効率良く生成することができる。
【００３７】
（５）、（１１）、（１３）及び（１８）の発明にあっては、至適な搬送計画候補群を次のように探索する。すなわち、前述した如く得られた各搬送計画候補群別に適合度をそれぞれ求め、得られた適合度の値に応じて各搬送計画候補群を順位付けする。次に、予め定めた順位より低い順位の各搬送計画候補群に対して遺伝的アルゴリズムを適用して新しい搬送計画候補群をそれぞれ生成する。遺伝的アルゴリズムとしては遺伝子交叉及び／又は遺伝子突然変異を用いることができる。
【００３８】
新しい搬送計画候補群を生成すると、予め定めた順位より高い順位の各搬送計画候補群及び生成した新しい各搬送計画候補群についてそれぞれ適合度を求め、得られた適合度の値に応じて各搬送計画候補群順位付けする。このような操作を、予め定めた回数だけ繰り返した後、より高い順位の搬送計画候補群を至適な搬送計画候補群とする。
【００３９】
このように、予め定めた順位より低い順位の各搬送計画候補群に対して遺伝的アルゴリズムを適用して新しい搬送計画候補群を生成し、高順位の搬送計画候補群と共に再び順位付けするため、より高効率の搬送計画を比較的容易に生成することができる。
【００４０】
（６）、（１２）、（１３）及び（１９）の発明にあっては、後述する（３）式に基づいて適合度を算出するため、前同様、同じ時刻に同じ搬送経路上に複数の搬送機が存在する場合は適合度を低くし、逆に、同じ時刻に同じ搬送経路上に複数の搬送機が存在する場合は適合度を高くする。また、搬送開始位置から搬送目的位置まで被搬送物を搬送するに要する時間が短い程、適合度を高くするようになっている。従って、搬送経路上で複数の搬送機間による渋滞が生じる場合であっても、各搬送機が全体としてより短い時間で被搬送物を搬送し得る搬送計画を策定することができる。
【図面の簡単な説明】
【００４１】
【図１】本発明に係る搬送システムの構成を説明する説明図である。
【図２】図１に示した搬送計画策定装置の構成を示すブロック図である。
【図３】図１に示した搬送機の構成を示すブロック図である。
【図４】相隣るノード間に設定される重みの一例を説明する説明図である。
【図５】図４に示した搬送経路及び重みを用いてＱ値を繰り返し算出する途中結果を示す表である。
【図６】搬送計画候補の生成方法を説明する説明図である。
【図７】図２に示した搬送計画策定部による搬送計画の策定手順を示すフローチャートである。
【図８】至適な搬送計画群を探索する手順を示すフローチャートである。
【図９】至適な搬送計画群を探索する手順を示すフローチャートである。
【図１０】至適な搬送計画群を探索する手順を示すフローチャートである。
【図１１】図８に示した最適搬送経路の探索手順を示すフローチャートである。
【図１２】図８に示した次善搬送経路の探索手順を示すフローチャートである。
【図１３】図８に示した次善搬送経路の探索手順を示すフローチャートである。
【図１４】図８に示した次善搬送経路の探索手順を示すフローチャートである。
【発明を実施するための形態】
【００４２】
以下、本発明を図面に基づいて詳細に説明する。なお、本実施の形態で説明する搬送計画策定に関する方法及び装置、搬送システム並びにコンピュータプログラムは、本発明の趣旨を説明する一例であり、本発明はその趣旨を逸脱しない範囲での変形を含むことはいうまでもない。
【００４３】
図１は本発明に係る搬送システムの構成を説明する説明図であり、図中、Ｗは物流倉庫である。物流倉庫Ｗ内には被搬送物を搬送する複数の搬送機２，２，…が設置してあり、この物流倉庫Ｗの床部Ｆ上には搬送機２，２，…が通行する複数の搬送路３０，３０，…が格子状に設けてある。
【００４４】
本実施の形態にあっては、１又は複数の被搬送物が、複数の収納棚を縦方向へ積層させてなるラックＲ内に収納されており、搬送機２はラックＲの最下段の収納棚の底部と床部Ｆとの間を挿通し得る高さ寸法になしてある。
【００４５】
この搬送機２には、障害物を検出するセンサ、位置情報を読み込む読込部、並びにバッテリ、モータ、駆動輪及びキャスタを含む駆動部が設けてあり、またこれらの動作を制御するＣＰＵが内蔵してある。センサから出力される検出信号、読込部が読み込んだ位置情報はＣＰＵに与えられるようになっており、ＣＰＵは与えられた検出信号及び位置情報を用いて、モータを介して駆動輪を駆動・停止させるとともに、キャスタの向きを制御することによって、搬送機２が所定の方向へ自律走行し得るようになっている。
【００４６】
一方、搬送機２の天井は昇降可能になしてラックＲを担持する担持部２２になっており、搬送機２はラックＲの最下段の収納棚の底部と床部Ｆとの間に進入したときに担持部２２を上昇させてラックＲ及び当該ラックＲに収納された被搬送物を担持し、その状態で移動することによって被搬送物を搬送し、予め定められた搬送目的位置で移動停止し、担持部２２を降下させることによって当該位置にラックＲ及び当該ラックＲに収納された被搬送物を当該搬送目的位置に再配置する。
【００４７】
前述した床部Ｆの各搬送路３０，３０，…が交差する各位置であるノードＮ，Ｎ，…にはそれぞれ、その位置に応じて定めたマーク又は電磁信号というように、当該位置情報を搬送機２へ付与する位置情報付与器４１，４１，…が配設してあり、各搬送機２，２，…には位置情報付与器４１，４１，…から付与される位置情報を読み込む読込部がそれぞれ設けてある。この読込部としては、例えば位置情報付与器４１から付与される位置情報がマークである場合にあっては前述した撮像器を適用することができる。この場合、撮像器で位置情報付与器４１に設定されたマークを撮像して得られた画像データから当該マークを識別し、予め各マーク別に設定された位置情報から当該マークに対応する位置情報を判定するのである。なお、位置情報付与器４１から付与される位置情報が電磁信号である場合、搬送機２にはそれに対応する読込部を設けておく。
【００４８】
物流倉庫Ｗ内の高位位置には送信器５０が配設してあり、送信器５０から、搬送機２，２，…の識別情報、搬送経路並びに待機位置及び待機時間を含む搬送計画が全ての搬送機２，２，…へ送信されるようになっている。搬送機２，２，…には受信部がそれぞれ設けてあり、搬送機２，２，…は受信部によって受信された搬送計画に基づいて、被搬送物２，２，…を目的位置まで搬送する。
【００４９】
一方、送信器５０には搬送機２，２，…による搬送計画を策定する搬送計画策定装置１から、後述するように搬送機２，２，…の識別情報及び当該搬送機２，２，…の搬送計画が与えられるようになっている。
【００５０】
なお、本実施の形態では、被搬送物を収納するラックＲ、及びこのラックＲを担持して当該ラックＲに収納された被搬送物を搬送する搬送機２を用いた場合について説明したが、本発明はこれに限られず、一又は複数の被収納物を搬送機で搬送できればいずれの構成であってもよい。また、本実施の形態では、自律走行することが可能な搬送機２を用いているが、レール又は信号等の誘導手段によって所定位置へ誘導される非自律型の搬送機を用いてもよいことはいうまでもない。
【００５１】
図２は図１に示した搬送計画策定装置１の構成を示すブロック図である。図２に示したように、搬送計画策定装置１は、キーボード、マウス等の入力部１１、モニタといった表示部１２、種々の情報を記憶するメモリ１３、各搬送機２，２，…の搬送計画を後述するようにして策定する搬送計画策定部１４、策定された搬送計画を前述した送信器５０（図１参照）へ出力する出力部１５、及びこれらの動作を制御するＣＰＵ１０を備えている。
【００５２】
前述したメモリ１３には、各搬送路３０，３０，…の構成、各ノードＮ，Ｎ，…の位置、及び相隣るノードＮ，Ｎ、Ｎ，Ｎ、…，…間に予め定められた重みを含む倉庫情報、被搬送物の種類及びそれらをそれぞれ収納したラックＲ，Ｒ，…の位置に係る被搬送物情報、搬送機２，２，…（いずれも図１参照）の識別情報を含む搬送機情報が入力部１１を介して記憶させてある。ＣＰＵ１０は、入力部１１から搬送計画の策定指令が入力されたか否かを判断し、当該指令が入力された場合、搬送計画策定部１４をして次のように各搬送機２，２，…の搬送計画を策定させる。
【００５３】
図７は、図２に示した搬送計画策定部１４による搬送計画の策定手順を示すフローチャートである。なお、そのような搬送計画を策定する手順はコンピュータプログラムとして搬送計画策定装置１に予め読み込ませてある。
【００５４】
搬送計画策定部１４は、搬送計画策定指令が与えられるとメモリ１３から倉庫情報、被搬送物情報及び搬送機情報を読み出した（ステップＳ１）後、これらの情報を用いて後述するように複数の搬送機２，２，…（図１参照）それぞれに割り当てるべき搬送経路、並びに待機位置及び待機時間を含む待機情報を備える複数の搬送計画候補群から至適な搬送計画群を探索し（ステップＳ２）、探索して得られた搬送計画群を構成する各搬送計画を対応する搬送機２，２，…にそれぞれ割り付ける（ステップＳ６）。そして、搬送計画策定部１４は、割り付けた搬送計画及び対応する搬送機２，２，…の識別情報をＣＰＵ１０に与えるようになっている（ステップＳ７）。
【００５５】
ＣＰＵ１０は搬送機２，２，…の識別情報及び当該搬送機に割り付けられた搬送計画が与えられると、それらを出力部１５を介して送信器５０から各搬送機２，２，…（いずれも図１参照）へ出力させる。
【００５６】
図３は図１に示した搬送機２の構成を示すブロック図である。図３に示したように、搬送機２は、送信器５０（図１参照）から送信される信号を受信する受信部２１と、情報を記憶するメモリ２５と、待機時間等を計測する計時部２６と、障害物を検出するためのセンサ２３と、ラックＲ及び被搬送物を担持する担持部２２と、位置情報を読み込む読込部２４と、バッテリ、モータ、駆動輪及びキャスタを含む駆動部２７と、これらの動作を制御するＣＰＵ２０とを備えており、送信器５０からの信号を受信部２１が受信すると、ＣＰＵ２０は予め設定された識別信号に対応する搬送計画をメモリ２５の所定領域に与えてそこに記憶させる。そして、ＣＰＵ２０は、計時部２６、センサ２３及び読込部２４からの情報を用いて、当該搬送計画に則した搬送経路並びに待機位置及び待機時間となるように駆動部２７及び担持部２２を制御し、ラックＲ及び被搬送物を搬送開始位置から搬送目的位置へ搬送・再配置する。
【００５７】
なお、本実施の形態では、障害物を検出するセンサ２３と、位置情報を読み込む読込部２４とを各別に設けた場合について説明したが、本発明はこれに限らず、例えば撮像器が撮像して得られた画像を処理することによって、障害物に係る情報と位置情報とを検出し得るように構成することによって、前記センサ２３と読込部２４とを兼用するようになしてもよい。
【００５８】
次に、図７に示したステップＳ２において至適な搬送計画群を探索する手順について詳細に説明する。
【００５９】
図８から図１０は、至適な搬送計画群を探索する手順を示すフローチャートである。図８に示したように、搬送計画策定部１４は、全搬送機２，２，…から搬送計画を策定すべき１又は複数の搬送機２，２，…の選定を促す画像をＣＰＵ１０を介して表示部１２に表示させ、搬送機２，２，…が選定されたと判断するまで待機する（ステップＳ２１，Ｓ２２）。搬送計画を策定すべき搬送機２，２，…が入力部１１を介して選定されると、搬送計画策定部１４は、選定された搬送機２，２，…の識別情報をメモリ１３の所定領域に与えてそこに記憶させる（ステップＳ２３）。次に、搬送計画策定部１４は、搬送先である搬送目的位置の入力を促す画像をＣＰＵ１０を介して表示部１２に表示させ、搬送目的位置が入力されたと判断するまで待機する（ステップＳ２４，Ｓ２５）。入力部１１を介して搬送目的位置が入力されると、搬送計画策定部１４は、搬送目的位置をメモリ１３の所定領域に与えてそこに記憶させた（ステップＳ２６）後、次のようにして各搬送機２，２，…別に最適搬送経路を探索する（ステップＳ３０）。
【００６０】
図１１は、図８に示した最適搬送経路の探索手順を示すフローチャートである。図１１に示したように、搬送計画策定部１４は、相隣るノードＮ，Ｎ、Ｎ，Ｎ、…，…間におけるＱ値の初期値として、Ｑ値としては存在しない程度に十分大きな数字、例えば１０００の入力を促す画像をＣＰＵ１０を介して表示部１２に表示させ（ステップＳ３０１）、当該初期値が入力されるまで待機する（ステップＳ３０２）。搬送計画策定部１４は、初期値が入力されると、その値を各ノードＮ，Ｎ、Ｎ，Ｎ、…，…間におけるＱ値の初期値として設定する（ステップＳ３０３）。搬送計画策定部１４は、メモリ１３に記憶された搬送目的位置及び、前述した倉庫情報を構成し、相隣るノードＮ，Ｎ、Ｎ，Ｎ、…，…間に予め設定された重みから、次の（１）式に従って、搬送目的位置へ被搬送物を搬送する場合における相隣る各ノードＮ，Ｎ、Ｎ，Ｎ、…，…間の通り易さ（コスト）であるＱ値をそれぞれ求める（ステップＳ３０４）。なお、Ｑ値の算出は、収束条件である次の（２）式が満足されるまで繰り返し実行する。
【００６１】
【数１】
0006695653.tif 000002
【００６２】
ここで、前述した相隣るノードＮ，Ｎ、Ｎ，Ｎ、…，…間に設定される重みについて説明する。
【００６３】
図４は、相隣るノードＮ，Ｎ、Ｎ，Ｎ、…，…間に設定される重みの一例を説明する説明図である。図４に示した場合にあっては、横長の長方形状になされた環状搬送路３５が設けてあり、この環状搬送路３５の縦方向の中央位置に環状搬送路３５の両短辺間を結ぶ中央搬送路３６が設けてある。また、環状搬送路３５の内部をその幅方向へ６等分するように環状搬送路３５両長辺間を結ぶ内部搬送路３７，３７，３７，３７，３７が設けてある。更に、環状搬送路３５の周囲にコ字状の外部搬送路３８が、その一縦搬送路３９が環状搬送路３５の一長辺の中央位置になるように設けてある。
【００６４】
これら環状搬送路３５、中央搬送路３６、内部搬送路３７，３７，３７，３７，３７、外部搬送路３８を構成する縦搬送路及び横搬送路が交差する位置がノードＮ，Ｎ，…であり、環状搬送路３５の左上の位置のノードＮから一段ずつ横方向へ順に連続番号が付してある。図４に示した場合にあっては、左上のノードＮが１番であり、外部搬送路３８の右下の位置が２３番である。
【００６５】
相隣るノードＮ，Ｎ、Ｎ，Ｎ、…，…間に設定される重みとは、相隣るノードＮ，Ｎ、Ｎ，Ｎ、…，…間における搬送機の通り易さ（コスト）であり、相隣るノードＮ，Ｎ間の距離、当該ノードＮ，Ｎ間での障害の程度、及び他の外部要因等によって定められる。図４に示した場合にあっては、１番のノードＮから２番のノードＮへ搬送する場合、２番のノードＮから１番のノードＮへ搬送する場合、及び２２番のノードＮから２３番のノードＮへ搬送する場合、両ノードＮ，Ｎ間の距離はいずれも２ブロック隔たっており、両ノードＮ，Ｎ間での障害及び他の外部要因も無いため、それぞれの重みは「２」に設定してある。同様に、１番のノードＮから８番のノードＮへ搬送する場合、８番のノードＮから１番のノードＮへ搬送する場合、及び１８番のノードＮから２２番のノードＮへ搬送する場合、各ノードＮ，Ｎ間の距離は４ブロック、４ブロック及び３ブロック隔たっており、各ノードＮ，Ｎ間での障害及び他の外部要因も無いため、それぞれの重みは「４」、「４」、「３」に設定してある。ここで、前述した各ブロックは、相隣るノードＮ，Ｎ間を予め定められた単位に従って分割して生成されるものとする。
【００６６】
一方、２２番のノードＮから１８番のノードＮへ搬送する場合、及び２３番のノードＮから２２番のノードＮへ搬送する場合、障害又は外部要因により搬送不可であるため、予め定められた最大値の重み（例えば、１０００）が設定してあり、これによって２２番のノードＮから１８番のノードＮへの搬送、２３番のノードＮから２２番のノードＮへの搬送は禁止される。
【００６７】
図５は、図４に示した搬送経路及び重みを用いてＱ値を繰り返し算出する途中結果を示す表である。ここで、最終的な搬送目的位置は２２番のノードとし、この２２番のノードのＱ値はゼロと定義する。
【００６８】
今、前記（１）式においてｎ＝０とすると、２２番のノードのＱ値を求めることになるため、前記定義よりＱ値はゼロであるので、表中、ノードが２２で向きが２２におけるＱ値として０が記入されている。
【００６９】
次に、前記（１）式においてｎ＝１とすると、２２番のノードに相隣る１８番及び２３番の各ノードが対象となり、算出すべきＱ値は、Ｑ（１８，２２）又はＱ（２３，２２）である。しかしながら、図４に示したように２３番のノードから２２番のノードへの搬送は禁止されているため、算出対象のＱ値は、Ｑ（１８，２２）のみとなる。Ｑ（１８，２２）は、（１）式から、１８番のノードと２２番のノードとの間の重みである３と、ＭｉｎＱ（２２，ｋ）の和として算出されるが、Ｑ（２２，ｋ）は最終的な目的位置である２２番のノードに該当するためＱ＝０しか存在せず、ＭｉｎＱ（２２，ｋ）＝０となり、従ってＱ（１８，２２）＝３＋０＝３が求められるため、表中、ノードが１８で向きが２２におけるＱ値として３が記入されている。
【００７０】
次に、（１）式においてｎ＝２とすると、１８番のノードに相隣る１７番、１９番及び１１番の各ノードが対象となるので、算出すべきＱ値は、Ｑ（１７，１８）、Ｑ（１９，１８）及びＱ（１１，１８）である。ここで、Ｑ（１７，１８）は、（１）式から、１７番のノードと１８番のノードとの間の重みである２と、ＭｉｎＱ（１８，ｋ）の和として算出される。ここで、１８番のノードのＱ値はＱ（１８，１１）、Ｑ（１８，１７）、Ｑ（１８，２２）、Ｑ（１８，１９）の４つが存在するが、ｎ＝１で求められたＱ（１８，２２）＝３以外には前述したように初期値として例えば１０００が設定されているため、これらの中で最小値は３であり、ＭｉｎＱ（１８，ｋ）＝３である。従ってＱ（１７，１８）＝２＋３＝５が求められるため、表中、ノードが１７で向きが１８におけるＱ値として５が記入される。
【００７１】
同様な計算を行うことによって、Ｑ（１９，１８）＝２＋３＝５が求められるため、表中、ノードが１９で向きが１８におけるＱ値として５が記入されている。
【００７２】
このような計算を、収束条件である（２）式が満足されるまで繰り返し実行することによって、相隣る各ノード間のＱ値をそれぞれ算出するのである。
【００７３】
このようにして相隣る各ノード間のＱ値がそれぞれ求められると、搬送計画策定部１４は、倉庫情報に含まれる全てのラックＲ，Ｒ，…（図１参照）のノードの位置を読み出したか否かを判断し（ステップＳ３０５）、読み出していないラックＲのノードの位置が存在する場合、読み出していないラックＲのノードの位置を読み出し（ステップＳ３０６）、当該ノードの位置が搬送目的位置であるか否かを判断する（ステップＳ３０７）。搬送計画策定部１４は、搬送目的位置でないと判断した場合、当該ノードに相隣る全てのノードの位置を認定し（ステップＳ３０８）、当該ノードとの間のＱ値がより小さいノードの位置を選択する（ステップＳ３０９）。搬送計画策定部１４は、当該ノードの位置が搬送目的位置であると判断するまで、ステップＳ３０７からステップＳ３０９までの操作を繰り返すことによって最適搬送経路を生成する。そして、搬送計画策定部１４は、このような操作をステップＳ３０５で読み出していないラックＲの位置が無いと判断するまで繰り返すことによって、全てのラックＲ，Ｒ，…に係る最適搬送経路を求める。
【００７４】
このようにして、各ラックＲ，Ｒ，…それぞれについて最適搬送経路を求めると、搬送計画策定部１４は、次のようにして次善搬送経路を探索する（ステップＳ５０）。
【００７５】
図１２から図１４は、図８に示した次善搬送経路の探索手順を示すフローチャートである。図１２に示したように、搬送計画策定部１４は、倉庫情報に基づいて、ラックＲ，Ｒ，…が配置された各ノードＮ，Ｎ，…（共に図１参照）の位置（以下、ノードの位置を単にノードという）を全て取得する（ステップＳ５０１）。
【００７６】
搬送計画策定部１４は、ラックＲ，Ｒ，…に対応する未選択のノードが存在するか否かを判断し（ステップＳ５０２）、未選択のノードが存在する場合、任意のノードを選択してそれを現在のノード（候補ノード）とする（ステップＳ５０３，Ｓ５０４）とともに、前記ステップＳ３０で求めた各最適搬送経路から、選択したノードに対応する最適搬送経路を特定する（ステップＳ５０５）。
【００７７】
次に、搬送計画策定部１４は、倉庫情報に基づいて、現在のノードに相隣るノードを全て特定する（ステップＳ５０６）。搬送計画策定部１４は、特定したノードについて未採択のノードが存在するか否かを判断し（ステップＳ５０７）、未採択のノードが存在する場合、特定したノードから任意のノードを採択する（ステップＳ５０８）。
【００７８】
搬送計画策定部１４は、現在のノードから前記採択したノード（第１のノード）への方向は、対応する最適搬送経路における現在のノードから相隣るノードへの方向と同じであるか否かを判断し（ステップＳ５０９）、同じ方向である場合は、前記採択したノードを候補ノードとする（ステップＳ５１０）。
【００７９】
一方、ステップＳ５０９で同じ方向ではないと判断した場合、図１３に示したように搬送計画策定部１４は、現在のノードと採択したノードとの間のＱ値を取得してこれをａとする（ステップＳ６０１）とともに、前記採択したノードに相隣るノードを全て認定する（ステップＳ６０２）。搬送計画策定部１４は、認定したノードについて未指定のノードが存在するか否かを判断し（ステップＳ６０３）、未指定のノードが存在する場合、任意のノードを指定する（ステップＳ６０４）。搬送計画策定部１４は、指定したノード（第２のノード）が現在のノードと同じであるか否かを判断し（ステップＳ６０５）、同じである場合、指定した当該ノードを候補から除外すべくステップＳ６０３へ戻って、未指定のノードが存在するか否かを判断する。これによって、同じ経路上を後戻りすることを回避することができ、搬送効率が明らかに低い次善搬送経路が生成されることを防止することができる。
【００８０】
搬送計画策定部１４は、ステップＳ６０５で指定したノードが現在のノードと異なると判断した場合、前記採択したノードと指定したノードとの間のＱ値を取得してこれをｂとし（ステップＳ６０６）、このｂが前記ａ未満であるか否かを判断する（ステップＳ６０７）。搬送計画策定部１４は、ｂがａ未満であった場合、ステップＳ５０８で採択したノードを候補ノードとする（ステップＳ６０８）一方、ｂがａ以上であった場合、指定した当該ノードを候補から除外すべくステップＳ６０３へ戻って、未指定のノードが存在するか否かを判断する。ステップＳ５０９において、最適搬送経路における現在のノードから相隣るノードへの方向と異なる方向のノードが採択されたと判断した場合、当該ノードを含む次善搬送経路は、最適搬送経路より冗長となっているが、このようにｂがａ未満である候補ノードを検出することによって、冗長さが積み増されることが防止することができ、より搬送効率が高い次善搬送経路を探索することができる。
【００８１】
搬送計画策定部１４は、ステップＳ６０３にて未指定のノードが存在しないと判断するまで、ステップＳ６０３〜ステップＳ６０８までの操作を繰り返す。なお、ステップＳ５０７にて採択されたノードによっては、ステップＳ６０７の条件を満足するノードが全く指定されない場合があり、かかる場合、採択されたノードは候補ノードから除外されることとなる。
【００８２】
ステップＳ５１０にて採択したノードを候補ノードにした場合、又はステップＳ６０３にて未指定のノードが存在しないと判断した場合、搬送計画策定部１４は、ステップＳ５０７へ戻って、未採択のノードが存在しないと判断するまでステップＳ５０７〜ステップＳ６０８までの操作を繰り返すことによって、現在のノードに相隣る各ノードそれぞれについて候補ノードとなるか否かについて判定するのである。
【００８３】
次に搬送計画策定部１４は、ステップＳ５０７で未採択のノードが存在しないと判断した場合、ステップＳ７０１へ移って、ステップＳ５１０及びステップＳ６０８にて生成された全ての候補ノードについて未取得の候補ノードが存在するか否かを判断する。搬送計画策定部１４は、未取得の候補ノードが存在すると判断した場合、任意の候補ノードを取得し（ステップＳ７０２）、取得した候補ノードは最終的な搬送目的位置のノードであるか否かを判断する（ステップＳ７０３）。そして、搬送計画策定部１４は、取得した候補ノードが最終的な搬送目的位置のノードではないと判断した場合、現在のノードを当該候補ノードに更新する（ステップＳ７０４）。
【００８４】
一方、搬送計画策定部１４は、ステップＳ７０２で取得した候補ノードが最終的な搬送目的位置のノードであると判断した場合、当該候補ノードの検出に関連した各候補ノードを通過する経路を生成し、それを次善搬送経路とする（ステップＳ７１０）。
【００８５】
搬送計画策定部１４は、ステップＳ７０１で未取得の候補ノードが存在しないと判断するまで、ステップＳ７０１〜ステップＳ７１０までの操作を繰り返した後、現在のノードが更新されているか否かを判断し（ステップＳ７２０）、現在のノードが更新されていないと判断するまで、ステップＳ５０６〜ステップＳ７１０までの操作を繰り返すことによって、ステップＳ５０３にて選択したノード、すなわち任意のラックＲに係る複数の次善搬送経路を生成する。
【００８６】
このとき、最適搬送経路と同じ経路の次善搬送経路が生成されることがあるが、この場合は次善搬送経路から除外する。また、次善搬送経路の生成は、予め定めた数だけ生成したときに停止するようにしてもよいし、次善搬送経路の生成数を外部要因によって変動させるようにしてもよい。
【００８７】
搬送計画策定部１４は、このような操作をステップＳ５０２にて未選択のノードが存在しないと判断するまで繰り返すことによって、各ラックＲ，Ｒ，…に係る複数の次善搬送経路をそれぞれ生成する。
【００８８】
このようにして、各ラックＲ，Ｒ，…別に、最適搬送経路及び複数の次善搬送経路を生成すると、図８に示したように搬送計画策定部１４は、各ラックＲ，Ｒ，…に近い位置に存在する搬送機２，２，…にそれぞれ対応する最適搬送経路及び各次善搬送経路を割り付けて搬送機別搬送経路群を得る（ステップＳ８１）。搬送計画策定部１４は、予め設定された数の搬送計画候補が生成されたか否かを判断し（ステップＳ８２）、所定数に達していない場合、図９に示したように、各搬送機別搬送経路群からそこに含まれる最適搬送経路又は次善搬送経路をランダムに選択し（ステップＳ８３）、選択した各最適搬送経路又は次善搬送経路の複数箇所中に、例えば０、１又は２の待機時間をランダムに設定する（ステップＳ８４）ことによって、各搬送機２，２，…別に最適搬送経路又は次善搬送経路及び待機時間が設定された搬送計画候補を生成する（ステップＳ８５）。搬送計画策定部１４は、ステップＳ８２で所定数に達したと判断するまでステップＳ８２〜ステップＳ８５までの操作を繰り返して所定数の搬送計画候補を生成する。なお、生成された搬送計画候補において、重複する搬送計画候補があれば予め除外されるようになっており、また、各搬送機別搬送経路群を構成する最適搬送経路は生成されたいずれかの搬送計画候補に反映されるようになしてある。
【００８９】
図６は搬送計画候補の生成方法を説明する説明図である。図６に示した例では、搬送機Ａ、Ｂ、Ｃの別にそれぞれ、搬送機別搬送経路群Ｐ１，Ｐ１，Ｐ１が生成されており、各搬送機別搬送経路群Ｐ１，Ｐ１，Ｐ１には最適搬送経路と２つの次善搬送経路が含まれている。各最適搬送経路及び次善搬送経路にあっては、理解を容易にするために、ノードが配設されている位置を正方形の第１ブロック３１，３１，…で表してあり、相隣るノード間の搬送路を長方形の第２ブロック３２，３２，…で表してある。
【００９０】
搬送計画候補を生成するには、例えば、搬送機Ａに係る最適搬送経路及び両次善搬送経路から一方の次善搬送経路を選択し、搬送機Ｂに係る最適搬送経路及び両次善搬送経路から最適搬送経路を選択し、搬送機Ｃに係る最適搬送経路及び両次善搬送経路から最適搬送経路を選択する。そして、選択した次善搬送経路及び両最適搬送経路をそれぞれ構成する各第２ブロック３２，３２，…にそれぞれ、０、１又は２の待機時間をランダムに設定することによって搬送機Ａ〜Ｃに対応する３つの搬送計画候補にて構成された第１搬送計画候補群が生成されている。なお、図６に示した場合にあっては、待機時間０が設定された第２ブロック３２，３２，…は空白で表してあり、待機時間１が設定された第２ブロック２３，２３，…は斜線で表してあり、待機時間２が設定された第２ブロック３２，３２，…はドットで表してある。
【００９１】
次に、搬送機Ａに係る最適搬送経路及び両次善搬送経路から最適搬送経路を選択し、搬送機Ｂに係る最適搬送経路及び両次善搬送経路から一方の次善搬送経路を選択し、搬送機Ｃに係る最適搬送経路及び両次善搬送経路から一方の次善搬送経路を選択する。そして、選択した次善搬送経路及び両最適搬送経路をそれぞれ構成する各第２ブロック３２，３２，…にそれぞれ、０、１又は２の待機時間をランダムに設定することによって搬送機Ａ〜Ｃに対応する３つの搬送計画候補にて構成された搬送計画候補群Ｐ２，Ｐ２，Ｐ２が生成されている。なお、待機時間の１単位は搬送路の構成及び搬送機の仕様等に応じて適宜に設定することができ、また、待機時間の最大値も適宜に設定することができる。
【００９２】
このような操作を予め設定された数の搬送計画候補群が生成されるまで繰り返すことによって、所定数の搬送計画候補群を生成するのである。
【００９３】
次に、図１０に示したように搬送計画策定部１４は、生成した各搬送計画候補群それぞれについて、次の（３）式を用いて適合度を算出し（ステップＳ９０）、算出した適合度に応じて各搬送計画候補群を並び替える（ステップＳ９１）。なお、（３）式にあっては、最適搬送経路及び次善搬送経路において搬送目的位置までに要する時間が短いほど、また同じ時刻に同じ搬送路上に複数の搬送機が存在する重複の数が少ないほど、適合度の値は高い。
【００９４】
【数２】
0006695653.tif 000003
【００９５】
搬送計画策定部１４は、後述する搬送計画候補群の更新を所定回数だけ行ったか否かを判断し（ステップＳ９２）、所定回数に達していない場合、例えば適合度が高い方から５つというように、適合度が上位の搬送計画候補については一時的に保存する措置を講じた（ステップＳ９３）後、例えば、適合度が中位である中位搬送計画候補群、及び適合度が下位である下位搬送計画候補群に分割し（ステップＳ９４）、両搬送計画候補群について遺伝的アルゴリズムを適用して次のように新たな搬送計画候補群を生成する。
【００９６】
まず、中位搬送計画候補群については遺伝子交叉を適用する。すなわち、中位搬送計画候補群に属する全搬送計画候補を２つのグループに分けて、それぞれグループから一つずつ搬送計画候補を選んで対とする。対にされた両搬送計画候補に含まれる各搬送経路について、予め設定された交叉頻度回数となるように搬送機別に対応する搬送経路を入れ替える操作を、全対の両搬送計画候補それぞれについて行う（ステップＳ９５）。
【００９７】
一方、下位搬送計画候補群については遺伝子突然変異を適用する。すなわち、下位搬送計画候補群に属する全搬送計画候補からランダムに１つの搬送計画候補を選択し、選択した搬送計画候補を構成する各搬送経路になるように、下位搬送計画候補群に属する他の全ての搬送計画候補を構成する各搬送経路を更新する。そして、これら全ての搬送計画候補をそれぞれ構成する各搬送経路について、予め設定した突然変異の確率で、待機時間を更新する（ステップＳ９６）。
【００９８】
搬送計画策定部１４は、ステップＳ９２で搬送計画候補群の更新を所定回数だけ行ったと判断するまで、ステップＳ９２〜ステップＳ９６までの操作を繰り返す。そして、搬送計画候補群の更新を所定回数だけ行ったと判断した場合、搬送計画策定部１４は、適合度が最も高い搬送計画候補群を選択し、当該搬送計画候補群を構成する各搬送計画を至適な搬送計画としてＣＰＵ１０へ与える（ステップＳ１００）。
【００９９】
このように、最適搬送経路又は次善搬送経路に待機時間を設定した複数の搬送計画候補群から至適な搬送計画を各搬送機別に検索するため、搬送経路上で複数の搬送機間による渋滞が生じることが回避され、各搬送機が全体としてより高い効率で被搬送物を目的位置まで搬送することができる。
【実施例】
【０１００】
次に、本発明方法によって得られた搬送計画、即ち最適搬送経路及び次善搬送経路を生成し、生成した最適搬送経路及び次善搬送経路を用いて探索した搬送計画に従って被搬送物の搬送をシミュレーションした結果と、次善搬送経路を生成せずに、最適搬送経路のみを用いて探索した搬送計画に従って被搬送物の搬送をシミュレーションした結果とを比較検討する。
【０１０１】
搬送路の構成は図４に示した構成とした。そして、図４に示した３番のノードＮと、１２番のノードＮと、２１番のノードＮをそれぞれ搬送開始位置とし、また２２番のノードＮを搬送目的位置とし、各搬送開始位置にそれぞれ対応する３台の搬送機を設定した。なお、相隣るノードＮ，Ｎ、Ｎ，Ｎ、…，…間の重みも図４に示した通りとした。
【０１０２】
本発明例にあっては、各搬送機に別に、前述したようにして最適搬送経路及び２個の次善搬送経路を生成した後、生成した各搬送機別搬送路群から最適搬送経路又は次善搬送経路を選択しつつ、０〜２の待ち時間をランダムに設定することによって搬送計画候補を６０組生成し、前述した（３）式のＰＥＮＡＬＴＹとして３０を設定して適合度を求めた。また、遺伝子交叉の頻度を２とし、遺伝子突然変異の確率を１０として２０１世代に亘って遺伝的アルゴリズムを適用して至適な搬送計画群を探索した。至適な搬送計画群を構成する各搬送計画を対応する３つの搬送機にそれぞれ割り付け、割り付けた搬送計画に従って各搬送機の搬送行動をシミュレーションして各搬送機の総走行時間の平均を求めた。
【０１０３】
一方、比較例にあっては、次善搬送経路を生成しない以外は前記本発明例と同様の操作を行って各搬送機の総走行時間の平均を求めた。
【０１０４】
同様の操作を本発明例及び比較例共に１０回実施した結果を次表に示す。
【０１０５】
【表１】
0006695653.tif 000004
【０１０６】
表から明らかなように、総走行時間の平均は全ての場合において、本発明例は比較例以下であり、従って搬送経路上で複数の搬送機間による渋滞が生じる場合であっても、各搬送機が全体としてより高い効率で被搬送物を搬送することができた。
【符号の説明】
【０１０７】
１    搬送計画策定装置
２    搬送機
１４    搬送計画策定部
２２    担持部
３０    搬送路
５０    送信器
Ｒ    ラック
Ｎ    ノード
【図１】
0006695653.tif 000011
【図２】
0006695653.tif 000012
【図３】
0006695653.tif 000013
【図４】
0006695653.tif 000014
【図５】
0006695653.tif 000015
【図６】
0006695653.tif 000016
【図７】
0006695653.tif 000017
【図８】
0006695653.tif 000018
【図９】
0006695653.tif 000019
【図１０】
0006695653.tif 000020
【図１１】
0006695653.tif 000021
【図１２】
0006695653.tif 000022
【図１３】
0006695653.tif 000023
【図１４】
0006695653.tif 000024