(57)【特許請求の範囲】
【請求項１】
訪問計画生成のために必要な、訪問先に関する情報として訪問先の位置および訪問先における仕事内容を含む情報、グループを構成し移動能力（速度）と前記仕事内容に対する処理時間を仕事能力とした各構成要素に関する情報、及びグループに関する情報を受ける入力手段と、
前記入力手段に接続され、所定の時点でのグループ毎の訪問計画、グループの構成要素及びグループへの訪問先の割当情報を示した状態Ｘとそれまでの訪問計画の最適な状態を記憶する状態記憶手段と、
前記状態記憶手段に接続され、当該状態記憶手段に格納された状態Ｘを基に、グループの構成要素と訪問計画を最適な状態に変更する状態変更手段と、
前記状態変更手段および前記入力手段に接続され、前記状態変更手段からのグループｉに属する構成要素と割り当てられた訪問先の位置とその仕事内容と、前記入力手段からの訪問先に関する情報と構成要素に関する情報である移動能力（速度）と前記仕事内容に対する処理時間である仕事能力とから、グループ毎の訪問計画のコストＦｉ（Ｘｉ）として移動に関する総時間と仕事に関する総時間とを計算し、このグループ毎の訪問計画のコストＦｉ（Ｘｉ）と前記入力手段からの情報とから、グループ毎の訪問計画Ｘｉを再構成して前記状態変更手段へ返送する計画再構成手段とを備え、
前記状態変更手段は、前記計画再構成手段から返送された状態Ｘにおけるグループｉの訪問計画Ｘｉとその訪問計画のコストＦｉ（Ｘｉ）を用いてグループの構成要素と訪問計画を、最適な状態に変更して前記状態記憶手段へ送付し、また、
前記状態変更手段により変更されたグループｉの訪問計画Ｘｉは、前記状態記憶手段に、グループｉの訪問計画の最適な状態として記憶されることを特徴とする訪問計画生成装置。
【請求項２】
前記状態変更手段は、前記状態記憶手段からの状態Ｘを受け、未割当訪問先をグループに割り当てる新規割当手段と、前記状態記憶手段からの状態Ｘを受け、既割当の訪問先の割当を変更する割当変更手段と、前記状態記憶手段からの状態Ｘを受け、グループの変更をするグループ構成変更手段とから構成されていることを特徴とする請求項１記載の訪問計画生成装置。
【請求項３】
前記グループに関する情報は、グループを構成する構成要素と構成要素間の関係（制約）とを含むことを特徴とする請求項１記載の訪問計画生成装置。
【請求項４】
前記グループに関する情報は、構成要素の変更ができない不変であること、または構成要素の変更が可能な可変であることを含むことを特徴とする請求項１記載の訪問計画生成装置。
【請求項５】
前記状態変更手段は、前記計画再構成手段からの状態Ｘにおけるグループｉの訪問計画Ｘｉとその訪問計画のコストＦｉ（Ｘｉ）から状態Ｘにおける（複数の）グループ間のコストの最大値を与える状態コスト関数Ｆ（Ｘ）を最小とするグループの構成要素と訪問計画を最適な状態に変更することを特徴とする請求項１乃至４のいずれかに記載の訪問計画生成装置。
【請求項６】
前記状態変更手段は、前記計画再構成手段からの状態Ｘにおけるグループｉの訪問計画Ｘｉとその訪問計画のコストＦｉ（Ｘｉ）から状態Ｘにおける（複数の）グループ間のコストの平均値を与える状態コスト関数Ｆ（Ｘ）を最小とするグループの構成要素と訪問計画を最適な状態に変更することを特徴とする請求項１乃至５のいずれかに記載の訪問計画生成装置。
【請求項７】
グループの制約は、構成要素の最大個数、構成し得る構成要素を含むことを特徴とする請求項３記載の訪問計画生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、構成要素（人または機械）が不変のグループおよび／または可変のグループが複数有り、複数の訪問先を前記グループで分担して訪問する際に、可変グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを行なうことができる訪問計画生成方法及び装置に関するものである。
【０００２】
【従来の技術】
最適な計画を生成する問題の典型例としては、巡回セールスマン問題があげられる。巡回セールスマン問題とは、訪れるべき複数の都市を、各都市を１度だけ訪れるという条件のもとで、最短距離で巡回できる訪問順序を求める問題であり、都市の訪問順序から一意に決まる巡回距離をコスト関数とした最適化問題である。例えば、HopfieldとTank（Hopfield,J.J., & Tank,D.W.(1985) "Neural" computation of decisions in optimization problems. Biological Cybernetics, 52, pp.141-152）は、ホップフィールドモデル(Hopfield,J.J. (1984) Neurons with graded response have collective computational properties like those of two-state neurons. Proceedings of the National Academy of Sciences USA, 81, pp.3088-3092)を利用して、巡回セールスマン問題の近似解法を提案している。
【０００３】
【発明が解決しようとする課題】
しかしながら、従来取り扱われていた巡回セールスマン問題では、一人のセールスマンが全ての都市を訪問することを前提にしていた。
【０００４】
そして、一人では全都市を訪問できないような場合には複数のグループで分担して訪問することが考えられるべきであるが、このような最適化問題は取り扱われていなかった。
【０００５】
本発明は上記従来の問題点に鑑みてなされたもので、その第１の目的は、訪問計画の最適化問題に対し、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを高速に行なうことができる訪問計画生成方法及び装置を提供することである。
【０００６】
本発明の第２の目的は、前記訪問計画の最適化問題を、輸送計画、工程計画、動作計画など、各種行動計画にも適用し得る訪問計画生成方法及び装置を提供することである。
【０００７】
【課題を解決するための手段】
本発明は上記目的を達成するため、巡回セールスマン問題のような個人的な訪問計画の生成ではなく、対象をグループに広げたグループ訪問計画を生成する技術を開発したものであり、前記グループに関する情報と、前記グループを構成する要素に関する情報と、前記訪問先に関する情報とを少なくとも受け、前記訪問計画を評価するコスト関数を利用して、前記グループの最適構成と、前記訪問先の各グループへの最適割当とを行なうようにした。これにより、複数のグループが複数の訪問先を分担して訪問する訪問計画を生成するに際して、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを行なうことができる。
【０００８】
そして、コスト関数を利用して、複数のグループ間のコストの最大値を最小化するか、または複数のグループ間のコストの平均値を最小化するか、または複数のグループ間のコストの均等化を行なうことを可能にし、訪問計画を、グループ全体でみて訪問行動を低コストで、或いはグループ間でコストの偏りがないように行なうことができるように生成することができる。
【０００９】
また、訪問計画生成処理動作中に、未割当訪問先がある場合、この未割当訪問先の新規割当およびそれに伴う訪問計画の再構成を行い、必要に応じて既割当訪問先の割当変更およびおよびそれらに伴う訪問計画の再構成を行なうこともでき、また、必要に応じて可変グループの構成変更を行なえ、未割当訪問先の追加を行なう場合に、容易にグループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とをコスト計算に基づいてグループの構成変更を行なうことができる。このように、本発明の訪問計画生成方法は、構成要素（人または機械）が不変のグループおよび／または可変のグループが複数有り、複数の訪問先を前記グループで分担して訪問する際に、可変グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを高速に求めることができる。そして、本発明は、例えば輸送計画、工程計画、動作計画、行動計画などの有効な方法となる。
【００１０】
このような態様を有する発明として、本発明は、訪問計画生成のために必要な、訪問先に関する情報として訪問先の位置および訪問先における仕事内容を含む情報、グループを構成し移動能力（速度）と前記仕事内容に対する処理時間を仕事能力とした構成要素に関する情報、及びグループに関する情報を受ける入力手段と、前記入力手段に接続され、所定の時点でのグループ毎の訪問計画、グループの構成要素及びグループへの訪問先の割当情報を示した状態Ｘとそれまでの訪問計画の最適な状態を記憶する状態記憶手段と、前記状態記憶手段に接続され、当該状態記憶手段に格納された状態Ｘを基に、グループの構成要素と訪問計画を最適な状態に変更する状態変更手段と、前記状態変更手段および前記入力手段に接続され、前記状態変更手段からのグループｉに属する構成要素と割り当てられた訪問先の位置とその仕事内容と、前記入力手段からの訪問先に関する情報と構成要素に関する情報である移動能力（速度）と前記仕事内容に対する処理時間である仕事能力とから、グループ毎の訪問計画のコストＦｉ（Ｘｉ）として移動に関する総時間と仕事に関する総時間とを計算し、このグループ毎の訪問計画のコストＦｉ（Ｘｉ）と前記入力手段からの情報とから、グループ毎の訪問計画Ｘｉを再構成して前記状態変更手段へ返送する計画再構成手段とを備え、前記状態変更手段は、前記計画再構成手段から返送された状態Ｘにおけるグループｉの訪問計画Ｘｉとその訪問計画のコストＦｉ（Ｘｉ）を用いてグループの構成要素と訪問計画を、最適な状態に変更して前記状態記憶手段へ送付し、また、前記状態変更手段により変更されたグループｉの訪問計画Ｘｉは、前記状態記憶手段に、グループｉの訪問計画の最適な状態として記憶されるようにしたものであり、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを行なうことができるという作用を有する。
【００１１】
本発明はまた、状態変更手段を、前記状態記憶手段からの状態Ｘを受け、未割当訪問先をグループに割り当てる新規割当手段と、前記状態記憶手段からの状態Ｘを受け、既割当の訪問先の割当を変更する割当変更手段と、前記状態記憶手段からの状態Ｘを受け、グループの変更をするグループ構成変更手段とから構成したものであり、未割当訪問先の追加を行なってもグループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とをコスト計算に基づいて行なうことができるという作用を有する。
【００１２】
本発明はまた、グループを構成する構成要素に関する情報は、移動能力（移動時の速度またはそれに準ずる値）と仕事能力（前記仕事内容を処理する時間またはそれに準ずる値）とを含むことを特徴とするものであり、構成要素の特性に応じて、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを行なうことができるという作用を有する。
【００１３】
本発明はまた、グループに関する情報は、グループを構成する構成要素と構成要素間の関係（制約）とを含むことを特徴とするものであり、グループの性質に応じて、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを行なうことができるという作用を有する。
【００１４】
本発明はまた、計画再構成手段は、グループ毎の訪問計画のコストＦｉ（Ｘｉ）として、移動に要する総時間と仕事に要する総時間とを計算することを特徴とするものであり、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを移動時間および仕事時間のコスト計算に基づいて行なうことができるという作用を有する。
【００１５】
本発明はまた、グループに関する情報は、構成要素の変更ができない不変であること、または構成要素の変更が可能な可変であることを含むことを特徴とするものであり、グループの性質に応じて、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを行なうことができるという作用を有する。
【００１６】
本発明はまた、状態変更手段は、前記計画再構成手段からの状態Ｘにおけるグループｉの訪問計画Ｘｉとその訪問計画のコストＦｉ（Ｘｉ）から状態Ｘにおける（複数の）グループ間のコストの最大値を与える状態コスト関数Ｆ（Ｘ）を最小とするグループの構成要素と訪問計画を最適な状態に変更することを特徴とするものであり、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とをコスト関数に基づくコスト計算に基づいてグループ全体でみて低コストで行なうことができるという作用を有する。
【００１７】
本発明はまた、状態変更手段は、前記計画再構成手段からの状態Ｘにおけるグループｉの訪問計画Ｘｉとその訪問計画のコストＦｉ（Ｘｉ）から状態Ｘにおける（複数の）グループ間のコストの平均値を与える状態コスト関数Ｆ（Ｘ）を最小とするグループの構成要素と訪問計画を最適な状態に変更することを特徴とするものであり、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とをコスト関数に基づくコスト計算に基づいてグループ全体でみて低コストで行なうことができるという作用を有する。
【００１８】
本発明はまた、グループの制約は、構成要素の最大個数、構成し得る構成要素を含むことを特徴とするものであり、グループに所属する構成要素の性質に応じて、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを行なうことができるという作用を有する。
【００１９】
本発明はまた、上記訪問計画装置を用いて実行する訪問計画方法として、訪問計画生成のために必要な、少なくとも訪問先に関する情報、グループを構成する構成要素に関する情報及びグループに関する情報とを受けるステップと、所定の時点でのグループ毎の訪問計画、グループの構成要素及びグループへの訪問先の割当情報を示した状態Ｘを基に、グループの構成要素と訪問計画を最適な状態に変更するステップと、前記、状態変更ステップにおける処理から、グループｉに属する構成要素と割り当てられた訪問先と、前記情報入力ステップからの少なくとも訪問先に関する情報と構成要素に関する情報とから、グループ毎の訪問計画のコストＦｉ（Ｘｉ）を計算し、グループ毎の訪問計画のコストＦｉ（Ｘｉ）と前記入力手段からの情報とから、グループ毎の訪問計画Ｘｉを再構成するステップとを備え、前記訪問先に関する情報を受けるステップにおいては、訪問先の位置と仕事内容に関する情報を受け、また、前記状態変更ステップにおいては、前記計画再構成ステップからの状態Ｘにおけるグループｉの訪問計画Ｘｉとその訪問計画のコストＦｉ（Ｘｉ）を用いてグループの構成要素と訪問計画を最適な状態に変更するようにしたものである。これにより、グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを行なうことができるという作用を有する。
【００３９】
【発明の実施の形態】
以下、本発明の実施の形態について、図１から図１４を用いて説明する。
【００４０】
（実施の形態１）
図１は、本発明の実施の形態１の訪問計画生成方法を実行する訪問計画生成装置の構成を示すブロック図である。図１において、１１は訪問先に関する情報とグループに関する情報と構成要素に関する情報とを少なくとも受ける入力手段であり、１２はある時点での状態（グループ構成、グループの訪問計画、訪問先の割当、構成要素の所属）とそれまでの最適な状態を記憶する状態記憶手段であり、１３は未割当訪問先の新規割り当てを行なう新規割り当て手段であり、１４は既割当訪問先の割り当て変更を行なう割り当て変更手段であり、１５はグループ構成の変更を行なうグループ構成変更手段であり、１６はグループ毎の訪問計画を再構成する計画再構成手段であり、１７はグループ毎の訪問計画のコストを計算するコスト計算手段であり、１８は出力手段である。入力手段１１は、訪問先に関する情報とグループに関する情報と構成要素に関する情報とを読み込み、これらの情報を保持する機能を持っている。
【００４１】
図２は訪問先に関する情報の一例であり、例えば訪問先３は、Ｘ＝１３、Ｙ＝５の位置にあり、そこに訪れた構成要素は仕事ＡとＢの両方を処理しなければならないことを意味している。
【００４２】
図３はグループに関する情報の一例であり、例えばグループ２は、不変グループであり、グループ構成が構成要素２、６であり、所属する構成要素間の関係が「２つの構成要素が一定距離以内にあること」（例えば、トランシーバなどを利用して２つの構成要素間で連絡を取り合いながら訪問するような場合における制約であり、２つの構成要素が紐で結ばれているような状況である）であることを意味している。また、グループ３は可変グループの例であり、所属しうる構成要素の最大数が３であり、全ての構成要素が所属可能で、構成要素間の関係が「３つの構成要素が等間隔で整列していること」であり、初期グループ構成が構成要素１、４であることを意味している。
【００４３】
図４は構成要素に関する情報の一例であり、例えば構成要素１は、移動能力（移動速度）が７であり、仕事Ａを処理する仕事能力（仕事時間）が３、仕事Ｂを処理する仕事時間が２、仕事Ｃを処理する仕事時間が１００である（仕事Ｃを苦手にしている）ことを意味している。
【００４４】
次に状態記憶手段１２について説明する。状態記憶手段１２は、まず、入力手段１１に保存される訪問先に関する情報とグループに関する情報と構成要素に関する情報とを読み、状態（グループ構成、訪問計画、訪問先の割当、構成要素の所属）を初期化して、以降は、後述の新規割当手段１３、後述の割当変更手段１４、後述のグループ構成変更手段１５による状態変更に伴って状態を更新し、記憶する。
【００４５】
図５はグループ毎のグループ構成と訪問計画の一例を示しており、例えば、可変グループであるグループ３は、構成要素１、５から構成され、まず、構成要素１で訪問先９を訪れて仕事Ｃを処理し、次に、構成要素５で訪問先１を訪れて仕事Ｃを処理し、最後に、構成要素５で訪問先５を訪れて仕事Ｂを処理することを意味している。
【００４６】
図６は訪問先の割当の一例を示しており、例えば訪問先１はグループ３に割当てられており、訪問先２は未割当訪問先であることを意味している。
【００４７】
図７は構成要素の所属の一例を示しており、例えば構成要素１はグループ３に所属しており、構成要素３は未所属構成要素であることを意味している。状態記憶手段１２は、こうした状態を記憶する機能に加え、未割当訪問先の個数が０になった後では、それまでに得られた状態コストＦ（Ｘ）（状態Ｘについてのコストであり、後述のコスト計算手段１６で計算される状態Ｘにおけるグループｉの訪問計画ＸｉについてのコストＦｉ（Ｘｉ）と区別するため、以下、状態コストと呼ぶ）最小の状態を記憶する機能も持っている。つまり、本発明の訪問計画生成方法は状態コストＦ（Ｘ）ができる限り小さな状態を求めることを特徴とする方法である。
【００４８】
本発明の訪問計画生成方法の特徴は、グループ間のコストの最大値の最小化、および／または、グループ間のコストの均等化を行なうことにあり、これは、例えば、次の状態コストＦ（Ｘ）の最小化によって実現できる：
Ｆ（Ｘ）＝α×ＭＡＸｉ［Ｆｉ（Ｘｉ）］＋β×Ｓ（Ｘ）・・・・（式１）
【００４９】
ここで、ＭＡＸｉ［Ｆｉ（Ｘｉ）］はＦｉ（Ｘｉ）のｉについての最大値を返す関数、言い換えれば、状態Ｘにおけるグループ間のコストの最大値が小さくなるにつれて小さな値を返す関数である。また、Ｓ（Ｘ）は状態ＸにおけるＦｉ  （Ｘｉ）のｉについてのバラツキを評価する関数、言い換えれば、状態Ｘにおけるグループ間のコストが均等になるにつれて小さな値を返す関数である。なお、Ｓ（Ｘ）の具体例としては、状態ＸにおけるＦｉ（Ｘｉ）のｉについての標準偏差や分散などがあげられる。さらに、係数αとβは、少なくとも一方が値を持つことを条件に、α≧０、β≧０である。
【００５０】
すなわち、（式１）で定義される状態コストＦ（Ｘ）は、状態Ｘにおけるグループ間のコストの最大値が小さくなるほど、および／または、状態Ｘにおけるグループ間のコストが均等化されるほど、小さな値をとることになり、これを最小化することで、グループ間のコストの最大値の最小化、および／または、グループ間のコストの均等化を実現できる。
【００５１】
また、グループ間のコストの平均値の最小化、および／または、グループ間のコストの均等化を実現するためには、状態コストＦ（Ｘ）を、例えば、次式のようにすればよい：
Ｆ（Ｘ）＝α×ＡＶＥｉ［Ｆｉ（Ｘｉ）］＋β×Ｓ（Ｘ）・・・・（式２）
【００５２】
ここで、ＡＶＥｉ［Ｆｉ（Ｘｉ）］はＦｉ（Ｘｉ）のｉについての平均値を返す関数、言い換えれば、状態Ｘにおけるグループ間のコストの平均値が小さくなるにつれて小さな値を返す関数である。
【００５３】
次に、新規割当手段１３を説明する。新規割当手段１３は状態記憶手段１２に記憶される状態Ｘを受け、後述の計画再構成手段１７を利用して、未割当訪問先をグループに新規割当てする機能を持つ。図８は新規割当手段１３の内部処理を示すフローチャートの一例であり、これを用いて説明する。まず、Ｓ８０１で状態Ｘを参照して（図６参照）、１または複数の未割当訪問先を選択する。次に、Ｓ８０２で、構成要素数が０のグループを除き、その時点で最小コストを持つグループを含む、１または複数のグループを選択する。次に、選択したグループ毎で（Ｓ８０３）、該グループに前記未割当部品を仮割当し（Ｓ８０３ａ）、計画再構成手段１７を利用して該グループの仮訪問計画と仮コストを求める（Ｓ８０３ｂ）。次に、Ｓ８０４で、選択したグループのうち、最小仮コストを持つグループａを選択する。次に、Ｓ８０５で、グループａに未割当訪問先を正式に割当てる。最後に、グループａの仮訪問計画を訪問計画として正式に採用する。以上により、未割当訪問先の割当先グループを適切に決めることができる。
【００５４】
次に、割当変更手段１４を説明する。割当変更手段１４は状態記憶手段１２に記憶される状態Ｘを受け、計画再構成手段１７を利用して、既割当訪問先の割当を変更する機能を持つ。図９および図１０は割当変更手段１４により実行される一連の割り当て変更処理の前半および後半をそれぞれ示すフローチャートの一例であり、これを用いて説明する。まず、Ｓ９０１で、構成要素数が０のグループを除き、その時点で最大コストを持つグループおよび／または最小コストを持つグループを含む、複数のグループを選択する。次に、Ｓ９０２で、選択したグループを、最大コストを持つグループ（グループＡ）とそれ以外のグループ（グループ群）とに分割する。次に、Ｓ９０３で、グループＡに割当てられている訪問先の割当を仮解除し、Ｓ９０４で、計画再構成手段１７を利用して、グループＡの仮訪問計画と仮コストを求める。次に、グループ群に属するグループの各々に対して（Ｓ９０５）、Ｓ９０３で仮解除された訪問先を該グループに仮割当し（Ｓ９０５ａ）、計画再構成手段１７を利用して該グループの仮訪問計画と仮コストを求める（Ｓ９０５ｂ）。次に、Ｓ９０６で、グループ群に属するグループのうち、最小仮コストを持つグループａを選択する。最後に、グループＡの仮コストとグループａの仮コストの両者がグループＡの元のコスト（仮解除前のコスト）以下である場合（Ｓ９０７）、Ｓ９０３でのグループＡについての仮解除を正式に採用し（Ｓ９０７ａ）、Ｓ９０４でのグループＡの仮訪問計画を訪問計画として正式に採用し（Ｓ９０７ｂ）、Ｓ９０５ａでのグループａへの仮割り当てを正式に採用し（Ｓ９０７ｃ）、Ｓ９０５ｂでのグループａの仮訪問計画を訪問計画として正式に採用する。以上により、既割当訪問先の割当先グループを適切に変更することができる。
【００５５】
次に、グループ構成変更手段１５を説明する。グループ構成変更手段１５は状態記憶手段１２に記憶される状態Ｘを受け、計画再構成手段１７を利用して、グループ構成を変更する機能を持つ。図１１、図１２、図１３および図１４はグループ構成変更手段１５により実行される各種グループ構成の変更処理を示すフローチャートの一例であり、これらを用いて説明する。なお、図１３および図１４は、一つの処理動作の前半および後半をそれぞれ示すフローチャートである。
【００５６】
図１１について説明する。まず、Ｓ１００１で、構成要素の数が所属しうる構成要素の最大個数（図３参照）に満たない可変グループを選択する。構成要素の数と所属しうる構成要素の最大個数との差の絶対値が最大の可変グループを選択するとしても構わない。次に、Ｓ１００２で、グループ制約（図３参照）を満たす範囲内で未所属構成要素を選択する。次に、選択した未所属構成要素の各々に対して（Ｓ１００３）、該可変グループに仮所属させ（Ｓ１００３ａ）、計画再構成手段１７を利用してその場合の仮訪問計画と仮コストを求める（Ｓ１００３ｂ）。最後に、Ｓ１００３の実行の際の最小仮コストが該可変グループの元のコスト以下である場合（Ｓ１００４）、その最小仮コストをもたらした未所属構成要素ａを選択し（Ｓ１００４ａ）、該可変グループに未所属構成要素ａを正式に所属させ（Ｓ１０４ｂ）、その場合の仮訪問計画を該可変グループの訪問計画として正式に採用する（Ｓ１００４ｃ）。以上により、構成要素の数が所属しうる構成要素の最大個数（図３参照）に満たない可変グループに、構成要素を追加所属させることができる。
【００５７】
次に、図１２について説明する。まず、Ｓ１１０１で、可変グループを選択し、その構成要素（の１つ）の所属を仮解除する。可変グループの選択の際、全ての可変グループのうち、その時点で最大コストを持つ可変グループを選択するとしても構わない。次に、Ｓ１１０２で、グループ制約（図３参照）を満たす範囲内で未所属構成要素を選択する。次に、選択した未所属構成要素の各々に対して（Ｓ１１０３）、該可変グループに仮所属させ（Ｓ１１０３ａ）、計画再構成手段１７を利用してその場合の仮訪問計画と仮コストを求める（Ｓ１１０３ｂ）。最後に、Ｓ１１０３の実行の際の最小仮コストが該可変グループの元のコスト以下である場合（Ｓ１１０４）、Ｓ１１０１で仮解除した該可変グループの構成要素を正式に解除し（Ｓ１１０４ａ）、前記最小仮コストをもたらした未所属構成要素ａを選択し（Ｓ１１０４ｂ）、該可変グループに未所属構成要素ａを正式に所属させ（Ｓ１１４ｃ）、その場合の仮訪問計画を該可変グループの訪問計画として正式に採用する（Ｓ１１０４ｄ）。以上により、構成要素の数が所属しうる構成要素の最大個数（図３参照）に等しい可変グループでも、構成要素を変更させることができる。
【００５８】
次に、図１３および図１４について説明する。まず、Ｓ１２０１で複数の可変グループを選択する。その際、全ての可変グループのうち、その時点で最大コストを持つ可変グループを少なくとも選択するとしても構わない。また、全ての可変グループのうち、その時点で最大コストを持つ可変グループと最小コストを持つ可変グループとを選択するとしても構わない。次に、Ｓ１２０２で、選択した可変グループを、その中で最大コストを持つ可変グループ（可変グループＡ）とそれ以外の可変グループからなる可変グループ群とに分割する。次に、前記可変グループ群に属するグループの各々に対して（Ｓ１２０３）、グループ制約を満たす範囲で該可変グループと可変グループＡとの間で構成要素を仮交換し（Ｓ１２０３ａ）、計画再構成手段１７を利用して、その場合の該可変グループに対しての仮訪問計画と仮コストの算出（Ｓ１２０３ｂ）、および、その場合の可変グループＡに対しての仮訪問計画と仮コストの算出（Ｓ１２０３ｃ）とを行なって、該可変グループの仮コストと可変グループＡの仮コストの大きい方をペアコストとする（Ｓ１２０３ｄ）。最後に、ペアコストの最小値が可変グループＡの元のコスト（前記最大コスト）以下である場合（Ｓ１２０４）、ペアコスト最小をもたらした可変グループ群の可変グループａを選択し（Ｓ１２０４ａ）、Ｓ１２０３ａでの可変グループａと可変グループＡとの間の構成要素の仮交換を正式に採用し（Ｓ１２０４ｂ）、Ｓ１２０３ｂでの可変グループａの仮訪問計画を訪問計画として正式に採用し（Ｓ１２０４ｃ）、Ｓ１２０３ｃでの可変グループＡの仮訪問計画を訪問計画として正式に採用する（Ｓ１２０４ｄ）。以上により、可変グループ間での構成要素の適切な交換を実現することができる。
【００５９】
次に、コスト計算手段１６の説明に移る。コスト計算手段１６は、状態Ｘにおけるグループｉの訪問計画Ｘｉと入力手段１１に記憶される訪問先に関する情報と構成要素に関する情報とを受け、訪問計画ＸｉのコストＦｉ（Ｘｉ）を返す機能を持つ。コストＦｉ（Ｘｉ）は、本実施の形態１での例の場合には、例えば、
Ｆｉ（Ｘｉ）＝Ａｉ×（Ｍ（Ｘｉ）＋Ｗ（Ｘｉ））＋Ｂｉ・・・・（式３）
と設計すればよい。
【００６０】
ここで、Ｍ（Ｘｉ）は訪問計画Ｘｉについての移動に要する総時間であり、Ｗ（Ｘｉ）は訪問計画Ｘｉについての仕事に要する総時間である。したがって、  （Ｍ（Ｘｉ）＋Ｗ（Ｘｉ））は訪問計画Ｘｉに要する総時間を示しており、グループｉにかかる「負担」ともいうことができる。また、ＡｉとＢｉはグループｉ固有の係数と閾値であり、これらの値によって、グループ間での「負担」の割合を変更することができる。なお、Ｍ（Ｘｉ）の計算は、グループの構成要素数が１の場合については容易であるが（２つの訪問位置間の距離／訪問する構成要素の移動速度）、２以上の場合には構成要素間の制約があるため若干の工夫（ある構成要素がある訪問先に向かっているときに、他の構成要素がどう動くかを取り決めておくこと）が必要となる。
【００６１】
次に、計画再構成手段１７を説明する。計画再構成手段１７は、新規割当手段１３または割当変更手段１４またはグループ構成変更手段１５によって利用され、グループｉに所属する構成要素と割当てられている訪問先と入力手段１１に記憶される訪問先に関する情報と構成要素に関する情報とを受け、コスト計算手段１６を利用して、訪問計画Ｘｉを生成する機能を持つ。これについては、貪欲法、山登り法、分枝限定法、ニューラルネット、シミュレーテッドアニーリング、遺伝的アルゴリズムなどの既存の最適化手法や、ヒューリスティクスを用いる方法、または、それらの任意の組合せによって実現できる。
【００６２】
最後に、出力手段１８を説明する。出力手段１８は状態記憶手段１２に記憶される最適な状態を外部に出力する機能を持つ。
【００６３】
なお、以上の説明においては、例えばグループ単位で訪問計画を立てる巡回セールスマン問題がイメージされるものであるが、この発明はそのような状況においてのみ適用されるのではない。その他には、例えばプリント基板へのＩＣなどの電子部品の実装工程（部品をつまんだ複数のアーム（訪問者）がプリント基板の所定の場所へ移動（訪問）し、実装作業をする）や、運輸業などにおける荷物の配送など、種々の行動がある。これら様々な業務に含まれる各行動における訪問計画の生成にも本発明は適用できるものである。
【００６４】
【発明の効果】
以上のように、本発明の訪問計画生成方法は、構成要素（人または機械）が不変のグループおよび／または可変のグループが複数有り、複数の訪問先を前記グループで分担して訪問する際に、可変グループの最適構成と訪問先のグループへの最適割当とグループ毎の最適計画の生成とを高速に求めることができる。したがって、本発明は、例えば輸送計画、工程計画、動作計画、行動計画などの有効な方法となり、その効果は大きい。
【図面の簡単な説明】
【図１】本発明の一実施の形態に係る訪問計画生成方法を実施する装置のブロック図
【図２】前記実施の形態における訪問先に関する情報を示す図
【図３】前記実施の形態におけるグループに関する情報を示す図
【図４】前記実施の形態における構成要素に関する情報を示す図
【図５】前記実施の形態における各グループのグループ構成と訪問計画を示す図
【図６】前記実施の形態における訪問先のグループへの割当を示す図
【図７】前記実施の形態における構成要素のグループへの所属を示す図
【図８】前記実施の形態における新規割当手段による新規割当処理動作を説明するフローチャート
【図９】前記実施の形態における割当変更手段による割当変更処理動作の前半部分を説明するフローチャート
【図１０】図９に示された割当変更処理動作の後半部分を説明するフローチャート
【図１１】前記実施の形態におけるグループ構成変更手段によるグループ構成変更処理動作を説明するフローチャート
【図１２】前記実施の形態におけるグループ構成変更手段による別のグループ構成変更処理動作を説明するフローチャート
【図１３】前記実施の形態におけるグループ構成変更手段によるさらに別のグループ構成変更処理動作の前半部分を説明するフローチャート
【図１４】図１３に示されたグループ構成変更処理動作の後半部分を説明するフローチャート
【符号の説明】
１１  入力手段
１２  状態記憶手段
１３  新規割当手段
１４  割当変更手段
１５  グループ構成変更手段
１６  コスト計算手段
１７  計画再構成手段
１８  出力手段
【図１】
0003739610.tif 000002
【図２】
0003739610.tif 000003
【図３】
0003739610.tif 000004
【図４】
0003739610.tif 000005
【図５】
0003739610.tif 000006
【図６】
0003739610.tif 000007
【図７】
0003739610.tif 000008
【図８】
0003739610.tif 000009
【図９】
0003739610.tif 000010
【図１０】
0003739610.tif 000011
【図１１】
0003739610.tif 000012
【図１２】
0003739610.tif 000013
【図１３】
0003739610.tif 000014
【図１４】
0003739610.tif 000015