(57)【要約】【課題】  納入先の納期を遵守し、且つ輸送コストを最小にする輸送計画を、短時間のうちに正確に立案することができるようにする。【解決手段】  各製品の品種、製造完了時刻、及び製造元からなる製品リストと、各納品に関する品種、納期、及び納入先からなる納品リストと、製造元から納入先までの輸送に要する時間からなる輸送時間テーブルとを、ユーザの入力装置１の操作に基づいてコンピュータ本体２が入力し、前記各製品と前記各納品との割り付けと、前記各製品のまとめ輸送方法とを表す整数変数を定め、輸送計画を立案するのに必要となる各種制約を、線形等式と線形不等式とで定式化し、納期遅れと輸送コストの重みつき総和で定義される評価関数の値を最小にする最適化計算を行い、前記各製品の納入先とまとめ輸送方法を決定する。【選択図】  図１
2005145573.tif 000002
【特許請求の範囲】
【請求項１】
異なる場所で製造される複数の製品を、異なる場所に存在する複数の納入先に輸送する際に、製品の納入先と、製品同士のまとめ輸送方法とを計画立案する方法であって、
前記製品毎に定められた輸送開始可能となる製造完了時刻、品種および製造元からなる製品リストと、
前記製品の納入先が必要とする納品毎に定められた納期、品種および納入先からなる納品リストと、
前記製品の製造元と納入先との組合せ毎に定められた輸送時間が登録された輸送時間テーブルとを入力し、
前記製品と前記納品との割り付けと、前記製品同士のまとめ輸送方法とを、それぞれ整数変数で表し、これらの整数変数を用いて、各納品の納期遅れと、各製品の輸送コストとを算出するための制約式を線形等式及び線形不等式で定式化し、
前記各納品の納期遅れと、前記各製品の輸送コストとの重み付き総和で定義される評価関数の値を最小にする最適化計算を行い、前記各製品の納入先と、前記製品同士のまとめ輸送方法とを計画立案することを特徴とする輸送計画立案方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、輸送計画立案方法に関し、特に、製品の納期を遵守し、かつ、製品の輸送コストを可及的に最小とするための輸送計画を立案するために用いて好適なものである。
【背景技術】
【０００２】
図２のように、複数の工場（製造元）Ａ、Ｂで製造した製品を、複数の客先（納入先）Ｐ、Ｑ、Ｒにトラック等の輸送車２０ａ、２０ｂで輸送する場合、指定された納期を遵守することが大事である。加えて、輸送車２０ａ、２０ｂが複数の製品を積載することが可能な場合には、輸送コストを少なくするため、前記複数の製品を極力まとめて輸送した方が望ましい。
図３は、製造される製品のリスト（製品リスト）を示した図である。この製品リスト３０に挙げられている製品には、過去に製造され、現在は出荷倉庫に存在する製品も含まれている。図４は、納入先に未入荷のリスト（納品リスト）を示した図である。
図３の製品リスト３０において、各々の製品は、製造完了時刻の早いものから順に並んでいる。また、図４の納品リスト４０において、各々の納品は、納期の早いものから順に並んでいる。
図５の輸送時間テーブル５０は、工場（製造元）Ａ、Ｂと、客先（納入先）Ｐ、Ｑ、Ｒとの間の輸送に要する時間であり、例えば工場（製造元）Ａから客先（納入先）Ｐまで製品を輸送する場合、１２分掛かるということを意味している。
【０００３】
ここで、従来の輸送計画例について説明する。
まず、全ての製品を１品ごとに客先（納入先）Ｐ、Ｑ、Ｒに輸送するとする。また、製品リスト３０において製造完了時刻が早い順（製品リスト順）、納品リスト４０において納期が早い順（納品リスト順）に見て、製品を品種が等しい納品に割り付ける。そうすると、輸送計画のリストは、図６のようになる。
図６の輸送計画のリスト６０において、輸送時間は、当該製品の工場（製造元）Ａ、Ｂから客先（納入先）Ｐ、Ｑ、Ｒまでの輸送に掛かる時間であり、図５の輸送時間テーブル５０で与えられる値である。
また、納入時刻は、製造完了時刻に輸送時間を加えた時刻である。なお、製造完了時刻が現在時刻より小さい場合には、現在時刻に輸送時間を加えた時刻を納入時刻にしなければならないが、ここでは、製造完了時刻は全て現在時刻より大きいとしている。
余裕時間は、納期から納入時刻を差し引いた時間である。図６の輸送計画のリスト６０の下に示されているように、この場合には総輸送時間は１２６分掛かってしまう。
【０００４】
次に、図６に示した輸送計画のリスト６０の上の行から順番に見て、ある製品を後に製造される製品とまとめて輸送しても納期に間に合う場合には、これらの製品をまとめて輸送することにすると、図６に示した輸送計画のリスト６０は、図７のようになる。図７の輸送計画のリスト７０において、太枠は、製品をまとめて輸送することを意味している。この場合には、総輸送時間を９４分に減らすことができる。
【０００５】
さらに、図７に示した輸送計画のリスト７０内の製品番号１０３〜１０７を見直し、図８のような輸送計画にすると、総輸送時間を７６分に減らすことができる。このような輸送計画を手作業で検証するためには、全ての輸送方法を列挙する必要があり、大変な時間が掛かる作業となってしまうが、実は、図８に示した輸送計画における割り付けは最適解の１つとなっている。
【０００６】
図８に示した輸送計画のリスト８０では、たまたま人手でも最適解を得ることが出来た例であるが、一般にはこのような問題を人手で解くことは困難である。最適解をコンピュータで演算するにしても、全数探索を行った場合には、｛製品数！×（製品数−１）！｝通り（！は階乗記号）もの探索が必要である。前述した例の場合には、約２億通りもの探索を必要とするので、多大の計算時間を要する。さらに、先に示したようなリスト内のパラメータを順番に探索して輸送計画を確定するような欲張り法では、図７の輸送計画のリスト７０に示した解程度しか得られず、最適解を確実に得ることはできない。また、特開平７−１７５５０４号公報、特開平８−１５３０８５号公報に記載されている、シミュレーテッド・アニーリング法を本問題に応用したとしても、局所最適点に落ち込んでしまい、真の最適解は求められず、探索の途中で得られた最良解（最終解)が得られるだけである。
【０００７】
【特許文献１】特開平７−１７５５０４号公報
【特許文献２】特開平８−１５３０８５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、前述の課題に鑑みてなされたものであり、納入先の納期を遵守し、且つ輸送コストを最小にする輸送計画を、短時間のうちに正確に立案することができるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明の輸送計画立案方法は、異なる場所で製造される複数の製品を、異なる場所に存在する複数の納入先に輸送する際に、製品の納入先と、製品同士のまとめ輸送方法とを計画立案する方法であって、前記製品毎に定められた輸送開始可能となる製造完了時刻、品種および製造元からなる製品リストと、前記製品の納入先が必要とする納品毎に定められた納期、品種および納入先からなる納品リストと、前記製品の製造元と納入先との組合せ毎に定められた輸送時間が登録された輸送時間テーブルとを入力し、前記製品と前記納品との割り付けと、前記製品同士のまとめ輸送方法とを、それぞれ整数変数で表し、これらの整数変数を用いて、各納品の納期遅れと、各製品の輸送コストとを算出するための制約式を線形等式及び線形不等式で定式化し、前記各納品の納期遅れと、前記各製品の輸送コストとの重み付き総和で定義される評価関数の値を最小にする最適化計算を行い、前記各製品の納入先と、前記製品同士のまとめ輸送方法とを計画立案することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、納期遅れと輸送コストの重み付き総和で定義される評価関数の値を最小にする輸送計画を立案することにより、納期遅れを最小に留め、かつ、輸送車の作業効率を向上させることが可能である。また、製品と納品との割付けを整数変数として表し、定式化しているため、探索空間が狭められており、輸送計画を高速に解くことができる。このため、操業変動が発生しても、その都度に計算し直すことが可能である。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照して、本発明の輸送計画立案方法を実施するための最良の形態について説明する。なお、以下の説明において、既に説明したものと同一の内容についての詳細な説明を省略する。
図１は、本実施形態の輸送計画立案方法に係わる全ての演算を１台のコンピュータにて実現した場合の装置の構成の一例を示すブロック図である。
図１の入力装置１は、キーボードおよびマウス、または、ネットワークで接続された機器等である。ユーザは、製品毎に定められた製品番号、品種、製造完了時刻、および製造元からなる製品リストと、納品毎に定められた納品番号、品種、納期、および納入先からなる納品リストと、製品を輸送するのに必要となる工場から客先までの輸送時間テーブルとを、この入力装置１を用いてコンピュータ本体２に入力する。前記製品リストは、例えば図３に示した製品リスト３０である。また、前記納品リストは、例えば図４に示した納品リスト４０である。また、前記輸送時間テーブルは、例えば図５に示した輸送時間テーブル５０である。
【００１２】
コンピュータ本体２は、中央処理装置やメモリ・ハードディスク等の記憶装置等から構成され、記憶装置内に格納されているプログラム通りに動作する。コンピュータ本体２は、入力装置１から読み出したデータより、製品と納品との割付けに関する等式制約と不等式制約とを、予め設定した定式化手順を基に作成する。次に、コンピュータ本体２は、前記等式制約と前記不等式制約とを満足し、且つ予め定められた評価関数の値を最小にする混合整数計画問題を解き、製品の納入先と製品同士のまとめ輸送方法とを出力装置３へ出力する。出力装置３はディスプレイやプリンタ、ネットワークで接続された機器等である。なお、前記において、混合整数計画問題とは、線形の等式制約と不等式制約とで表され、変数の一部が整数変数という制約の元で、指定された評価関数を最小にする解を求める手法のことをいう。
【００１３】
（実施例）
以下の関係式で使用する変数や定数の記号を図９に示す。なお、ここでは、前記変数を全て０以上とする。
図９において、δikは、第ｉ製品を第ｋ納品に割り付けるときに１、それ以外は０の値をとる整数変数である。σijは、第ｉ製品と第ｊ製品とをまとめて輸送するときに１、それ以外は０の値をとる整数変数である。ただし、整数変数σij、σjiは、どちらか一方で構わないので、ｉ≦ｊならばσij＝０として、σijを要素とするσ行列は下三角しか用いないことにする。
例えば、図６に示した輸送計画の場合、整数変数δikを要素とするδ行列とσ行列は、図１０に示すようになる。全ての製品を１つずつ運ぶため、σ行列の要素は全て０となっている。
一方、図７に示した輸送計画のように、複数の製品をまとめて運ぶときには、前記変数の定義は多少異なり、まとめて運ぶ複数の製品の中で、製造リストの一番先頭に位置する製品に全ての納品を割り当てる。具体的には、第ｉ製品と第ｊ製品（ｉ＜ｊとする）を第ｋ納品と第ｈ納品にまとめて輸送する時には、δik＝δih＝１、δjk＝δjh＝０、とする。例えば、図７に示した輸送計画の場合、δ行列とσ行列は図１１に示すようになる。
このように、整数変数δikおよびσijを定めた場合、これらの変数は、式１〜式３の制約を満足しなければならない。
【００１４】
【数１】
2005145573.tif 000003
【００１５】
ここで、ｕkcは、第ｋ納品の品種がｃのときに１、それ以外のときに０となる定数である。νicは、第ｉ製品の品種がｃのときに１、それ以外のときに０となる定数である。Ｎはまとめて運ぶことが出来る製品数である。また、（∀ｉ，∀ｃ）は、全ての製品と全ての品種に対して、制約が必要であるということを表している。
式１の制約は、第ｋ納品が何らかの１つの製品に割り付かなければならないという制約を表している。
式２の制約は、σ行列の一意性と、製品をまとめて輸送する時の製品数の上限の制約とを表している。３つの製品をまとめて輸送する場合、仮に製品番号１００、１０４および１０６をまとめて輸送する場合、σ行列の表し方は図１２（ａ）〜（ｃ）に示した３通りの方法がある。式２の制約は、図１２（ａ）のように、まとめて輸送するときには、同じ列（縦）に１を並べるという制約を表している。なぜなら、整数変数σijは０以上の変数であるため、左辺は０以上である。従って、右辺も０以上の必要があり、少なくとも以下の式４を満足しなければならない。
【００１６】
【数２】
2005145573.tif 000004
【００１７】
すなわち、Σσijは０または１となる。これは、σの各行を列方向に見たときに、１となる要素は１つ以下という制約となっており、同じ行に１が複数存在する図１２（ｂ）のσ行列はありえない。また、Σσijが１のときには、式２の右辺は０となるので、左辺のΣσjiも０となる。すなわち、第ｉ行に１の要素がある場合には、第ｉ列には１の要素はないということになり、図１２（ｃ）のσ行列もありえない。以上より、図１２（ａ）のように、同じ列（縦）に１を並べることだけが許され、σ行列が一意的に決まる。さらに、第ｉ列に対応する製品とまとめて輸送できる数（１となる個数）は（Ｎ−１）以下という、まとめ輸送の製品数の制約となっている。
【００１８】
式３の制約は、製品と納品とは、同じ品種を割り当てる制約を表している。式３の左辺は、第ｉ製品と共にまとめて輸送する全ての製品が割り付いている全ての納品に対し、品種がｃの納品個数を表している。一方、右辺の第１項は、製品ｉの品種がｃのときに１、それ以外のときには０となり、右辺の第２項は、製品ｉと共にまとめて輸送する製品のうち、品種がｃの製品個数を表している。すなわち、右辺全体は、製品ｉと共に輸送する製品ｉを含めた全ての製品に対し、品種がｃの製品個数を表している。この制約により、品種ＸおよびＹの２つの納品に対しては、必ず品種ＸおよびＹの２つの製品を割り当てるということが保証される。
製品をまとめて運ぶときには、製造元と納入先とが同じ場合のみという制約は、以下の式５と式６で表すことができる。
【００１９】
【数３】
2005145573.tif 000005
【００２０】
ここで、式５は、第ｉ製品と第ｊ製品の製造元が異なる場合のみ必要となり、式６は、第ｋ納品と第ｈ納品との納入先が異なる場合にのみ必要となる制約である。
製品ｉの輸送開始時刻ｓiと、納品ｋに割り付いている製品の到着時刻ａkとは、式７〜式９の制約式で表すことができる。
【００２１】
【数４】
2005145573.tif 000006
【００２２】
ここで、ｅiは、製造完了時刻（＝輸送開始可能時刻）である。Ｔikは、第ｉ製品の製造元から第ｋ納品の納入先までの輸送時間であり、図５に示した輸送時間テーブル５０から求められる定数である。また、Ａikは、割り付いていない製品の輸送開始時刻ｓiと納品の到着時刻ａkとが無関係となるように、式９にδik＝０を代入した以下の式１０が必ず成り立つように十分大きな値を指定する。
【００２３】
【数５】
2005145573.tif 000007
【００２４】
到着時刻ａkより、納品に対する納期遅れｄkは、以下の式１１の制約式で表すことができる。
【００２５】
【数６】
2005145573.tif 000008
【００２６】
ここで、ｂkは納期である。
第ｉ製品を輸送するときに掛かる輸送コスト（＝輸送時間）ｘiは、以下の式１２の制約式で表すことができる。
【００２７】
【数７】
2005145573.tif 000009
【００２８】
ただし、式１２を見れば分かるように、第ｉ製品が製品リストの上側に位置するの製品とまとめて輸送されるときには、整数変数δikは０になるため、輸送コストｘiの下限は０となり、輸送コストは０ということになる。言い換えると、まとめて輸送するときには、輸送コストは製品リストの一番上に位置する製品のみという制約になっている。式１２では輸送コストとして輸送時間を採用したが、輸送コストとして、輸送費用等の別の値を用いても構わない、その場合、例えば、式１２のＴikの代わりに、第ｉ製品をその製造元から第ｋ納品の納入先に輸送する際の輸送費用Ｆikを用いればよい。
納期遅れｄkと輸送コストｘiとの合計値の線形和の評価関数は式１３で表すことができる。
【００２９】
【数８】
2005145573.tif 000010
【００３０】
ここで、Ｗkは、第ｋ納品の納期遅れに対する重み、Ｋiは、第ｉ製品の輸送コストに対する重みであり、これらにより、納期遅れと輸送コストとのバランスを調整することができる。納期遅れが絶対に許されない場合には重みＷkを大きく（重みＫiを小さく）すればよい。一方、多少納期遅れが出ても輸送コストを小さくして、輸送効率を高めたい時には重みＫiを大きく（重みＷkを小さく）すればよい。
【００３１】
以上より、式１〜式３、式５〜式９および式１１〜式１２を制約式とし、式１３の評価関数の値を最小にする解を混合整数計画法により求めれば、最適な製品の納入先と、製品同士のまとめ輸送方法とを求めることができる。
以上の定式化において、製品数と納品数とが同じで、かつ、製品の品種の数と納品の品種の数とが同じであれば、必ず解が得られることが保証されている。なぜなら、まとめ輸送を全くせずに、同じ品種の製品と納品とを割り当てれば、納期遅れが発生するかも知れないが、前述した制約は必ず満足される。
一方、納期遅れを必ず発生させないように、以下の式１４の制約を用いて計算を行っても良いが、この場合には、必ず解が得られるとは限らず、実用性が低くなってしまう。
【００３２】
【数９】
2005145573.tif 000011
【００３３】
補足として、整数変数δを前述した構造にした理由を記載する。整数変数δikを、まとめ輸送に拘わらず、第ｉ製品を第ｋ納品に割り付けるときに１、それ以外は０の値を取る整数変数としても定式化は可能である。ただし、この場合、例えば、図７に示した輸送計画の場合、製品番号１００および１０４は同じ品種Ｘであるため、割り付けを入れ替えることも可能であり、図１３のように、δ行列は２通りの同じ表し方が存在してしまう（製品番号１００および１０４の１となる要素が入れ替わっている）。このように、１つの輸送計画に複数の解の形式が存在すると、それだけ探索空間が広がってしまい、計算時間が多く掛かってしまう。
【００３４】
以上のように本実施形態では、納期遅れ（Ｗk）と輸送コスト（Ｋi）の重み付き総和で定義される評価関数（式１３）の値を最小にする輸送計画を立案することにより、納期遅れを最小に留め、かつ、輸送車の作業効率を向上させることが可能である。また、製品と納品との割付けを整数変数（δik、σij）として表し、定式化しているため、探索空間が狭められており、輸送計画を高速に解くことができる。このため、操業変動が発生しても、その都度に計算し直すことが可能である。例えば、図３〜図５の例の場合、２．２ＧＨｚのＣＰＵクロックを有するパーソナルコンピュータを用いると、輸送計画の計算時間は、７８ミリ秒となる。
【００３５】
（本発明の他の実施形態）
上述した実施形態の機能を実現するべく各種のデバイスを動作させるように、該各種デバイスと接続された装置あるいはシステム内のコンピュータに対し、前記実施形態の機能を実現するためのソフトウェアのプログラムコードを供給し、そのシステムあるいは装置のコンピュータ（ＣＰＵあるいはＭＰＵ）に格納されたプログラムに従って前記各種デバイスを動作させることによって実施したものも、本発明の範疇に含まれる。
【００３６】
また、この場合、前記ソフトウェアのプログラムコード自体が上述した実施形態の機能を実現することになり、そのプログラムコード自体、及びそのプログラムコードをコンピュータに供給するための手段、例えば、かかるプログラムコードを格納した記録媒体は本発明を構成する。かかるプログラムコードを記憶する記録媒体としては、例えばフレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
【００３７】
また、コンピュータが供給されたプログラムコードを実行することにより、上述の実施形態の機能が実現されるだけでなく、そのプログラムコードがコンピュータにおいて稼働しているＯＳ（オペレーティングシステム）あるいは他のアプリケーションソフト等と共同して上述の実施形態の機能が実現される場合にもかかるプログラムコードは本発明の実施形態に含まれることは言うまでもない。
【００３８】
さらに、供給されたプログラムコードがコンピュータの機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに格納された後、そのプログラムコードの指示に基づいてその機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって上述した実施形態の機能が実現される場合にも本発明に含まれることは言うまでもない。
【図面の簡単な説明】
【００３９】
【図１】輸送計画立案方法に係わる全ての演算を１台のコンピュータにて実現した場合の装置の構成の一例を示すブロック図である。
【図２】納入先に製品を輸送する形態の一例を示した図である。
【図３】製品リストの一例を示した図である。
【図４】納品リストの一例を示した図である。
【図５】輸送時間テーブルの一例を示した図である。
【図６】輸送計画のリストの第１の例を示した図である。
【図７】輸送計画のリストの第２の例を示した図である。
【図８】輸送計画のリストの第３の例を示した図である。
【図９】制約式で用いられる記号を説明する図である。
【図１０】図６に示した輸送計画の第１の例に対応するδ行列とσ行列とを示した図である。
【図１１】図７に示した輸送計画の第２の例に対応するδ行列とσ行列とを示した図である。
【図１２】３つの製品をまとめて輸送する場合のσ行列の一例を示した図である。
【図１３】図７に示した輸送計画の第２の例に対応するσ行列の他の例を示した図である。
【符号の説明】
【００４０】
１  入力装置
２  コンピュータ本体
３  出力装置
３０  製品リスト
４０  納品リスト
５０  輸送時間テーブル
【図１】
2005145573.tif 000012
【図２】
2005145573.tif 000013
【図３】
2005145573.tif 000014
【図４】
2005145573.tif 000015
【図５】
2005145573.tif 000016
【図６】
2005145573.tif 000017
【図７】
2005145573.tif 000018
【図８】
2005145573.tif 000019
【図９】
2005145573.tif 000020
【図１０】
2005145573.tif 000021
【図１１】
2005145573.tif 000022
【図１２】
2005145573.tif 000023
【図１３】
2005145573.tif 000024