JP2009003883A - 情報処理装置、情報処理方法及びプログラム - Google Patents

Abstract

【課題】巡回セールスマン問題において、複数の時間的期間に細分化された所定の時間的期間内で、全体として最適な順序を求めることを目的とする。
【解決手段】納期に係る順番の期限を表す納期期限情報と、納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と、納期違反量と、に関する納期制約条件式を満たしつつ、納期違反のペナルティ値がかけられている納期違反量を変数として含む、移動費用に関する目的関数が最小となるよう、分枝限定法を用いて解を求めることによって課題を解決する。
【選択図】図１

Description

本発明は、情報処理装置、情報処理方法及びプログラムに関する。

巡回セールスマン問題（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ：ＴＳＰ）では、ｎ箇所の都市を全て１回通って元の場所に戻る為に最もコストのかからないルートを探索することを解の目的としている。１０箇所を巡る場合、スタート地点が決まっていたとすると、スタート地点から見て次に行く箇所は９通りある。このようにルート候補を探索すると全部で９！通りのルート候補が存在する。たかが１０箇所でも３６万通り以上のルート候補が存在する。最適化を行うには、この３６万通り以上のルート候補の中から最もコストがかからないかを評価しなければならない。

最適解を探索するために、例えばＰＣ等の情報処理装置は、それぞれの解（ルート候補）について評価を行う。ここで、巡回セールスマン問題において、例えば、日本全国の１０箇所を巡るセールスマンが各箇所に"いつまでには到着しなければならない"という条件（制約条件）を伴うことがある。情報処理装置は、この制約条件を満足した上で、最も交通費が安価なルート候補を巡回セールスマン問題の最適解とする。

なお、特許文献１には、最適解を求める際に、制約条件に違反した場合、ペナルティを課して評価値を求める手法が提案されている。

特開平６−１７５９９５号公報

ところで、巡回セールスマン問題では、都市訪問の順番決めをするにあたり、１週間等、所定の期間内に訪問すべき都市が決まっており、その期間内の順番の最適化を行う場合がある。しかしながら、最適解を求めたい事象としては、１週間の内で更に期間の区分分けがされており、その区分毎に順番を決めなくてはならない場合もある。

より具体的に説明すると、１週間の内に７０都市を巡る順番決めを行わなければならず、更に、"１週間の各１日でそれぞれ１０都市を巡らなくてはならない"という制約条件が付く場合がある。このような場合、従来では、７０都市をまず７等分し、１０都市ずつにする。そして、１日単位で訪問すべき１０都市の順番を決めて、それらを繋げて１週間分の順番とする等、していた。

しかしながら、従来の手法では、何れかのルール若しくは無作為に７０都市を７等分しており、この段階で最適解を排除してしまっている可能性があった。また、何れかのルールに基づいて７０都市を７等分している場合であっても、様々な制約条件が発生しうる事象を対象とした巡回セールスマン問題の場合、ルールを作ること自体困難な問題があった。

本発明はこのような問題点に鑑みなされたもので、巡回セールスマン問題において、複数の時間的期間に細分化された所定の時間的期間内で、全体として最適な順序を求めることを目的とする。

そこで、本発明は、納期に係る順番の期限を表す納期期限情報と、納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と、納期違反量と、に関する納期制約条件式を満たしつつ、納期違反のペナルティ値がかけられている納期違反量を変数として含む、移動費用に関する目的関数が最小となるよう、分枝限定法を用いて解を求めることを特徴とする。

また、本発明は、情報処理装置における巡回セールスマン問題の求解方法であって、納期違反のペナルティ値がかけられている納期違反量を補助変数として含む、移動費用に関する目的関数及び納期に係る順番の期限を表す納期期限情報と納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と前記納期違反量とに関する納期制約条件式を最適化手段に入力する入力ステップと、前記最適化手段が、入力された前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求める求解ステップと、前記最適化手段より解を取得する取得ステップと、前記取得ステップにおいて取得された解を表示装置に出力する出力ステップと、を有することを特徴とする。

また、本発明は、データを取得するデータ取得手段と、前記データ取得手段において取得されたデータを用いて、納期違反のペナルティ値がかけられている納期違反量を補助変数として含む移動費用に関する目的関数の定数と、定数である納期に係る順番の期限を表す納期期限情報と納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と補助変数である前記納期違反量とに関する納期制約条件式の定数と、に値を代入する代入手段と、前記代入手段において定数に値が代入された前記目的関数と、前記納期制約条件式と、を最適化手段に入力する入力手段と、前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求める最適化手段と、前記最適化手段が出力する解を取得する解取得手段と、前記解取得手段において取得された解を表示装置に出力する出力手段と、を有することを特徴とする。

