(57)【要約】【課題】物流センターから配送先への荷物輸送と、集荷先から物流センターへの荷物輸送を混載した車両の集配送先での時間制約を守った効率的な輸送スケジュールを作成する。【解決手段】輸送スケジュールを作成する際に、物流センターや集配送先拠点の位置情報を入力し、輸送すべき荷物の荷物量、集配送先、集配送先での、輸送車両の到着時刻の締め切り時刻である時間制約を含む荷物情報を入力し、輸送車両の積載量上限を含む輸送車両情報を入力し、複数車両の巡回拠点からなる輸送スケジュールへ、同一拠点への物流センターからの配送荷物と、物流センターへの集荷荷物を一台の車両で同時に輸送可能かを判定し、配送時間制約を守った条件下で、前記各情報を用いて輸送車両のスケジュールを作成する。【選択図】　図１
2004001975.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも入出力装置と、処理装置と、記憶装置とを有した物流センターから、集配送先拠点への荷物の配送と集荷を行う車両の輸送スケジュール作成を行うシステムにおいて、物流センターや、集荷・配送先などの拠点の位置情報を入力する拠点情報登録ステップと、各荷物の荷物量、配送先拠点・配送時間制約を含む荷物情報を入力する荷物情報登録ステップと、トラックなどの輸送車両の積載量限界などを含む輸送車両情報を入力する輸送便情報登録ステップと、これらの情報からトラックなどの輸送車両の輸送スケジュールを作成する輸送スケジュール作成ステップと、作成した輸送スケジュールを出力するスケジュール出力ステップとを有することを特徴とする双方向輸送スケジュール作成方法。
【請求項２】
請求項１において、前記輸送スケジュール作成ステップは、複数トラックの輸送スケジュールからなる初期集団を作成する初期輸送スケジュール作成ステップと、その初期スケジュール集団を遺伝的操作により改良するスケジュール改良ステップからなる遺伝的アルゴリズムを用いた輸送スケジュール作成ステップとを有することを特徴とする双方向輸送スケジュール作成方法。
【請求項３】
請求項２において、前記輸送スケジュール作成ステップは、集配送対象の荷物を一意に識別するＩＤを設け、そのＩＤを輸送に利用する車両の巡回順序で一次元に並べた遺伝子構造を用いる遺伝的アルゴリズムによる輸送計画作成に用い、交差処理においてはランダムに二つの遺伝子を選択して、その交差位置を決め、一方の遺伝子の交差位置よりも前に記録されている輸送スケジュールと、その輸送スケジュールに含まれていない荷物の集配送先拠点を、もう一方の遺伝子中の順序に従って、先の輸送スケジュールにＮＩ法（Ｎｅａｒｅｓｔ　Ｉｎｓｅｒｔｉｏｎ　Ｍｅｔｈｏｄ：最近隣挿入法）により追加を行うことを特徴とする双方向輸送スケジュール作成方法。
【請求項４】
請求項３の前記遺伝的アルゴリズムの突然変異操作において、ランダムに選択した遺伝子に記録されている一つの荷物を選択し、その荷物の集配送先拠点および、更にランダム距離を一つ選択して、先に選択した集配送先拠点から、その距離以内の集配送先の荷物を、遺伝子から削除し、再度ＮＩ法で追加することを特徴とする双方向輸送スケジュール作成方法。
【請求項５】
請求項３または請求項４の前記ＮＩ法による集配送先の輸送スケジュールへの追加処理において、同一集配送先拠点への、集荷荷物と配送荷物をペアにして、一台の車両で、その二つの荷物の輸送が可能な車両を探索し、二つの荷物を追加できる車両があれば、その車両に二つの荷物を同時に追加することにより物流センターから配送先拠点への配送を行った後に、集荷拠点を配送時とは逆順に巡回して集荷を行う輸送形態と、各集配送先拠点巡回時に配送と集荷を同時に行う輸送形態が全て指定により自在にできることを特徴とする双方向輸送スケジュール作成方法。
【請求項６】
請求項５の前記集荷荷物と配送荷物の同時追加処理において、各荷物に設定された集荷時間及び配送時間の制約を満足し、かつ、それら荷物の追加により車両の積載量上限を超過しない場合、それら二つの荷物の追加で、車両の走行距離増分が最小になる車両と、その車両で巡回する順序を選択することを特徴とする双方向輸送スケジュール作成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、物流分野におけるスケジューリング作成を計算機で行う方法に係り、特に、計算機を利用した物流計画の双方向輸送スケジュール作成方法に関する。
【０００２】
【従来の技術】
物流システムでの、輸送スケジュール作成技術としては、いわゆる巡回セールスマン問題やビークルルーティング問題に相当する一定地域内に存在する顧客先の効率的な巡回計画を作成する技術がある。
（特開平５−１３５０７０号公報「配送スケジューリング装置」）
また、特開平１０−１２４５８８号公報「地理情報に基づくスケジュール作成装置」は、地理情報と共に、顧客先間の最短経路決定にニューラルネットを用いることで、最適なスケジュール作成することが開示される。
【０００３】
また、特開平８−１１５４９５号公報「自動配車装置」では、多数の配送先をクラスタリングして、各クラスター内で輸送ルートを作成する方式を実現している。
【０００４】
更に、特開平９−３０５６６９号公報「配送計画方法と装置」では、トラックの積載量制約と稼働時間制約を守った上で効率的な配車計画を作成するために、いわゆるスウィープ法（増井忠幸他著「ロジスティクスのＯＲ」槇書店　１９９８年）に基づく技法を用いている。
【０００５】
更に、小規模な輸送ルートを高速に作成する方法として、２ｏｐｔ法やＬＫ法などのアルゴリズムも開発されている。（茨木俊秀「離散最適化法とアルゴリズム」岩波書店　１９９３年）
【０００６】
【発明が解決しようとする課題】
トラック輸送などを対象とした物流スケジューリングは、荷物を指定された時刻に正確に輸送するとともに、トラックなどの機材や、運用に関わる人員や物流センターなどの設備の利用効率向上、コスト削減が必要である。
【０００７】
トラックでの輸送は、一般的に物流センターから顧客先などへの一方向の輸送が多く、従来の技術で挙げたスケジューリング作成方法は、このような物流センターから顧客先などへの配送か、顧客先から物流センターへの集荷の一方だけを扱っているものが多い。しかし、トラック輸送を主体とした物流の効率は、片方向の輸送だけでは十分に向上させることは困難であり、顧客先から物流センターへの輸送と、物流センターから顧客先の荷物を混在させて輸送する必要がある。
【０００８】
例えば、特開平８−１１５４９５号公報「自動配車装置」においても、複数の届け先の車両別エリア範囲を決定するために、トラックの積載量に基づくクラスタリングを用いているが、この手法では、物流センターから顧客先などへの配送荷物の荷量と、顧客先から物流センターに輸送する荷物の荷量を区別できないため、両者が混在した輸送を扱うことはできないという問題がある。
【０００９】
また、特開平９−３０５６６９号公報「配送計画方法と装置」では、物流センターと配送先間の双方向輸送を扱えるが、スウィープ法をトラック輸送のルート作成に用いているため、作成される輸送ルート自体の効率が悪く、充分な輸送効率の向上を実現できない。更に、Ｊｕｓｔ　Ｉｎ　Ｔｉｍｅ納入やサプライチェーンマネージメントの実現に必要な時間を指定した輸送に対応したトラック輸送のルート作成も、スウィープ法では実現できないという問題がある。
【００１０】
また、物流センターと顧客先の双方向輸送を行う場合には、トラックの構造上、物流センターから顧客先への荷物を全て配送した後でないと、顧客先から物流センターへの荷物を積載できない場合も多い。通常このような条件下では、物流センターから配送を行った配送先を、逆順に物流センターへ戻ることも多い。単純なスウィープ法では、このような輸送ルートを作成することもできないという問題がある。
【００１１】
さらに、道路渋滞などの条件を考慮すると、単純に物流センターから配送した順序の逆順で戻るだけでは、輸送効率が落ちることもあり、状況に合致したスケジュールを作成する必要があるという問題がある。
【００１２】
【課題を解決するための手段】
上記目的を達成するため、少なくとも入出力装置と処理装置と記憶装置とを有した輸送計画作成を行うシステムにおける輸送計画作成方法であって、物流拠点、集配送先などの拠点の位置情報を入力する拠点情報登録ステップと、各荷物の荷物量、集配送先拠点、集荷・配送する時間の制限等を含む荷物情報を入力する荷物情報登録ステップと、トラックなどの輸送車両の積載量限界や物流センターからの出発時間を含む輸送車両情報を入力する輸送車両情報登録ステップと、これらの情報から車両が荷物を輸送する際の輸送スケジュール作成ステップと、作成結果を出力する出力ステップとを有し、荷物情報登録ステップにおいて入力された各荷物の配送時間制約や車両の積載量制約などの条件を守って、最適な輸送計画の作成を行う。
【００１３】
また、輸送スケジュールを作成する輸送スケジュール作成方法において、スケジュール作成ステップは、初期スケジュールを作成する初期解生成ステップと、初期スケジュールから開始して遺伝的操作を行いスケジュールを改良していくスケジュール改良ステップとを含む遺伝的アルゴリズムを用いて輸送スケジュールを算出するものである。
【００１４】
また、遺伝的アルゴリズムを用いた輸送スケジュール作成方法において、その交差処理は、ランダムに二つの遺伝子を選択して、その交差位置を決め、一方の遺伝子の交差位置よりも前方に記録されている輸送スケジュールと、その輸送スケジュールには含まれていない輸送対象荷物を、もう一方の遺伝子中の順序に従って取り出し、その取り出した順序でＮＩ（Ｎｅａｒｅｓｔ　Ｉｎｓｅｒｔｉｏｎ）法を用いて、先の輸送スケジュール中に追加する。
【００１５】
また、遺伝的アルゴリズムを用いた輸送スケジュール作成方法において、その突然変異処理は、輸送スケジュール中の集配送先拠点を一つランダムに選択するとともに、その拠点からランダムに決定した半径内の集配送先を全て輸送スケジュールを表す遺伝子上から削除し、これら削除した集配送先を、再度ＮＩ法で追加する。
【００１６】
また、ＮＩ法による集配送先拠点の既存輸送スケジュールへの追加処理において、物流センターから配送する荷物の輸送先拠点から物流センターに集荷する荷物を同時に追加可能な車両を輸送スケジュール中から探索し、指定により、まず物流センターから配送先拠点への配送を行った後に、配送経路を逆順に巡回して集荷を行う輸送形態と、集配送先拠点巡回時に配送と集荷を同時に行う輸送形態を自在に選択して車両の輸送スケジュールを作成する。
【００１７】
また、ＮＩ法による集配送先拠点の既存輸送スケジュールへの追加処理において、物流センターから配送する荷物の輸送先拠点から物流センターに集荷する荷物を同時に追加可能な車両を輸送スケジュール中から探索し、条件に合致する車両が見つかった場合には、その車両に前記の二つの荷物を同時に追加する。
【００１８】
【発明の実施の形態】
以下、本発明の一実施の形態を、図面を用いて詳細に説明する。本実施の形態では、輸送は物流センターに所属する複数台の車両（トラック等）が物流センターを出発して、複数の拠点への荷物の配送と、それら拠点からの物流センターへの荷物の集荷を行うスケジュールの作成を想定している。
【００１９】
図１は、本発明のシステム構成を示すブロック図である。本システムは、入力装置１０１、プリンタなどの出力装置１０２、ディスプレイなどの表示装置１０３、処理装置１０４、記憶装置１０９を備える。
【００２０】
処理装置１０４は、入力処理部１０６、輸送スケジュール作成部１０７および結果出力部１０８を含む一連のプログラム１０５を実行する。また、記憶装置１０９には、拠点情報１１０、荷物情報１１１、輸送車両情報１１２、距離テーブル１１３、道路地図１１４、及び、これらから作成される輸送ルート情報１１５が格納される。また、輸送ルート作成に用いる、遺伝子情報１１６及び車両管理情報１１７も格納される。
【００２１】
図２は図１の記憶装置１０９に格納される各情報のフォーマットの一例を示す図である。拠点情報１１０には、物流センターや荷物の集配送先拠点の位置情報を格納する。具体的には、物流センターや集配送先拠点を一意に識別する拠点ＩＤ２０１、拠点の名称２０２、拠点の住所２０３、拠点の位置を示す緯度２０４と経度２０５等が格納される。
【００２２】
荷物情報１１１には、輸送の対象となる各荷物に関する情報を格納する。具体的には、個々の荷物に１から順次付与した荷物インデックス２０６、荷物を一意に識別する荷物ＩＤ２０７、物流センターから配送先に送る荷物か、集配先拠点から物流センターに集荷する荷物かを表す集配／配送２０８、荷物の集配送先を示す拠点ＩＤ２０９、荷量２１０、その配送先での荷物集荷・配送の指定時間帯を示す時間制約２１１からなる。
【００２３】
輸送車両情報１１２には、利用可能な車両の積載重量に関する能力や限界、また、車両の稼働時間についての情報を格納する。具体的には、輸送車両情報１１２には、車両を一意に識別するために１から順次付与した車両Ｎｏ２１２、その種類の車両の積載量上限２１３、および、その車両の物流センターからの出発時刻２１４と配送業務を終える帰着時刻２１５からなる。
【００２４】
距離テーブル１１３には、輸送スケジュール作成で必要になる、拠点間のトラックなどの輸送車両での走行距離・時間に関する情報を格納する。具体的には、出発拠点のＩＤ２１６と到着拠点のＩＤ２１７、その拠点間の距離２１８と拠点間の走行所要時間２１９からなる。
【００２５】
輸送ルート情報１１５は、本発明に係わる方法によって作成される輸送スケジュールで車両が巡回する拠点と、その車両の巡回順序を示す情報を格納する。具体的には車両Ｎｏ２２０、車両の巡回拠点数２２１、や集荷送先拠点の拠点ＩＤ２２２と、その拠点への到着時間２２３、その拠点との輸送を行う荷物インデックス２２４を格納する。また、合計荷物量２２８や総走行距離２２９を格納する。
【００２６】
図３の遺伝子情報１１６には輸送スケジュール作成部１０７で用いる遺伝的アルゴリズムによる輸送スケジュール作成で用いる遺伝子表現の一例を示している。遺伝子には、トラックなどの輸送車両で配送する荷物の荷物インデックス３０１がそれぞれ格納される。
【００２７】
車両管理情報１１７には、輸送スケジュール作成部１０７で用いる遺伝子情報１１６の車両への対応関係を示す情報を格納する。遺伝子情報１１６は、単に荷物インデックスを一次元に並べた配列であり、どの荷物がどの車両に積載されているかは記録されていない。この車両管理情報１１７には、各車両に積載される荷物が、遺伝子情報１１６のどの部分に対応しているかを示すために、以下の情報を車両毎に格納する。つまり車両を一意に識別する車両Ｎｏ３０４、その車両に積載する荷物の遺伝子上での開始位置を示す遺伝子開始位置３０５、終了位置を示す遺伝子終了位置３０６からなる。
【００２８】
図４は、処理装置１０４が実行するプログラム１０５の概要を示すフローチャートである。まず、入力処理　（４０１）で、拠点情報１１０、荷物情報１１１、輸送車両情報１１２等の輸送計画を作成するために必要な情報をユーザが入力する。この処理の詳細は図５で後述する。次の輸送スケジュール作成処理（４０２）では、入力処理　（４０１）によって得られた情報から、最適と考えられる輸送計画を決定する。ここで輸送計画の決定とは、入力された全ての荷物を配送先に届けることが可能なトラックが従うべき荷物のトラックへの割り当てとスケジュール（輸送スケジュール情報）を決定することを指す。この処理の詳細は図６で後述する。次に、結果出力処理　（４０３）では、作成したスケジュールを、その評価とともに出力する。この処理の詳細は図４で後述する。
【００２９】
図５は、図４中の入力処理　（４０１）の詳細を示すフローチャートである。まず、拠点情報登録　（５０１）で、拠点情報１１０の登録を行う。次に、荷物情報登録　（５０２）で、荷物情報１１１の登録を行う。次に輸送車両情報登録　（５０３）で、輸送ルート情報１１５の登録を行う。次に距離テーブル生成処理（５０４）で拠点間の距離とトラックによる走行所要時間を道路地図１１４を参照して生成する。なお、道路地図１１４は、カーナビゲーションで利用されるような道路及びその道路間の接続関係や距離情報が格納されているものが予め用意されているものとする。
【００３０】
図６は、輸送スケジュール作成処理（４０２）の詳細を示すフローチャートである。この輸送スケジュール作成処理（４０２）は、ＧＡ（遺伝的アルゴリズム）に従っている。まず、ランダム性を含んだ方法によって、初期解集団生成処理（６０１）により、それぞれが異なる初期解集団を作成する。この処理の詳細は図１３で後述する。次に、変数Ｉに１を代入する（６０２）。次に遺伝的処理による解集団の改良を行う（６０３）。この処理の詳細は図１５で後述する。
【００３１】
ステップ６０３の処理によって、解集団の少なくとも一部分は変化し、ステップ６０３〜ステップ６０５の処理の繰り返しによって解集団は徐々に最適な解へ近づいて行く。ステップ６０２の処理の後、集団の評価を行う（６０４）。評価は輸送ルート情報１１５から算出される車両の走行距離や利用車両台数などさまざまな要素に対し行われ、その結果によって解集団中の個々の解に対して順位がつけられる。この評価結果が上位の解を、次世代の解として選択する（６０５）。　次に、変数Ｉに１を加える（６０６）。Ｉが予め設定されているＧＡの処理世代数Ｇ＿ＭＡＸを越えるか、次世代の集団中の最良解の評価値が予め与えられている目標値よりも良いかチェックする（６０７）。もし条件が成立すれば、現在の解集団で最良の解を出力して処理を終える（６０８）。ステップ６０７で条件が成立しなければ、ステップ６０３に戻り遺伝的処理による解集団の改良を繰り返す。
【００３２】
図７は、図６の遺伝的アルゴリズムを用いた輸送スケジュール作成処理の初期解集団の作成（６０１）、解集団の改良処理（６０３）で用いる荷物の輸送スケジュールへの荷物の追加処理の詳細を示すフローチャートである。
【００３３】
この処理は、複数台の輸送車両からなる輸送スケジュールに、一つの荷物の集配送を追加する処理である。まず、変数Ｌに新たにスケジュールに追加する荷物のインデックスを代入する（７０１）。次に、その荷物と同一の集配送先の荷物で、まだスケジュール中に追加されていないもので、追加対象の荷物と集荷・配送が異なる荷物があるかチェックする（７０２）。もしステップ７０２で、条件に合致する荷物がある場合には、以下の処理を行う。
【００３４】
まず、変数Ｌ１にＬの値を代入する（７０３）。次にステップ７０２で見つかった荷物のインデックスをＬ２に代入する（７０４）。次に、Ｌ１，　Ｌ２の荷物をペアで輸送スケジュール中に追加する（７０５）。この処理の詳細は図８で説明する。ステップ７０２で条件に合致する荷物が無いの場合には、インデックスがＬの荷物を輸送スケジュール中追加する（７０６）。この処理の詳細は図９で説明する。
【００３５】
図８は、ステップ７０５のペア荷物追加処理の詳細を示すフローチャートである。この処理では、変数Ｌ１及びＬ２に設定された二つの荷物を輸送可能な車両を見つけ、その車両の輸送スケジュールへ、その二つの荷物を追加する。もし、輸送スケジュールに二つの荷物を追加できる車両が無ければ、新しい車両を、その二つの荷物の輸送に割り当てる。この処理では、追加対象の二つの荷物のインデックスが変数Ｌ１、Ｌ２に事前に設定されているとする。
【００３６】
まず、変数Ｉに１を代入する（８０１）。変数Ｐｏｓ１、Ｐｏｓ２、Ｔｒｕｃｋに−１を設定する（８０２）。次に変数Ｔｍｉｎに利用する計算機で表現可能な最大数（Ｍａｘ＿Ｖａｌｕｅと表記する。）を設定する（８０３）。次に、Ｉの値と、既に輸送スケジュールを割り当てられている車両台数を表す変数Ｍａｘ＿Ｔｒｕｃｋの値を比較する（８０４）。もしＩの値がＭａｘ＿Ｔｒｕｃｋを越えていない場合には、以下の処理を行う。まず、変数Ｔ＿ＮｏにＩの値を設定する（８０５）。次に、Ｔ＿Ｎｏ番目の車両へＬ１とＬ２の荷物を同時に積載可能かチェックする（８０６）。この処理の詳細は図１０で説明する。
【００３７】
次に、変数Ｔｍｉｎと変数Ｔの値を比較する（８０７）。この変数Ｔには、ステップ８０６の処理でＴ＿Ｎｏ番目の車両への二つの荷物の追加ができた場合の、Ｔ＿Ｎｏ番目の車両の走行時間の増分値が設定されている。もしＴ＿Ｎｏ番目の車両に積載できない場合には、ＴにはＭａｘ＿Ｖａｌｕｅが設定されている。
【００３８】
もし、ステップ８０７でＴが小さい場合には、変数ＴｒｕｃｋにＴ＿Ｎｏの値を、Ｐｏｓ１にＰ１、Ｐｏｓ２にＰ２の値を設定する（８０８）。ここで、変数Ｐ１及びＰ２はステップ８０６の処理でＴ＿Ｎｏ番目の車両への二つの荷物の追加が可能な場合の、その車両のスケジュール中への各荷物の追加位置が設定されている。次に、変数Ｉに１を加え（８０９）、ステップ８０４に戻り、次の車両のチェックに移る。ステップ８０４でＩがＭａｘ＿Ｔｒｕｃｋの値を超えれば次の処理を行う。
【００３９】
まず、変数Ｔｒｕｃｋの値が−１か否かをチェックする（８１０）。もし、−１で無ければ、既存の輸送スケジュール中に、二つの荷物の追加が可能なトラックが見つかったので、そのトラックへの荷物の追加を行う。すなわち、変数Ｔｒｕｃｋの値の車両Ｎｏの車両のＰｏｓ１の位置に荷物Ｌ１を追加し、次にＰｏｓ２の位置に荷物Ｌ２を追加する（８１１）。もし、ステップ８１０で変数Ｔｒｕｃｋの値が−１ならば、既存スケジュール中には二つの荷物を運べる車両が無いので、新しい車両を追加して、変数Ｍａｘ＿Ｔｒｕｃｋに１を加える（８１２）。次に、追加した車両にＬ１とＬ２の荷物を追加する（８１３）。
【００４０】
図９は図７のステップ７０６の単独荷物追加処理の詳細を示すフローチャートである。この処理では、変数Ｌに追加対象荷物のインデックスが予め設定されている。まず、変数Ｉに１を設定する（９０１）。次に、変数Ｐｏｓ及びＴｒｕｃｋに−１を設定する（９０２）。次に、変数ＴｍｉｎにＭａｘ＿Ｖａｌｕｅを設定する（９０３）。次に、変数Ｉの値と、Ｍａｘ＿Ｔｒｕｃｋの値を比較する（９０４）。ＩがＭａｘ＿Ｔｒｕｃｋを越えていなければ、以下の処理を行う。
【００４１】
まず、Ｔ＿ＮｏにＩの値を設定する（９０５）。Ｔ＿Ｎｏ番目の車両での荷物Ｌの輸送が可能か否かをチェックする（９０６）。この処理の詳細は図１１で説明する。
【００４２】
このステップ９０６の処理で、変数Ｔには、Ｔ＿Ｎｏ番目の車両に荷物Ｌの輸送を追加した場合、その車両の走行時間の増分が代入される。また、変数Ｐｏｓ１には、荷物Ｌの追加位置が設定される。Ｔ＿Ｎｏ番目の車両での輸送が行えない場合には、ＴにはＭａｘ＿Ｖａｌｕｅが設定される。
【００４３】
ステップ９０６により、上記の様に変数Ｔ及びＰに値が設定されるので、次に、ＴｍｉｎとＴの値を比較する（９０７）。もし、ＴがＴｍｉｎよりも小さければ、ＴｒｕｃｋにＴ＿Ｎｏの値を代入し、ＰｏｓにＰｏｓ１の値を代入する（９０８）。次に、Ｉに１を加え（９０９）、ステップ９０４に戻り、次の車両のチェックに移る。ステップ９０７で、ＴがＴｍｉｎ以上の値であった場合には、その車両への荷物追加は最適でないので、ステップ９０９に移り、Ｉに１を加え（９０９）、次の車両の処理に移る。
【００４４】
ステップ９０４でＩがＭａｘ＿Ｔｒｕｃｋの値を超えた場合、輸送スケジュールを割り当て済みの全車両のチェックを終えたので、以下の処理を行う。
【００４５】
まず、変数Ｔｒｕｃｋの値が−１かチェックする（９１０）。−１で無い場合には、荷物Ｌを輸送可能な車両が見つかったので、その車両のＰｏｓ番目の位置に荷物Ｌを追加する（９１１）。ステップ９１０でＴｒｕｃｋの値が−１で無い場合には、荷物Ｌを輸送可能な車両が無いので、新しい車両を輸送スケジュールに追加し変数Ｍａｘ＿Ｔｒｕｃｋに１を加え（９１２）、その車両に荷物Ｌを追加する（９１３）。
【００４６】
図１０はステップ８０７のペア荷物追加チェック処理の詳細を示すフローチャートである。この処理では、予め変数Ｌ１，Ｌ２に追加対象の二つの荷物のインデックスが格納され、それら荷物の輸送可能性をチェックする対象車両の車両Ｎｏは変数Ｔ＿Ｎｏに設定されているとする。この処理が終わると、二つの荷物を輸送可能な場合には、その輸送の追加によるＴ＿Ｎｏ番目の車両の走行時間の増分がＴに代入され、追加位置が変数Ｐｏｓ１，　Ｐｏｓ２に設定される。その車両で輸送ができない場合には、ＴにはＭａｘ＿Ｖａｌｕｅが設定される。具体的な処理手順は次の通りである。
【００４７】
まず、変数Ｐ１、Ｐ２に−１を設定し、変数ＴにＭａｘ＿Ｖａｌｕｅを設定する（１００１）。次に、Ｌ１の荷物がＴ＿Ｎｏ番目の車両に積載可能かチェックする（１００２）。この処理の詳細は図１２で説明する。
【００４８】
ステップ１００２で荷物Ｌ１が追加可能でなければ、処理を終える。ステップ１００２で荷物Ｌ１の追加が可能だった場合には、変数Ｐｏｓ１に荷物Ｌ１の追加位置Ｐｏｓを代入する（１００３）。変数Ｐｏｓには、図１２で説明する処理の中で荷物の追加位置が設定されている。
【００４９】
次に、荷物Ｌ１をＴ＿Ｎｏ番目車両のＰ１の位置に追加する。（１００４）。次に変数Ｔ１に荷物Ｌ１の追加による、Ｔ＿Ｎｏ番目車両の走行時間の増分量を設定する（１００５）。次に、荷物Ｌ２がＴ＿Ｎｏ番目車両での輸送が可能かチェックする（１００６）。この処理はステップ１００２の処理と同一の処理であり、図１２で詳細を説明する。
Ｔ＿Ｎｏ番目の車両での荷物Ｌ２の輸送が行えない場合には、ステップ１０１１に移り、Ｔ＿Ｎｏ番目車両の輸送スケジュール中の荷物Ｌ１を削除し処理を終える。
ステップ１００６で、荷物Ｌ２が輸送可能な場合には、Ｐｏｓ２に荷物Ｌ２の追加位置Ｐｏｓを代入する（１００７）。変数Ｐｏｓには図１２で説明するステップ１００６の処理で、荷物の追加位置が設定されている。ステップ１００６の次に、Ｌ２の荷物をＴ＿Ｎｏ番目の車両のＰｏｓ２の位置に追加する（１００８）。次に、変数ＴにＴ１の値と荷物Ｌ２の輸送によるＴ＿Ｎｏ番目車両の走行時間の増分値を和を設定する（１００９）。次に、荷物Ｌ１及びＬ２をＴ＿Ｎｏ番目の車両の輸送スケジュール中から削除する（１０１０）。
【００５０】
図１１はステップ９０６の単独荷物追加チェック処理の詳細を示すフローチャートである。この処理では、予め変数Ｔ＿Ｎ　ｏに追加チェック対象の車両Ｎｏが、Ｌには追加する荷物のインデックスが設定されている。
【００５１】
まず、変数Ｐｏｓ１に−１、ＴにＭａｘ＿Ｖａｌｕｅを設定する（１１０１）。次に、荷物ＬがＩ番目の車両で輸送可能かチェックする（１１０２）。この処理の詳細は図１２で説明する。荷物Ｌが輸送できない場合には、処理を終える。Ｔ＿Ｎｏ番目の車両で荷物Ｌを輸送可能な場合には、以下の処理を行う。
【００５２】
まず、変数Ｐｏｓ１にＰｏｓの値を代入する（１１０３）。変数Ｐｏｓは図１２で詳細を説明する処理中で設定されている。次に変数ＴにＴ＿Ｎｏ番目の車両への荷物Ｌの追加による走行時間の増分を設定する（１１０４）。この増分値は図１２で詳細を説明するステップ１１０２の処理中で変数Ｄ＿ＭＩＮに設定されている。
【００５３】
図１２は図１０及び図１１の荷物追加チェック処理の詳細を示すフローチャートである。
【００５４】
この処理では、予めスケジュールへの追加対象の荷物のインデックスが変数Ｌに、また追加可能かチェックする車両の車両Ｎｏが変数Ｔ＿Ｎｏに設定されているとする。この処理が終わると、荷物Ｌの輸送が車両Ｔ＿Ｎｏで可能であった場合には、変数Ｐｏｓに追加位置が設定され、Ｄ＿ＭＩＮに、その荷物の追加による車両の走行時間の増分値が設定される。追加できなかった場合には、Ｐｏｓには−１、Ｄ＿ＭＩＮにはＭａｘ＿Ｖａｌｕｅが設定される。
【００５５】
まず、変数Ｚに追加対象荷物Ｌの集配送先拠点ＩＤを代入する（１２０１）。次に、変数Ｖに荷物Ｌの荷量を設定する（１２０２）。次に、変数Ｐｏｓに−１を設定する（１２０３）。次に、Ｄ＿ＭＩＮにＭａｘ＿Ｖａｌｕｅを設定し（１２０４）、変数Ｉに車両管理情報１１７を参照して、Ｔ＿Ｎｏ番目の車両の遺伝子開始位置を設定する（１２０５）。
【００５６】
次に、変数Ｉの値と、その車両の遺伝子終了位置＋１の値を比較する（１２０６）。　Ｉが大きい場合には、処理を終える。Ｉが前記の値を超えていない場合には、次の処理を行う。
【００５７】
まず、ＩがＴ＿Ｎｏ番目の車両の遺伝子開始位置と比較する（１２０７）。等しい場合には、変数Ｘには車両が出発する物流センターを表す拠点ＩＤを代入する（１２０９）。等しくない場合には、その車両の遺伝子情報１１６中の（Ｉ−１）番目の荷物の集配送先の拠点ＩＤを代入する（１２０８）。次に、ＩとＴ＿Ｎｏ番目の車両の遺伝子終了位置＋１の値と比較する（１２１０）。もし等しければ、変数Ｙには物流センターの拠点ＩＤを代入する（１２１２）。等しくない場合には、ＹにＴ＿Ｎｏ番目の車両のＩ番目の荷物の集配送先拠点のＩＤを代入する（１２１１）。
【００５８】
次に、荷量Ｖの荷物Ｌを、Ｉ番目の車両のＸ番目の輸送荷物とＹ番目の輸送荷物の間に積載可能かチェックする（１２１２）。つまり、追加対象荷物が、配送荷物の場合には、車両が出発する物流センターから、Ｘ番目の輸送荷物の集配送先拠点までの間で、その車両の荷量にＬを加えた値が、その車両の最大積載量を超過しないかチェックする。また、その荷物が集荷荷物の場合には、その車両のＹ番目の荷物の集配送先拠点から、物流センターに戻るまでの間の各集配送先拠点での積載荷量にＬを加えた値が、その車両の最大積載量を超過していないかをチェックする。
【００５９】
次に、Ｄｅｌｔａ＿ＴにＸとＺ間の所要時間と、ＺとＹ間の所要時間の和からＸとＹ間の所要時間を差し引いた値を代入する（１２１３）。次に、その車両のＹ以降の荷物の輸送で巡回する集配送先の車両到着時間にＤｅｌｔａ＿Ｔを加えた値が、時間制約を破らないかチェックする（１２１４）。図１２ではＴＩＭＥ（Ｘ，Ｙ）で拠点ＸからＹへの車両の走行所用時間を表している。次に、Ｄ＿ＭＩＮとＤｅｌｔａ＿Ｔを比較する（１２１５）。Ｄｅｌｔａ＿Ｔが小さければ、Ｄ＿ＭＩＮにＤｅｌｔａ＿Ｔの値を加え、ＰｏｓにＩの値を代入する（１２１６）。
次に、Ｉに１を加え（１２１７）、ステップ１２０６に戻り次の追加位置の処理に移る。
【００６０】
図１３は初期解集団生成処理（６０１）の詳細を示すフローチャートである。なお、一つの解には複数の車両の巡回スケジュールが登録されている。また、解集団は複数の解を含んでいる。　変数ＳＩＺＥには、予め初期集団に登録する遺伝子の個体数を設定しておく。また、変数ＬＥＮにはルートに登録される配送先拠点の数を設定しておく。まず、変数Ｉに１を代入する（１３０１）。
【００６１】
次に、ＩがＳＩＺＥよりも小さい間、ステップ１３０３からステップ１３０６の処理を繰り返してＳＩＺＥで指定された個数の遺伝子を生成する。まず、各要素に値が設定されていない空の遺伝子を記憶するエリアを生成する（１３０３）。次に、荷物情報１１１の荷物をランダムな順序に並べかえた配列Ｔ［］を作成する（１３０４）。次に、空の遺伝子に、配列Ｔ［］に登録した荷物を、この順序で図７に示した追加手順により順次追加する（１３０５）。次に変数Ｉに１を加えて（１３０６）、ステップ１３０２に戻り次の初期解の作成をする。
【００６２】
図１４は、解集団の改良（６０３）の詳細を示すフローチャートである。遺伝的処理は、解集団の変化、改良を行うＧＡの中心的な処理である。まず、まず、変数ＳＩＺＥに解集団に登録されている解の個数を代入する（１４０１）。次に、Ｃ＿ＮＵＭにＳＩＺＥに予め設定されている交差率を掛けて、その値を超えない最大整数を代入する（１４０２）。次に、変数Ｉに１を代入する（１４０３）。ＩがＣ＿ＮＵＭ以下の場合には（１４０４）、次の処理を繰り返して交差処理を行う。まず、解集団から異なる二つの解（遺伝子）を選択する（１４０５）。次に、選択した二つの解（遺伝子）を元に、交差処理を行い、交差処理で新たに生成された解（遺伝子）を解集団に加える（１４０６）。この交差処理の詳細は、図１２で詳細を説明する。
【００６３】
次に、Ｉに１を加え（１４０７）、ステップ１４０４に戻り次の交差処理に移る。ステップ１４０４で、ＩがＣ＿ＮＵＭを超過していれば、突然変異処理に移る。つまり、変数Ｍ＿ＮＵＭにＳＩＺＥに予め設定されている突然変異率を掛け、その値を超えない最大整数を代入する（１４０８）。次に、変数Ｉに１を代入する（１４０９）。次に、ＩがＭ＿ＮＵＭの値以下の間、次の処理を繰り返す（１４１０）。まず、解集団から、ランダムに一つの解（遺伝子）を選択する（１４１１）。次に選択した解に突然変異処理を行い、その解（遺伝子）を解集団に加える（１４１２）。この処理の詳細は図１６で説明する。次に変数Ｉから１を加え（１４１３）、ステップ１４１０に戻り処理を続ける。
【００６４】
図１５は、ステップ１４０６の交差処理の詳細を示すフローチャートである。まず、変数Ｎに各解（遺伝子）に登録されている荷物数を代入する（１５０１）。次に、交差対象の二つの解（遺伝子）を配列Ｇ１［］，Ｇ２［］にコピーする（１５０２）。次に、交差点を決定するために、２以上Ｎ−１以下の整数をランダムに生成して変数Ｐに代入する（１５０３）。次に、Ｇ１のＰ番目以降の荷物データインデックスを削除する（１５０４）。つまり削除対象の要素に−１を代入する。　次に変数Ｉに１を代入する（１５０５）。次に、ＩがＮ以下の間（１５０６）、次の処理を行う。Ｇ２［Ｉ］が配列Ｇ１［］中には含まれていないかチェックする（１５０７）。もし、含まれていない場合には、その荷物情報を図７に示した処理手順によりＧ１［］の輸送スケジュール中に追加する（１５０８）。次に、変数Ｉに１を加え（１５０９）、次の処理に移る。ステップ１５０７で条件が成立しない場合には、ステップ１５０９に移り次の処理に移る。ステップ１５０６でＩがＮを越えれば処理を終える。
【００６５】
図１６はステップ１４１２の突然変異処理の詳細を示すフローチャートである。まず、突然変異処理対象の解（遺伝子）を配列Ｇ［　］にコピーする。（１６０１）　次に、物流センターから最も遠い集配送先拠点と、物流センターからの距離を変数Ｌに代入する（１６０２）。　変数Ｒに０と０．３の範囲の実数をランダムに生成して代入する（１６０３）。次に、変数Ｌ１に変数Ｌの値とＲの値の積を代入する（１６０４）。
【００６６】
次に、遺伝子上での突然変異箇所を定めるために、変数Ｐに１以上Ｎ以下の整数をランダムに選択して代入する（１６０５）。次に、変数Ｉに２、Ｊに０を代入する（１６０６）。変数ＫにはＧ［Ｐ］の値、つまり荷物情報１１１のインデックス値を代入する（１６０７）。ＩがＮ−１以下の間（１６０８）、次の処理を繰り返す。インデックスがＫの荷物の集配送先拠点とＧ［Ｉ］の荷物の集配送先拠点の距離がＬ１以下かチェックする（１６０９）。条件が成立する場合には、Ｔ［Ｊ］にＧ［Ｉ］の値を代入し、Ｇ［Ｉ］には−１を代入する（１６１０）。次に、変数Ｊに１を加え（１６１１）、Ｉにも１を加え（１６１２）、ステップ１６０８に戻り処理を続ける。ステップ１６０８でＩの値がＮ−１の値を超えた場合には、配列Ｇの中で値が−１の要素を削除して、前方に詰め合わせる（１６１３）。次に、配列Ｔに格納されているＪ個の荷物の集配送先拠点を先頭から順次図７に示した処理手順により配列Ｇの輸送スケジュールの中に追加する（１６１４）。
【００６７】
図１７は結果出力処理（４０３）の詳細を示すフローチャートである。まず、各輸送便の通過拠点を地図上に表示する（１７０１）。次に、輸送スケジュール作成処理によって得られたスケジュールとその所用車両台数や走行距離などの値とともに表やグラフを作成し、表示する（１７０２）。次に印刷指示があればグラフや表を印刷する（１７０３）。
【００６８】
本実施例によれば、物流センターから配送先拠点への荷物と、集配先拠点から物流センターへの荷物を、各集配送先拠点での車両の到着時刻に制約と車両の積載量制約を充足して、効率的な輸送を行う輸送スケジュール作成を行うことができる。
【００６９】
特に、同一拠点への配送と、その拠点からの集荷荷物に、同一の時間帯を指定することで、車両が拠点巡回時に、配送と集荷を同時に行う輸送スケジュールを作成できる。
【００７０】
また、集荷荷物の集荷指定時間帯と配送荷物の配送指定時間帯の指定が異なる場合には、配送先を巡回して、荷物の配送を行った後に、配送経路を逆順で走行して集荷を行う行き帰り対称型の輸送ルートを用いた輸送スケジュールを作成することができる。
【発明の効果】
以上説明したように、本発明によれば、物流センターから配送先拠点への荷物と、集配先拠点から物流センターへの荷物を、各集配送先拠点での車両の到着時刻に制約と車両の積載量制約を充足して、効率的な輸送を行う輸送スケジュール作成を行うことができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明のシステム構成を示すブロック図である。
【図２】記憶装置に含まれるデータの構成を示す図である。
【図３】記憶装置に含まれる輸送スケジュールデータの構成を示す図である。
【図４】全体的な処理の流れを示すフローチャートである。
【図５】入力処理を示すフローチャートである。
【図６】輸送スケジュール作成処理を示すフローチャートである。
【図７】輸送スケジュール作成で用いる、輸送スケジュールへの荷物の集配送先拠点の追加処理のフローチャートである。
【図８】物流センターからの配送荷物と、物流センターに輸送する集荷荷物のペア追加処理のフローチャートである。
【図９】配送荷物か集荷荷物を単独で輸送スケジュールに追加する単独追加処理のフローチャートである。
【図１０】配送荷物と集荷荷物のペア追加の可否チェック処理のフローチャートである。
【図１１】荷物追加チェック処理のフローチャートである。
【図１２】荷物追加位置判定処理のフローチャートである。
【図１３】初期集団生成処理のフローチャートである。
【図１４】遺伝的処理の概要を示すフローチャートである。。
【図１５】交差処理を示すフローチャートである。
【図１６】突然変異処理を示すフローチャートである。
【図１７】結果出力処理を示すフローチャートである。
【符号の説明】
１０１…入力装置、１０２…出力装置、１０３…表示装置、１０４…処理装置、１０５…プログラム、１０６…入力処理部、１０７…輸送スケジュール作成部、１０８…結果出力部、１０９…記憶装置、１１０…拠点情報、１１１…荷物情報、１１２…輸送車両情報、１１３…距離テーブル、１１４…道路地図、１１５…輸送スケジュール情報、１１６…遺伝子情報、１１７…車両管理情報。
【図１】
2004001975.tif 000003
【図２】
2004001975.tif 000004
【図３】
2004001975.tif 000005
【図４】
2004001975.tif 000006
【図５】
2004001975.tif 000007
【図６】
2004001975.tif 000008
【図７】
2004001975.tif 000009
【図８】
2004001975.tif 000010
【図９】
2004001975.tif 000011
【図１０】
2004001975.tif 000012
【図１１】
2004001975.tif 000013
【図１２】
2004001975.tif 000014
【図１３】
2004001975.tif 000015
【図１４】
2004001975.tif 000016
【図１５】
2004001975.tif 000017
【図１６】
2004001975.tif 000018
【図１７】
2004001975.tif 000019