(57)【要約】【課題】複数の作業と図３のような複数の輸送車とを割付ける際に、厳密な最適解を演算すること。【解決手段】各搬送作業の要求時刻・搬送元位置・搬送先位置・作業時間・優先度からなる作業リストと、各輸送車の作業終了時刻と作業終了位置からなる輸送車リストと、輸送車の移動時間テーブルを入力とし、各輸送車が行う搬送作業とその順番を表す整数変数を定め、割付けに必要な各種制約を線形等式と線形不等式で定式化し、各搬送作業の優先度を重みとした遅刻時間と空走時間との重み付き総和で定義される評価関数の値を最小にする最適化計算を行い、各輸送車が行う搬送作業とその順番を決定する。【選択図】        図１
2004210445.tif 000002
【特許請求の範囲】
【請求項１】
複数の搬送作業を複数の輸送車に割付ける輸送車の最適搬送計画立案方法であって、
搬送作業ごとに定められた、搬送作業が開始可能となる要求時刻と、搬送元、搬送先、搬送に必要となる作業時間、作業の優先度からなる作業リストと、
輸送車ごとに定められた、既に割付けられている最後の搬送作業の作業終了時刻と作業終了位置からなる輸送車リストと、
輸送車がある地点からある地点まで移動するのに必要となる所要時間を登録した移動時間テーブルを入力とし、
各輸送車が行う搬送作業とその順番を整数変数で表し、前記整数変数を用いて、
各搬送作業の輸送車到着時刻が、当該輸送車の前作業終了時刻と前作業搬送先から当該作業搬送元への移動時間との和以上であるという第１の制約と、
各搬送作業の開始時刻が、当該搬送作業の輸送車到着時刻以上であるという第２の制約と、
各搬送作業の終了時刻が、当該搬送作業の開始時刻と作業時間との和に等しいという第３の制約と、
各搬送作業の遅刻時間が、当該搬送作業の開始時刻または輸送車到着時刻と、要求時刻との差に等しいという第４の制約と、
各搬送作業の空走時間が、当該搬送作業の搬送元への輸送車の移動時間と等しいという第５の制約と、
各搬送作業の優先度を重みとした遅刻時間と空走時間との重み付き総和で定義される評価関数を、
線形等式または線形不等式として定式化し、前記全制約を満足し、前記評価関数の値を最小にする最適化計算を行い、各輸送車が行う搬送作業とその順番を決定することを特徴とする、輸送車の最適搬送計画立案方法。
【請求項２】
複数の搬送作業を複数の輸送車に割付ける輸送車の最適搬送計画立案方法であって、
搬送作業ごとに定められた、搬送作業が開始可能となる要求時刻と、搬送元、搬送先、搬送に必要となる作業時間、作業の優先度からなる作業リストと、
輸送車ごとに定められた、既に割付けられている最後の搬送作業の作業終了時刻と作業終了位置からなる輸送車リストと、
輸送車がある地点からある地点まで移動するのに必要となる所要時間を登録した移動時間テーブルと、前作業と後作業とで定義される段取り時間テーブルを入力とし、
各輸送車が行う搬送作業とその順番を整数変数で表し、前記整数変数を用いて、
各搬送作業の輸送車到着時刻が、当該輸送車の前作業終了時刻と前作業搬送先から当該作業搬送元への移動時間との和以上であるという第１の制約と、
各搬送作業の段取り時間が、段取り時間テーブルと前記整数変数との積に等しいという第６の制約と、
各搬送作業の開始時刻が、当該搬送作業の輸送車到着時刻と段取り時間の和、以上であるという第７の制約と、
各搬送作業の終了時刻が、当該搬送作業の開始時刻と作業時間との和に等しいという第３の制約と、
各搬送作業の遅刻時間が、当該搬送作業の開始時刻または輸送車到着時刻と、要求時刻との差に等しいという第４の制約と、
各搬送作業の空走時間が、当該搬送作業の搬送元への輸送車の移動時間と等しいという第５の制約と、
各搬送作業の優先度を重みとした遅刻時間と空走時間と段取り時間との重み付き総和で定義される評価関数を、
線形等式または線形不等式として定式化し、前記全制約を満足し、前記評価関数の値を最小にする最適化計算を行い、各輸送車が行う搬送作業とその順番を決定することを特徴とする、輸送車の最適搬送計画立案方法。
【請求項３】
ある搬送作業が他の搬送作業開始もしくは終了後、一定時間後にしか開始できないという第８の制約を加えたことを特徴とする、請求項１または請求項２に記載の輸送車の最適搬送計画立案方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、設定された複数の搬送作業を、複数の輸送車に割付け指示する方法に関する。
【０００２】
【従来の技術】
図２の作業リストは割り当てを必要とされる搬送作業、図３の輸送車リストは現在の輸送車の作業状態、図４の移動時間テーブルは輸送車が空状態で移動元から移動先まで移動するときの時間（以下空走時間と記載する）を表している（Ａ→ＢとＢ→Ａは同じ時間として省略している）。ここで、図２の「要求時刻」は搬送作業が開始可能となる時刻であり、「優先度」は作業の優先度であり、値が大きい方の作業を優先する。図３の「作業終了時刻」と「作業終了位置」は輸送車に割付けられている最後の作業が終了する、もしくは、終了した時刻とその位置を表している。
【０００３】
例えば、優先度を考えずに、図２の作業リストの先頭から順番に割付を決定することとし、搬送先に最も早く到着できる輸送車に割付けた場合を考えると、割付結果は図５のようになる。最右列の輸送車番号が割付結果である。輸送車番号毎に割付られた作業のスケジュールを計算すると、図６のようになる。ここで、「到着時刻」は輸送車が作業の搬送先に到着する時刻、「開始時刻」は作業を開始する時刻であり、到着時刻と要求時刻の大きいほうの時刻となっている。「終了時刻」は開始時刻に作業時間を足し合わせた時刻である。「遅刻時間」は開始時刻と要求時刻との差であり、「空走時間」は前作業の搬送先もしくは図３の作業終了位置から、当該作業の搬送先まで移動に要した時間を記載している。遅刻時間は勿論小さい方が望ましいが、輸送車の搬送効率を上げるためには、空走時間も小さい方が望ましい。また、各輸送車の先頭行の搬送先と終了時刻は、それぞれ、図３の作業終了位置と作業終了時刻を転記している。
【０００４】
一方、別の割付を手作業で考えると、図７のようになる。図６、図７いずれの割付でも搬送作業は可能であるが、図６の割付では遅刻時間が１０分であるのに対し、図７の割付では遅刻時間が５分となっているため、割付は図７の方が望ましい。このように、割付により輸送車の作業品質（遅刻時間と空走時間）は大きく異なり、より大きな問題になると最適な割付を求めることは人手では困難である。
【０００５】
複数の作業を複数の輸送車に割り当てる方法は、幾つか提案されている。特許文献１、特許文献２では、複数作業を何らかの指標に従って順番に並べ、先頭作業から順番に割付ける方法、特許文献３、特許文献４では、シミュレーテッド・アニーリング法で最適配車を求める方法を提案している。前者の方法は真の最適解を得ることはできないことは勿論であるが、後者の方法でも、局所最適点に落ち込んでしまい、真の最適解は求められず、探索の途中で得られた最良解（最終解）が得られるだけである。
【０００６】
【特許文献１】
特開平１１−３２７６４４号公報
【特許文献２】
特開平２００１−２３０７４号公報
【特許文献３】
特開平７−１７５５０４号公報
【特許文献４】
特開平８−１５３０８５号公報
【０００７】
【発明が解決しようとする課題】
そこで、本発明では、図２のような複数の作業と図３のような複数の輸送車とを割付ける際に、厳密な最適解を演算することができる輸送車の最適搬送計画立案方法を提供することを目的とする。
【０００８】
【課題を解決するための手段】
課題を解決するための手段として、本発明の輸送車の最適搬送計画立案方法を説明すれば、本発明は、
複数の搬送作業を複数の輸送車に割付ける輸送車の最適搬送計画立案方法であって、
搬送作業ごとに定められた、搬送作業が開始可能となる要求時刻と、搬送元、搬送先、搬送に必要となる作業時間、作業の優先度からなる作業リストと、
輸送車ごとに定められた、既に割付けられている最後の搬送作業の作業終了時刻と作業終了位置からなる輸送車リストと、
輸送車がある地点からある地点まで移動するのに必要となる所要時間を登録した移動時間テーブルを入力とし、
各輸送車が行う搬送作業とその順番を整数変数で表し、前記整数変数を用いて、
各搬送作業の輸送車到着時刻が、当該輸送車の前作業終了時刻と前作業搬送先から当該作業搬送元への移動時間との和以上であるという第１の制約と、
各搬送作業の開始時刻が、当該搬送作業の輸送車到着時刻以上であるという第２の制約と、
各搬送作業の終了時刻が、当該搬送作業の開始時刻と作業時間との和に等しいという第３の制約と、
各搬送作業の遅刻時間が、当該搬送作業の開始時刻または輸送車到着時刻と、要求時刻との差に等しいといいう第４の制約と、
各搬送作業の空走時間が、当該搬送作業の搬送元への輸送車の移動時間と等しいという第５の制約と、
各搬送作業の優先度を重みとした遅刻時間と空走時間との重み付き総和で定義される評価関数を、
線形等式または線形不等式として定式化し、前記全制約を満足し、前記評価関数の値を最小にする最適化計算を行い、各輸送車が行う搬送作業とその順番を決定する点に特徴を有する。
また、作業リスト、輸送車リスト、移動時間テーブルに加え、前作業と後作業とで定義される段取り時間テーブルを入力とし、第２の制約の代わりに、
各搬送作業の段取り時間が、段取り時間テーブルと前記整数変数との積に等しいという第６の制約と、
各搬送作業の開始時刻が、当該搬送作業の輸送車到着時刻と段取り時間の和、以上であるという第７の制約を用い、
各搬送作業の優先度を重みとした遅刻時間と空走時間と段取り時間との重み付き総和で定義される評価関数を、
線形等式または線形不等式として定式化し、前記全制約を満足し、前記評価関数の値を最小にする最適化計算を行い、各輸送車が行う搬送作業とその順番を決定しも良い。
さらに、ある搬送作業が他の搬送作業開始もしくは終了後、一定時間後にしか開始できないという第８の制約を加えても良い。
【０００９】
【発明の実施の形態】
以下、図面を参照して、本発明の輸送車の最適搬送計画立案方法の実施の形態について説明する。図１は本発明に係わる全ての演算を１台のコンピュータにて実現した場合の実施の形態を示す図である。
図１の入力装置１はキーボードおよびマウス、または、ネットワークで接続された機器等であり、搬送作業ごとに定められた、搬送作業が開始可能となる要求時刻と、搬送元位置、搬送先位置、搬送に必要となる作業時間、作業の優先度からなる作業リストと、輸送車ごとに定められた、既に割付けられている最後の搬送作業の作業終了時刻と作業終了位置からなる輸送車リスト（作業終了時刻は過去の実績時刻でも未来の予測時刻でも良い）と、輸送車がある地点からある地点まで移動するのに必要となる所要時間を登録した移動時間テーブルを、コンピュータ本体２に入力する。コンピュータ本体２は中央処理装置やメモリ・ハードディスク等の記憶装置等から構成され、記憶装置内に格納されているプログラム通りに動作する。コンピュータ本体２は入力装置１から読み込んだデータより、輸送車の割付けに関する等式制約と不等式制約を作成する。次に、コンピュータ本体２は評価関数を定め、前記等式と不等式制約を満足し、評価関数の値を最小にする混合整数計画問題を解き、各輸送車の搬送作業と搬送順を求め、出力装置３へ出力する。出力装置３はディスプレイやプリンタ、ネットワークで接続された機器等である。
【００１０】
【実施例】
以下の関係式で使用する変数や定数の記号を図８に示す（変数は全て０以上とする）。ここで、δ１とδ２は、各輸送車が行う搬送作業とその順番を表す０または１の整数変数である。すなわち、δ１ｉｋは第ｋ輸送車の最初の搬送作業を表す０，１から成る整数変数であり、第ｋ輸送車の最初の作業が第ｉ作業の時にδ１ｉｋ＝１となる。また、δ２ｉｊは第ｉ作業と第ｊ作業の前後関係を表す０，１から成る整数変数であり、第ｊ作業の次に第ｉ作業を行う時にδ２ｉｊ＝１となる。２台の輸送車で３つの作業を行う場合の搬送作業と輸送車の割付け例を図９に示す。δ１３１＝１であるため、第１輸送車が最初に行う作業は第３作業であり、δ１１２＝１であるため、第２輸送車が最初に行う作業は第１作業である。また、δ２２３＝１であるため、第３作業を行った第１輸送車は、次に第２作業を行うという割付けになる。
【００１１】
このように、各輸送車が行う搬送作業とその順番を表す整数変数δ１，δ２を定めた場合、δ１とδ２は式１〜式３の制約を満足しなければならない。
【数１】
2004210445.tif 000003
式１の制約は１つの作業が１台の輸送車で搬送されるための条件であり、式２と式３の制約はある輸送車が同時に複数の作業を行わないための条件である。例えば、図１０の割付けの場合（式１を満足しない）、第１作業は、第２輸送車で最初に搬送され、かつ、第３作業の次に再度搬送されてしまう（第３作業は第１輸送車で搬送されるため、第１作業は第１輸送車で搬送されることになる）。また、図１１の割付けの場合（式２を満足しない）、第１輸送車は第１作業と第３作業の２つの作業を同時に最初に搬送することになってしまう。
【００１２】
上記の各輸送車が行う搬送作業とその順番を表す整数変数δ１，δ２を用いると、第１の制約〜第５の制約と評価関数は、以下のように線形等式と線形不等式で、定式化できる。
（１）各搬送作業の輸送車到着時刻が、当該輸送車の前作業終了時刻と前作業搬送先から当該作業搬送元への移動時間との和以上であるという第１の制約
【数２】
2004210445.tif 000004
ここで、Ａは十分大きな正の定数であり、δ２ｉｊ＝０のときに、ａｉとｅｊを無関係にするための定数である。第４式の右辺は、第ｉ作業が第ｋ輸送車で最初に搬送されるとき、第ｉ作業の搬送元への輸送車が最も早く到着できる時刻を表しており、第５式の右辺は、第ｉ作業が第ｊ作業の次に搬送されるとき、第ｊ作業を搬送した輸送車が第ｉ作業の搬送元へ最も早く到着できる時刻を表している。
（２）各搬送作業の開始時刻が、当該搬送作業の輸送車到着時刻以上であるという第２の制約
【数３】
2004210445.tif 000005
（３）各搬送作業の終了時刻が、当該搬送作業の開始時刻と作業時間との和に等しいという第３の制約
ｅｉ＝ｓｉ＋ｗｉ                              （式７）
（４）各搬送作業の遅刻時間が、当該搬送作業の開始時刻または輸送車到着時刻と、要求時刻との差に等しいといいう第４の制約
ｘｉ＝ｓｉ−ｒｉ                              （式８）
ｘｉ＝ａｉ−ｒｉ                              （式９）
（５）各搬送作業の空走時間が、当該搬送作業の搬送元への輸送車の移動時間と等しいという第５の制約
【数４】
2004210445.tif 000006
（６）各搬送作業の優先度を重みとした遅刻時間と空走時間との重み付き総和で定義される評価関数
【数５】
2004210445.tif 000007
である。
以上より、式１〜式１０（ただし、式８と式９はどちらか一方を用いる）を制約式とし、式１１の評価関数値を最小にする解を混合整数計画法により求めれば、各輸送車が行う搬送作業とその順番の最適解δ１，δ２を求めることができる。
【００１３】
以上は、基本的な制約のみを考えた割付け方法であるが、作業と作業の前後関係により、段取り時間が生じることもある。例えば、図１２の段取り時間テーブルのように、前作業と後作業により段取り時間が決められているときもある。ここで、図１２の表の第１行から第３行までは輸送車の番号であり、輸送車が最初に後作業を搬送した場合の段取り時間が定められている。第４行以降は作業番号であり、前作業と後作業との間の段取り時間が定めたれている。段取り時間を考慮する場合には、作業リスト、輸送車リスト、移動時間テーブルに加え、図１２に例示される段取り時間テーブルを入力とし、第２の制約の代わりに、以下の第６の制約と第７の制約と評価関数を用いる。
（７）各搬送作業の段取り時間が、段取り時間テーブルと前記整数変数との積に等しいという第６の制約
【数６】
2004210445.tif 000008
（８）各搬送作業の開始時刻が、当該搬送作業の輸送車到着時刻と段取り時間の和、以上であるという第７の制約
【数７】
2004210445.tif 000009
（９）各搬送作業の優先度を重みとした遅刻時間と空走時間と段取り時間との重み付き総和で定義される評価関数を
【数８】
2004210445.tif 000010
である。
以上より、式１〜式５、式７〜式１０（ただし、式８と式９はどちらか一方を用いる）、式１２〜式１３を制約式とし、式１４の評価関数値を最小にする解を混合整数計画法により求めれば、各輸送車が行う搬送作業とその順番の最適解δ１，δ２を求めることができる。
【００１４】
さらに、以上は、各作業同士が無関係である場合の割付け方法であるが、ある作業が他のある作業より後に搬送されなければならない、という制約が課せられる場合もある。この場合には、以下の制約を追加しても構わない。
（１０）ある搬送作業が他の搬送作業開始もしくは終了後、一定時間後にしか開始できないという第８の制約
【数９】
2004210445.tif 000011
ここで、式１５は第ｊ作業終了後でしか第ｉ作業を開始できないときの制約式であり、第ｊ作業終了時刻と第ｉ作業開始時刻との最小時間差を表す定数δ１，δ２τｉｊ≧０の時のみ追加する。式１６は第ｊ作業開始後でしか第ｉ作業を開始できないときの制約式であり、第ｊ作業開始時刻と第ｉ作業開始時刻との最小時間差を表す定数ρｉｊ≧０の時のみ追加する。
【００１５】
【発明の効果】
以上詳しく説明したように、本発明によれば、輸送車の空走時間と遅刻時間を最小にする厳密な最適解を算出することにより、輸送車の作業効率が向上すると共に、遅刻時間を最小に留めることが可能である。さらに、搬送作業と輸送車の割付けを整数変数として表し、定式化しているため、探索空間が狭められており、高速に解くことができる。数値実験でも３０搬送作業と１１輸送車の割付け問題が、２．２ＧＨｚのＣＰＵクロックを有するパーソナルコンピュータで、平均１秒程度で計算時間可能であるため、作業の追加の発生や、輸送車の故障等、状況が変わったときでも、瞬時に最適解を算出することが可能である。
【図面の簡単な説明】
【図１】本発明にかかる輸送車の最適搬送計画立案方法の実施形態を示す図。
【図２】輸送車の搬送作業リスト図。
【図３】輸送車の作業状態を示す輸送リスト図。
【図４】移動時間テーブル図。
【図５】輸送車の割付結果を示す図。
【図６】割付けられた作業のスケジュール計算結果を示す図。
【図７】別の割付けを手作業で行った場合のスケジュール図。
【図８】本発明の実施例で使用する変数や定数の記号の意味を示す図。
【図９】２台の輸送車で３つの作業を行う場合の搬送作業と輸送車の割付け例の図。
【図１０】別の割付け例（式１を満足しない）の図。
【図１１】更に、別の割付け例（式２を満足しない）の図。
【図１２】段取り時間テーブルを示す図。
【符号の説明】
１…入力装置
２…コンピュータ本体
３…出力装置
【図１】
2004210445.tif 000012
【図２】
2004210445.tif 000013
【図３】
2004210445.tif 000014
【図４】
2004210445.tif 000015
【図５】
2004210445.tif 000016
【図６】
2004210445.tif 000017
【図７】
2004210445.tif 000018
【図８】
2004210445.tif 000019
【図９】
2004210445.tif 000020
【図１０】
2004210445.tif 000021
【図１１】
2004210445.tif 000022
【図１２】
2004210445.tif 000023