係る構成とすることにより、例えば、１週間の内に７０都市を巡る順番決めを行わなければならず、更に、１週間の各１日でそれぞれ１０都市を巡らなくてはならないという制約条件がある問題でも、納期遅れ単位量毎の納期違反量を考慮して、全体として最適な順序を求めることができる。

また、本発明は、情報処理方法及びプログラムとしてもよい。

本発明によれば、巡回セールスマン問題において、複数の時間的期間に細分化された所定の時間的期間内で、全体として最適な順序を求めることができる。

以下、本発明の実施形態について図面に基づいて説明する。

＜実施形態１＞
図１は、情報処理装置１のハードウェア構成の一例を示す図である。図１に示されるように、情報処理装置１は、ハードウェア構成として、入力装置１１と、表示装置１２と、記録媒体ドライブ装置１３と、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１５と、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１６と、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１７と、インターフェース装置１８と、ＨＤ（Ｈａｒｄ Ｄｉｓｋ）１９と、を含む。

入力装置１１は、情報処理装置１の操作者が操作するキーボード及びマウス等で構成され、情報処理装置１に各種操作情報等を入力するのに用いられる。表示装置１２は、情報処理装置１の操作者が利用するディスプレイ等で構成され、各種情報（又は画面）等を表示するのに用いられる。

インターフェース装置１８は、情報処理装置１をネットワークに接続するネットワーク接続装置である。後述する情報処理装置１の機能又は後述するフローチャート等に係るプログラムは、例えば、ＣＤ−ＲＯＭ等の記録媒体１４によって情報処理装置１に提供されるか、ネットワーク等を通じてダウンロードされる。記録媒体１４は、記録媒体ドライブ装置１３にセットされ、プログラムが記録媒体１４から記録媒体ドライブ装置１３を介してＨＤ１９にインストールされる。

ＲＯＭ１５は、情報処理装置１の電源投入時に最初に読み込まれるプログラム（例えばブートプログラム等）等を記録する。ＲＡＭ１６は、情報処理装置１のメインメモリである。ＣＰＵ１７は、必要に応じて、ＨＤ１９よりプログラムを読み出して、ＲＡＭ１６に格納し、プログラムを実行することで、後述する機能の全て又は一部を提供したり、後述するフローチャート等を実行したりする。

なお、ＨＤ１９には、プログラム以外に、後述する図３に示すような制約条件定義情報等が記憶されている。

図２は、実施形態１の情報処理装置１の機能構成の一例を示す図である。図２に示されるように、情報処理装置１は、機能構成として、画面制御部２１と、制約条件選択部２２と、データ取得部２３と、第一の制約条件式呼び出し部２４と、代入部２５と、入力部２６と、最適化エンジン部２７と、解取得部２８と、第二の制約条件式呼び出し部２９と、後処理部３０と、出力部３１と、を含む。

画面制御部２１は、後述するデータ入力画面や、制約条件選択画面等に関する制御を行う。より具体的に説明すると、画面制御部２１は、ユーザからの要求に応じて、データ入力画面や、制約条件選択画面等を表示装置１２に表示させたり、データ入力画面において入力されたデータをデータ取得部２３に渡したり、制約条件選択画面において選択された制約条件の情報を制約条件選択部２２に渡したりする。
本実施形態において、ユーザは、制約条件選択画面において、後述する開始制約条件、繋ぎ保証制約条件、順番固定制約条件、連続上限制約条件、先行制約条件、間隔下限制約条件、分割上限制約条件、汎化納期制約条件を選択するものとする。なお、本実施形態において、後述する納期制約条件は、既にデフォルトとして選択されているものとする。

制約条件選択部２２は、画面制御部２１より受け取った情報に基づいて、制約条件を選択する。データ取得部２３は、画面制御部２１より受け取ったデータ（目的関数や制約条件に係る入力データ）を取得する。なお、画面制御部２１は、目的関数や、納期制約条件式及び制約条件選択部２２が選択した制約条件に応じた制約条件式の定数を入力するためのデータ入力画面を表示装置１２に表示させる。そして、画面制御部２１は、上述したように、データ入力画面において入力されたデータをデータ取得部２３に渡す。

第一の制約条件式呼び出し部２４は、図３に示されるような制約条件定義情報に基づいて、制約条件選択部２２において選択された制約条件に対応する制約条件式の内、最適化エンジン部２７に入力する制約条件式を呼び出す。

