(57)【特許請求の範囲】
【請求項１】
中央演算装置と、ワーキングメモリと、読出専用メモリと、記録装置と、入出力インタフェース部とを共通バスでそれぞれ接続してなり、入出力インタフェース部を介して入力機器ならびに画像表示装置が接続された、複数の拠点を巡回する際における、運送コストあるいは巡回所要時間あるいは拠点数を最適化する自動最適化装置であって、
前記読出専用メモリには、条件設定手段、最適化手段、目的函数設定手段、最適化結果表示手段が、それぞれ前記中央演算装置によって実行可能なプログラムで記録されており、前記ワーキングメモリには、目的函数設定手段によって設定された前記複数の拠点を巡回する際における、運送コストあるいは巡回所要時間あるいは拠点数に基づく目的函数が一時記録され、
前記条件設定手段は、予め設定された複数の拠点と前記複数の拠点間の距離と方向を規定した平面上での分散配置状態と、かつ前記各拠点において必要とする物量が設定されているマップに基づいて、少なくとも前記距離、方向、物量を最適化演算のための条件として設定し、
前記目的函数の設定手段は、前記目的函数を前記物量を金額換算した金額を含めて運送する製品の製品代金と前記運送コストとの和である金額と前記距離と方向を時間換算した時間を含めた前記巡回所要時間との積として設定し、前記最適化演算のために使用され、
前記記憶装置は、二箇所以上の拠点からなるクラスターの構成拠点を順に辿る順序を規定したクラスター・パターンがデータとして記録し、
前記最適化手段は、前記条件下で前記マップを構成する前記複数の拠点を前記クラスター・パターンに当てはめて各クラスタに分割するとともに、前記各クラスタ毎に目的函数を分割の仕方すべての場合に対して計算し、前記目的函数を最小にする最適化するような前記クラスタの組み合わせを求めることを特徴とする自動最適化装置。
【請求項２】
中央演算装置と、ワーキングメモリと、読出専用メモリと、記録装置と、入出力インタフェース部とを共通バスでそれぞれ接続してなり、入出力インタフェース部を介して入力機器ならびに画像表示装置が接続された装置により実行する複数の拠点を巡回する際における、運送コストあるいは巡回所要時間あるいは拠点数を最適化する最適化方法であって、
前記読出専用メモリに記憶されたプログラムにより前記中央演算装置により、予め設定された複数の拠点と前記複数の拠点間の距離と方向を規定した平面上での分散配置状態と、かつ前記各拠点において必要とする物量が設定されているマップに基づいて、少なくとも前記距離、方向、物量を最適化演算のための条件として設定する条件設定工程と、
前記読出専用メモリに記憶されたプログラムにより前記中央演算装置により、最適化演算のために使用される前記複数の拠点を巡回する際における、運送コストあるいは巡回所要時間あるいは拠点数に基づく、前記物量を金額換算した金額を含めて運送する製品の製品代金と前記運送コストとの和である金額と前記距離と方向を時間換算した時間を含めた前記巡回所要時間との積として目的函数を設定する工程と、
前記読出専用メモリに記憶されたプログラムにより前記中央演算装置により、二箇所以上の拠点からなるクラスターの構成拠点を順に辿る順序を規定したクラスター・パターンが、データとして記録された記録装置から前記クラスター・パターンを読出し、前記条件下で前記マップを構成する前記複数の拠点を前記クラスター・パターンに当てはめて各クラスタに分割するとともに、前記各クラスタ毎に目的函数を分割の仕方すべての場合に対して計算し、前記目的函数を最小にする前記最適化するようなクラスタの組み合わせを演算する最適化工程と、を少なくとも含んで成ることを特徴とする最適化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、最適化方法および自動最適化装置に関し、詳しくは、所定の目的函数を指標として、分散配置された複数の拠点を最適化する最適化方法および自動最適化装置に関するものである。
【０００２】
【従来の技術】
予め設定された距離と方向を互いに保つ複数の拠点が、平面上に分散配置されていて、しかもこれら各拠点において所定の物量が必要とされるようなシステムは、物資の集荷や配送業務において多く見うけられる。
【０００３】
例えば、ある配送センターから所定の物量を積載した貨物車が、各拠点において必要量の物資をおろしつつ、順に各拠点を巡る場合や、集荷用の貨物車が各拠点において物資を搭載しつつ、順に各拠点を巡る場合がある。このような場合には、拠点を巡る途中の物資の増減と、巡回経路によって決まる走行距離とに依存して配送／集荷コストあるいは所要時間が変化するから、配送／集荷コストあるいは所要時間を最小にするために、巡回経路の最適化が必要となる。
【０００４】
あるいは、配送センターから貨物車が各拠点に物資を配達する場合に、与えられた制約条件下で、例えば配達コストあるいは所要配達時間の極小化を実現すべく拠点数を減らす必要があるとき、いずれの拠点を残して集約させるかの、拠点数の最適化が必要となる。
【０００５】
【発明が解決しようとする課題】
しかしながら、従来においては前記のような、運送コストあるいは巡回所要時間を最小にする巡回経路の最適化、または拠点数の集約による最適化を可能にする容易な方法や、こうした最適化を自動的に実行可能な装置が提供されていなかった。
【０００６】
本発明は、前記のような従来技術における問題点を解決するためなされたもので、複数の拠点を巡回する際における、運送コストあるいは巡回所要時間あるいは拠点数を最適化する方法および自動最適化装置を提供することを目的とするものである。
【０００７】
【課題を解決するための手段】
前記課題を解決するため本発明に係る自動最適化装置は、  中央演算装置と、ワーキングメモリと、読出専用メモリと、記録装置と、入出力インタフェース部とを共通バスでそれぞれ接続してなり、入出力インタフェース部を介して入力機器ならびに画像表示装置が接続された、複数の拠点を巡回する際における、運送コストあるいは巡回所要時間あるいは拠点数を最適化する自動最適化装置であって、読出専用メモリには、条件設定手段、最適化手段、目的函数設定手段、最適化結果表示手段が、それぞれ中央演算装置によって実行可能なプログラムで記録されており、ワーキングメモリには、目的函数設定手段によって設定された複数の拠点を巡回する際における、運送コストあるいは巡回所要時間あるいは拠点数に基づく目的函数が一時記録され、条件設定手段は、予め設定された複数の拠点と複数の拠点間の距離と方向を規定した平面上での分散配置状態と、かつ各拠点において必要とする物量が設定されているマップに基づいて、少なくとも距離、方向、物量を最適化演算のための条件として設定し、目的函数の設定手段は、目的函数を物量を金額換算した金額を含めて運送する製品の製品代金と運送コストとの和である金額と距離と方向を時間換算した時間を含めた巡回所要時間との積として設定し、最適化演算のために使用され、記憶装置は、二箇所以上の拠点からなるクラスターの構成拠点を順に辿る順序を規定したクラスター・パターンがデータとして記録し、最適化手段は、条件下で前記マップを構成する複数の拠点をクラスター・パターンに当てはめて各クラスタに分割するとともに、各クラスタ毎に目的函数を分割の仕方すべての場合に対して計算し、目的函数を最小にする最適化するようなクラスタの組み合わせを求めることを特徴とする。
【０００８】
前記の構成を有する本発明に係る自動最適化装置によれば、条件設定手段によってマップに基づく条件設定がなされ、ついで最適化手段によって、記録装置に記録されているクラスター・パターンを適用してマップがサブパターンに分割され、目的函数を最適化するようなサブパターンの組み合わせが自動演算されることによって最適な解が提供される。
【０００９】
また、本発明に係る最適化方法は、中央演算装置と、ワーキングメモリと、読出専用メモリと、記録装置と、入出力インタフェース部とを共通バスでそれぞれ接続してなり、入出力インタフェース部を介して入力機器ならびに画像表示装置が接続された装置により実行する複数の拠点を巡回する際における、運送コストあるいは巡回所要時間あるいは拠点数を最適化する最適化方法であって、読出専用メモリに記憶されたプログラムにより中央演算装置により、予め設定された複数の拠点と複数の拠点間の距離と方向を規定した平面上での分散配置状態と、かつ各拠点において必要とする物量が設定されているマップに基づいて、少なくとも距離、方向、物量を最適化演算のための条件として設定する条件設定工程と、読出専用メモリに記憶されたプログラムにより中央演算装置により、最適化演算のために使用される複数の拠点を巡回する際における、運送コストあるいは巡回所要時間あるいは拠点数に基づく、物量を金額換算した金額を含めて運送する製品の製品代金と運送コストとの和である金額と距離と方向を時間換算した時間を含めた巡回所要時間との積として目的函数を設定する工程と、読出専用メモリに記憶されたプログラムにより中央演算装置により、二箇所以上の拠点からなるクラスターの構成拠点を順に辿る順序を規定したクラスター・パターンが、データとして記録された記録装置からクラスター・パターンを読出し、条件下でマップを構成する複数の拠点をクラスター・パターンに当てはめて各クラスタに分割するとともに、各クラスタ毎に目的函数を分割の仕方すべての場合に対して計算し、目的函数を最小にする最適化するようなクラスタの組み合わせを演算する最適化工程と、を少なくとも含んで成ることを特徴とする。
【００１０】
前記の構成を有する本発明にかかる最適化方法によれば、条件設定工程により設定されたマップが、最適化工程により、記録装置に記録されているクラスター・パターンに基づいてサブパターンに分割され、さらに目的函数を最適化するようなサブパターンの組み合わせが自動演算されることによって最適な解が提供される。
【００１１】
【発明の実施の形態】
以下、この発明の好適な実施形態を添付図を参照して詳細に説明する。なお、以下に述べる実施形態は、この発明の本質的な構成と作用を示すための好適な例の一部であり、したがって技術構成上好ましい種々の限定が付されている場合があるが、この発明の範囲は、以下の説明において特にこの発明を限定する旨の記載がない限り、これらの形態に限られるものではない。
【００１２】
図１は本発明に係る自動最適化装置の一実施の形態を示すブロック構成図である。本発明に係る自動最適化装置１は、入力機器２と、条件設定手段３と、最適化手段４と、目的函数設定手段５と、最適結果表示手段６と、クラスター・パターン７と、クラスター・パターン７が群として記録されている記録装置８とからなる。
【００１３】
条件設定手段３は、互いに予め設定された距離と方向を保つ複数の拠点の平面上での分散配置状態と、かつ各拠点において必要とする物量が設定されているマップに基づいて、少なくとも距離、方向、物量を最適化演算のための条件として設定する。
【００１４】
目的函数設定手段５は、最適化のための指標として、最適化演算において使用される。クラスター・パターン７は、二箇所以上の拠点からなるクラスターの構成拠点を順に辿る順序を規定したデータとして記録されている。最適化手段４は、前記の条件下でマップを構成する複数の拠点をクラスター・パターンに当てはめてサブパターンに分割するとともに、目的函数を最適化するようなサブパターンの組み合わせを演算する。
【００１５】
図２は記録装置に記録されているクラスター・パターンの例を示す説明図である。クラスター・パターンは、数個のポイントとアローが形成させるトポロジー的属性を規定するもので、とりわけポイント相互の位置関係と辿る経路情報をそれぞれ有している。図２で、丸印は拠点を、矢印は経路を示し、丸印内のＳは経路の始点を、丸印内のＴは経路の終点を示す。
【００１６】
パターン１１は、二つの拠点から成るもので、基本パターンである。したがって他のパターンと併用して適用される。一方、パターン１２は、三つの拠点から成るもので、始点から終点までが順に最寄りの拠点を辿って経路が構成される。さらにパターン１３は、同じく三つの拠点から成るが、最寄りの拠点を辿らず経路が構成されるものである。一方、パターン１４〜１６は、四つの拠点から成る場合の種々の経路構成を示している。クラスター・パターン７の群は、図示されたこれらパターン以外の多くのパターンから構成されている。
【００１７】
図３は、図１に示される自動最適化装置のハードウエア構成図である。自動最適化装置１は、中央演算装置（ＣＰＵ）２１と、ワーキングメモリ（ＲＡＭ）２２と、読出専用メモリ（ＲＯＭ）２３と、例えばハード磁気ディスクを記録媒体としてクラスターパターン７が記録された記録装置８と、入出力インタフェース部２４とを共通バス（ＢＵＳ）２５でそれぞれ接続してなる。入出力インタフェース部２４を介して入力機器２ならびに画像表示装置２６が接続される。
【００１８】
読出専用メモリ（ＲＯＭ）２３には、条件設定手段３、最適化手段４、目的函数設定手段５、最適化結果表示手段６が、それぞれ中央演算装置ＣＰＵによって実行可能なプログラムで記録されている。揮発性のワーキングメモリ（ＲＡＭ）２２には、目的函数設定手段５によって設定された目的函数２７が一時記録される。
【００１９】
目的函数２７は、例えば製品代金と輸送費用との和である金額と、所要時間との積として設定され、最適化はこの積が最小となるよう変数設定される。ここで、物量すなわち輸送量の評価単位としては、個数や体積、重量が選択可能であるが、これを金額換算して適用することが好ましい。さらに拠点間の隔たりの評価単位としては、距離あるいは速度が選択可能であるが、これを時間換算して適用することが好ましい。
【００２０】
図４は拠点のマップの例を示す説明図である。マップＭＰは、平面上に拡がった領域にポイント（拠点）が分布している状態と、ポイント間の距離または速度が時間換算された値と、各ポイントへ運搬すべき物量すなわち重量または体積が金額換算された値を規定するもので、図では工場、店舗、倉庫、配送／集積場などの拠点であるポイントがＰ１からＰ７までの７拠点、それぞれのポイントにおける物量が金額換算値でＴ１からＴ７、それに各ポイントＰ１〜Ｐ７間の距離が時間換算値でＤ１からＤ１２として示されている。このマップが、入力機器２から条件設定手段３へ入力される。
【００２１】
図５は、図１に示される自動最適化装置の動作フローチャートである。条件として入力機器２からマップＭＰが入力されると、これに基づき条件設定手段３が条件の設定を行い、ワーキングメモリＲＡＭに一時記憶する（ステップＳ１）。次に、目的函数設定手段５が最適化の指標となる目的函数を設定してワーキングメモリＲＡＭに一時記憶すると（ステップＳ２）、最適化手段４が記録装置８からクラスターパターン７を読みだしてワーキングメモリＲＡＭに一時記憶する（ステップＳ３）。
【００２２】
次いで、最適化手段４は、一時記憶したクラスター・パターン７と、設定された条件を用いて、マップＭＰを複数個のクラスターに分割する（ステップＳ４）。このとき、適用されるクラスター・パターン７は、図２に示したもののうちの一種類とは限らず、複数のパターンの組み合わせとなるのが一般的である。したがって、分割方法とパターンの適用方法の組み合わせにより多くのケースが発生する。
【００２３】
このようにして分割形成された各クラスターにつき、ポイント間の時間換算値と各ポイントでの物量の金額換算値を適用して、目的函数を指標として最適化を演算する（ステップＳ５）。これは部分最適化となる。
【００２４】
前記のような部分最適化を分割形成されたクラスター全部につき実行し（ステップＳ６）、このようにして各クラスターにつき部分最適化がなされると、ついで最適化手段４はこの結果を用いてマップＭＰ全体の最適化を行う（ステップＳ７）。なお、この全体の最適化において再度ステップＳ４に戻ってマップの分割を試みる（イタレーション）必要が生じる場合がある。
【００２５】
このようにして最適化がなされると、最適結果表示手段６により結果が表示可能な形式に編成され、画面表示装置ＣＲＴによって表示がなされる。このように、本発明の構成によればクラスターパターンが予め準備されているので、マップの分割および条件を適用しての最適化演算が容易となり、また最適化演算の自動化が可能になる。
【００２６】
図６は最適化の例を示すグラフである。図６において、縦軸は総費用Ｃｔ、横軸はポイント数Ｎｐであり、線図Ｃは総輸送費、線図Ｄは輸送時間を最小にしたときの輸送費である。さらに線図Ａは、線図Ｃの値と線図Ｄの値の和による総費用である。本最適化においてはこの総費用Ａが目的函数となる。
【００２７】
図６から明らかなように、総費用の線図Ａはポイント数Ｂｐにおいて最小となる。このＢｐが求める最適ポイント数となる。このように、本発明に係る自動最適化装置によれば、前記のような経路の最適化のみならず、目的函数を適切に選び適用することによって、ネットワークを構成する拠点の数を削減する際の最適化をも容易に実行することが可能になる。しかもこの最適化操作において、図６では表示されていないが、拠点数と同時に、削減さるべき個別のポイント（あるいは集約するポイント）を特定させることも可能である。
【００２８】
【発明の効果】
以上詳述したように本発明の請求項１に係る自動最適化装置は、記録装置にクラスター・パターン群を備え、最適化手段がクラスター・パターンに基づいてマップをサブパターンに分割して、目的函数を最適化するようなサブパターンの組み合わせを演算する構成とするものであるから、最適な拠点構成を自動演算可能な装置が実現できるという効果を奏する。
【００２９】
本発明の請求項２に係る最適化方法は、記録装置から読みだしたクラスター・パターンに基づいてマップをサブパターンに分割して、目的函数を最適化するようなサブパターンの組み合わせを演算する構成とするものであるから、最適な拠点構成を得ることができる。
【図面の簡単な説明】
【図１】本発明に係る自動最適化装置の一実施の形態を示すブロック構成図
【図２】記録装置に記録されているクラスター・パターンの例を示す説明図
【図３】図１に示される自動最適化装置のハードウエア構成図
【図４】拠点のマップの例を示す説明図
【図５】図１に示される自動最適化装置の動作フローチャート
【図６】最適化の例を示すグラフ
【符号の説明】
１…自動最適化装置、２…入力装置、３…条件設定手段、４…最適化手段、５…目的函数設定手段、６…最適結果表示手段、７…クラスター・パターン群、８…記録装置。
【図１】
0003578916.tif 000002
【図２】
0003578916.tif 000003
【図３】
0003578916.tif 000004
【図４】
0003578916.tif 000005
【図５】
0003578916.tif 000006
【図６】
0003578916.tif 000007