(57)【特許請求の範囲】
【請求項１】
製造工程における通品順序を決定する情報処理装置であって、
通品対象の品の各２品間について一方の品を製造工程に通してから他方の品を製造工程に通すまでに必要となるコストを示すコスト定数と、通品対象の各品について通品する順番の期限を表す納期期限定数と、上記納期期限定数によって表わされる通品する順番の期限を超えた場合の納期違反のペナルティ値を示すペナルティ定数と、上記納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量を示す納期遅れ単位量定数とを含むデータを、取得するデータ取得手段と、
前記通品順序の決定に、制約条件式及び目的関数を用いた巡回セールスマン問題の解法を適用するために、前記データ取得手段において取得された前記コスト定数、前記納期期限定数、前記ペナルティ定数、及び納期遅れ単位量定数を、前記コスト定数と通品順序が連続するか否かを示す補助変数との積の合計と、前記ペナルティ定数と納期違反量を示す補助変数との積の合計との和によって表わされる目的関数と、前記納期期限定数、納品の順番を示す変数、及び前記納期遅れ単位量定数と前記納期違反量を示す補助変数との積を用いて表わされる納期に係る制約を示す納期制約条件式と、に代入する代入手段と、
前記納期制約条件式を満たしつつ、前記目的関数が最少となるよう解を求める最適化手段と、
を有することを特徴とする情報処理装置。
【請求項２】
前記最適化手段は、分枝限定法を用いて、前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求めることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
制約条件を選択する制約条件選択手段と、
制約条件定義情報に基づいて、前記制約条件選択手段において選択された制約条件に対応する制約条件式の内、最適化手段に入力する制約条件式を呼び出す第一の制約条件式呼び出し手段と、
を更に有し、
前記代入手段は、前記データ取得手段において取得されたデータを用いて、前記目的関数の定数と、前記納期制約条件式の定数と、前記第一の制約条件式呼び出し手段において呼び出された制約条件式の定数と、に値を代入し、
前記最適化手段は、前記納期制約条件式及び前記第一の制約条件式を満たしつつ、前記目的関数が最少となるよう解を求めることを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
制約条件定義情報に基づいて、前記制約条件選択手段において選択された制約条件に対応する制約条件式の内、後処理に用いる制約条件に対応する制約条件があるか否かに応じて、後処理を行うか否かを判定し、後処理を行うと判定した場合、後処理で用いる制約条件式を呼び出す第二の制約条件式呼び出し手段と、
前記第二の制約条件式呼び出し手段において呼び出された制約条件式を用いて、前記最適化手段によって求められた解に対して後処理を行う後処理手段と、
を更に有することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記後処理手段は、後処理として、前記最適化手段によって求められた解を、連続上限制約条件を満たすように修正を行うことを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記後処理手段は、３−ｏｐｔ法を用いて、前記最適化手段によって求められた解を、連続上限制約条件を満たすように修正を行うことを特徴とする請求項４に記載の情報処理装置。
【請求項７】
データ取得手段と、代入手段と、最適化手段とを備えた製造工程における通品順序を決定する情報処理装置における情報処理方法であって、
前記データ取得手段が、通品対象の品の各２品間について一方の品を製造工程に通してから他方の品を製造工程に通すまでに必要となるコストを示すコスト定数と、通品対象の各品について通品する順番の期限を表す納期期限定数と、上記納期期限定数によって表わされる通品する順番の期限を超えた場合の納期違反のペナルティ値を示すペナルティ定数と、上記納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量を示す納期遅れ単位量定数とを含むデータを、取得するデータ取得ステップと、
前記代入手段が、前記通品順序の決定に、制約条件式及び目的関数を用いた巡回セールスマン問題の解法を適用するために、前記データ取得ステップにおいて取得された前記コスト定数、前記納期期限定数、前記ペナルティ定数、及び納期遅れ単位量定数を、前記コスト定数と通品順序が連続するか否かを示す補助変数との積の合計と、前記ペナルティ定数と納期違反量を示す補助変数との積の合計との和によって表わされる目的関数と、前記納期期限定数、納品の順番を示す変数、及び前記納期遅れ単位量定数と前記納期違反量を示す補助変数との積を用いて表わされる納期に係る制約を示す納期制約条件式と、に代入する代入ステップと、
前記最適化手段が、前記納期制約条件式を満たしつつ、前記目的関数が最少となるよう解を求める最適化ステップと、
を含むことを特徴とする情報処理方法。
【請求項８】
製造工程における通品順序を決定するコンピュータを、
通品対象の品の各２品間について一方の品を製造工程に通してから他方の品を製造工程に通すまでに必要となるコストを示すコスト定数と、通品対象の各品について通品する順番の期限を表す納期期限定数と、上記納期期限定数によって表わされる通品する順番の期限を超えた場合の納期違反のペナルティ値を示すペナルティ定数と、上記納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量を示す納期遅れ単位量定数とを含むデータを、取得するデータ取得手段と、
前記通品順序の決定に、制約条件式及び目的関数を用いた巡回セールスマン問題の解法を適用するために、前記データ取得手段において取得された前記コスト定数、前記納期期限定数、前記ペナルティ定数、及び納期遅れ単位量定数を、前記コスト定数と通品順序が連続するか否かを示す補助変数との積の合計と、前記ペナルティ定数と納期違反量を示す補助変数との積の合計との和によって表わされる目的関数と、前記納期期限定数、納品の順番を示す変数、及び前記納期遅れ単位量定数と前記納期違反量を示す補助変数との積を用いて表わされる納期に係る制約を示す納期制約条件式と、に代入する代入手段と、
前記納期制約条件式を満たしつつ、前記目的関数が最少となるよう解を求める最適化手段と、
して機能させることを特徴とするプログラム。
【請求項９】
製造工程における通品順序を決定する情報処理装置であって、
データを取得するデータ取得手段と、
前記データ取得手段において取得されたデータを用いて、納期違反のペナルティ値がかけられている納期違反量を補助変数として含む移動費用に関する目的関数の定数と、定数である納期に係る順番の期限を表す納期期限情報と納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と補助変数である前記納期違反量とに関する納期制約条件式の定数と、に値を代入する代入手段と、
前記代入手段において定数に値が代入された前記目的関数と、前記納期制約条件式と、を最適化手段に入力する入力手段と、
前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求める最適化手段と、
前記最適化手段が出力する解を取得する解取得手段と、
前記解取得手段において取得された解を表示装置に出力する出力手段と、
を有し、
前記目的関数は、
Σh∈NΣi∈Nｃhiｘhi＋Σh∈s1ｐhｚh
で表わされ、
納期制約条件式は、
ｙh−ｕhｚh≦ｄh  （ｈ∈Ｓ1）
ｚh∈Ｚ+  （ｈ∈Ｓ1）
で表わされることを特徴とする情報処理装置。
ここで、
・品の個数：ｎ
・品の集合：Ｎ＝｛１，．．．．．．．，ｎ｝
・ＳＴＲＡＴ／ＧＯＡＬとなる品：品１
・品ｈの通品順番（決定変数）：ｙh（ｈ∈Ｎ）
・品ｈから品ｉへの移動（補助変数［有：１，無：０］）：ｘhi  （ｈ，ｉ∈Ｎ）
・品ｈから品ｉへの移動コスト：ｃｈｉ  （ｈ，ｉ∈Ｎ）
・納期制約を課す品の集合：Ｓ1⊆Ｎ
・品ｈの通品期限順番：ｄh（ｈ∈Ｓ1）
・品ｈの納期遅れ単位量：ｕh（ｈ∈Ｓ1）
・品ｈの通品に対する納期違反量を補助変数：ｚh（ｈ∈Ｓ1）
・品ｈの通品に対する納期違反のペナルティ値：ｐh（ｈ∈Ｓ1）
Ｚ＋は、ゼロ以上の整数の集合である。
【請求項１０】
製造工程における通品順序を決定する情報処理装置であって、
制約条件選択画面を介したユーザ操作に基づいて、制約条件を選択する選択手段と、
データ入力画面を介したユーザ操作に基づいて、データを取得するデータ取得手段と、
前記データ取得手段において取得されたデータを用いて、納期違反のペナルティ値がかけられている納期違反量を補助変数として含む移動費用に関する目的関数の定数と、定数である納期に係る順番の期限を表す納期期限情報と納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と補助変数である前記納期違反量とに関する納期制約条件式の定数と、前記選択手段で選択された制約条件に対応する制約条件式の定数と、に値を代入する代入手段と、
前記代入手段において定数に値が代入された前記目的関数と、前記納期制約条件式と、前記選択手段で選択された制約条件と、を最適化手段に入力する入力手段と、
前記制約条件式及び前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求める最適化手段と、
前記最適化手段が出力する解を取得する解取得手段と、
前記選択手段で選択された制約条件の内、後処理に用いる制約条件に対応する制約条件があるか否かに基づいて、後処理を行うか否かを判定する判定手段と、
前記判定手段で後処理を行うと判定された場合、前記後処理で用いる制約条件式を呼び出す呼び出し手段と、
前記呼び出し手段で呼びされた制約条件式を用いて、前記解取得手段で取得された解に対して後処理を行う後処理手段と、
前記後処理手段で後処理された前記解を表示装置に出力する出力手段と、
を有することを特徴とする情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
巡回セールスマン問題（Ｔｒａｖｅｌｉｎｇ  Ｓａｌｅｓｍａｎ  Ｐｒｏｂｌｅｍ：ＴＳＰ）では、ｎ箇所の都市を全て１回通って元の場所に戻る為に最もコストのかからないルートを探索することを解の目的としている。１０箇所を巡る場合、スタート地点が決まっていたとすると、スタート地点から見て次に行く箇所は９通りある。このようにルート候補を探索すると全部で９！通りのルート候補が存在する。たかが１０箇所でも３６万通り以上のルート候補が存在する。最適化を行うには、この３６万通り以上のルート候補の中から最もコストがかからないかを評価しなければならない。
【０００３】
最適解を探索するために、例えばＰＣ等の情報処理装置は、それぞれの解（ルート候補）について評価を行う。ここで、巡回セールスマン問題において、例えば、日本全国の１０箇所を巡るセールスマンが各箇所に"いつまでには到着しなければならない"という条件（制約条件）を伴うことがある。情報処理装置は、この制約条件を満足した上で、最も交通費が安価なルート候補を巡回セールスマン問題の最適解とする。
【０００４】
なお、特許文献１には、最適解を求める際に、制約条件に違反した場合、ペナルティを課して評価値を求める手法が提案されている。
【０００５】
【特許文献１】特開平６−１７５９９５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、巡回セールスマン問題では、都市訪問の順番決めをするにあたり、１週間等、所定の期間内に訪問すべき都市が決まっており、その期間内の順番の最適化を行う場合がある。しかしながら、最適解を求めたい事象としては、１週間の内で更に期間の区分分けがされており、その区分毎に順番を決めなくてはならない場合もある。
【０００７】
より具体的に説明すると、１週間の内に７０都市を巡る順番決めを行わなければならず、更に、"１週間の各１日でそれぞれ１０都市を巡らなくてはならない"という制約条件が付く場合がある。このような場合、従来では、７０都市をまず７等分し、１０都市ずつにする。そして、１日単位で訪問すべき１０都市の順番を決めて、それらを繋げて１週間分の順番とする等、していた。
【０００８】
しかしながら、従来の手法では、何れかのルール若しくは無作為に７０都市を７等分しており、この段階で最適解を排除してしまっている可能性があった。また、何れかのルールに基づいて７０都市を７等分している場合であっても、様々な制約条件が発生しうる事象を対象とした巡回セールスマン問題の場合、ルールを作ること自体困難な問題があった。
【０００９】
本発明はこのような問題点に鑑みなされたもので、巡回セールスマン問題において、複数の時間的期間に細分化された所定の時間的期間内で、全体として最適な順序を求めることを目的とする。
【課題を解決するための手段】
【００１０】
そこで、本発明は、製造工程における通品順序を決定する情報処理装置であって、通品対象の品の各２品間について一方の品を製造工程に通してから他方の品を製造工程に通すまでに必要となるコストを示すコスト定数と、通品対象の各品について通品する順番の期限を表す納期期限定数と、上記納期期限定数によって表わされる通品する順番の期限を超えた場合の納期違反のペナルティ値を示すペナルティ定数と、上記納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量を示す納期遅れ単位量定数とを含むデータを、取得するデータ取得手段と、前記通品順序の決定に、制約条件式及び目的関数を用いた巡回セールスマン問題の解法を適用するために、前記データ取得手段において取得された前記コスト定数、前記納期期限定数、前記ペナルティ定数、及び納期遅れ単位量定数を、前記コスト定数と通品順序が連続するか否かを示す補助変数との積の合計と、前記ペナルティ定数と納期違反量を示す補助変数との積の合計との和によって表わされる目的関数と、前記納期期限定数、納品の順番を示す変数、及び前記納期遅れ単位量定数と前記納期違反量を示す補助変数との積を用いて表わされる納期に係る制約を示す納期制約条件式と、に代入する代入手段と、前記納期制約条件式を満たしつつ、前記目的関数が最少となるよう解を求める最適化手段と、を有することを特徴とする。
【００１４】
また、本発明は、情報処理方法及びプログラムとしてもよい。
【発明の効果】
【００１５】
本発明によれば、巡回セールスマン問題において、複数の時間的期間に細分化された所定の時間的期間内で、全体として最適な順序を求めることができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施形態について図面に基づいて説明する。
【００１７】
＜実施形態１＞
図１は、情報処理装置１のハードウェア構成の一例を示す図である。図１に示されるように、情報処理装置１は、ハードウェア構成として、入力装置１１と、表示装置１２と、記録媒体ドライブ装置１３と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１５と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１６と、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１７と、インターフェース装置１８と、ＨＤ（Ｈａｒｄ  Ｄｉｓｋ）１９と、を含む。
【００１８】
入力装置１１は、情報処理装置１の操作者が操作するキーボード及びマウス等で構成され、情報処理装置１に各種操作情報等を入力するのに用いられる。表示装置１２は、情報処理装置１の操作者が利用するディスプレイ等で構成され、各種情報（又は画面）等を表示するのに用いられる。
【００１９】
インターフェース装置１８は、情報処理装置１をネットワークに接続するネットワーク接続装置である。後述する情報処理装置１の機能又は後述するフローチャート等に係るプログラムは、例えば、ＣＤ−ＲＯＭ等の記録媒体１４によって情報処理装置１に提供されるか、ネットワーク等を通じてダウンロードされる。記録媒体１４は、記録媒体ドライブ装置１３にセットされ、プログラムが記録媒体１４から記録媒体ドライブ装置１３を介してＨＤ１９にインストールされる。
【００２０】
ＲＯＭ１５は、情報処理装置１の電源投入時に最初に読み込まれるプログラム（例えばブートプログラム等）等を記録する。ＲＡＭ１６は、情報処理装置１のメインメモリである。ＣＰＵ１７は、必要に応じて、ＨＤ１９よりプログラムを読み出して、ＲＡＭ１６に格納し、プログラムを実行することで、後述する機能の全て又は一部を提供したり、後述するフローチャート等を実行したりする。
【００２１】
なお、ＨＤ１９には、プログラム以外に、後述する図３に示すような制約条件定義情報等が記憶されている。
【００２２】
図２は、実施形態１の情報処理装置１の機能構成の一例を示す図である。図２に示されるように、情報処理装置１は、機能構成として、画面制御部２１と、制約条件選択部２２と、データ取得部２３と、第一の制約条件式呼び出し部２４と、代入部２５と、入力部２６と、最適化エンジン部２７と、解取得部２８と、第二の制約条件式呼び出し部２９と、後処理部３０と、出力部３１と、を含む。
【００２３】
画面制御部２１は、後述するデータ入力画面や、制約条件選択画面等に関する制御を行う。より具体的に説明すると、画面制御部２１は、ユーザからの要求に応じて、データ入力画面や、制約条件選択画面等を表示装置１２に表示させたり、データ入力画面において入力されたデータをデータ取得部２３に渡したり、制約条件選択画面において選択された制約条件の情報を制約条件選択部２２に渡したりする。
本実施形態において、ユーザは、制約条件選択画面において、後述する開始制約条件、繋ぎ保証制約条件、順番固定制約条件、連続上限制約条件、先行制約条件、間隔下限制約条件、分割上限制約条件、汎化納期制約条件を選択するものとする。なお、本実施形態において、後述する納期制約条件は、既にデフォルトとして選択されているものとする。
【００２４】
制約条件選択部２２は、画面制御部２１より受け取った情報に基づいて、制約条件を選択する。データ取得部２３は、画面制御部２１より受け取ったデータ（目的関数や制約条件に係る入力データ）を取得する。なお、画面制御部２１は、目的関数や、納期制約条件式及び制約条件選択部２２が選択した制約条件に応じた制約条件式の定数を入力するためのデータ入力画面を表示装置１２に表示させる。そして、画面制御部２１は、上述したように、データ入力画面において入力されたデータをデータ取得部２３に渡す。
【００２５】
第一の制約条件式呼び出し部２４は、図３に示されるような制約条件定義情報に基づいて、制約条件選択部２２において選択された制約条件に対応する制約条件式の内、最適化エンジン部２７に入力する制約条件式を呼び出す。
【００２６】
ここで、図３は、制約条件定義情報の一例を示す図である。図３に示されるように、制約条件定義情報には、例えば、後処理で用いる制約条件式に対応する制約条件が定義されている。ユーザは、入力装置１１等を用いて、制約条件定義情報を編集することによって、後処理で用いる制約条件式を設定（又は定義）することができる。
なお、制約条件定義情報において、後処理部ではなく、最適化エンジン部２７に入力する制約条件式に対応する制約条件を設定（又は定義）する構成としてもよい。但し、本実施形態では、制約条件定義情報には、後処理で用いる制約条件式に対応する制約条件が定義されているものとする。
【００２７】
納期制約条件を課さない場合の、一般的な巡回セールスマン問題に関する目的関数及び制約条件式を以下に示す。
目的関数：Σh∈NΣi∈Nｃhiｘhi
制約条件式：Σh∈Nｘhi＝１  （ｉ∈Ｎ）
Σi∈Nｘhi＝１  （ｈ∈Ｎ）
ｙh＋１≦ｙi＋ｎ（１−ｘhi）  （ｈ，ｉ∈Ｎ，ｉ≠１）
ｙ1＝１
ｙh∈｛１，．．．．，ｎ｝  （ｈ∈Ｎ）
ｘhi∈｛０，１｝  （ｈ，ｉ∈Ｎ）
ここで、
・都市の個数：ｎ
・都市の集合：Ｎ＝｛１，．．．．，ｎ｝
・ＳＴＡＲＴ／ＧＯＡＬとなる都市：都市１
・都市ｈの訪問順番（決定変数）：ｙh  （ｈ∈Ｎ）
・都市ｈから都市ｉへの移動（補助変数[有：１，無：０]）：ｘhi  （ｈ，ｉ∈Ｎ）
・都市ｈから都市ｉへの移動コスト：ｃhi  （ｈ，ｉ∈Ｎ）
である。
【００２８】
次に、本実施形態に係る目的関数及び条件式等を以下に示す。
納期制約条件を課すと、
目的関数は、Σh∈NΣi∈Nｃhiｘhi＋Σh∈S1ｐhｚh                  （式）
と表される。
また、納期制約条件を課すと、納期制約に係る条件式（納期制約条件式）は、
ｙh−ｕhｚh≦ｄh  （ｈ∈Ｓ1）
ｚh∈Ｚ+  （ｈ∈Ｓ1）
と表される。
ここで、
・納期制約を課す都市の集合：Ｓ1⊆Ｎ
・都市ｈの訪問期限順番（都市ｈはｄh番目までに訪問する）：ｄh（ｈ∈Ｓ1）
・都市ｈの納期遅れ単位量（１違反とする遅れの許容範囲）：ｕh（ｈ∈Ｓ1）
・都市ｈの訪問に対する納期違反量（補助変数）：ｚh（ｈ∈Ｓ1）
・都市ｈの訪問に対する納期違反ペナルティ値：ｐh（ｈ∈Ｓ1）
である。
なお、Ｚ+は、ゼロ以上の整数の集合を表している。
【００２９】
なお、納期制約のより具体的な例を、図４を用いて説明する。図４は、納期制約の一例を説明するための図である。上述したｄhを５、ｕhを２、ｐhを１００とすると、図４に示されるように「都市ｈには、５番目までに訪れたいが、１番でも遅れると１００の違反ペナルティ値を課す。納期遅れ単位量が２なので、２番遅れまでは１００の違反ペナルティ値であるが、３番遅れになると更に１００の違反ペナルティ値を課す。以下同様に納期遅れ単位量毎に所定のペナルティ値を課す。」という納期制約条件となる。なお、納期が複数の時間的期間ではなく、単純に訪問順番で与えられるのであれば、納期遅れ単位量を１とすればよい。また、納期制約条件を必ず守る必要があれば、納期遅れ単位量を０とすることで、納期違反量に関する新たな項を、考慮しないようにすればよい。
【００３０】
次に、ユーザが選択可能な制約条件に対応する制約条件式を以下に示す。
【００３１】
開始制約条件式
ｙh≧ａh  (ｈ∈Ｓ2)
ここで、
・開始制約を課す都市の集合：Ｓ2⊆Ｎ
・都市ｈの訪問開始可能順番：ａh（ｈ∈Ｓ2）
である。都市ｈの訪問は 、ａh番目以降でなければならないという制約である。
【００３２】
繋ぎ保証制約条件式
ｘhi＝１  （（ｈ，ｉ）∈Ｗ3）
ここで、
・繋ぎ保証制約を課す都市のペアの集合：Ｗ3⊆Ｎ×Ｎ
である。都市ｉの訪問は、都市ｈの次でなければならないという制約である。
【００３３】
順番固定制約条件式
ｙh＝ｆh（ｈ∈Ｓ4）
ここで、
・順番固定制約を課す都市の集合：Ｓ4⊆Ｎ
・固定順番：ｆh（ｈ∈Ｓ4）
である。都市ｈの訪問は、ｆh番目でなければならないという制約である。
【００３４】
先行制約条件式
ｙh＋１≦ｙi  （（ｈ，ｉ）∈Ｗ5）
ここで、
・先行制約を課す都市のペアの集合：Ｗ5⊆Ｎ×Ｎ
である。都市ｉの訪問は、都市ｈよりも後でなければならないという制約である。
【００３５】
連続上限制約条件式
｛ｈ∈Ｎ＼Ｓ6｜ｖ≦ｙh≦ｖ＋ｋ｝≠φ  （ｖ＝１，．．．．，ｎ−ｋ）
ここで、
・連続上限制約を課す都市の集合：Ｓ6⊆Ｎ
・連続上限番数：ｋ
である。集合Ｓ6に含まれる都市の訪問は、ｋ都市までしか連続してはならないという制約である。
【００３６】
間隔下限制約条件式
｛ｈ∈Ｓ7：ｙi＋１≦ｙh≦ｙi＋ｍ｝＝φ  （ｉ∈Ｓ7）
ここで、
・間隔下限制約を課す都市の集合：Ｓ7⊆Ｎ
・間隔下限番数：ｍ
である。集合Ｓ7に含まれる都市の訪問間隔は、ｍ都市より離れなくてはならないという制約である。
【００３７】
分割上限制約条件式
Σh∈N＼S8Σi∈S8ｘhi≦ｇ
ここで、
・分割上限制約を課す都市の集合：Ｓ8⊆Ｎ
・分割上限回数：ｇ
である。集合Ｓ8に含まれる都市の訪問は連続させ、連続がｇ回より分割してはならないという制約である。
【００３８】
汎化納期制約条件式
Σ(i,j)∈Rhｔij≦ｅh  （ｈ∈Ｓ9）
ここで、
・汎化納期制約を課す都市の集合：Ｓ9⊆Ｎ
・都市ｈまでの道程：Ｒh＝｛（ｉ，ｊ）∈Ｎ×Ｎ｜ｘij＝１，ｙj≦ｙh｝  （ｈ∈Ｓ9）
・都市ｉと都市ｊ間の所要時間：ｔij  （ｉ，ｊ∈Ｎ）
・都市ｈの訪問期限時間：ｅh（ｈ∈Ｓ9）
である。都市ｈにはスタートからの時間ｅhまでに訪れなくてはならないという制約である。
【００３９】
再び図２の説明に戻り、代入部２５は、データ取得部２３において取得されたデータを用いて、上述した（式）で示される目的関数、納期制約条件式、及び第一の制約条件式呼び出し部２４において呼び出された制約条件式の定数に値を代入する。
【００４０】
入力部２６は、代入部２５において、定数に値が代入された前記目的関数及び前記制約条件式を最適化エンジン部２７に入力する。最適化エンジン部２７は、入力された制約条件式の下、目的関数が最小となるよう、例えば、分枝限定法等を用いて、解を求め（又は最適解を探索し）、求めた解を出力する。
【００４１】
解取得部２８は、最適化エンジン部２７が出力する解を取得する。第二の制約条件式呼び出し部２９は、制約条件定義情報に基づいて、制約条件選択部２２において選択された制約条件に対応する制約条件式の内、後処理に用いる制約条件式を呼び出す。
【００４２】
後処理部３０は、第二の制約条件式呼び出し部２９において呼び出された制約条件式を用いて、解取得部２８において取得された解に対して後処理を行う。出力部３１は、解取得部２８において取得された解、又は後処理部３０において後処理された解を表示装置１２に表示する。
【００４３】
図５は、情報処理装置１における情報処理の一例を示すフローチャートである。
なお、画面制御部２１は、ユーザ操作等に応じて、制約条件選択画面を表示装置１２上に表示させているものとする。以下、ユーザが、制約条件選択画面において、繋ぎ保証制約条件と、連続上限制約条件と、を選択したものとして説明を行う。
【００４４】
ステップＳ１１において、制約条件選択部２２は、画面制御部２１より受け取った情報に基づいて、制約条件を選択する。より具体的に説明すると、制約条件選択部２２は、繋ぎ保証制約条件と、連続上限制約条件と、を選択する。
【００４５】
ステップＳ１２において、画面制御部２１は、ステップＳ１１で制約条件選択部２２が選択した制約条件に応じた制約条件式の定数等を入力するためのデータ入力画面を作成し、表示装置１２に表示させる。ユーザは、このデータ入力画面を介して、目的関数、納期制約条件式及び自身が選択した制約条件に対応する制約条件式の定数に関するデータを入力する。より具体的に説明すると、ユーザは、上述したｎ，ｃhi，Ｓ1，ｄh，ｕh，ｐh，Ｗ3，Ｓ6，ｋ等に関するデータを入力する。
【００４６】
ステップＳ１３において、データ取得部２３は、画面制御部２１より入力されたデータを取得する。
【００４７】
ステップＳ１４において、第一の制約条件式呼び出し部２４は、制約条件定義情報に基づいて、ステップＳ１１で制約条件選択部２２において選択された制約条件に対応する制約条件式の内、最適化エンジン部２７に入力する制約条件式を呼び出す。ここで、制約条件定義情報が図３に示されるような場合、連続上限制約条件は後処理で用いる制約条件式に対応する制約条件として設定されている。よって、第一の制約条件式呼び出し部２４は、繋ぎ保証制約条件式を呼び出す。なお、ここで、式を呼び出すとは、例えば、ファイル等に記述された式をＨＤ１９又はＲＡＭ１６等から読み出す（呼び出す）ことである。
【００４８】
ステップＳ１５において、代入部２５は、ステップＳ１３でデータ取得部２３において取得されたデータを用いて、上述した（式）で示される目的関数、納期制約条件式、及びステップＳ１４で第一の制約条件式呼び出し部２４において呼び出された制約条件式の定数に値を代入する。
【００４９】
ステップＳ１６において、入力部２６は、ステップＳ１５で代入部２５において定数に値が代入された目的関数及び制約条件式を最適化エンジン部２７に入力する。
【００５０】
ステップＳ１７において、最適化エンジン部２７は、入力された制約条件式の下、目的関数が最小となるよう、例えば、分枝限定法等を用いて、解を求め（又は最適解を探索し）、求めた解を出力する。
【００５１】
ステップＳ１８において、解取得部２８は、最適化エンジン部２７が出力する解を取得する。ステップＳ１９において、第二の制約条件式呼び出し部２９は、後処理を行うか否かを判定する。第二の制約条件式呼び出し部２９は、制約条件定義情報に基づいて、制約条件選択部２２において選択された制約条件の内、後処理に用いる制約条件式に対応する制約条件があるか否かに応じて、後処理を行うか否かを判定する。後処理を行う場合、ステップＳ２０に進み、後処理を行わない場合、ステップＳ２２に進む。
【００５２】
ステップＳ２０において、第二の制約条件式呼び出し部２９は、制約条件定義情報に基づいて、制約条件選択部２２において選択された制約条件に対応する制約条件式の内、後処理に用いる制約条件式を呼び出す。より具体的に説明すると、第二の制約条件式呼び出し部２９は、連続上限制約条件式を呼び出す。
【００５３】
ステップＳ２１において、後処理部３０は、ステップＳ２０で第二の制約条件式呼び出し部２９において呼び出された制約条件式を用いて、ステップＳ１８で解取得部２８において取得された解に対して後処理を行う。より具体的に説明すると、後処理部３０は、ステップＳ１８で解取得部２８において取得された解に対して、連続上限制約条件式を満たすように、例えば、３−ｏｐｔ法で解を修正する。連続上限制約条件式を満たすように、３−ｏｐｔ法で解を修正する処理の一例を、後述する図６等に示す。
【００５４】
ステップＳ２２において、出力部３１は、ステップＳ１９においてＮＯと判定され、本ステップの処理を実行する場合は、解取得部２８において取得された解を、また、ステップＳ１９においてＹＥＳと判定され、ステップＳ２０及びステップＳ２１の処理を経て本ステップの処理を実行する場合は、後処理部３０において後処理された解を、表示装置１２に表示する。
【００５５】
図６は、連続上限制約条件式を満たすように、３−ｏｐｔ法で解を修正する処理の一例を示すフローチャートである。
ステップＳ３１において、後処理部３０は、分解不能フラグをリセットする。
【００５６】
ステップＳ３２において、後処理部３０は、Ｓ6の都市の連続箇所の内、分割不能な部分を除き、最長の連続Ａを選択する。続いて、ステップＳ３３において、後処理部３０は、Ａの連続数がｋ（つまり、連続上限番数）より大きいか否かを判定する。後処理部３０は、Ａの連続数がｋより大きいと判定すると、ステップＳ３４に進み、Ａの連続数がｋより大きくはないと判定すると、図６に示す処理を終了する。
【００５７】
続いて、ステップＳ３４において、後処理部３０は、順番を入れ替える区切り都市ＴＯＰ，ＭＩＤ，ＢＯＴを選択する。ここで、後処理部３０は、入れ替え後の並びが、他の制約条件に違反しないよう、また、収束を保証するための制約条件に違反しないよう、また、他の前記制約条件と、収束を保証するための制約条件と、を満たしつつ、目的関数が最小となるよう、ＴＯＰ，ＭＩＤ，ＢＯＴを選択する。
【００５８】
続いて、ステップＳ３５において、後処理部３０は、ＴＯＰ，ＭＩＤ，ＢＯＴを選択できたか否かを判定する。後処理部３０は、選択できたと判定すると、ステップＳ３６に進み、選択できなかったと判定すると、ステップＳ３７に進む。
【００５９】
ステップＳ３６において、後処理部３０は、都市並びのＴＯＰからの部分列と、ＭＩＤからの部分列と、を入れ替える。図７は、入れ替えの一例を説明するための図である。一方、ステップＳ３７において、後処理部３０は、Ａが分割不能であることを示すよう、分割不能フラグをセットする。
【００６０】
以上、上述したように本実施形態によれば、巡回セールスマン問題において、複数の時間的期間に細分化された所定の時間的期間内で、全体として最適な順序を求めることができる。
【００６１】
＜実施形態２＞
上述した実施形態では、納期制約条件をデフォルトの制約条件として説明を行ったが、他の制約条件と同様に、ユーザが選択可能な制約条件としてもよい。
【００６２】
＜実施形態３＞
上述した実施形態では、説明の簡略化のため、納期制約条件の場合のみ、ペナルティ値を課すよう説明を行った。つまり、情報処理装置１は、納期制約条件の場合のみ、上述した（式）で表されるように、目的関数に、納期違反ペナルティ値が重み付けされている、納期違反量に関する新たな項を追加した。
しかしながら、上述した制約条件の内、順番固定制約条件以外の制約条件に関しては、納期制約条件の場合と同様に、各制約条件に係るペナルティ値を重み付けした、違反量に関する新たな項を目的関数に追加するようにしてもよい。
【００６３】
図８は、実施形態３の情報処理装置１の機能構成の一例を示す図である。図８に示されるように、情報処理装置１は、機能構成として、画面制御部５１と、制約条件選択部５２と、データ取得部５３と、第一の制約条件式呼び出し部５４と、代入部５５と、入力部５６と、最適化エンジン部５７と、解取得部５８と、第二の制約条件式呼び出し部５９と、後処理部６０と、出力部６１と、目的関数変更部６２と、を含む。
【００６４】
画面制御部５１は、データ入力画面や、制約条件選択画面等に関する制御を行う。より具体的に説明すると、画面制御部５１は、ユーザからの要求に応じて、データ入力画面や、制約条件選択画面等を表示装置１２に表示させたり、データ入力画面において入力されたデータをデータ取得部５３に渡したり、制約条件選択画面において選択された制約条件の情報を制約条件選択部５２に渡したりする。
本実施形態において、ユーザは、制約条件選択画面において、納期制約条件、開始制約条件、繋ぎ保証制約条件、順番固定制約条件、先行制約条件、連続上限制約条件、間隔下限制約条件、分割上限制約条件、汎化納期制約条件を選択するものとする。
【００６５】
制約条件選択部５２は、画面制御部５１より受け取った情報に基づいて、制約条件を選択する。データ取得部５３は、画面制御部５１より受け取ったデータ（目的関数や制約条件に係る入力データ）を取得する。なお、画面制御部５１は、目的関数や、制約条件選択部５２が選択した制約条件に応じた制約条件式の定数を入力するためのデータ入力画面を表示装置１２に表示させる。そして、画面制御部５１は、上述したように、データ入力画面において入力されたデータをデータ取得部５３に渡す。
【００６６】
第一の制約条件式呼び出し部５４は、制約条件定義情報に基づいて、制約条件選択部５２において選択された制約条件に対応する制約条件式の内、最適化エンジン部５７に入力する制約条件式を呼び出す。
【００６７】
目的関数変更部６２は、第一の制約条件式呼び出し部５４が呼び出した制約条件式に対応する制約条件に応じて、例えば、この制約条件に応じた違反ペナルティ値を重み付けした違反量に関する項を目的関数に追加する等して目的関数を変更する。
【００６８】
代入部５５は、データ取得部５３において取得されたデータを用いて、目的関数変更部６２において変更された（項を新たに追加された）目的関数及び第一の制約条件式呼び出し部５４において呼び出された制約条件式の定数に値を代入する。
【００６９】
入力部５６は、代入部５５において、定数に値が代入された前記目的関数及び前記制約条件式を最適化エンジン部５７に入力する。最適化エンジン部５７は、入力された制約条件式の下、目的関数が最小となるよう、例えば、分枝限定法等を用いて、解を求め（又は最適解を探索し）、求めた解を出力する。
【００７０】
解取得部５８は、最適化エンジン部５７が出力する解を取得する。第二の制約条件式呼び出し部５９は、制約条件定義情報に基づいて、制約条件選択部５２において選択された制約条件に対応する制約条件式の内、後処理に用いる制約条件式を呼び出す。
【００７１】
後処理部６０は、第二の制約条件式呼び出し部５９において呼び出された制約条件式を用いて、解取得部５８において取得された解に対して後処理を行う。出力部６１は、解取得部５８において取得された解、又は後処理部６０において後処理された解を表示装置１２に表示する。
【００７２】
＜実施形態４＞
上述した実施形態では、都市の訪問順番を決定する例を用いて、巡回セールスマン問題に関する情報処理装置１の処理の説明を行ったが、上述した処理は、例えば、製造業における様々な製造工程の通品順序決めに適用することができる。この場合、上述した「都市間の移動コスト」は、「品種切り替えによる歩留まりにかかるコストや製造設備の組み替えにかかるコスト」等に対応する。
【００７３】
また、通品順序決めに適用した場合、納期（ある順番までに通品すること）を守ることに関する条件が、上述した納期制約条件に対応する。また、ある資材到着後に通品できることに関する条件が、上述した開始制約条件に対応する。また、品Ａの次に品Ｂを通すことに関する条件が、上述した繋ぎ保証制約に対応する。また、通品順番が指定されていることに関する条件が、上述した順番固定制約条件に対応する。また、品Ａは品Ｂより先に通品することに関する条件が、上述した先行制約条件に対応する。また、特定品種の連続番数に上限があることに関する条件が、上述した連続上限制約条件に対応する。また、特定品種の間隔番数に下限があることに関する条件が、上述した間隔下限制約条件に対応する。また、連続通品させたい品種の連続が分割される回数に上限があることに関する条件が、上述した分割上限制約条件に対応する。また、納期（作業時間等の累積）を守ることに関する条件が、上述した汎化納期制約条件に対応する。
【００７４】
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【図面の簡単な説明】
【００７５】
【図１】情報処理装置１のハードウェア構成の一例を示す図である。
【図２】実施形態１の情報処理装置１の機能構成の一例を示す図である。
【図３】制約条件定義情報の一例を示す図である。
【図４】納期制約の一例を説明するための図である。
【図５】情報処理装置１における情報処理の一例を示すフローチャートである。
【図６】連続上限制約条件式を満たすように、３−ｏｐｔ法で解を修正する処理の一例を示すフローチャートである。
【図７】入れ替えの一例を説明するための図である。
【図８】実施形態３の情報処理装置１の機能構成の一例を示す図である。
【符号の説明】
【００７６】
１    情報処理装置
１１  入力装置
１２  表示装置
１３  記録媒体ドライブ装置
１４  記録媒体
１５  ＲＯＭ
１６  ＲＡＭ
１７  ＣＰＵ
１８  インターフェース装置
１９  ＨＤ
２１  画面制御部
２２  制約条件選択部
２３  データ取得部
２４  第一の制約条件式呼び出し部
２５  代入部
２６  入力部
２７  最適化エンジン部
２８  解取得部
２９  第二の制約条件式呼び出し部
３０  後処理部
３１  出力部
【図１】
0004999573.tif 000002
【図２】
0004999573.tif 000003
【図３】
0004999573.tif 000004
【図４】
0004999573.tif 000005
【図５】
0004999573.tif 000006
【図６】
0004999573.tif 000007
【図７】
0004999573.tif 000008
【図８】
0004999573.tif 000009