ここで、図３は、制約条件定義情報の一例を示す図である。図３に示されるように、制約条件定義情報には、例えば、後処理で用いる制約条件式に対応する制約条件が定義されている。ユーザは、入力装置１１等を用いて、制約条件定義情報を編集することによって、後処理で用いる制約条件式を設定（又は定義）することができる。
なお、制約条件定義情報において、後処理部ではなく、最適化エンジン部２７に入力する制約条件式に対応する制約条件を設定（又は定義）する構成としてもよい。但し、本実施形態では、制約条件定義情報には、後処理で用いる制約条件式に対応する制約条件が定義されているものとする。

納期制約条件を課さない場合の、一般的な巡回セールスマン問題に関する目的関数及び制約条件式を以下に示す。
目的関数：Σ_h∈NΣ_i∈Nｃ_hiｘ_hi
制約条件式：Σ_h∈Nｘ_hi＝１ （ｉ∈Ｎ）
Σ_i∈Nｘ_hi＝１ （ｈ∈Ｎ）
ｙ_h＋１≦ｙ_i＋ｎ（１−ｘ_hi） （ｈ，ｉ∈Ｎ，ｉ≠１）
ｙ₁＝１
ｙ_h∈｛１，．．．．，ｎ｝ （ｈ∈Ｎ）
ｘ_hi∈｛０，１｝ （ｈ，ｉ∈Ｎ）
ここで、
・都市の個数：ｎ
・都市の集合：Ｎ＝｛１，．．．．，ｎ｝
・ＳＴＡＲＴ／ＧＯＡＬとなる都市：都市１
・都市ｈの訪問順番（決定変数）：ｙ_h （ｈ∈Ｎ）
・都市ｈから都市ｉへの移動（補助変数[有：１，無：０]）：ｘ_hi （ｈ，ｉ∈Ｎ）
・都市ｈから都市ｉへの移動コスト：ｃ_hi （ｈ，ｉ∈Ｎ）
である。

次に、本実施形態に係る目的関数及び条件式等を以下に示す。
納期制約条件を課すと、
目的関数は、Σ_h∈NΣ_i∈Nｃ_hiｘ_hi＋Σ_h∈S1ｐ_hｚ_h （式）
と表される。
また、納期制約条件を課すと、納期制約に係る条件式（納期制約条件式）は、
ｙ_h−ｕ_hｚ_h≦ｄ_h （ｈ∈Ｓ₁）
ｚ_h∈Ｚ₊ （ｈ∈Ｓ₁）
と表される。
ここで、
・納期制約を課す都市の集合：Ｓ₁⊆Ｎ
・都市ｈの訪問期限順番（都市ｈはｄ_h番目までに訪問する）：ｄ_h（ｈ∈Ｓ₁）
・都市ｈの納期遅れ単位量（１違反とする遅れの許容範囲）：ｕ_h（ｈ∈Ｓ₁）
・都市ｈの訪問に対する納期違反量（補助変数）：ｚ_h（ｈ∈Ｓ₁）
・都市ｈの訪問に対する納期違反ペナルティ値：ｐ_h（ｈ∈Ｓ₁）
である。
なお、Ｚ₊は、ゼロ以上の整数の集合を表している。

なお、納期制約のより具体的な例を、図４を用いて説明する。図４は、納期制約の一例を説明するための図である。上述したｄ_hを５、ｕ_hを２、ｐ_hを１００とすると、図４に示されるように「都市ｈには、５番目までに訪れたいが、１番でも遅れると１００の違反ペナルティ値を課す。納期遅れ単位量が２なので、２番遅れまでは１００の違反ペナルティ値であるが、３番遅れになると更に１００の違反ペナルティ値を課す。以下同様に納期遅れ単位量毎に所定のペナルティ値を課す。」という納期制約条件となる。なお、納期が複数の時間的期間ではなく、単純に訪問順番で与えられるのであれば、納期遅れ単位量を１とすればよい。また、納期制約条件を必ず守る必要があれば、納期遅れ単位量を０とすることで、納期違反量に関する新たな項を、考慮しないようにすればよい。

次に、ユーザが選択可能な制約条件に対応する制約条件式を以下に示す。

開始制約条件式
ｙ_h≧ａ_h (ｈ∈Ｓ₂)
ここで、
・開始制約を課す都市の集合：Ｓ₂⊆Ｎ
・都市ｈの訪問開始可能順番：ａ_h（ｈ∈Ｓ₂）
である。都市ｈの訪問は 、ａ_h番目以降でなければならないという制約である。

繋ぎ保証制約条件式
ｘ_hi＝１ （（ｈ，ｉ）∈Ｗ₃）
ここで、
・繋ぎ保証制約を課す都市のペアの集合：Ｗ₃⊆Ｎ×Ｎ
である。都市ｉの訪問は、都市ｈの次でなければならないという制約である。

