(57)【要約】【課題】車輌の稼働率を最大化し、全車輌の１日の運行時間を均等化することができる輸送割り当てシステムを提供することにある。【解決手段】輸送割り当て作成装置は、トリップを車輌にランダムに割り当てる初期割り当て作成処理部と、初期割り当てを改良する初期割り当て改良処理部と、初期割り当ての評価値と改良割り当ての評価値とを比較し評価値が高いほうの割り当てを最良解として保存する最良解保存部と、を有し、初期割り当ての作成処理、初期割り当ての改良処理、及び最良解の保存処理を規定の回数だけ繰り返す。【選択図】  図１
2004217333.tif 000002
【特許請求の範囲】
【請求項１】
出発時刻及び帰着時刻を含むトリップ情報と車輌の運行開始時刻及び運行終了時刻を含む車輌情報を入力するための入力処理部と車輌にトリップを割り当てる割り当て処理部と該割り当て処理部によって得られた結果を出力する結果出力部とを有し、上記割り当て処理部は、トリップを車輌にランダムに割り当てる初期割り当て作成処理部と、該初期割り当て作成処理部によって作成された初期割り当てを改良する初期割り当て改良処理部と、上記初期割り当て作成処理部によって作成された初期割り当ての評価値と上記初期割り当て改良処理部によって得られた改良割り当ての評価値を算出する評価値算出部と、上記初期割り当ての評価値と上記改良割り当ての評価値とを比較し評価値が高いほうの割り当てを最良解として保存する最良解保存部と、上記初期割り当て作成処理部による初期割り当ての作成処理、上記初期割り当て改良処理部による初期割り当ての改良処理、上記評価値算出部による評価値算出処理及び上記最良解保存部による最良解の保存処理の実行回数を計数する処理ループ実行回数計数部と、を有し、該処理ループ実行回数計数部によって実行回数が規定の回数を超えたと判定されたとき、上記結果出力部は、上記最良解保存部に保存された割り当てを出力することを特徴とする輸送割り当て作成装置。
【請求項２】
請求項１記載の輸送割り当て作成装置において、上記初期割り当て作成処理部は、既にトリップが割り当てられている車輌に対してトリップの追加が可能であるか否かを判定し、該車輌に対してトリップの追加が可能でないとき未だトリップが割り当てられていない車輌に対してトリップを割り当てることによって初期割り当てを作成することを特徴とする輸送割り当て作成装置。
【請求項３】
請求項２記載の輸送割り当て作成装置において、上記初期割り当て作成処理部は、既にトリップが割り当てられている車輌に対してトリップの追加が可能であるか否かを判定するとき、トリップの出発時刻の最大可能遅れ時間を表す余裕時間を考慮して、トリップの追加が可能であるか否かを判定することを特徴とする輸送割り当て作成装置。
【請求項４】
請求項１記載の輸送割り当て作成装置において、上記初期割り当て改良処理部は、上記初期割り当て作成処理部によって作成された初期割り当ての結果、最も評価値が低い車輌に割り当てられたトリップを他の車輌に割り当てる再割り当てを行い、再割り当ての結果による全車輌の評価値の合計が改善されなくなるまで、再割り当てを繰り返すことを特徴とする輸送割り当て作成装置。
【請求項５】
請求項１記載の輸送割り当て作成装置において、上記評価値算出部は車輌の稼働率を評価値とすることを特徴とする輸送割り当て作成装置。
【請求項６】
トリップをランダムな順に車輌に割り当てる初期割り当てステップと、該初期割り当て作成ステップによって得られた初期割り当てを改良する初期割り当て改良ステップと、初期割り当てステップと初期割り当て改良ステップを規定の回数だけ繰り返し、最良の割り当てを出力する結果出力ステップと、を含む輸送割り当て作成方法。
【請求項７】
請求項６記載の輸送割り当て作成方法において、上記初期割り当て改良ステップは、評価値が最小の車輌に割り当てられているトリップを他の車輌に割り当てる再割り当てステップと、上記初期割り当てステップによって得られた初期割り当ての評価値と上記再割り当てステップによって得られた再割り当ての評価値を算出する評価値算出ステップと、初期割り当ての評価値と再割り当ての評価値を比較する評価値比較ステップと、を有し、上記初期割り当ての評価値よりも上記再割り当ての評価値が高い場合に、再割り当てを保存し、更に上記再割り当てステップ及び上記評価値比較ステップを繰り返し、上記初期割り当ての評価値よりも上記再割り当ての評価値が高くない場合に、保存されている再割り当てを改良された割り当てとして出力することを特徴とする輸送割り当て作成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、物流分野における輸送スケジューリングの作成技術に関し、特に、コンピュータを利用して車輌に対して輸送を割り当てるためのシステムに関する。
【０００２】
【従来の技術】
物流分野における輸送及び配車スケジュールの作成は、従来人手で行われていたが、近年、コンピュータを利用して自動的に行われる。コンピュータを利用した輸送及び配車スケジュールの作成方法として、例えば、遺伝的アルゴリズム（非特許文献１）やタブーサーチなどの各種最適化技法（非特許文献２）を適用した方法が知られている。
【０００３】
特開平７−２３４９９７号公報には、遺伝的ニューロ処理を利用して最適な配車計画を立案する方法が提案されている。
【０００４】
【特許文献１】
特開平７−２３４９９７号公報
【非特許文献１】
北野宏明著「遺伝的アルゴリズム」１９９３年発行  産業出版
【非特許文献２】
久保幹雄著「ロジスティク工学」  朝倉書店
【０００５】
【発明が解決しようとする課題】
物流センターの運用では、一台の車輌は、物流センターを出発して、複数の集荷配送先拠点を巡回し、再度物流センターに戻る。これを、トリップと呼ぶ。トリップの作成方法は既知であり、例えば、特開平７−３２４９９７号公報に記載されている。
【０００６】
一台の車輌には一日に複数回のトリップが割り当てられる。トリップの出発から帰着までの時間はトリップ毎に異なる。従って、各車輌に対して同一数のトリップを割り当てると、運行時間が短い車輌と長い車輌が生ずる可能性がある。また、トリップとトリップの間の空き時間が長い車輌と短い車輌が生ずる可能性がある。
【０００７】
本発明の目的は、車輌の稼働率を最大化し、全車輌の１日の運行時間を均等化することができる輸送割り当てシステムを提供することにある。
【０００８】
【課題を解決するための手段】
本発明によると、トリップの車輌への割り当てを次の方法で行う。尚、トリップの作成は、既知の方法、例えば、特開平７−３２４９９７号公報に記載されたスケジューリング方法によって行われてよい。
（１）利用可能な車輌の運行開始時刻と運行終了時刻を登録する。
（２）先ず初期割り当てを作成する。予め登録されているトリップを、ランダムに並べ、その順に車輌に割り当てる。
（３）次に初期割り当ての改良処理を行う。先ず、初期割り当てがなされた車輌のうち評価値が最小の車輌を取り出し、その車輌へ割り当てられているトリップを解除し、それを他の車輌に再割り当てする。この再割り当て結果、元の初期割り当てよりも、全車輌の評価値が向上したならば、再割り当てを保存し、再割り当てに対して更に再割り当て処理を行う。再割り当て処理の結果、元の割り当てよりも、全車輌の評価値が向上しなくなったら、この改良処理を終了する。
（４）上記の（２）の初期割り当てと（３）の改良処理を複数回繰り返し、その中で最良の割り当てを出力する。
この方法により、全車輌の稼働率を最大化し各車輌の一日の運行時間を均一化することができる。
【０００９】
【発明の実施の形態】
以下、本発明の一実施例を図面を用いて説明する。図１を参照して発明による輸送割り当て装置の例を説明する。本例の輸送割り当て装置は、ユーザが命令、情報等を入力するための入力装置１０１と、プリンタ等の出力装置１０２と、ディスプレイ等の表示装置１０３と、各種のプログラムを実行するための処理装置１０４と、各種の情報を記憶するための記憶装置１０９とを備える。処理装置１０４は、入力処理部１０６、割り当て処理部１０７及び結果出力処理部１０８を含むプログラム実行部１０５を有する。また、記憶装置１０９には、拠点情報１１０、トリップ情報１１１、車輌情報１１２が格納される。
【００１０】
図１１を参照して、割り当て処理部１０７の構成を説明する。本例の割り当て処理部１０７は、トリップを車輌にランダムに割り当てる初期割り当て作成処理部１０７１と、初期割り当てを改良する初期割り当て改良処理部１０７２と、初期割り当ての評価値と改良割り当ての評価値を算出する評価値算出部１０７３と、初期割り当ての評価値と改良割り当ての評価値とを比較し評価値が高いほうの割り当てを最良解として保存する最良解保存部１０７４と、初期割り当て作成処理部による初期割り当ての作成処理、初期割り当て改良処理部による初期割り当ての改良処理、評価値算出部による評価値算出処理及び最良解保存部による最良解の保存処理の実行回数を計数する処理ループ実行回数計数部１０７５と、を有する。
【００１１】
処理ループ実行回数計数部１０７５によって実行回数が規定の回数を超えたと判定されたとき、結果出力処理部１０８は、最良解保存部１０７４に保存された割り当てを出力する。
【００１２】
図２を参照して図１の記憶装置１０９に格納される情報の例を説明する。拠点情報１１０は、物流センターを出発した車輌が立ち寄る集配送先拠点の位置に関する情報を含む。具体的には、集配送先拠点を一意に識別する拠点識別記号２０１、その拠点の名称２０２、その拠点の住所２０３、その拠点の位置を示す緯度２０４、経度２０５を含む。
【００１３】
トリップ情報１１１は、物流センターを出発した車輌が集配送先拠点を巡回して、再度物流センターに戻るまでの巡回経路や物流センターからの出発時刻等のトリップに関する情報を含む。具体的には、トリップを一意に識別するトリップ識別記号２０６、そのトリップの物流センターからの出発時刻２０７、そのトリップにおける車輌の走行時間２０８、そのトリップの出発を遅らせることができる限度を表す余裕時間２０９、そのトリップにおける巡回先拠点数２１０、そのトリップにおける巡回先の拠点識別記号２１１、２１２、２１３を含む。
【００１４】
トリップの出発時刻２０７と車輌の走行時間２０８の和は車輌の帰着時刻となる。このトリップ情報に記録されている拠点への巡回を行う車輌の出発は、出発時刻２０７から最大限遅れても余裕時間の範囲内である。
【００１５】
車輌情報１１２は、車輌に関する情報とその車輌に割り当てられたトリップに関する情報を含む。具体的には、車輌を一意に識別する車輌番号２１４、その車輌のその日の運行開始時刻２１５、運行終了時刻２１６、その車輌に割り当てられているトリップ数２１７、割り当てられているトリップの識別記号２１８、そのトリップの出発時刻２１９を含む。
【００１６】
図３を参照して図１の処理装置１０４が実行するプログラムの概要を説明する。ステップ３０１にて、トリップ情報１１１、車輌情報１１２等のトリップの車輌への割り当てを行うために必要な情報をユーザが入力する。但し、車輌情報１１２のうち、車輌に割り当てられたトリップに関連する情報には何も入力しない。即ち、初期値として０が設定される。
【００１７】
次のステップ３０２では、ステップ３０１にて入力された情報に基づいて、トリップの車輌への最適な割り当てを作成する。最適な割り当てとは、全車輌の評価値が最大となる割り当てをいう。評価値については後に説明する。トリップの車輌への割り当てとは、全てのトリップを車輌に割り当て、各車輌が物流センターを出発する時刻と帰着する時刻を決定する処理である。この処理の詳細は図５以下で説明する。最後にステップ３０３では、トリップの車輌への割り当て結果と各車輌の走行距離、運行時間、稼働率等の評価値を出力する。
【００１８】
図４を参照して図３のステップ３０１の入力処理の詳細を説明する。ステップ４０１にて、図２に示した拠点情報１１０の各項目の内容を登録する。次にステップ４０２にて、図２に示したトリップ情報１１１の各項目の内容を登録する。ステップ４０３にて、図２に示した車輌情報１１２の各項目を登録する。但し、車輌情報１１２のうち、車輌に割り当てられたトリップ数２１７、割り当てられたトリップの識別記号２１８、そのトリップの出発時刻２１９等には、初期値として０が設定される。
【００１９】
図５を参照して図３のステップ３０２のトリップの車輌への割り当て処理の詳細を説明する。この処理では、トリップをランダムに並べ、その順に車輌に割り当てる初期割り当てを作成する。次に、この初期割り当ての改良処理を行う。初期割り当ての作成処理とその改良処理を複数回繰り返し、その中で最良の割り当てを選ぶ。これは、いわゆるランダム多スタート法と呼ばれる。
【００２０】
ステップ５０１にて、変数Ｉに１を代入する。変数Ｉは処理のループ数を表す。ステップ５０２にて、変数ＥＶａｌｕｅにＭｉｎＶａｌｕｅを代入する。変数ＥＶａｌｕｅは、前回のループまでの最良解を表す。ＭｉｎＶａｌｕｅは、最良解の初期値であり、設定可能な最小数とする。ＭｉｎＶａｌｕｅは、例えば０である。
【００２１】
ステップ５０３にて、変数Ｉと１００を比較する。変数Ｉが１００を超えていないなら、ステップ５０４にて、初期割り当てを作成する。最初の処理ループでは、変数Ｉが１であるから、作成された初期割り当ては初期解となる。この初期割り当て作成処理の詳細は図６にて説明する。この初期割り当ては、ランダム性を含む方法により作成されるため、ステップ５０４が実行されるたびに、異なる割り当てが作成される。
【００２２】
ステップ５０５にて、ステップ５０４にて作成した初期割り当てを改良する。この処理の詳細は図７にて説明する。
【００２３】
ステップ５０６にて、ステップ５０５にて改良した割り当ての評価値を変数Ｖａｌｕｅに代入する。評価値は大きいほうが良い。評価値の算出方法は、図７及び図９にて説明する。ステップ５０７にて、変数Ｖａｌｕｅを変数ＥＶａｌｕｅと比較する。これは改良した割り当ての評価値が、前回の処理までの最良解より大きいか否かを判定することを意味する。変数Ｖａｌｕｅが変数ＥＶａｌｕｅより大きいか又は等しい場合には、ステップ５０８に進み、このＩ番目の割り当て結果を最良解として記録する。ステップ５０９にて、変数ＥＶａｌｕｅに変数Ｖａｌｕｅの値を代入する。従って、変数ＥＶａｌｕｅには、Ｉ回の割り当て改良処理のうち最良の割り当ての評価値が保持される。ステップ５１０にて、変数Ｉに１を加え、ステップ５０３に戻る。
【００２４】
ステップ５０７にて、変数Ｖａｌｕｅが変数ＥＶａｌｕｅより小さければ、ステップ５１０に進み、変数Ｉに１を加え、ステップ５０３に戻る。即ち、このＩ番目の割り当ての評価値が前回までの最良の割り当ての評価値より小さければ、Ｉ番目の割り当てを採用しない。
【００２５】
ステップ５０３にて、変数Ｉが１００を超えたなら、トリップを車輌へ割り当てる処理を終了する。ステップ５０８の記録処理にて、最良の割り当てが保存されている。また、ステップ５０９の処理にて、変数ＥＶａｌｕｅには、最良の割り当ての評価値が保存されている。
【００２６】
図６を参照して図５のステップ５０４の初期割り当て作成処理の詳細を説明する。先ず、この処理の概要を説明する。トリップをランダムに並べ、その順に車輌に割り当てる。先ず、既にトリップが割り当てられている車輌に対してトリップの追加が可能であるか否かを判定する。既にトリップが割り当てられている車輌に対して、トリップの追加が不可能であるとき、未だトリップが割り当てられていない車輌に対してトリップを割り当てる。次のトリップも同様に、先ず、既にトリップが割り当てられている車輌に対してトリップの追加が可能であるか否を判定し、既にトリップが割り当てられている車輌に対してトリップの追加が不可能であるとき、未だトリップが割り当てられていない車輌に対してトリップを割り当てる。以下に、詳細に説明する。
【００２７】
ステップ６０１にて、全てのトリップ情報１１１のトリップを取り出し、ランダムな順序に並べる。ステップ６０２にて、車輌への割り当てが行われていないトリップがあるか否かをチェックする。全てのトリップが車輌へ割り当てられている場合には、この初期割り当て作成処理を終了する。
【００２８】
上述のように初期状態では、全てのトリップは未割り当てであり、ステップ６０３に進む。ステップ６０３にて、未割り当てのトリップを一つ取り出す。ステップ６０４にて、変数Ｎに、少なくとも１つのトリップが割り当てられている車輌の総数を代入する。初期値では、変数Ｎ＝０である。
【００２９】
ステップ６０５にて、変数Ｊに１を代入する。変数Ｊは、トリップの割り当てが可能か否かを判定する対象となる車輌の順番を表す。ステップ６０６にて、変数Ｊが変数Ｎより大きいか否かをチェックする。初期値では変数Ｎ＝０、変数Ｊ＝１であるから、Ｊ＞Ｎでありステップ６１１に進む。ステップ６１１にて、新しい車輌に、トリップを割り当てる。ここでは割り当て済みの車輌は０であり、そのうちの１つ車輌にトリップを割り当てる。ステップ６０２に戻る。ステップ６０２にて未割り当てのトリップがあればステップ６０３に進む。
【００３０】
ステップ６０３にて、次の未割り当てのトリップを１つ取り出す。ステップ６０４にて、変数Ｎに、少なくとも１つのトリップが割り当てられている車輌の総数を代入する。前回のステップ６１１にて、新しい車輌にトリップを割り当てているため、変数Ｎ＝１となる。ステップ６０５にて、変数Ｊ＝１とする。即ち、Ｊ（＝１）番目の車輌に対してトリップの追加が可能か否かを判定する。ステップ６０６にて、変数Ｊが変数Ｎより大きいか否かをチェックする。変数Ｎ＝１、変数Ｊ＝１であり、条件Ｊ＞Ｎに適合しないから、ステップ６０７に進む。ステップ６０７にて、Ｊ（＝１）番目の車輌にトリップの割り当ての追加が可能か否かの判定処理を行う。この処理の詳細は図８にて説明する。
【００３１】
ステップ６０８にて、もし、追加可能であれば、ステップ６１０に進み、Ｊ（＝１）番目の車輌にトリップを追加し、ステップ６０２に戻り、次の未割り当てのトリップの処理を行う。
【００３２】
ステップ６０８にて、追加可能でなければ、ステップ６０９にて、変数Ｊに１を加える。変数Ｊ＝２となり、次の車輌となる。ステップ６０６にて、変数Ｊが変数Ｎより大きいか否かをチェックする。変数Ｊ＝２、変数Ｎ＝１であり、条件Ｊ＞Ｎに適合し、ステップ６１１に進む。
【００３３】
ステップ６１１にて、新しい車輌に、即ち、未だトリップが割り当てられていない車輌にトリップを割り当てる。ステップ６０２に戻る。以下同様に繰り返す。ステップ６０２にて、未割り当てのトリップがなくなると、この処理を終了する。
【００３４】
図７を参照して、図５のステップ５０５の初期割り当ての改良処理を説明する。この処理は、図６にて説明した初期割り当て作成処理にて作成したトリップの車輌への割り当てを改良するものである。まず、ステップ７０１にて、トリップが割り当てられている全車輌の評価値を算出する。評価値は高いほうが良い。この評価値の計算方法の例については、図９にて説明する。次に、ステップ７０２にて、トリップ割り当て済みの全車輌の評価値の合計を算出し、それを変数Ｅ０に代入する。ステップ７０３にて、トリップ割り当て済みの車輌の中で評価値が最小の車輌を選択し、その車輌の車輌番号ＴＮｏを変数Ｔに代入する。
【００３５】
ステップ７０４にて、変数Ｔの車輌番号を有する車輌に割り当てられているトリップを他の車輌に割り当て、変数Ｔの車輌番号を有する車輌にはトリップが割り当てられていない状態にする。この処理の詳細は図１０にて示す。
【００３６】
ステップ７０５にて、再度、トリップ割り当て済みの全車輌の評価値を算出し、その合計値を変数Ｅに代入する。ステップ７０６にて、変数Ｅが変数Ｅ０よりも大きいか又は等しいか否かを判定する。即ち、改良後の割り当ての評価値Ｅが改良前の割り当ての評価値Ｅ０よりも大きいか又は等しいか否かを判定する。
【００３７】
ステップ７０６にて、変数Ｅが変数Ｅ０よりも大きいか又は等しい場合には、ステップ７０７に進み、改良後の割り当てを確定し記憶装置に格納する。次に、ステップ７０１に戻り、上述の処理を繰り返す。即ち、トリップの割り当ての改良によって評価値が改善された場合には、上述の処理を繰り返す。
【００３８】
ステップ７０６にて、変数Ｅが変数Ｅ０よりも小さければ、図５のステップ５０５の初期割り当ての改良処理を終了する。即ち、トリップの割り当ての改良によって評価値が改善されなくなったら、初期割り当ての改良処理を終了する。ステップ７０７にて保存された割り当てを最良解として出力する。
【００３９】
図８を参照して、図６のステップ６０７の車輌へのトリップの割り当ての追加が可能か否か判定する処理を説明する。先ず、この処理の概要を説明する。判定対象のトリップの出発時刻から帰着時刻までの走行時間帯を判定対象の車輌の空き時間帯と比較する。判定対象のトリップの走行時間帯が判定対象の車輌の空き時間帯の中に収まる場合には、判定対象のトリップの追加が可能であると判定し、判定対象のトリップの走行時間帯が判定対象の車輌の空き時間帯の中に収まらない場合には、判定対象のトリップの追加が不可能である判定する。
【００４０】
尚、本例では、更に、判定対象のトリップの走行時間帯を所定の余裕時間だけ遅延させた時間帯を判定対象の車輌の空き時間帯と比較する。判定対象のトリップの走行時間帯が判定対象の車輌の空き時間帯の中に収まらない場合であっても、遅延させた走行時間帯が車輌の空き時間帯の中に収まる場合には、判定対象のトリップの割り当ての追加が可能であると判定する。
【００４１】
車輌の空き時間帯は、車輌の１日の運行開始時刻から運行終了時刻までの運行時間のうち、既に割り当てられているトリップの走行時間帯を除いた時間帯である。従って、既に割り当てられているトリップ数をＭとすると、空き時間帯の数はＭ＋１となる。例えば、判定対象の車輌に対して既に２つのトリップが割り当てられている場合、この車輌の空き時間帯は、車輌の運行開始時刻から最初のトリップの出発時刻までの第０の空き時間帯と、最初のトリップの帰着時刻から次のトリップの出発時刻までの第１の空き時間帯と、次のトリップの帰着時刻から車輌の運行終了時刻までの第２の空き時間帯の３つの空き時間帯を含む。
【００４２】
本例では、これらのＭ＋１個の空き時間帯に対して順次、判定対象のトリップの走行時間帯が収まるか否かを判定する。
【００４３】
ステップ８０１にて、変数ｔ＿ｓｔａｒｔに、追加対象のトリップの出発時刻を代入する。ステップ８０２にて、変数ｔ＿ｅｎｄに、そのトリップの帰着時刻を代入する。トリップの帰着時刻は、トリップの出発時刻とそのトリップの走行時間の和である。
【００４４】
ステップ８０３にて、変数ｔ＿ｄｅｌａｙに、そのトリップの余裕時間を代入する。余裕時間は、上述のようにそのトリップの出発を遅らせることができる時間の限度であり、予め与えられている。ステップ８０４にて、変数Ｍに、判定対象の車輌に既に割り当てられているトリップ数を代入する。
【００４５】
ステップ８０５にて、変数ＦＬＧと変数Ｐに０を代入する。変数ＦＬＧはその車輌へのトリップの追加が可能か不可能かを示し、ＦＬＧ＝０であればトリップの追加が不可能であり、ＦＬＧ＝１であればトリップの追加が可能である。変数Ｐは、車輌の空き時間帯の位置を表す。変数Ｐ＝０は、車輌の運行開始時刻から最初のトリップの出発時刻までの空き時間帯を表す。ステップ８０６にて、変数ｋに０を代入する。変数ｋは、車輌に対して割り当ての追加を行うトリップの番号を表す。
【００４６】
ステップ８０７にて、変数ｋが変数Ｍを超えているか、又はＦＬＧの値が１であるかチェックする。変数ｋが変数Ｍを超えている場合とは、判定対象の車輌の全ての空き時間帯に対して、トリップの追加が可能か否かの判定処理を実行したが、トリップの追加は不可能であると判定されたものである。従って、ＦＬＧの値は０である。ＦＬＧの値が１であればトリップの追加が可能であり、その追加位置はＰ番目のトリップの次である。
【００４７】
最初の処理ループでは、ｋ＝０であり、Ｍがどのよう値であっても、ｋ＞Ｍは成立しない。また、ステップ８０５よりＦＬＧ＝０であり、ＦＬＧ＝１も成立しない。従って、ステップ８０７の判定条件は成立しない。
【００４８】
ステップ８０８にて、変数Ｘ１に、ｋ番目のトリップの帰着時刻を代入する。ｋ番目のトリップの帰着時刻は、ｋ番目のトリップの出発時刻と走行時間の和である。変数Ｘ１はｋ番目の空き時間帯の開始時刻を表す。ここで変数ｋが０の場合には、変数Ｘ１には、その走行車輌の運行開始時刻を代入する。０番目の空き時間帯の開始時刻は、その車輌の運行開始時刻に相当するからである。
【００４９】
ステップ８０９にて、変数Ｘ２に、ｋ＋１（＝１）番目のトリップの出発時刻を代入する。変数Ｘ２はｋ番目の空き時間帯の終了時刻を表す。変数ｋ＝Ｍの場合には、変数Ｘ２に、その車輌の運行終了時刻を代入する。最後の空き時間帯の終了時刻は、その車輌の運行終了時刻に相当するからである。判定対象の車輌に割り当てられているトリップ数が０である場合、即ち、変数Ｍ＝０の場合にも、変数Ｘ２には、その車輌の運行終了時刻を代入する。
【００５０】
ステップ８１０にて、変数ｔ＿ｄｅｌａｙと変数Ｘ２−ｔ＿ｅｎｄの小さい方の値を変数Ｄに代入する。変数Ｘ２−ｔ＿ｅｎｄは、ｋ番目の空き時間帯の終了時刻から追加対象のトリップの帰着時刻を引いたものである。従って、ステップ８１０にて得られた変数Ｄは最大可能遅延時間を表す。
【００５１】
ステップ８１１にて、次の条２つの件が成立するか否かをチェックする。
【数１】
（１）    Ｘ１＜  ｔ＿ｓｔａｒｔ      且つ  ｔ＿ｅｎｄ  ＜Ｘ２
（２）    Ｘ１＜  ｔ＿ｓｔａｒｔ  ＋  Ｄ  且つ  ｔ＿ｅｎｄ  ＋  Ｄ＜Ｘ２
【００５２】
これは、車輌のｋ番目の空き時間帯に追加対象のトリップの時間帯が収まるか否かチェックするものである。最初の条件（１）は、追加対象のトリップの走行時間帯がｋ番目の空き時間帯の中に収まることを示し、次の条件（２）は、追加対象のトリップの走行時間帯を遅延時間Ｄだけ遅らせた時間帯がｋ番目の空き時間帯の中に収まることを示す。
【００５３】
もし、ステップ８１１の条件が成立すれば、ステップ８１２に進み、変数ＦＬＧに１、変数Ｐに変数ｋの値を代入し、ステップ８１３に進む。ステップ８１１の条件が成立しない場合には、そのままステップ８１３に進む。ステップ８１３にて、変数ｋに１を加える。変数ｋ＝１となる。ステップ８０７に戻る。
【００５４】
ステップ８０７にて、再度、ｋ＞Ｍ、又は、ＦＬＧ＝１であるかチェックする。例えば、判定対象の車輌に既に割り当てられているトリップ数Ｍが３であると仮定する。今回のループでは、ｋ＝１であり、Ｍ＝３であるから、条件ｋ＞Ｍは成立しない。また、前回のループにてステップ８１２を通過しないなら、依然としてＦＬＧ＝０であり、ＦＬＧ＝１も成立しない。従って、ステップ８０７の判定条件は成立しない。従って、ステップ８０８以下の処理に進む。
【００５５】
前回のループにてステップ８１２を通過したなら、ＦＬＧ＝１であり、ステップ８０７の判定条件が成立する。従って、追加判定処理は終了する。
【００５６】
図９を参照して図７のステップ７０１の車輌の評価値の算出処理の詳細を説明する。この例では、車輌の評価値は、車輌の稼働率であり、運行可能時間帯の中で、実際にトリップが割り当てられている時間の割合である。従って評価値は高いほどよい。評価値は０以上且つ１未満である。尚、評価値は、目的に応じて適当に定義してよく、稼働率以外のパラメータを用いてもよい。
【００５７】
まず、ステップ９０１にて、変数Ｔｒｉｐ＿Ｔｉｍｅに初期値として０を代入する。変数Ｔｒｉｐ＿Ｔｉｍｅは、評価の対象となる車輌に割り当てられたトリップの走行時間である。ステップ９０２にて、変数Ｔｏｔａｌ＿ｔｉｍｅに、その車輌の運行時間を代入する。即ち、車輌の帰着時刻から出発時刻を引いた値を代入する。ステップ９０３にて、変数ｉに１を代入し、変数Ｍに、その車輌に割り当てられている全トリップ数を代入する。
【００５８】
ステップ９０４にて、変数Ｍが０であるか否かを判定する。変数Ｍ＝０なら、その車輌にはトリップが割り当てられていないことになり、ステップ９０９にて、変数Ｖａｌｕｅに１を代入する。これは、その車輌に割り当てられるべきトリップが他の車輌に割り当てられたことになり、全車輌の評価値を高くするためである。変数Ｍが０でないなら、ステップ９０５に進む。
【００５９】
ステップ９０５にて、変数ｉが変数Ｍより大きいかをチェックする。これは、評価の対象となる車輌に割り当てられたＭ個のトリップの全てに対して、走行時間の加算演算を終了したか否かを判定することを意味する。変数ｉが変数Ｍを超えていない場合には、ステップ９０６に進み、まず、Ｔｒｉｐ＿Ｔｉｍｅにｉ番目のトリップの走行時間を加える。次に、ステップ９０７にて、変数ｉに１を加え、ステップ９０５に戻る。ステップ９０５にて、変数ｉが変数Ｍを超えていれば、ステップ９０８に進み、Ｔｒｉｐ＿ＴｉｍｅをＴｏｔａｌ＿Ｔｉｍｅで割った商を変数Ｖａｌｕｅに代入し、処理を終える。ステップ９０８は、車輌の稼働率を評価値としていることを意味する。
【００６０】
図１０を参照して、図７のステップ７０４のトリップの再割り当て処理の詳細を説明する。先ず再割り当ての前に、評価値が最小の車輌に割り当てられている全てのトリップを未割り当て状態にする。ステップ１００１にて、変数Ｌに、未割り当てのトリップのリストを代入する。即ち、変数Ｌに、評価値が最小の車輌に割り当てられていたトリップのリストを代入する。ステップ１００２にて、変数Ｌに、トリップが一つも登録されていないか否かをチェックする。即ち、空リストか否かをチェックする。変数Ｌが空リストの場合には、トリップの再割り当ての処理を終える。変数Ｌが空リストでない場合には、ステップ１００３に進み、変数Ｌに登録されている未割り当てのトリップを一つ取り出し、それを変数ＴＲに代入する。変数ＴＲは追加割り当ての対象となるトリップを示す。
【００６１】
ステップ１００４にて、変数Ｎに、少なくとも１つのトリップが割り当てられている車輌の総数を代入する。ステップ１００５にて、変数Ｉに１を代入する。変数Ｉはトリップの割り当てが可能か否かの判定の対象となる車輌の順番を示す。ステップ１００６にて、変数ＦＬＧ、変数ＴＮｏ、変数Ｐｏｓに０を代入する。図８にて説明したように、変数ＦＬＧはＩ番目の車輌にトリップＴＲの追加が可能か否かを示す。ＦＬＧ＝０であればトリップＴＲの追加が不可能であり、ＦＬＧ＝１であればトリップＴＲの追加が可能である。変数ＴＮｏは車輌番号を示す。変数Ｐｏｓは、車輌の空き時間帯の位置、即ち、トリップの追加位置を表す。
【００６２】
ステップ１００７にて、変数Ｉが変数Ｎを超えているか又は変数ＦＬＧが１であるかをチェックする。変数Ｉが変数Ｎを超えている場合とは、判定対象の車輌の全ての空き時間帯に対して、トリップの追加が可能か否かの判定処理を実行したが、トリップの追加は不可能であると判定されたものである。従って、ＦＬＧの値は０である。ＦＬＧの値が１であればトリップの追加が可能である。
【００６３】
ステップ１００７の条件が成立しなければ、ステップ１００８に進み、Ｉ番目の車輌にトリップＴＲの追加が可能か否かをチェックする。この処理は図８で説明した処理手順で行う。もしトリップの追加が可能ならば、ステップ１００９にて、変数ＴＮｏに変数Ｉを代入し、変数Ｐｏｓに、車輌中でのトリップの追加位置を示すＰの値を代入する。このＰは図８のフローチャートで説明したものである。変数ＦＬＧに１を代入し、ステップ１０１０に進む。
【００６４】
ステップ１００８にてトリップの追加ができない場合にはステップ１０１０に進む。ステップ１０１０にて、変数Ｉに１を加え、ステップ１００７に戻る。
【００６５】
ステップ１００７の条件が成立した場合には、次の処理を行う。まず、ステップ１０１１にて、変数ＦＬＧの値が０か否かを判定する。変数ＦＬＧの値が０の場合には、ステップ１０１２にて、トリップが未割り当ての車輌を一台選択して、その車輌にトリップＴＲを割り当て、ステップ１００２に戻る。
【００６６】
ステップ１０１１にて、変数ＦＬＧが０でない場合、即ち、変数ＦＬＧ＝１の場合には、ステップ１０１３にて、変数ＴＮｏの車輌番号を有する車輌のＰｏｓ番目のトリップの後ろにトリップＴＲを追加する。
【００６７】
以上、本発明による例を説明したが、本発明は上述の例に限定されるものではなく、特許請求の範囲に記載された発明の範囲にて様々な変形が可能であることは当業者に理解されよう。
【００６８】
【発明の効果】
本発明によれば、車輌に対するトリップの最適な割り当てを行うことができる効果がある。
【図面の簡単な説明】
【図１】本発明の輸送割り当て装置の構成を示す図である。
【図２】本発明の輸送割り当て装置の記憶装置に格納されている情報の例を示す図である。
【図３】本発明の輸送割り当てのプログラムの流れを示す図である。
【図４】本発明の輸送割り当てのプログラムのうちの入力処理の流れを示す図である。
【図５】本発明の輸送割り当てのプログラムのうちの車輌割り当てて処理の流れを示す図である。
【図６】図５の車輌割り当てて処理のうちのステップ５０４の初期割り当ての作成処理を示す図である。
【図７】図５の車輌割り当てて処理のうちのステップ５０５の初期割り当ての改良処理を示す図である。
【図８】図６の初期割り当ての作成処理のうちのステップ６０７の車輌へのトリップの追加が可能であるか否かを判定する処理を示す図である。
【図９】図７の初期割り当ての改良処理のうちステップ７０１の車輌の評価処理を示す図である。
【図１０】図７の初期割り当ての改良処理のうちステップ７０４のトリップの再割り当ての処理を示す図である。
【図１１】本発明の輸送割り当て装置の処理装置の割り当て処理部の構成例を示す図である。
【符号の説明】
１０１…入力装置、１０２…出力装置、１０３…表示装置、１０４…処理装置、１０５…プログラム実行部、１０６…入力処理部、１０７…車輌割り当て処理部、１０８…結果出力処理部、１０９…記憶装置、１１０…拠点情報、１１１…トリップ情報、１１２…車輌情報
【図１】
2004217333.tif 000003
【図２】
2004217333.tif 000004
【図３】
2004217333.tif 000005
【図４】
2004217333.tif 000006
【図５】
2004217333.tif 000007
【図６】
2004217333.tif 000008
【図７】
2004217333.tif 000009
【図８】
2004217333.tif 000010
【図９】
2004217333.tif 000011
【図１０】
2004217333.tif 000012
【図１１】
2004217333.tif 000013