順番固定制約条件式
ｙ_h＝ｆ_h（ｈ∈Ｓ₄）
ここで、
・順番固定制約を課す都市の集合：Ｓ₄⊆Ｎ
・固定順番：ｆ_h（ｈ∈Ｓ₄）
である。都市ｈの訪問は、ｆ_h番目でなければならないという制約である。

先行制約条件式
ｙ_h＋１≦ｙ_i （（ｈ，ｉ）∈Ｗ₅）
ここで、
・先行制約を課す都市のペアの集合：Ｗ₅⊆Ｎ×Ｎ
である。都市ｉの訪問は、都市ｈよりも後でなければならないという制約である。

連続上限制約条件式
｛ｈ∈Ｎ＼Ｓ₆｜ｖ≦ｙ_h≦ｖ＋ｋ｝≠φ （ｖ＝１，．．．．，ｎ−ｋ）
ここで、
・連続上限制約を課す都市の集合：Ｓ₆⊆Ｎ
・連続上限番数：ｋ
である。集合Ｓ₆に含まれる都市の訪問は、ｋ都市までしか連続してはならないという制約である。

間隔下限制約条件式
｛ｈ∈Ｓ₇：ｙ_i＋１≦ｙ_h≦ｙ_i＋ｍ｝＝φ （ｉ∈Ｓ₇）
ここで、
・間隔下限制約を課す都市の集合：Ｓ₇⊆Ｎ
・間隔下限番数：ｍ
である。集合Ｓ₇に含まれる都市の訪問間隔は、ｍ都市より離れなくてはならないという制約である。

分割上限制約条件式
Σ_h∈N＼S8Σ_i∈S8ｘ_hi≦ｇ
ここで、
・分割上限制約を課す都市の集合：Ｓ₈⊆Ｎ
・分割上限回数：ｇ
である。集合Ｓ₈に含まれる都市の訪問は連続させ、連続がｇ回より分割してはならないという制約である。

汎化納期制約条件式
Σ_(i,j)∈Rhｔ_ij≦ｅ_h （ｈ∈Ｓ₉）
ここで、
・汎化納期制約を課す都市の集合：Ｓ₉⊆Ｎ
・都市ｈまでの道程：Ｒ_h＝｛（ｉ，ｊ）∈Ｎ×Ｎ｜ｘ_ij＝１，ｙ_j≦ｙ_h｝ （ｈ∈Ｓ₉）
・都市ｉと都市ｊ間の所要時間：ｔ_ij （ｉ，ｊ∈Ｎ）
・都市ｈの訪問期限時間：ｅ_h（ｈ∈Ｓ₉）
である。都市ｈにはスタートからの時間ｅ_hまでに訪れなくてはならないという制約である。

再び図２の説明に戻り、代入部２５は、データ取得部２３において取得されたデータを用いて、上述した（式）で示される目的関数、納期制約条件式、及び第一の制約条件式呼び出し部２４において呼び出された制約条件式の定数に値を代入する。

入力部２６は、代入部２５において、定数に値が代入された前記目的関数及び前記制約条件式を最適化エンジン部２７に入力する。最適化エンジン部２７は、入力された制約条件式の下、目的関数が最小となるよう、例えば、分枝限定法等を用いて、解を求め（又は最適解を探索し）、求めた解を出力する。

解取得部２８は、最適化エンジン部２７が出力する解を取得する。第二の制約条件式呼び出し部２９は、制約条件定義情報に基づいて、制約条件選択部２２において選択された制約条件に対応する制約条件式の内、後処理に用いる制約条件式を呼び出す。

後処理部３０は、第二の制約条件式呼び出し部２９において呼び出された制約条件式を用いて、解取得部２８において取得された解に対して後処理を行う。出力部３１は、解取得部２８において取得された解、又は後処理部３０において後処理された解を表示装置１２に表示する。

図５は、情報処理装置１における情報処理の一例を示すフローチャートである。
なお、画面制御部２１は、ユーザ操作等に応じて、制約条件選択画面を表示装置１２上に表示させているものとする。以下、ユーザが、制約条件選択画面において、繋ぎ保証制約条件と、連続上限制約条件と、を選択したものとして説明を行う。

ステップＳ１１において、制約条件選択部２２は、画面制御部２１より受け取った情報に基づいて、制約条件を選択する。より具体的に説明すると、制約条件選択部２２は、繋ぎ保証制約条件と、連続上限制約条件と、を選択する。

ステップＳ１２において、画面制御部２１は、ステップＳ１１で制約条件選択部２２が選択した制約条件に応じた制約条件式の定数等を入力するためのデータ入力画面を作成し、表示装置１２に表示させる。ユーザは、このデータ入力画面を介して、目的関数、納期制約条件式及び自身が選択した制約条件に対応する制約条件式の定数に関するデータを入力する。より具体的に説明すると、ユーザは、上述したｎ，ｃ_hi，Ｓ₁，ｄ_h，ｕ_h，ｐ_h，Ｗ₃，Ｓ₆，ｋ等に関するデータを入力する。

ステップＳ１３において、データ取得部２３は、画面制御部２１より入力されたデータを取得する。

ステップＳ１４において、第一の制約条件式呼び出し部２４は、制約条件定義情報に基づいて、ステップＳ１１で制約条件選択部２２において選択された制約条件に対応する制約条件式の内、最適化エンジン部２７に入力する制約条件式を呼び出す。ここで、制約条件定義情報が図３に示されるような場合、連続上限制約条件は後処理で用いる制約条件式に対応する制約条件として設定されている。よって、第一の制約条件式呼び出し部２４は、繋ぎ保証制約条件式を呼び出す。なお、ここで、式を呼び出すとは、例えば、ファイル等に記述された式をＨＤ１９又はＲＡＭ１６等から読み出す（呼び出す）ことである。

ステップＳ１５において、代入部２５は、ステップＳ１３でデータ取得部２３において取得されたデータを用いて、上述した（式）で示される目的関数、納期制約条件式、及びステップＳ１４で第一の制約条件式呼び出し部２４において呼び出された制約条件式の定数に値を代入する。

ステップＳ１６において、入力部２６は、ステップＳ１５で代入部２５において定数に値が代入された目的関数及び制約条件式を最適化エンジン部２７に入力する。

ステップＳ１７において、最適化エンジン部２７は、入力された制約条件式の下、目的関数が最小となるよう、例えば、分枝限定法等を用いて、解を求め（又は最適解を探索し）、求めた解を出力する。

ステップＳ１８において、解取得部２８は、最適化エンジン部２７が出力する解を取得する。ステップＳ１９において、第二の制約条件式呼び出し部２９は、後処理を行うか否かを判定する。第二の制約条件式呼び出し部２９は、制約条件定義情報に基づいて、制約条件選択部２２において選択された制約条件の内、後処理に用いる制約条件式に対応する制約条件があるか否かに応じて、後処理を行うか否かを判定する。後処理を行う場合、ステップＳ２０に進み、後処理を行わない場合、ステップＳ２２に進む。

ステップＳ２０において、第二の制約条件式呼び出し部２９は、制約条件定義情報に基づいて、制約条件選択部２２において選択された制約条件に対応する制約条件式の内、後処理に用いる制約条件式を呼び出す。より具体的に説明すると、第二の制約条件式呼び出し部２９は、連続上限制約条件式を呼び出す。

ステップＳ２１において、後処理部３０は、ステップＳ２０で第二の制約条件式呼び出し部２９において呼び出された制約条件式を用いて、ステップＳ１８で解取得部２８において取得された解に対して後処理を行う。より具体的に説明すると、後処理部３０は、ステップＳ１８で解取得部２８において取得された解に対して、連続上限制約条件式を満たすように、例えば、３−ｏｐｔ法で解を修正する。連続上限制約条件式を満たすように、３−ｏｐｔ法で解を修正する処理の一例を、後述する図６等に示す。

ステップＳ２２において、出力部３１は、ステップＳ１９においてＮＯと判定され、本ステップの処理を実行する場合は、解取得部２８において取得された解を、また、ステップＳ１９においてＹＥＳと判定され、ステップＳ２０及びステップＳ２１の処理を経て本ステップの処理を実行する場合は、後処理部３０において後処理された解を、表示装置１２に表示する。

図６は、連続上限制約条件式を満たすように、３−ｏｐｔ法で解を修正する処理の一例を示すフローチャートである。
ステップＳ３１において、後処理部３０は、分解不能フラグをリセットする。

ステップＳ３２において、後処理部３０は、Ｓ₆の都市の連続箇所の内、分割不能な部分を除き、最長の連続Ａを選択する。続いて、ステップＳ３３において、後処理部３０は、Ａの連続数がｋ（つまり、連続上限番数）より大きいか否かを判定する。後処理部３０は、Ａの連続数がｋより大きいと判定すると、ステップＳ３４に進み、Ａの連続数がｋより大きくはないと判定すると、図６に示す処理を終了する。

続いて、ステップＳ３４において、後処理部３０は、順番を入れ替える区切り都市ＴＯＰ，ＭＩＤ，ＢＯＴを選択する。ここで、後処理部３０は、入れ替え後の並びが、他の制約条件に違反しないよう、また、収束を保証するための制約条件に違反しないよう、また、他の前記制約条件と、収束を保証するための制約条件と、を満たしつつ、目的関数が最小となるよう、ＴＯＰ，ＭＩＤ，ＢＯＴを選択する。

続いて、ステップＳ３５において、後処理部３０は、ＴＯＰ，ＭＩＤ，ＢＯＴを選択できたか否かを判定する。後処理部３０は、選択できたと判定すると、ステップＳ３６に進み、選択できなかったと判定すると、ステップＳ３７に進む。

ステップＳ３６において、後処理部３０は、都市並びのＴＯＰからの部分列と、ＭＩＤからの部分列と、を入れ替える。図７は、入れ替えの一例を説明するための図である。一方、ステップＳ３７において、後処理部３０は、Ａが分割不能であることを示すよう、分割不能フラグをセットする。

以上、上述したように本実施形態によれば、巡回セールスマン問題において、複数の時間的期間に細分化された所定の時間的期間内で、全体として最適な順序を求めることができる。

＜実施形態２＞
上述した実施形態では、納期制約条件をデフォルトの制約条件として説明を行ったが、他の制約条件と同様に、ユーザが選択可能な制約条件としてもよい。

＜実施形態３＞
上述した実施形態では、説明の簡略化のため、納期制約条件の場合のみ、ペナルティ値を課すよう説明を行った。つまり、情報処理装置１は、納期制約条件の場合のみ、上述した（式）で表されるように、目的関数に、納期違反ペナルティ値が重み付けされている、納期違反量に関する新たな項を追加した。
しかしながら、上述した制約条件の内、順番固定制約条件以外の制約条件に関しては、納期制約条件の場合と同様に、各制約条件に係るペナルティ値を重み付けした、違反量に関する新たな項を目的関数に追加するようにしてもよい。

図８は、実施形態３の情報処理装置１の機能構成の一例を示す図である。図８に示されるように、情報処理装置１は、機能構成として、画面制御部５１と、制約条件選択部５２と、データ取得部５３と、第一の制約条件式呼び出し部５４と、代入部５５と、入力部５６と、最適化エンジン部５７と、解取得部５８と、第二の制約条件式呼び出し部５９と、後処理部６０と、出力部６１と、目的関数変更部６２と、を含む。

画面制御部５１は、データ入力画面や、制約条件選択画面等に関する制御を行う。より具体的に説明すると、画面制御部５１は、ユーザからの要求に応じて、データ入力画面や、制約条件選択画面等を表示装置１２に表示させたり、データ入力画面において入力されたデータをデータ取得部５３に渡したり、制約条件選択画面において選択された制約条件の情報を制約条件選択部５２に渡したりする。
本実施形態において、ユーザは、制約条件選択画面において、納期制約条件、開始制約条件、繋ぎ保証制約条件、順番固定制約条件、先行制約条件、連続上限制約条件、間隔下限制約条件、分割上限制約条件、汎化納期制約条件を選択するものとする。

制約条件選択部５２は、画面制御部５１より受け取った情報に基づいて、制約条件を選択する。データ取得部５３は、画面制御部５１より受け取ったデータ（目的関数や制約条件に係る入力データ）を取得する。なお、画面制御部５１は、目的関数や、制約条件選択部５２が選択した制約条件に応じた制約条件式の定数を入力するためのデータ入力画面を表示装置１２に表示させる。そして、画面制御部５１は、上述したように、データ入力画面において入力されたデータをデータ取得部５３に渡す。

第一の制約条件式呼び出し部５４は、制約条件定義情報に基づいて、制約条件選択部５２において選択された制約条件に対応する制約条件式の内、最適化エンジン部５７に入力する制約条件式を呼び出す。

目的関数変更部６２は、第一の制約条件式呼び出し部５４が呼び出した制約条件式に対応する制約条件に応じて、例えば、この制約条件に応じた違反ペナルティ値を重み付けした違反量に関する項を目的関数に追加する等して目的関数を変更する。

代入部５５は、データ取得部５３において取得されたデータを用いて、目的関数変更部６２において変更された（項を新たに追加された）目的関数及び第一の制約条件式呼び出し部５４において呼び出された制約条件式の定数に値を代入する。

入力部５６は、代入部５５において、定数に値が代入された前記目的関数及び前記制約条件式を最適化エンジン部５７に入力する。最適化エンジン部５７は、入力された制約条件式の下、目的関数が最小となるよう、例えば、分枝限定法等を用いて、解を求め（又は最適解を探索し）、求めた解を出力する。

解取得部５８は、最適化エンジン部５７が出力する解を取得する。第二の制約条件式呼び出し部５９は、制約条件定義情報に基づいて、制約条件選択部５２において選択された制約条件に対応する制約条件式の内、後処理に用いる制約条件式を呼び出す。

後処理部６０は、第二の制約条件式呼び出し部５９において呼び出された制約条件式を用いて、解取得部５８において取得された解に対して後処理を行う。出力部６１は、解取得部５８において取得された解、又は後処理部６０において後処理された解を表示装置１２に表示する。

＜実施形態４＞
上述した実施形態では、都市の訪問順番を決定する例を用いて、巡回セールスマン問題に関する情報処理装置１の処理の説明を行ったが、上述した処理は、例えば、製造業における様々な製造工程の通品順序決めに適用することができる。この場合、上述した「都市間の移動コスト」は、「品種切り替えによる歩留まりにかかるコストや製造設備の組み替えにかかるコスト」等に対応する。

また、通品順序決めに適用した場合、納期（ある順番までに通品すること）を守ることに関する条件が、上述した納期制約条件に対応する。また、ある資材到着後に通品できることに関する条件が、上述した開始制約条件に対応する。また、品Ａの次に品Ｂを通すことに関する条件が、上述した繋ぎ保証制約に対応する。また、通品順番が指定されていることに関する条件が、上述した順番固定制約条件に対応する。また、品Ａは品Ｂより先に通品することに関する条件が、上述した先行制約条件に対応する。また、特定品種の連続番数に上限があることに関する条件が、上述した連続上限制約条件に対応する。また、特定品種の間隔番数に下限があることに関する条件が、上述した間隔下限制約条件に対応する。また、連続通品させたい品種の連続が分割される回数に上限があることに関する条件が、上述した分割上限制約条件に対応する。また、納期（作業時間等の累積）を守ることに関する条件が、上述した汎化納期制約条件に対応する。

以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。

情報処理装置１のハードウェア構成の一例を示す図である。 実施形態１の情報処理装置１の機能構成の一例を示す図である。 制約条件定義情報の一例を示す図である。 納期制約の一例を説明するための図である。 情報処理装置１における情報処理の一例を示すフローチャートである。 連続上限制約条件式を満たすように、３−ｏｐｔ法で解を修正する処理の一例を示すフローチャートである。 入れ替えの一例を説明するための図である。 実施形態３の情報処理装置１の機能構成の一例を示す図である。

符号の説明

１ 情報処理装置
１１ 入力装置
１２ 表示装置
１３ 記録媒体ドライブ装置
１４ 記録媒体
１５ ＲＯＭ
１６ ＲＡＭ
１７ ＣＰＵ
１８ インターフェース装置
１９ ＨＤ
２１ 画面制御部
２２ 制約条件選択部
２３ データ取得部
２４ 第一の制約条件式呼び出し部
２５ 代入部
２６ 入力部
２７ 最適化エンジン部
２８ 解取得部
２９ 第二の制約条件式呼び出し部
３０ 後処理部
３１ 出力部

Claims (10)

1. 納期に係る順番の期限を表す納期期限情報と、納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と、納期違反量と、に関する納期制約条件式を満たしつつ、納期違反のペナルティ値がかけられている納期違反量を変数として含む、移動費用に関する目的関数が最小となるよう、分枝限定法を用いて解を求めることを特徴とする納期付きの巡回セールスマン問題の求解方法。
2. 情報処理装置における巡回セールスマン問題の求解方法であって、
   納期違反のペナルティ値がかけられている納期違反量を補助変数として含む、移動費用に関する目的関数及び納期に係る順番の期限を表す納期期限情報と納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と前記納期違反量とに関する納期制約条件式を最適化手段に入力する入力ステップと、
   前記最適化手段が、入力された前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求める求解ステップと、
   前記最適化手段より解を取得する取得ステップと、
   前記取得ステップにおいて取得された解を表示装置に出力する出力ステップと、
   を有することを特徴とする巡回セールスマン問題の求解方法。
3. 前記最適化手段は、分枝限定法を用いて、前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求めることを特徴とする請求項２に記載の巡回セールスマン問題の求解方法。
4. 前記取得ステップにおいて取得された解に対して、連続上限制約条件を満たすように、３−ｏｐｔ法を用いて修正を行う修正ステップを更に有し、
   前記出力ステップでは、前記修正ステップにおいて修正された解を表示装置に出力することを特徴とする請求項２又は３に記載の巡回セールスマン問題の求解方法。
5. データを取得するデータ取得手段と、
   前記データ取得手段において取得されたデータを用いて、納期違反のペナルティ値がかけられている納期違反量を補助変数として含む移動費用に関する目的関数の定数と、定数である納期に係る順番の期限を表す納期期限情報と納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と補助変数である前記納期違反量とに関する納期制約条件式の定数と、に値を代入する代入手段と、
   前記代入手段において定数に値が代入された前記目的関数と、前記納期制約条件式と、を最適化手段に入力する入力手段と、
   前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求める最適化手段と、
   前記最適化手段が出力する解を取得する解取得手段と、
   前記解取得手段において取得された解を表示装置に出力する出力手段と、
   を有することを特徴とする情報処理装置。
6. 制約条件を選択する制約条件選択手段と、
   前記制約条件選択手段において選択された制約条件に対応する制約条件式を呼び出す第一の制約条件式呼び出し手段と、
   を更に有し、
   前記代入手段は、前記データ取得手段において取得されたデータを用いて、前記目的関数の定数と、前記納期制約条件式の定数と、前記第一の制約条件式呼び出し手段において呼び出された制約条件式の定数と、に値を代入し、
   前記入力手段は、前記代入手段において定数に値が代入された、前記目的関数と、前記納期制約条件式と、前記第一の制約条件式呼び出し手段において呼び出され、前記代入手段において定数に値が代入された前記制約条件式と、を最適化手段に入力することを特徴とする請求項５に記載の情報処理装置。
7. 制約条件を選択する制約条件選択手段と、
   制約条件定義情報に基づいて、前記制約条件選択手段において選択された制約条件に対応する制約条件式の内、最適化手段に入力する制約条件式を呼び出す第一の制約条件式呼び出し手段と、
   を更に有し、
   前記代入手段は、前記データ取得手段において取得されたデータを用いて、前記目的関数の定数と、前記納期制約条件式の定数と、前記第一の制約条件式呼び出し手段において呼び出された制約条件式の定数と、に値を代入し、
   前記入力手段は、前記代入手段において定数に値が代入された、前記目的関数と、前記納期制約条件式と、前記第一の制約条件式呼び出し手段において呼び出され、前記代入手段において定数に値が代入された前記制約条件式と、を最適化手段に入力することを特徴とする請求項５に記載の情報処理装置。
8. 制約条件定義情報に基づいて、前記制約条件選択手段において選択された制約条件に対応する制約条件式の内、後処理で用いる制約条件式を呼び出す第二の制約条件式呼び出し手段と、
   前記第二の制約条件式呼び出し手段において呼び出された制約条件式を用いて、前記解取得手段において取得された解に対して後処理を行う後処理手段と、
   を更に有し、
   前記出力手段は、前記後処理手段において後処理された解を表示装置に出力することを特徴とする請求項７に記載の情報処理装置。
9. 情報処理装置における情報処理方法であって、
   データを取得するデータ取得ステップと、
   前記データ取得ステップにおいて取得されたデータを用いて、納期違反のペナルティ値がかけられている納期違反量を補助変数として含む移動費用に関する目的関数の定数と、定数である納期に係る順番の期限を表す納期期限情報と納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と補助変数である前記納期違反量とに関する納期制約条件式の定数と、に値を代入する代入ステップと、
   前記代入ステップにおいて定数に値が代入された前記目的関数と、前記納期制約条件式と、を最適化手段に入力する入力ステップと、
   前記最適化手段が前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求める最適化ステップと、
   前記最適化手段が出力する解を取得する解取得ステップと、
   前記解取得ステップにおいて取得された解を表示装置に出力する出力ステップと、
   を有することを特徴とする情報処理方法。
10. コンピュータを、
    データを取得するデータ取得手段と、
    前記データ取得手段において取得されたデータを用いて、納期違反のペナルティ値がかけられている納期違反量を補助変数として含む移動費用に関する目的関数の定数と、定数である納期に係る順番の期限を表す納期期限情報と納期に対して何番目の遅れまでを１違反とするかを表す納期遅れ単位量と補助変数である前記納期違反量とに関する納期制約条件式の定数と、に値を代入する代入手段と、
    前記代入手段において定数に値が代入された前記目的関数と、前記納期制約条件式と、を最適化手段に入力する入力手段と、
    前記納期制約条件式を満たしつつ、前記目的関数が最小となるよう解を求める最適化手段と、
    前記最適化手段が出力する解を取得する解取得手段と、
    前記解取得手段において取得された解を表示装置に出力する出力手段と、
    して機能させることを特徴とするプログラム。

Images