【０００１】
【発明の属する技術分野】
本発明は、物流分野におけるスケジューリング作成を計算機で行う方法および装置、システム、プログラムに関するものであり、具体的には計算機を利用した物流計画の作成方法に関するものである。
【０００２】
【従来の技術】
物流システムでの、輸送スケジュール作成技術としては、いわゆる巡回セールスマン問題やビークルルーティング問題に相当する一定地域内に存在する顧客先の効率的な巡回計画を作成する技術はすでに開発されている（特開平５−１３５０７０号公報「配送スケジューリング装置」）。
【０００３】
例えば、特開平１０−１２４５８８号公報「地理情報に基づくスケジュール作成装置」は地理情報と共に、顧客先間の最短経路決定にニューラルネットを用いることで、最適なスケジュール作成を行っている。
【０００４】
また、特開平８−１１５４９５号公報「自動配車装置」では、多数の配送先をクラスタリングして、各クラスター内で輸送ルートを作成する方式を実現している。
【０００５】
更に、特開平９−３０５６６９号公報「配送計画方法と装置」は、トラックの積載量制約と稼働時間制約を守った上で効率的な配車計画を作成するために、いわゆるスウィープ法（増井忠幸他著「ロジスティクスのＯＲ」槇書店 １９９８年）に基づく技法を用いている。
【０００６】
更に、小規模な輸送ルートを高速に作成する方法として、２ｏｐｔ法やＬＫ法などのアルゴリズムも開発されてきている（茨木俊秀「離散最適化法とアルゴリズム」岩波書店 １９９３年）。
【０００７】
【特許文献１】
特開平５−１３５０７０号公報
【特許文献２】
特開平１０−１２４５８８号公報
【特許文献３】
特開平８−１１５４９５号公報
【特許文献４】
特開平９−３０５６６９号公報
【非特許文献１】
増井忠幸他著「ロジスティクスのＯＲ」槇書店 １９９８年
【非特許文献２】
茨木俊秀「離散最適化法とアルゴリズム」岩波書店 １９９３年
【０００８】
【発明が解決しようとする課題】
トラック輸送などを対象とした物流のスケジュール作成は、一般にトラックなどの機材や物流センターなどの設備利用効率の向上や運用に関わる人員の業務効率向上を通して物流コストの削減を目的としている。また、サプライチェーンマネージメントと進展に伴い、ジャスト・イン・タイムでの輸送も求められている。更に、実際のトラックの運用を考えると、スケジュール作成時には、トラックの運行エリアや、利用車種の制限、利用車庫など様々な制約条件を考慮しなければならない。
【０００９】
また、実際の運用では、顧客からの受注や、トラックや物流センターの要員の確保にも時間的余裕が必要なため、スケジュール作成に要する時間も限られている。このため、輸送車両のスケジュール作成を自動化するためには、単にスケジュールの最適性だけでなく、実用的な応答性能も要求される。
【００１０】
しかし、物流スケジュールの作成は、数学的には巡回セールスマン問題やビークルルーティング問題に分類される問題であり、実用的な処理時間内に厳密解を求めることが不可能である。従って、高精度の近似解法が必要とされる。
【００１１】
しかしながら、単純なスィープ法やセービング法などの近似解法では、最適解から数十％誤差を含む解が生成されることもあり、実用化は困難である。このため、タブーサーチやＳＡ（Ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ）法、ＧＡ（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ：遺伝的アルゴリズム）などの最適化技法を適用した解法が提案されている。
【００１２】
これらの技法を適用しても、先に記したような制約条件がある場合には、スケジュール作成時に、これら多数の制約条件のチェックが必要となり、応答性能上の問題が発生する。
【００１３】
【課題を解決するための手段】
上記問題を解決するために、請求項１に関わる発明は、少なくとも入出力装置と処理装置と記憶装置を有し、物流センターから輸送先拠点への荷物輸送を行う複数車両の、各車両への輸送担当荷物の割当と、各車両の輸送ルートを作成する輸送スケジュール作成システムであって、物流センターや、輸送先などの拠点の位置情報を入力する拠点情報登録ステップと、各荷物の荷物量、輸送先拠点・配送時間制約を含む荷物情報を入力する荷物情報登録ステップと、トラックなどの輸送車両の積載量限界などを含む輸送車両情報を入力する輸送便情報登録ステップと、同一車両で巡回可能な輸送拠点を入力する輸送エリア情報登録ステップと、拠点の地理的位置や各拠点の輸送時間制約などの制約条件を解析し、同一車両での巡回が不可能な荷物の情報を示す排他荷物情報を生成する制約条件解析ステップと、これらの情報からトラックなどの輸送車両の輸送スケジュールを作成する輸送スケジュール作成ステップと、作成した輸送スケジュールを出力するスケジュール出力ステップとを備えた輸送スケジュール作成方法であり、輸送スケジュール作成スッテプは、ＧＡ（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ：遺伝的アルゴリズム）を用い、つまり、輸送スケジュールを複数生成する初期集団作成ステップと、その初期スケジュール集団を突然変異及び交差処理等の遺伝的操作を適用して改良するスケジュール改良スッテプからなり、更に、初期集団作成ステップとスケジュール改良ステップにおいて、各車両への荷物割当時に制約条件解析ステップにおいて作成された排他荷物情報を参照して、同一車両に積載可能な荷物を決定することを特徴とする。
【００１４】
請求項２に係る発明は、請求項１記載の輸送スケジュール作成ステップに適用した遺伝的アルゴリズムにおいて、輸送対象の荷物を一意に識別するＩＤを設け、そのＩＤを輸送に利用する車両の巡回順序で一次元に並べた遺伝子構造を用い、その交差処理においてはランダムに二つの遺伝子を選択して、その交差位置を決め、一方の遺伝子の交差位置よりも前に記録されている輸送スケジュールと、その輸送スケジュールに含まれていない荷物を、もう一方の遺伝子中に現れる順序に従って、先の一方の遺伝子の交差位置よりも前方の輸送スケジュールに含まれている車両のルートへＮＩ法（Ｎｅａｒｅｓｔ Ｉｎｓｅｒｔｉｏｎ Ｍｅｔｈｏｄ：最近隣挿入法）で追加した場合の、その輸送車両の距離の増分が、その輸送車両の、その荷物追加前の走行距離の一定割合を越えない場合にだけ追加し、追加できない荷物は、他の追加可能な荷物の追加処理の後に、再度、その時点の輸送スケジュールに含まれている輸送車両のルートへＮＩ法を用いて追加し、制約条件を満足する輸送車両がない場合には輸送車両のスケジュールへの追加を行うことを特徴とする。
【００１５】
請求項３に係る発明は、請求項１記載の輸送スケジュール作成ステップに適用した遺伝的アルゴリズムの突然変異操作において、ランダムに選択した遺伝子に記録されている一つの荷物を選択し、その荷物の輸送先拠点および、更にランダム距離を一つ選択して、先に選択した輸送先拠点から、その距離以内の集配送先の荷物を、遺伝子から削除し、これら荷物を輸送スケジュールに含まれている輸送車両のルートへＮＩ法（Ｎｅａｒｅｓｔ Ｉｎｓｅｒｔｉｏｎ Ｍｅｔｈｏｄ：最近隣挿入法）で追加した場合に、その輸送車両の走行距離の増分が、その輸送車両の元の走行距離の一定割合を越えない場合にだけ再度追加し、追加できない荷物は、他の追加可能な荷物の追加処理の後に、再度、その時点で、輸送スケジュールに含まれている輸送車両のルートへＮＩ法を用いて追加し、制約条件を満足する輸送車両がない場合には輸送車両のスケジュールへの追加を行うことを特徴とする。
【００１６】
【発明の実施の形態】
以下、本発明の一実施例を図面を用いて説明する。
【００１７】
本実施形態では、輸送は物流センターに所属する複数台の輸送車両（トラック等）が物流センターを出発して、複数の輸送先拠点への荷物を行うスケジュールの作成を想定している。この実施例は、荷物の配送を想定しているが、当然複数の拠点から物流センターに荷物を集める、集荷スケジュールの作成にも適用できるものである。
【００１８】
図１は、本発明のシステムの構成図である。
【００１９】
本システムは、入力装置（１０１）、プリンタなどの出力装置（１０２）、ディスプレイなどの表示装置（１０３）、処理装置（１０４）、記憶装置（１０５）を備える。
【００２０】
処理装置（１０４）は、入力処理部（１０７）、制約条件解析処理部（１０８）、輸送スケジュール作成部（１０９）および結果出力部（１１０）を含む一連のプログラム（１０６）を実行する。
【００２１】
また、記憶装置（１０５）には、拠点情報（１１１）、荷物情報（１１２）、輸送車両情報（１１３）、輸送エリア定義情報（１１４）、距離テーブル（１１５）、道路地図（１１６）、排荷物情報（１１７）及び、これらから作成される。輸送ルート情報（１１８）が格納される。また、輸送ルート作成に用いる、遺伝子情報（１１９）及び車両管理情報（１２０）も格納される。
【００２２】
図２は図１の記憶装置（１０５）に格納される拠点情報（１１１）の一例を示している。
【００２３】
拠点情報（１１１）には、物流センターや荷物の集配送先拠点の位置情報を格納する。具体的には、物流センターや輸送先拠点を一意に識別する拠点ＩＤ（２０１）、拠点の名称（２０２）、拠点の住所（２０３）、拠点の位置を示す緯度（２０４）と経度（２０５）等が格納される。
【００２４】
図３は図１の記憶装置（１０５）に格納される荷物情報（１１２）の一例を示している。
【００２５】
荷物情報（１１２）には、輸送の対象となる各荷物に関する情報を格納する。具体的には、個々の荷物に１から順次付与した荷物インデックス（３０１）、荷物を一意に識別する荷物ＩＤ（３０２）、物流センターから配送先に送る荷物か、荷物の輸送先を示す拠点ＩＤ（３０３）、荷量（３０４）、その輸送先への車両の到着指定時間帯を示す時間制約（３０５）からなる。
【００２６】
図４は図１の記憶装置（１０５）に格納される輸送車両情報（１１３）の一例を示している。
【００２７】
輸送車両情報（１１３）には、利用可能な車両の積載重量に関する能力や限界、また、車両の稼働時間についての情報を格納する。具体的には、輸送車両情報には、車両を一意に識別するために１から順次付与した車両Ｎｏ（４０１）、その種類の車両の積載重量限界値（４０２）、および、その車両の物流センターからの出発時間（４０３）と配送業務を終える終了時間（４０４）からなる。
【００２８】
図５は図１の記憶装置（１０５）に格納される輸送エリア定義情報（１１４）の一例を示している。
【００２９】
エリア定義情報（１１４）には、各拠点のエリアＩＤを登録する。このエリアＩＤが同一であることは、同一のエリアＩＤを付与された拠点は、同一の輸送車両で巡回が可能であることを表す。つまり、輸送スケジュール作成時に、異なるエリアＩＤを有する拠点の荷物は同一の輸送車両には割当てない。
【００３０】
具体的には、エリア定義情報には、拠点ＩＤ（５０１）と、そのエリアＩＤ（５０２）を登録する。また、本実施例では、このエリア定義情報に登録されていない拠点は、どのエリアを巡回する輸送車両でも輸送可能として扱う。
【００３１】
図６は図１の記憶装置（１０５）に格納される排他荷物情報（１１７）の一例を示している。
【００３２】
排他荷物情報（１１７）は、制約条件解析処理部（１０８）により、輸送先拠点の地理的位置や輸送時間制約等の制約条件を解析し、同一車両での輸送が不可能な荷物の情報が設定されている。つまり、荷物インデックスがＩとＪの荷物が同一車両に混載して輸送ができない場合には、この排他荷物情報を表すテーブルの（Ｉ，Ｊ）要素と（Ｊ，Ｉ）要素には１を設定する。それ以外の要素には０を設定する。
【００３３】
図７は図１の記憶装置（１０５）に格納される距離テーブル（１１５）の一例を示している。
【００３４】
距離テーブル（１１７）には、二つの拠点のＩＤ（７０１と７０２）及び、その拠点ＩＤ１（７０１）から拠点ＩＤ２（７０２）への輸送車両による走行距離（７０３）及び走行所要時間（７０４）を格納する。
【００３５】
図８は図１の記憶装置（１０５）に格納される輸送ルート情報（１１８）の一例を示している。
【００３６】
輸送ルート情報（１１８）は、本発明に係わる方法によって作成される輸送スケジュールで車両が巡回する拠点と、その車両の巡回順序を示す情報を格納する。具体的には車両Ｎｏ（８０１）、車両の巡回拠点数（８０２）、や輸送先拠点の拠点ＩＤ（８０３）と、その拠点への到着時間（８０４）、その拠点との輸送を行う荷物のインデックス（８０５）を格納する。また、合計荷物量（８１０）や総走行距離（８１１）を格納する。
【００３７】
図９の遺伝子情報（１１６）は輸送スケジュール作成部（１０９）で用いる遺伝的アルゴリズムによる輸送スケジュール作成で用いる遺伝子表現の一例を示している。遺伝子には、トラックなどの輸送車両で配送する荷物の荷物インデックス（９０１）がそれぞれ格納される。
【００３８】
車両管理情報（１２０）には、輸送スケジュール作成部（１０９）で用いる遺伝子情報（１１９）の車両への対応関係を示す情報を格納する。遺伝子情報（１１９）は、単に荷物インデックスを一次元に並べた配列であり、どの荷物がどの車両に積載されているかは記録されていない。この車両管理情報には、各車両に積載される荷物が、遺伝子情報のどの部分に対応しているかを示すために、以下の情報を車両毎に格納する。つまり車両を一意に識別する車両Ｎｏ（９０４）、その車両に積載する荷物の遺伝子上での開始位置を示す遺伝子開始位置（９０５）、終了位置を示す遺伝子終了位置（９０６）からなる。
【００３９】
図１０は、図１中の処理装置（１０４）が実行するプログラム（１０６）の概要を示すフローチャートである。まず入力処理ステップ（１００１）で、拠点情報（１１１）、荷物情報（１１２）、輸送車両情報（１１３）、輸送エリア定義情報（１１４）等の輸送計画を作成するために必要な情報をユーザが入力する。この処理の詳細は図１１に後述する。次の制約条件解析処理（１００２）では、輸送先拠点の地理的位置や輸送時間制約等の制約条件を解析し、排他荷物情報（１１７）を生成する。この処理の詳細は、図１２に後述する。次の輸送スケジュール作成ステップ（１００３）では、入力処理ステップ（１００１）によって得られた情報から、最適と考えられる輸送計画を決定する。ここで輸送計画の決定とは、入力された全ての荷物を配送先に届けることが可能なトラックが従うべき荷物のトラックへの割り当てとスケジュール（輸送スケジュール情報）を決定することを指す。この処理の詳細は図１３に後述する。次に、結果出力処理ステップ（１００４）では、作成したスケジュールを、その評価とともに出力する。この処理の詳細は図２３で後述する。
【００４０】
図１１は、図１０中の入力処理ステップ（１００１）の詳細を示すフローチャートである。まず、拠点情報登録ステップ（１１０１）で、拠点情報（１１１）の登録を行う。次に、荷物情報登録ステップ（１００２）で、荷物情報（１１２）の登録を行う。次に輸送車両情報登録ステップ（５０４）で、輸送車両情報 （１１３）の登録を行う。次に輸送エリア登録処理（１１０４）で、輸送エリア定義情報（１１４）の登録を行う。次に距離テーブル生成処理（１１０５）で拠点間の距離とトラックによる走行所要時間を道路地図（１１６）を参照して生成する。なお、道路地図（１１６）はカーナビゲーションで利用されるような道路及びその道路間の接続関係や距離情報が格納されているものが予め用意されているものとする。
【００４１】
図１２は図１０中の制約条件解析処理（１００２）の詳細を示すフローチャートである。ここでは、各拠点の地理的条件や、荷物毎に指定されている時間制約を解析して、同一車両に混載して輸送できない荷物を決定し、排他荷物情報（１１７）を生成する。こ具体的には、まず、排他荷物情報を初期化する（１２０１）。つまり、二次元配列である排他荷物情報の全要素に０を代入する。以下、排他荷物情報は二次元配列ＸＬ［Ｉ，Ｊ］と記述する。次に、二つの荷物を同一車両に混載した場合に、制約違反が生ずるか否かを以下の処理により判定する。
【００４２】
まず、変数Ｉに１を代入する（１２０２）。次にＩの値と荷物情報に登録されている荷物数を表す変数Ｌ＿ＭＡＸを比較する（１２０３）。ＩがＬ＿ＭＡＸよりも大きい場合には処理を終える、ＩがＬ＿ＭＡＸ以下の場合には、以下の処理を行う。まず、変数ＪにＩ＋１を代入する（１２０４）。次に、ＪとＬ＿ＭＡＸを比較する（１２０５）。もしＪがＬ＿ＭＡＸよりも大きければ、ステップ１２２０に進み、変数Ｉに１を加え（１２２０）、次ステップ１２０３に戻り処理を繰り返す。
【００４３】
ステップ１２０５でＪがＬ以下ならば、荷物情報（１１２）の荷物インデックス（３０１）がＩとＪの荷物の同一車両への混載が制約条件違反を生じるか否かを判定するために以下の処理を行う。
【００４４】
まず、荷物ＩとＪの荷物の輸送先拠点の輸送エリア定義に登録されているエリアＩＤが異なっているかチェックする（１２０６）。もし、二つの拠点共にエリアＩＤが登録されていて、両者のエリアＩＤが異なる場合にだけこの条件は成立する。本実施例では、少なくとも片方の拠点のエリアＩＤが登録されていない場合には、そのエリア情報が登録されていない拠点は、他のエリアＩＤの拠点を巡回する輸送車両の荷物と混載可能であるとしているので、上記以外の場合には条件は成立しない。
【００４５】
次に、二つの拠点を巡回する車両が、車両の走行時間上限内で走行可能か判定する。つまり、変数Ｄ１に物流センターと荷物Ｉの輸送先拠点の走行所要時間を距離テーブルを参照して代入する（１２０７）。次に、変数Ｄ１にセンターと荷物Ｊの輸送先拠点の走行所要時間を同じようにして代入する（１２０８）。次に、変数Ｄ３に荷物Ｉと荷物Ｊの輸送先拠点間の走行所要時間を同じようにして代入する（１２０９）。次に、変数ＤにＤ１とＤ２とＤ３の和を代入する（１２１０）。次に、変数Ｄの値とトラックの走行時間上限を比較する（１２１１）。Ｄがトラック走行時間上限を超過している場合には（ステップ１２１１でＮｏの場合）、排他情報テーブルの（Ｉ，Ｊ）要素と（Ｊ，Ｉ）要素に１を代入し（１２１７，１２１８）して、次の荷物の組合せに移る。
【００４６】
ステップ１２１１の判定でＹｅｓの場合には、二つの荷物がそれぞれの輸送指定時間枠内に輸送可能か調べるために以下の処理を行う。まず変数ＢＩに荷物Ｉの輸送指定時間枠の開始時刻を代入する（１２１２）。
【００４７】
次に、変数ＥＩに荷物Ｉの輸送指定時間枠の終了時刻を代入する（１２１３）。次に、変数ＢＪに荷物Ｊの輸送指定時間枠の開始時刻を代入する（１２１４）。次に、変数ＥＪに荷物Ｊの輸送指定時間枠の終了時刻を代入する（１２１５）。
【００４８】
次に、Ｄ３が（ＥＪ−ＢＩ）以下またはＤ３が（ＥＩ−ＢＪ）以下かチェックする（１２１６）。条件が成立しない場合には、ステップ１２１７，１２１８で排他荷物情報の（Ｉ，Ｊ）及び（Ｊ，Ｉ）要素に１を設定する。ステップ１２１６で条件が成立した場合には、荷物Ｉと荷物Ｊは時間制約からだけでは同一車両での輸送が不可能とは判定できないので、排他荷物情報の（Ｉ，Ｊ）及び（Ｊ，Ｉ）要素は０のまま、次の処理に移る。
【００４９】
次に、変数Ｊに１を加え（１２１９）ステップ１２０５に戻る。ステップ１２０５の判定結果がＹｅｓの場合にはステップ１２２０に進み変数Ｉに１を加えステップ１２０３に戻る。
【００５０】
図１３は、図１０中の輸送スケジュール作成処理（１００３）の詳細を示すフローチャートである。このスケジュール作成処理は、ＧＡ（遺伝的アルゴリズム）に従っている。まず、ランダム性を含んだ方法によって、それぞれが異なる初期解集団を作成する（１３０１）。この処理の詳細は図１９に後述する。次に、変数Ｉに１を代入する（１３０２）。次に遺伝的処理による解集団の改良を行う（１３０３）。この処理の詳細は図２０で後述する。（１３０３）の処理によって、解集団の少なくとも一部分は変化し、（１３０３）〜（１３０５）の処理の繰り返しによって解集団は徐々に最適な解へ近づいて行く。（１３０２）の処理の後、集団の評価を行う（１３０４）。評価はルート情報から算出される車両の走行距離や利用車両台数などさまざまな要素に対し行われ、その結果によって解集団中の個々の解に対して順位がつけられる。この評価結果が上位の解を、次世代の解として選択する（１３０５）。次に変数Ｉに１を加える（１３０６）。
【００５１】
Ｉが予め設定されているＧＡの処理世代数Ｇ＿ＭＡＸを越えるか、次世代の集団中の最良解の評価値が予め与えられている目標値よりも良いかチェックする（１３０７）。もし条件が成立すれば、現在の解集団で最良の解を出力して（１３０８）処理を終える。ステップ１３０７で条件が成立しなければ、ステップ１３０３に戻り遺伝的処理による解集団の改良を繰り返す。
【００５２】
図１４は、図１３の遺伝的アルゴリズムを用いた輸送スケジュール作成処理の初期解集団の作成（１３０１）、解集団の改良処理（１３０３）で用いる荷物の輸送スケジュールへの荷物の追加処理の詳細を示すフローチャートである。この処理は、複数台の輸送車両からなる輸送スケジュールに、一つの荷物の集配送を追加する処理である。
【００５３】
配列Ｌに、追加する荷物の荷物インデックスが登録されているとする。また、配列Ｌに登録されている荷物数は変数Ｌ＿ＭＡＸに登録されているとする。まず、変数Ｉに１を代入する（１４０１）。次にＩとＬ＿ＭＡＸを比較する（１４０２）。ＩがＬ＿ＭＡＸ以下の場合（１４０２でＮｏの場合）には、以下の処理を行う。まず荷物Ｌ［Ｉ］を輸送可能な車両があるかチェックする（１４０３）。この処理の詳細は図１５で説明する。ステップ１４０３の処理で、輸送可能な車両がある場合には、荷物Ｌ［Ｉ］をその車両に追加し（１４０５）、Ｌ［Ｉ］に−１を代入して（１４０６）、変数Ｉに１を加え（１４０７）、ステップ１４０２に戻り次の荷物の処理に移る。ステップ１４０４でＮｏの場合には、ステップ１４０７に移る。
【００５４】
ステップ１４０２の判定がＹｅｓの場合には、ステップ１４０８に移り、変数Ｉに１を代入する。
【００５５】
次に、変数ＩとＬ＿ＭＡＸの値を比較する（１４０９）。ＩがＬ＿ＭＡＸより大きい場合には、処理を終える。ＩがＬ＿ＭＡＸ以下の場合には以下の処理を行う。
【００５６】
まず、Ｌ［Ｉ］が−１と等しいかチェックする（１４１０）。等しい場合には、Ｌ［Ｉ］は既に車両への割当て済みなのでステップ１４１５に進み変数Ｉに１を加え次の荷物の処理に移る。
【００５７】
ステップ１４１０でＬ［Ｉ］が−１と等しくない場合には、次の処理を行う。
【００５８】
まず、荷物Ｌ［Ｉ］を輸送可能な車両があるかチェックする（１４１１）。この処理の詳細は図１６で説明する。
【００５９】
もし追加可能な車両があれば、その車両に荷物Ｌ［Ｉ］を追加する（１４１３）。追加可能な車両が無い場合には、新たな車両を、荷物Ｌ［Ｉ］の輸送用に割当てる（１４１４）。次に、変数Ｉに１を加え（１４１５）、ステップ１４０９に戻り、次の荷物の処理に移る。
【００６０】
図１５は図１４中のステップ１４０３の処理の詳細を示すフローチャートである。
【００６１】
この処理では、追加対象の荷物を積載可能な輸送車両を探索し、もしある場合には変数Ｔｒｕｃｋにその車両の番号及び荷物の積載位置を変数Ｐに代入する。もし無い場合にはＰには−１が設定される。
【００６２】
Ｍａｘ＿Ｔｒｕｃｋには、既に荷物の輸送を割当て済みの輸送車両数が設定されているものとする。
【００６３】
まず、変数Ｋに１を代入し、変数Ｄには、利用する計算機で表現できる最大の整数Ｍａｘ＿Ｖａｌｕｅを設定し、変数ＴｒｕｃｋとＰには−１を設定する（１５０１）。次に、変数ＫとＭａｘ＿Ｔｒｕｃｋの値を比較する（１５０２）。もしＫがＭａｘ＿Ｔｒｕｃｋよりも大きければ、処理を終える。
【００６４】
ＫがＭａｘ＿Ｔｒｕｃｋ以下の場合には、次の処理を行う。まず、Ｋ番目の輸送車両に荷物の追加が可能か否かをチェックする（１５０３）。この処理の詳細は図１７に後述する。追加可能な場合には、ステップ１５０３の処理で設定される、その車両の運行時間の増分Ｄ＿ＭＩＮと変数Ｄの値を比較する（１５０５）。もしＤが大きければ、ＤにはＤ＿ＭＩＮの値を代入し、ＴｒｕｃｋにはＫ、ＰにはＰｏｓを代入する（１５０６）。変数Ｄ＿ＭＩＮ及びＰｏｓにはステップ１５０３の処理で値が設定される。ＤがＤ＿ＭＩＮ以下ならば、ステップ１５０７に移り次の車両のチェックを行う。
【００６５】
図１６は図１４中のステップ１４１１の処理の詳細を示すフローチャートである。
【００６６】
この処理では、追加対象の荷物を積載可能な輸送車両を探索し、もしある場合には変数Ｔｒｕｃｋにその車両の番号及び荷物の積載位置を変数Ｐに代入する。もし無い場合にはＰには−１が設定される。
【００６７】
Ｍａｘ＿Ｔｒｕｃｋには、既に荷物の輸送を割当て済みの輸送車両数が設定されているものとする。
【００６８】
まず、変数Ｋに１を代入し、変数Ｄには、利用する計算機で表現できる最大の整数Ｍａｘ＿Ｖａｌｕｅを設定し、変数ＴｒｕｃｋとＰには−１を設定する（１６０１）。次に、変数ＫとＭａｘ＿Ｔｒｕｃｋの値を比較する（１６０２）。もしＫがＭａｘ＿Ｔｒｕｃｋよりも大きければ、処理を終える。
【００６９】
ＫがＭａｘ＿Ｔｒｕｃｋ以下の場合には、次の処理を行う。まず、Ｋ番目の輸送車両に荷物の追加が可能か否かをチェックする（１６０３）。この処理の詳細は図１８に後述する。追加可能な場合には、ステップ１６０３の処理で設定される、その車両の運行時間の増分Ｄ＿ＭＩＮと変数Ｄの値を比較する（１６０５）。もしＤが大きければ、ＤにはＤ＿ＭＩＮの値を代入し、ＴｒｕｃｋにはＫ、ＰにはＰｏｓを代入する（１６０６）。変数Ｄ＿ＭＩＮ及びＰｏｓにはステップ１６０３の処理で値が設定される。ＤがＤ＿ＭＩＮ以下ならば、ステップ１６０７に移り次の車両のチェックを行う。
【００７０】
図１７は、図１５のフロー図中のステップ１５０３の詳細を示すフローである。
【００７１】
この処理では、スケジュールに追加する荷物の荷物インデックスを変数Ｌに代入してあるものとする。また、荷物Ｌが追加可能か判定する対象の車両番号が設定されているとする。この処理が終わると、荷物Ｌの輸送が車両Ｔ＿Ｎｏで可能であった場合には、変数Ｐｏｓに追加位置が設定され、Ｄ＿ＭＩＮに、その荷物の追加による車両の走行時間の増分値が設定される。追加できなかった場合には、Ｐｏｓには−１、Ｄ＿ＭＩＮにはＭａｘ＿Ｖａｌｕｅが設定される。変数まず、変数Ｚに荷物Ｌの輸送先拠点のＩＤを代入する（１７０１）。次に、変数Ｖに荷物Ｌの荷量を代入する（１７０２）。次に変数Ｐｏｓに−１を、Ｄ＿ＭＩＮに利用する計算機で表現可能な最大数（Ｍａｘ＿Ｖａｌｕｅと表記する）を設定する（１７０３）。次に変数Ｉに車両管理情報（１２０）を参照して、Ｔ＿Ｎｏ番目の車両の遺伝子開始位置を設定する（１７０４）。次に変数ＴＨにＴ＿Ｎｏ番目のの車両の総走行時間を代入する（１７０５）。次に、荷物ＬとＴ＿Ｎｏ番目の車両に積載されている荷物が同一車両で輸送不可能でないかを排他荷物情報を参照して判定する（１７０６）。つまり、荷物ＬとＴ＿Ｎｏ番目の車両に積載されている荷物の荷物インデックスを用いて、二次元配列である排他荷物情報を参照して、その要素が１の場合には同一車両では輸送できないと判定する。ステップ１７０６のチェックで載せあわせが不可能と判定された場合には、処理を終える（１７０７）。それ以外の場合には、以下の処理を行う。
【００７２】
次に、変数Ｉの値と、その車両の遺伝子終了位置＋１の値を比較する（１７０８）。Ｉが大きい場合には、処理を終える。Ｉが前記の値を超えていない場合には、次の処理を行う。
【００７３】
まず、ＩがＴ＿Ｎｏ番目の車両の遺伝子開始位置と比較する（１７０９）。等しい場合には、変数Ｘには車両が出発する物流センターを表す拠点ＩＤを代入する（１７１１）。等しくない場合には、その車両の遺伝子情報中の（Ｉ−１）番目の荷物の集配送先の拠点ＩＤを代入する（１７１０）。次に、ＩとＴ＿Ｎｏ番目の車両の遺伝子終了位置＋１の値と比較する。もし等しければ、変数Ｙには物流センターの拠点ＩＤを代入する（１７１４）。等しくない場合には、ＹにＴ＿Ｎｏ番目の車両のＩ番目の荷物の集配送先拠点のＩＤを代入する（１７１３）。
【００７４】
次に、荷量Ｖの荷物Ｌを、Ｉ番目の車両のＸ番目の輸送荷物とＹ番目の輸送荷物の間に積載可能かチェックする（１７１５）。つまり、追加対象荷物が、配送荷物の場合には、車両が出発する物流センターから、Ｘ番目の輸送荷物の集配送先拠点までの間で、その車両の荷量にＬを加えた値が、その車両の最大積載量を超過しないかチェックする。また、その荷物が集荷荷物の場合には、その車両のＹ番目の荷物の集配送先拠点から、物流センターに戻るまでの間の各集配送先拠点での積載荷量にＬを加えた値が、その車両の最大積載量を超過していないかをチェックする。
【００７５】
次にＴ＿ＤｅｌｔａにＸとＺ間の所要時間と、ＺとＹ間の所要時間の和からＸとＹ間の所要時間を差し引いた値を代入する（１７１６）。次に、その車両のＹ以降の荷物の輸送で巡回する集配送先の車両到着時間にＤｅｌｔａ＿Ｔを加えた値が、時間制約を破らないかチェックする（１７１７）。図１７ではＴＩＭＥ（Ｘ，Ｙ）で拠点ＸからＹへの車両の走行所用時間を表している。次に、Ｔ＿ＤｅｌｔａがＴＨの０．２５倍を超えていないかチェックする（１７１８）。超えている場合には、処理を終える。超えていない場合には、以下の処理を行う。
【００７６】
次Ｄ＿ＭＩＮとＴ＿Ｄｅｌｔａを比較する（１７１９）。Ｔ＿Ｄｅｌｔａが小さければ、Ｄ＿ＭＩＮにＴ＿Ｄｅｌｔａの値を代入し、ＰｏｓにＩの値を代入する（１７２０）。
【００７７】
次に、Ｉに１を加え（１７２１）、ステップ１７０８に戻り次の追加位置のチェックに移る。
【００７８】
図１８は、図１６のフロー図中のステップ１６０３の詳細を示すフローである。
【００７９】
この処理では、スケジュールに追加する荷物の荷物インデックスを変数Ｌに代入してあるものとする。また、荷物Ｌが追加可能か判定する対象の車両番号が設定されているとする。この処理が終わると、荷物Ｌの輸送が車両Ｔ＿Ｎｏで可能であった場合には、変数Ｐｏｓに追加位置が設定され、Ｄ＿ＭＩＮに、その荷物の追加による車両の走行時間の増分値が設定される。追加できなかった場合には、Ｐｏｓには−１、Ｄ＿ＭＩＮにはＭａｘ＿Ｖａｌｕｅが設定される。変数まず、変数Ｚに荷物Ｌの輸送先拠点のＩＤを代入する（１８０１）。次に、変数Ｖに荷物Ｌの荷量を代入する（１８０２）。次に変数Ｐｏｓに−１を、Ｄ＿ＭＩＮに利用する計算機で表現可能な最大数（Ｍａｘ＿Ｖａｌｕｅと表記する。）を設定する（１８０３）。次に変数Ｉに車両管理情報（１２０）を参照して、Ｔ＿Ｎｏ番目の車両の遺伝子開始位置を設定する（１８０４）。次に、荷物ＬとＴ＿Ｎｏ番目の車両に積載されている荷物が同一車両で輸送不可能でないかを排他荷物情報（）を参照して判定する（１８０５）。つまり、荷物ＬとＴ＿Ｎｏ番目の車両に積載されている荷物の荷物インデックスを用いて、二次元配列である排他荷物情報を参照して、その要素が１の場合には同一車両では輸送できないと判定する。ステップ１８０５のチェックで載せあわせが不可能と判定された場合には、処理を終える（１８０６）。それ以外の場合には、以下の処理を行う。
【００８０】
次に、変数Ｉの値と、その車両の遺伝子終了位置＋１の値を比較する（１８０７）。Ｉが大きい場合には、処理を終える。Ｉが前記の値を超えていない場合には、次の処理を行う。
【００８１】
まず、ＩがＴ＿Ｎｏ番目の車両の遺伝子開始位置と比較する（１８０８）。等しい場合には、変数Ｘには車両が出発する物流センターを表す拠点ＩＤを代入する（１８１０）。等しくない場合には、その車両の遺伝子情報中の（Ｉ−１）番目の荷物の集配送先の拠点ＩＤを代入する（１８０９）。次に、ＩとＴ＿Ｎｏ番目の車両の遺伝子終了位置＋１の値と比較する。もし等しければ、変数Ｙには物流センターの拠点ＩＤを代入する（１８１３）。等しくない場合には、ＹにＴ＿Ｎｏ番目の車両のＩ番目の荷物の集配送先拠点のＩＤを代入する（１８１２）。
【００８２】
次に、荷量Ｖの荷物Ｌを、Ｉ番目の車両のＸ番目の輸送荷物とＹ番目の輸送荷物の間に積載可能かチェックする（１８１４）。つまり、追加対象荷物が、配送荷物の場合には、車両が出発する物流センターから、Ｘ番目の輸送荷物の集配送先拠点までの間で、その車両の荷量にＬを加えた値が、その車両の最大積載量を超過しないかチェックする。また、その荷物が集荷荷物の場合には、その車両のＹ番目の荷物の集配送先拠点から、物流センターに戻るまでの間の各集配送先拠点での積載荷量にＬを加えた値が、その車両の最大積載量を超過していないかをチェックする。
【００８３】
次にＴ＿ＤｅｌｔａにＸとＺ間の所要時間と、ＺとＹ間の所要時間の和からＸとＹ間の所要時間を差し引いた値を代入する（１８１５）。次に、その車両のＹ以降の荷物の輸送で巡回する集配送先の車両到着時間にＤｅｌｔａ＿Ｔを加えた値が、時間制約を破らないかチェックする（１８１６）。図１７ではＴＩＭＥ（Ｘ，Ｙ）で拠点ＸからＹへの車両の走行所用時間を表している。次Ｄ＿ＭＩＮとＴ＿Ｄｅｌｔａを比較する（１８１７）。Ｔ＿Ｄｅｌｔａが小さければ、Ｄ＿ＭＩＮにＴ＿Ｄｅｌｔａの値を代入し、ＰｏｓにＩの値を代入する（１８１８）。
【００８４】
次に、Ｉに１を加え（１８１９）、ステップ１８０７に戻り次の追加位置のチェックに移る。
【００８５】
図１９は図１３中の初期解集団生成処理（１３０１）の詳細を示すフローチャートである。
【００８６】
なお、一つの解には複数の車両の巡回スケジュールが登録されている。また、解集団は複数の解を含んでいる。
【００８７】
変数ＳＩＺＥには、予め初期集団に登録する遺伝子の個体数を設定しておく。また、変数ＬＥＮにはルートに登録される配送先拠点の数を設定しておく。
【００８８】
まず、変数Ｉに０を代入する（１９０１）。次にＩがＳＩＺＥよりも小さい間、（１９０３）から（１９０６）の処理を繰り返してＳＩＺＥで指定された個数の遺伝子を生成する。
【００８９】
まず、各要素に値が設定されていない空の遺伝子を記憶するエリアを生成する（１９０３）。
【００９０】
次に、荷物情報の荷物をランダムな順序に並べかえた配列Ｔを作成する（１９０４）。
【００９１】
次に、空の遺伝子に、配列Ｔに登録した荷物を、この順序で図１４に示した追加手順により順次追加する（１９０５）。
【００９２】
次に変数Ｉに１を加えて（１９０６）次の初期解の作成に移る。
【００９３】
図２０は、図１３中の解集団の改良（１３０３）の詳細を示すフローチャートである。遺伝的処理は、解集団の変化、改良を行うＧＡの中心的な処理である。
【００９４】
まず、変数ＳＩＺＥに解集団に登録されている解の個数を代入する（２００１）。次にＣ＿ＮＵＭにＳＩＺＥに予め設定されている交差率を掛けて、その値を超えない最大整数を代入する（２００２）。次に、変数Ｉに１を代入する。ＩがＣ＿ＮＵＭ以下の場合には、次の処理を繰り返して交差処理を行う（２００４）。
【００９５】
まず、解集団から異なる二つの解（遺伝子）を選択する（２００５）。
【００９６】
次に、選択した二つの解（遺伝子）を元に、交差処理を行い、交差処理で新たに生成された解（遺伝子）を解集団に加える（２００６）。
【００９７】
この交差処理の詳細は、図２１で詳細を説明する。
【００９８】
次に、Ｉに１を加え（２００７）ステップ２００４に戻り次の交差処理に移る。
【００９９】
ステップ２００４でＩがＣ＿ＮＵＭを超過していれば、次に突然変異処理に移る。つまり、変数Ｍ＿ＮＵＭにＳＩＺＥに予め設定されている突然変異率を掛け、その値を超えない最大整数を代入する（２００８）。
【０１００】
次に、変数Ｉに１を代入する（２００９）。
【０１０１】
次に、ＩがＭ＿ＮＵＭの値以下の間、次の処理を繰り返す（２０１０）。
【０１０２】
まず、解集団から、ランダムに一つの解（遺伝子）を選択する（２０１１）。
【０１０３】
次に選択した解に突然変異処理を行い、その解（遺伝子）を解集団に加える（２０１２）。この処理の詳細は図２２で説明する。
【０１０４】
次に変数Ｉから１を加え（２２１３）、ステップ２２１０に戻り処理を続ける。
【０１０５】
図２１は、図２０中の交差処理（２００６）の詳細を示すフローチャートである。
【０１０６】
まず、変数Ｎに各解（遺伝子）に登録されている荷物数を代入する（２１０１）。
【０１０７】
次に、交差対象の二つの解（遺伝子）を配列Ｇ１，Ｇ２にコピーする（２１０２）。次に、交差点を決定するために、２以上Ｎ−１以下の整数をランダムに生成して変数Ｐに代入する（２１０３）。
【０１０８】
次に、Ｇ１のＰ番目以降の荷物データインデックスを削除する（２１０４）。つまり削除対象の要素に−１を代入する。次に変数Ｉに１を代入する（２１０５）。
【０１０９】
次に、ＩがＮ以下の間（２１０６）、次の処理を行う。
【０１１０】
Ｇ２［Ｉ］が配列Ｇ１中には含まれていないかチェックする（２１０７）。もし、含まれていない場合には、その荷物情報を図１４に示した処理手順によりＧ１の輸送スケジュール中に追加する（２１０８）。
【０１１１】
次に、変数Ｉに１を加え（２１０９）、次の処理に移る。
【０１１２】
ステップ２１０７で条件が成立しない場合には、ステップ２１０９に移り次の処理に移る。
【０１１３】
ステップ２１０６でＩがＮを越えれば処理を終える。
【０１１４】
図２２は図２０中の突然変異処理（２０１２）の詳細を示すフローチャートである。
【０１１５】
まず、突然変異処理対象の解（遺伝子）を配列Ｇ［］にコピーする（２２０１）。次に、物流センターから最も遠い集配送先拠点と、物流センターからの距離を変数Ｌに代入する（２２０２）。
【０１１６】
変数Ｒに０と０．３の範囲の実数をランダムに生成して代入する（２２０３）。
【０１１７】
次に、変数Ｌ１に変数Ｌの値とＲの値の積を代入する（２２０４）。
【０１１８】
次に、遺伝子上での突然変異箇所を定めるために、変数Ｐに１以上Ｎ以下の整数をランダムに選択して代入する（２２０５）。
【０１１９】
次に、変数Ｉに０、Ｊに０を代入する（２２０６）。
【０１２０】
変数ＫにはＧ［Ｐ］の値、つまり荷物情報のインデックス値を代入する（２２０７）。
【０１２１】
ＩがＮ以下の間（２２０８）、次の処理を繰り返す。
【０１２２】
インデックスがＫの荷物の集配送先拠点とＧ［Ｉ］の荷物の集配送先拠点の距離がＬ１以下かチェックする（２２０９）。
【０１２３】
条件が成立する場合には、Ｔ［Ｊ］にＧ［Ｉ］の値を代入し、Ｇ［Ｉ］には−１を代入する（２２１０）。
【０１２４】
次に、変数Ｊに１を加え（２２１１）、Ｉにも１を加え（２２１２）、ステップ２２０８に戻り処理を続ける。
【０１２５】
ステップ２２０８でＩの値がＮの値を超えた場合には、配列Ｇの中で値が−１の要素を削除して、前方に詰め合わせる（２２１３）。
【０１２６】
次に、配列Ｔに格納されているＪ個の荷物の集配送先拠点を先頭から順次図７に示した処理手順により配列Ｇの輸送スケジュールの中に追加する（２２１４）。
【０１２７】
図２３は図１０中の結果出力処理（１００４）の詳細を示すフローチャートである。まず各輸送便の通過拠点を地図上に表示する（２３０１）。次に、輸送スケジュール作成処理によって得られたスケジュールとその所用車両台数や走行距離などの値とともに表やグラフを作成し、表示する（２３０２）。次に印刷指示があればグラフや表を印刷する（２７０３）。
【０１２８】
【発明の効果】
以上説明したように、本発明によれば、輸送スケジュール作成時に充足しなければならない、制約条件を事前に解析し、これら制約条件の違反により互いに同一車両では輸送できない二つの荷物の組を予め作成することで、各車両の輸送ルート作成時に、上記の排他的な荷物の組み合わせ発生を回避することで、スケジュール作成時に、同一車両への荷物乗せ合わせの組み合わせを削減することができ、これによりスケジュール作成の応答速度向上を実現できる。更に、ＧＡを適用したスケジュール作成方法において、交差処理や突然変異処理において、作成途上のスケジュールに、荷物追加を行う場合、既存輸送ルートへの荷物輸送の追加による、その輸送ルートの走行距離の増分が、既存ルートの走行距離の一定割合を超過する場合には、その荷物輸送の追加を行わないことで、既存ルートに遠方の輸送先拠点を追加することを抑制することで、輸送車量間の走行距離の差異を減少させると共に、一度全ての荷物輸送先拠点の追加を試みた後、上記条件により追加できなかった荷物だけを再度追加し、この段階で輸送車両が不足した場合に、輸送車両の追加を行うことで、不要な輸送車両の追加を抑制する。
【図面の簡単な説明】
【図１】本発明のシステム構成図である。
【図２】本発明の記憶装置に含まれる拠点情報の構成を示す図である。
【図３】本発明の記憶装置に含まれる荷物情報の構成を示す図である。
【図４】本発明の記憶装置に含まれる輸送車両情報の構成を示す図である。
【図５】本発明の記憶装置に含まれるエリア定義情報の構成を示す図である。
【図６】本発明の記憶装置に含まれる排他荷物情報の構成を示す図である。
【図７】本発明の記憶装置に含まれる距離テーブルの構成を示す図である。
【図８】本発明の記憶装置に含まれる輸送ルート情報の構成を示す図である。
【図９】本発明の記憶装置に含まれる遺伝的アルゴリズムを用いた輸送スケジュール作成に用いる、遺伝子情報の構成を示す図である。
【図１０】本発明の全体的な処理の流れを示すフローチャートである。
【図１１】本発明の入力処理を示すフローチャートである。
【図１２】本発明の制約条件解析処理を示すフローチャートである。
【図１３】本発明の輸送スケジュール作成処理を示すフローチャートである。
【図１４】本発明の輸送スケジュール作成で用いる、輸送スケジュールへの荷物追加処理のフローチャートである。
【図１５】本発明の荷物追加処理で用いる、追加車両チェック１処理のフローチャートである。
【図１６】本発明の荷物追加処理で用いる、追加車両チェック２処理のフローチャートである。
【図１７】本発明の追加車両チェック処理１で用いる、荷物追加チェック処理１のフローチャートである。
【図１８】本発明の追加車両チェック処理２で用いる、荷物追加チェック処理２のフローチャートである。
【図１９】本発明の初期集団生成処理のフローチャートである。
【図２０】本発明の遺伝的処理の概要を示すフローチャートである。
【図２１】本発明の交差処理を示すフローチャートである。
【図２２】本発明の突然変異処理を示すフローチャートである。
【図２３】本発明の結果出力処理を示すフローチャートである。
【符号の説明】
１０１…入力装置、１０２…出力装置、１０３…表示装置、１０４…処理装置、１０５…記憶装置、１０６…プログラム、１０７…入力処理部、１０８…制約条件解析処理部、１０９…輸送スケジュール作成部、１１０…結果出力部、１１１…拠点情報、１１２…荷物情報、１１３…輸送車両情報、１１４・・・距離テーブル、１１５…道路地図、１１６・・・排他荷物情報、１１７…輸送ルート情報、１１８…遺伝子情報、１１９…車両管理情報。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a method, an apparatus, a system, and a program for performing scheduling creation in the physical distribution field using a computer, and more specifically, to a method for creating a physical distribution plan using a computer.
[0002]
[Prior art]
As a transportation schedule creation technology in the logistics system, a technology for creating an efficient patrol plan for customers existing in a certain area corresponding to the so-called traveling salesman problem and vehicle routing problem has already been developed. No. 5-135070, “Distribution Scheduling Device”).
[0003]
For example, Japanese Patent Application Laid-Open No. 10-124588 “Schedule Creation Device Based on Geographic Information” creates an optimal schedule by using a neural network for determining the shortest route between customer customers together with geographic information.
[0004]
Japanese Patent Application Laid-Open No. 8-115495 “Automatic Vehicle Allocation Device” realizes a system in which a large number of delivery destinations are clustered to create a transportation route within each cluster.
[0005]
Further, Japanese Patent Laid-Open No. 9-305669 “Delivery Planning Method and Device” discloses a so-called sweep method (Tadayuki Masui et al.) In order to create an efficient vehicle allocation plan while complying with the load restrictions and operating time restrictions of trucks. The technique based on the book “OR of Logistics” (Tsubaki Shoten 1998) is used.
[0006]
Furthermore, algorithms such as the 2opt method and the LK method have been developed as a method for creating a small transport route at high speed (Toshihide Ibaraki “Discrete Optimization Method and Algorithm” Iwanami Shoten 1993).
[0007]
[Patent Document 1]
JP-A-5-135070
[Patent Document 2]
JP 10-124588 A
[Patent Document 3]
JP-A-8-115495
[Patent Document 4]
JP-A-9-305669
[Non-Patent Document 1]
Tadayuki Masui et al. “OR of Logistics” Tsuji Shoten 1998
[Non-Patent Document 2]
Toshihide Ibaraki “Discrete Optimization Method and Algorithm” Iwanami Shoten 1993
[0008]
[Problems to be solved by the invention]
Logistics schedules for trucking and other purposes are generally aimed at reducing logistics costs by improving equipment utilization efficiency of equipment such as trucks and logistics centers and operational efficiency of personnel involved in operation. With supply chain management and progress, just-in-time transport is also required. Furthermore, considering the actual operation of trucks, when creating a schedule, it is necessary to consider various restrictions such as the truck operating area, restrictions on the type of vehicle used, and garage used.
[0009]
In actual operation, time is also required to create a schedule because it takes time to secure orders from customers and to secure truck and distribution center personnel. For this reason, in order to automate the creation of a transportation vehicle schedule, not only the optimality of the schedule but also a practical response performance is required.
[0010]
However, the creation of a distribution schedule is a problem that is mathematically classified into a traveling salesman problem and a vehicle routing problem, and it is impossible to obtain an exact solution within a practical processing time. Therefore, a highly accurate approximate solution is required.
[0011]
However, an approximate solution such as a simple sweep method or a saving method may generate a solution containing an error of several tens of percent from the optimal solution, and is difficult to put into practical use. For this reason, solutions have been proposed that apply optimization techniques such as tabu search, SA (Simulated Annealing) method, GA (Genetic Algorithm).
[0012]
Even if these techniques are applied, if there are constraints as described above, it is necessary to check many of these constraints when creating a schedule, which causes a problem in response performance.
[0013]
[Means for Solving the Problems]
In order to solve the above-mentioned problem, the invention according to claim 1 includes at least an input / output device, a processing device, and a storage device, and a plurality of vehicles that transport cargo from a distribution center to a transportation destination base to each vehicle. This is a transportation schedule creation system that creates the transportation route of each vehicle by assigning the transportation charge, and the location information registration step for inputting the location information of the logistics center and the location such as the transportation destination, It is possible to travel with the same vehicle, a package information registration step for entering package information including destination locations and delivery time constraints, and a transport information registration step for entering transport vehicle information including the load capacity limit of transport vehicles such as trucks. The transportation area information registration step to enter a proper transportation base and the constraint conditions such as the geographical position of the base and the transportation time restriction of each base are analyzed, and the load that cannot be visited by the same vehicle A constraint condition analysis step for generating exclusive package information indicating the information of the vehicle, a transport schedule creation step for creating a transport schedule for a transport vehicle such as a truck from these pieces of information, and a schedule output step for outputting the created transport schedule The transport schedule creation step uses GA (Genetic Algorithm), that is, the initial population creation step for generating a plurality of transport schedules, and the initial schedule population is mutated and cross-processed. Exclusive package information created in the constraint analysis step when assigning packages to each vehicle in the initial group creation step and schedule improvement step. Reference to, and determines a possible loading luggage same vehicle.
[0014]
According to a second aspect of the present invention, in the genetic algorithm applied to the transportation schedule creation step according to the first aspect, an ID for uniquely identifying a package to be transported is provided, and the ID is used in a traveling order of vehicles used for transportation. Using a gene structure arranged in one dimension, in the crossing process, two genes are selected at random, the crossing position is determined, the transport schedule recorded before the crossing position of one gene, In accordance with the order in which the packages not included in the transport schedule appear in the other gene, the NI method (Nearest Insertion Method: to the route of the vehicle included in the transport schedule ahead of the crossing position of the previous one gene: When added by the nearest neighbor insertion method), the increment of the distance of the transport vehicle is the same as that of the transport vehicle. Baggage that can only be added if it does not exceed a certain percentage of the previous mileage, and can not be added, is added again to the route of the transport vehicle included in the current transport schedule after adding other available baggage. It is added using the NI method, and when there is no transport vehicle that satisfies the constraint condition, the transport vehicle is added to the schedule.
[0015]
The invention according to claim 3 selects one package recorded in a randomly selected gene in the genetic algorithm mutation operation applied to the transport schedule creation step according to claim 1, and transports the package. Select one destination and a random distance, delete the collection and delivery destination packages within that distance from the previously selected destination, and transfer these packages in the transport schedule. When added to the route of a vehicle by the NI method (Nearest Insertion Method), the increase in the travel distance of the transport vehicle does not exceed a certain percentage of the original travel distance of the transport vehicle. Baggage that can be added and not added is included in the transport schedule again at that time, after additional processing of other possible baggage Feeding vehicle route into using NI method to add, if there is no transport vehicle that satisfies the constraints and performs an addition to the schedule of the transport vehicle.
[0016]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, an embodiment of the present invention will be described with reference to the drawings.
[0017]
In the present embodiment, it is assumed that a plurality of transport vehicles (trucks, etc.) belonging to the distribution center depart from the distribution center and prepare a schedule for carrying packages to a plurality of destinations. Although this embodiment assumes delivery of packages, it is naturally applicable to creation of a collection schedule in which packages are collected from a plurality of bases to a distribution center.
[0018]
FIG. 1 is a block diagram of the system of the present invention.
[0019]
The system includes an input device (101), an output device (102) such as a printer, a display device (103) such as a display, a processing device (104), and a storage device (105).
[0020]
The processing device (104) executes a series of programs (106) including an input processing unit (107), a constraint condition analysis processing unit (108), a transportation schedule creation unit (109), and a result output unit (110).
[0021]
The storage device (105) includes base information (111), luggage information (112), transport vehicle information (113), transport area definition information (114), distance table (115), road map (116), discharge map. Package information (117) and created from these. The transport route information (118) is stored. In addition, gene information (119) and vehicle management information (120) used for creating a transportation route are also stored.
[0022]
FIG. 2 shows an example of the base information (111) stored in the storage device (105) of FIG.
[0023]
In the base information (111), location information of a distribution center or a collection / delivery destination base of a package is stored. Specifically, a base ID (201) for uniquely identifying a distribution center or a transport destination base, a base name (202), a base address (203), a latitude (204) and a longitude (205) indicating the base position Etc. are stored.
[0024]
FIG. 3 shows an example of the package information (112) stored in the storage device (105) of FIG.
[0025]
In the package information (112), information regarding each package to be transported is stored. Specifically, a package index (301) sequentially assigned to each package from 1, a package ID (302) for uniquely identifying the package, a package sent from the distribution center to the delivery destination, or a base ID indicating the package transport destination (303), a load amount (304), and a time constraint (305) indicating a designated arrival time zone of the vehicle to the transportation destination.
[0026]
FIG. 4 shows an example of transport vehicle information (113) stored in the storage device (105) of FIG.
[0027]
In the transport vehicle information (113), information on the capacity and limit relating to the load capacity of the usable vehicle and the operation time of the vehicle is stored. Specifically, the transport vehicle information includes a vehicle number (401) sequentially assigned from 1 to uniquely identify the vehicle, a load weight limit value (402) of that type of vehicle, and a distribution center of the vehicle. The departure time (403) and the end time (404) for finishing the delivery work.
[0028]
FIG. 5 shows an example of transport area definition information (114) stored in the storage device (105) of FIG.
[0029]
In the area definition information (114), the area ID of each base is registered. The fact that the area IDs are the same means that the bases to which the same area ID is assigned can patrol with the same transport vehicle. That is, when creating a transportation schedule, a baggage at a base having a different area ID is not assigned to the same transportation vehicle.
[0030]
Specifically, the base ID (501) and the area ID (502) are registered in the area definition information. Further, in this embodiment, a base that is not registered in the area definition information is handled as transportable by any transportation vehicle that travels around any area.
[0031]
FIG. 6 shows an example of exclusive package information (117) stored in the storage device (105) of FIG.
[0032]
The exclusive baggage information (117) is analyzed by the constraint condition analysis processing unit (108) for the constraint conditions such as the geographical location of the transport destination base and the transport time constraint, and information on the packages that cannot be transported by the same vehicle is obtained. Is set. In other words, when the packages with the package indexes I and J cannot be transported together in the same vehicle, 1 is set in the (I, J) element and (J, I) element of the table representing the exclusive package information. To do. Other elements are set to 0.
[0033]
FIG. 7 shows an example of the distance table (115) stored in the storage device (105) of FIG.
[0034]
In the distance table (117), the IDs (701 and 702) of the two bases, the travel distance (703) by the transportation vehicle from the base ID1 (701) to the base ID2 (702), and the travel time (704). Store.
[0035]
FIG. 8 shows an example of transport route information (118) stored in the storage device (105) of FIG.
[0036]
The transportation route information (118) stores information indicating a base where the vehicle circulates in the transportation schedule created by the method according to the present invention and the circulation order of the vehicle. Specifically, the vehicle number (801), the number of traveling sites (802) of the vehicle, the site ID (803) of the transport destination site, the arrival time (804) at the site, and the luggage to be transported to the site The index (805) is stored. Further, the total luggage amount (810) and the total travel distance (811) are stored.
[0037]
The gene information (116) in FIG. 9 shows an example of gene expression used in transport schedule creation by the genetic algorithm used in the transport schedule creation unit (109). The gene stores a package index (901) of a package delivered by a transport vehicle such as a truck.
[0038]
The vehicle management information (120) stores information indicating the correspondence relationship of the gene information (119) used in the transport schedule creation unit (109) to the vehicle. The gene information (119) is simply an array in which the package indexes are arranged one-dimensionally, and it is not recorded which package is loaded on which vehicle. In the vehicle management information, the following information is stored for each vehicle in order to indicate which part of the genetic information corresponds to the load loaded on each vehicle. That is, it consists of a vehicle number (904) for uniquely identifying the vehicle, a gene start position (905) indicating the start position on the gene of the load loaded on the vehicle, and a gene end position (906) indicating the end position.
[0039]
FIG. 10 is a flowchart showing an outline of the program (106) executed by the processing device (104) in FIG. First, in the input processing step (1001), the user obtains information necessary for creating a transportation plan such as base information (111), luggage information (112), transportation vehicle information (113), transportation area definition information (114). input. Details of this processing will be described later with reference to FIG. In the next constraint condition analysis process (1002), the constraint conditions such as the geographical position of the transport destination base and the transport time constraint are analyzed to generate exclusive package information (117). Details of this processing will be described later with reference to FIG. In the next transportation schedule creation step (1003), the transportation plan considered to be optimal is determined from the information obtained in the input processing step (1001). Here, the determination of the transportation plan refers to determining the allocation and schedule (transport schedule information) of the packages to be followed by the truck that can deliver all the input packages to the delivery destination. Details of this processing will be described later with reference to FIG. Next, in the result output processing step (1004), the created schedule is output together with the evaluation. Details of this processing will be described later with reference to FIG.
[0040]
FIG. 11 is a flowchart showing details of the input processing step (1001) in FIG. First, in the base information registration step (1101), the base information (111) is registered. Next, in the package information registration step (1002), the package information (112) is registered. Next, in the transport vehicle information registration step (504), the transport vehicle information (113) is registered. Next, in the transportation area registration process (1104), the transportation area definition information (114) is registered. Next, in the distance table generation process (1105), the distance between the bases and the required travel time by the truck are generated with reference to the road map (116). It is assumed that a road map (116) storing roads used in car navigation, connection relationships between the roads, and distance information is prepared in advance.
[0041]
FIG. 12 is a flowchart showing details of the constraint condition analysis processing (1002) in FIG. Here, the geographical conditions of each base and the time constraints specified for each package are analyzed to determine the packages that cannot be transported mixedly in the same vehicle, and the exclusive package information (117) is generated. Specifically, first, the exclusive package information is initialized (1201). That is, 0 is substituted for all the elements of the exclusive package information that is a two-dimensional array. Hereinafter, the exclusive package information is described as a two-dimensional array XL [I, J]. Next, it is determined by the following processing whether or not a constraint violation occurs when two packages are mixedly loaded in the same vehicle.
[0042]
First, 1 is assigned to the variable I (1202). Next, the value I is compared with a variable L_MAX representing the number of packages registered in the package information (1203). If I is greater than L_MAX, the process is terminated. If I is less than or equal to L_MAX, the following process is performed. First, I + 1 is substituted for variable J (1204). Next, J and L_MAX are compared (1205). If J is larger than L_MAX, the process proceeds to step 1220, 1 is added to the variable I (1220), and the process returns to the next step 1203 to repeat the process.
[0043]
If J is less than or equal to L in step 1205, the following processing is performed to determine whether or not mixed loading of the luggage with the luggage index (301) of the luggage information (112) into the same vehicle causes violation of the constraint condition. I do.
[0044]
First, it is checked whether or not the area IDs registered in the transport area definition of the transport destination bases of the packages I and J are different (1206). This condition is satisfied only when the area IDs are registered in the two bases and the area IDs of the two bases are different. In this embodiment, when the area ID of at least one of the bases is not registered, the base in which the area information is not registered can be mixed with the luggage of the transportation vehicle that circulates the base of the other area ID. Therefore, the condition is not satisfied in cases other than the above.
[0045]
Next, it is determined whether the vehicle traveling around the two bases can travel within the upper travel time limit of the vehicle. In other words, the travel required time of the distribution center and the transport destination base for the package I is substituted into the variable D1 with reference to the distance table (1207). Next, the travel required time of the center and the transport destination base of the package J is similarly substituted into the variable D1 (1208). Next, the travel time between the transport destination bases of the package I and the package J is assigned to the variable D3 in the same manner (1209). Next, the sum of D1, D2, and D3 is substituted for variable D (1210). Next, the value of the variable D is compared with the upper limit of the track traveling time (1211). If D exceeds the track travel time upper limit (No in step 1211), 1 is substituted into the (I, J) and (J, I) elements of the exclusive information table (1217, 1218). Then, move on to the next package combination.
[0046]
If the determination in step 1211 is Yes, the following processing is performed to check whether the two packages can be transported within the respective transport designated time frames. First, the start time of the designated transportation period for the package I is substituted into the variable BI (1212).
[0047]
Next, the end time of the designated transportation time frame for the package I is substituted into the variable EI (1213). Next, the start time of the designated transportation time frame for the package J is substituted into the variable BJ (1214). Next, the end time of the designated transportation time frame for the package J is substituted into the variable EJ (1215).
[0048]
Next, it is checked whether D3 is (EJ-BI) or less or D3 is (EI-BJ) or less (1216). If the condition is not satisfied, 1 is set to the (I, J) and (J, I) elements of the exclusive package information in steps 1217 and 1218. If the condition is satisfied in step 1216, it is not possible to determine that the package I and the package J cannot be transported by the same vehicle only due to time constraints. ) The element remains 0, and the process proceeds to the next process.
[0049]
Next, 1 is added to the variable J (1219), and the process returns to step 1205. If the determination result in step 1205 is Yes, the process proceeds to step 1220, 1 is added to the variable I, and the process returns to step 1203.
[0050]
FIG. 13 is a flowchart showing details of the transportation schedule creation processing (1003) in FIG. This schedule creation process follows GA (genetic algorithm). First, different initial solution groups are created by a method including randomness (1301). Details of this processing will be described later with reference to FIG. Next, 1 is substituted into the variable I (1302). Next, the solution population is improved by genetic processing (1303). Details of this processing will be described later with reference to FIG. By the processing of (1303), at least a part of the solution population changes, and the solution population gradually approaches the optimal solution by repeating the processing of (1303) to (1305). After the processing of (1302), the group is evaluated (1304). The evaluation is performed on various factors such as the travel distance of the vehicle calculated from the route information and the number of vehicles used, and the result gives a ranking to each solution in the solution group. The solution with the highest evaluation result is selected as the next-generation solution (1305). Next, 1 is added to the variable I (1306).
[0051]
It is checked whether I exceeds the preset GA processing generation number G_MAX or whether the evaluation value of the best solution in the next generation group is better than a predetermined target value (1307). If the condition is satisfied, the best solution in the current solution group is output (1308), and the process is terminated. If the condition is not satisfied in step 1307, the process returns to step 1303 and the solution population improvement by genetic processing is repeated.
[0052]
FIG. 14 shows details of the process for adding a package to the package transportation schedule used in the creation of the initial solution group (1301) and the solution group improvement process (1303) of the transportation schedule creation process using the genetic algorithm of FIG. It is a flowchart to show. This process is a process of adding collection and delivery of one package to a transportation schedule composed of a plurality of transportation vehicles.
[0053]
It is assumed that the package index of the package to be added is registered in the array L. Further, it is assumed that the number of packages registered in the array L is registered in the variable L_MAX. First, 1 is substituted into the variable I (1401). Next, I and L_MAX are compared (1402). When I is L_MAX or less (No in 1402), the following processing is performed. First, it is checked whether there is a vehicle capable of transporting the luggage L [I] (1403). Details of this processing will be described with reference to FIG. If there is a vehicle that can be transported in the processing of step 1403, the luggage L [I] is added to the vehicle (1405), -1 is substituted for L [I] (1406), and the variable I is set to 1. (1407), the process returns to step 1402 and proceeds to the processing of the next package. If No in step 1404, the process proceeds to step 1407.
[0054]
If the determination in step 1402 is Yes, the process moves to step 1408 and 1 is substituted into the variable I.
[0055]
Next, the values of the variable I and L_MAX are compared (1409). If I is greater than L_MAX, the process ends. When I is less than or equal to L_MAX, the following processing is performed.
[0056]
First, it is checked whether L [I] is equal to -1 (1410). If equal, L [I] has already been assigned to the vehicle, so the routine proceeds to step 1415, where 1 is added to the variable I and the processing of the next package is started.
[0057]
If L [I] is not equal to −1 in step 1410, the following processing is performed.
[0058]
First, it is checked whether there is a vehicle capable of transporting the luggage L [I] (1411). Details of this processing will be described with reference to FIG.
[0059]
If there is a vehicle that can be added, the luggage L [I] is added to the vehicle (1413). If there is no vehicle that can be added, a new vehicle is allocated for transportation of the load L [I] (1414). Next, 1 is added to the variable I (1415), and the process returns to step 1409 to proceed to the next package processing.
[0060]
FIG. 15 is a flowchart showing details of the processing in step 1403 in FIG.
[0061]
In this process, a transport vehicle that can load the load to be added is searched for. If not, P is set to -1.
[0062]
It is assumed that the number of transport vehicles that have already been assigned to transport packages is set in Max_Truck.
[0063]
First, 1 is substituted for the variable K, the maximum integer Max_Value that can be expressed by the computer to be used is set for the variable D, and −1 is set for the variables Truck and P (1501). Next, the value of variable K and Max_Truck are compared (1502). If K is larger than Max_Truck, the process ends.
[0064]
When K is less than or equal to Max_Track, the following processing is performed. First, it is checked whether or not a baggage can be added to the Kth transport vehicle (1503). Details of this processing will be described later with reference to FIG. If it can be added, the operation time increment D_MIN set in the processing of step 1503 is compared with the value of the variable D (1505). If D is large, the value of D_MIN is substituted for D, K is substituted for Truck, and Pos is substituted for P (1506). Values are set to the variables D_MIN and Pos in step 1503. If D is equal to or less than D_MIN, the process proceeds to step 1507 to check the next vehicle.
[0065]
FIG. 16 is a flowchart showing details of the processing in step 1411 in FIG.
[0066]
In this process, a transport vehicle that can load the load to be added is searched, and if there is, the number of the vehicle and the load position of the load are substituted into the variable P for the variable Truck. If not, P is set to -1.
[0067]
It is assumed that the number of transport vehicles that have already been assigned to transport packages is set in Max_Truck.
[0068]
First, 1 is substituted for the variable K, the maximum integer Max_Value that can be expressed by the computer to be used is set for the variable D, and −1 is set for the variables Truck and P (1601). Next, the variable K is compared with the value of Max_Truck (1602). If K is larger than Max_Truck, the process ends.
[0069]
When K is less than or equal to Max_Track, the following processing is performed. First, it is checked whether or not a package can be added to the Kth transport vehicle (1603). Details of this processing will be described later with reference to FIG. If it can be added, the operation time increment D_MIN set in step 1603 is compared with the value of the variable D (1605). If D is large, D_MIN is substituted for D, K is substituted for Truck, and Pos is substituted for P (1606). Values are set to the variables D_MIN and Pos in step 1603. If D is less than or equal to D_MIN, the process moves to step 1607 to check the next vehicle.
[0070]
FIG. 17 is a flowchart showing details of step 1503 in the flowchart of FIG.
[0071]
In this process, it is assumed that the package index of the package to be added to the schedule is substituted for the variable L. In addition, it is assumed that a vehicle number that is a target for determining whether the luggage L can be added is set. When this processing is completed, if the transportation of the luggage L is possible in the vehicle T_No, an additional position is set in the variable Pos, and an increment value of the traveling time of the vehicle due to the addition of the luggage is set in D_MIN. . If it could not be added, −1 is set in Pos, and Max_Value is set in D_MIN. Variable First, the ID of the transport destination base of the package L is substituted into the variable Z (1701). Next, the load amount of the load L is substituted into the variable V (1702). Next, −1 is set to the variable Pos, and the maximum number (expressed as Max_Value) that can be expressed by the computer used for D_MIN is set (1703). Next, with reference to the vehicle management information (120) for the variable I, the gene start position of the T_Noth vehicle is set (1704). Next, the total travel time of the T_No.th vehicle is substituted into the variable TH (1705). Next, it is determined with reference to the exclusive baggage information whether the baggage loaded on the baggage L and the T_Noth vehicle is not transportable by the same vehicle (1706). That is, using the luggage L and the luggage index of the luggage loaded on the T_Noth vehicle, the exclusive luggage information that is a two-dimensional array is referred to, and if the element is 1, it is determined that the same vehicle cannot be transported. To do. If it is determined in step 1706 that the placement is impossible, the process ends (1707). In other cases, the following processing is performed.
[0072]
Next, the value of the variable I is compared with the value of the gene end position + 1 of the vehicle (1708). If I is large, the process ends. If I does not exceed the above value, the following processing is performed.
[0073]
First, I is compared with the gene start position of the T_Noth vehicle (1709). If they are equal, the base ID representing the distribution center from which the vehicle departs is substituted for the variable X (1711). If they are not equal, the base ID of the collection / delivery destination of the (I-1) th package in the genetic information of the vehicle is substituted (1710). Next, I is compared with the value of the gene end position + 1 of the T_Noth vehicle. If they are equal, the base ID of the distribution center is substituted for the variable Y (1714). If they are not equal, the ID of the collection / delivery destination base of the I-th package of the T_No-th vehicle is substituted for Y (1713).
[0074]
Next, it is checked whether or not the load L of the load V can be loaded between the Xth transport bag and the Yth transport bag of the Ith vehicle (1715). That is, when the additional target baggage is a delivery baggage, a value obtained by adding L to the load amount of the vehicle between the distribution center from which the vehicle departs and the collection and delivery destination base of the Xth transport baggage, Check if the maximum load capacity of the vehicle is exceeded. If the package is a collected package, the value obtained by adding L to the loaded quantity at each collection and delivery destination base from the collection destination of the Yth package of the vehicle until it returns to the distribution center Check if the maximum load capacity of the vehicle has been exceeded.
[0075]
Next, a value obtained by subtracting the required time between X and Y from the sum of the required time between X and Z and the required time between Z and Y is substituted into T_Delta (1716). Next, it is checked whether the value obtained by adding Delta_T to the vehicle arrival time of the collection and delivery destination that circulates in the transportation of the luggage after Y of the vehicle does not break the time constraint (1717). In FIG. 17, TIME (X, Y) represents the travel time of the vehicle from the base X to Y. Next, it is checked whether T_Delta does not exceed 0.25 times TH (1718). If it exceeds, the process ends. If not, the following processing is performed.
[0076]
Next, D_MIN and T_Delta are compared (1719). If T_Delta is small, the value of T_Delta is substituted for D_MIN, and the value of I is substituted for Pos (1720).
[0077]
Next, 1 is added to I (1721), and the process returns to step 1708 to check the next additional position.
[0078]
FIG. 18 is a flowchart showing details of step 1603 in the flowchart of FIG.
[0079]
In this process, it is assumed that the package index of the package to be added to the schedule is substituted for the variable L. In addition, it is assumed that a vehicle number that is a target for determining whether the luggage L can be added is set. When this processing is completed, if the transportation of the luggage L is possible in the vehicle T_No, an additional position is set in the variable Pos, and an increment value of the traveling time of the vehicle due to the addition of the luggage is set in D_MIN. . If it could not be added, −1 is set in Pos, and Max_Value is set in D_MIN. Variable First, the ID of the transportation destination base of the package L is substituted into the variable Z (1801). Next, the load amount of the load L is substituted into the variable V (1802). Next, −1 is set to the variable Pos, and the maximum number (expressed as Max_Value) that can be expressed by the computer used for D_MIN is set (1803). Next, referring to the vehicle management information (120) for the variable I, the gene start position of the T_No.th vehicle is set (1804). Next, it is determined by referring to the exclusive luggage information () whether the luggage loaded on the luggage L and the T_Noth vehicle is not transportable by the same vehicle (1805). That is, using the luggage L and the luggage index of the luggage loaded on the T_Noth vehicle, the exclusive luggage information that is a two-dimensional array is referred to, and if the element is 1, it is determined that the same vehicle cannot be transported. To do. If it is determined in step 1805 that the placement is impossible, the process ends (1806). In other cases, the following processing is performed.
[0080]
Next, the value of the variable I is compared with the value of the gene end position + 1 of the vehicle (1807). If I is large, the process ends. If I does not exceed the above value, the following processing is performed.
[0081]
First, I is compared with the gene start position of the T_Noth vehicle (1808). If equal, the base ID representing the distribution center from which the vehicle departs is substituted for the variable X (1810). If they are not equal, the base ID of the collection / delivery destination of the (I-1) th package in the genetic information of the vehicle is substituted (1809). Next, I is compared with the value of the gene end position + 1 of the T_Noth vehicle. If they are equal, the base ID of the distribution center is substituted for variable Y (1813). If they are not equal, the ID of the collection / delivery destination base of the I-th package of the T_No-th vehicle is substituted for Y (1812).
[0082]
Next, it is checked whether or not the load L of the load V can be loaded between the Xth transport bag and the Yth transport bag of the Ith vehicle (1814). That is, when the additional target baggage is a delivery baggage, a value obtained by adding L to the load amount of the vehicle between the distribution center from which the vehicle departs and the collection and delivery destination base of the Xth transport baggage, Check if the maximum load capacity of the vehicle is exceeded. If the package is a collected package, the value obtained by adding L to the loaded quantity at each collection and delivery destination base from the collection destination of the Yth package of the vehicle until it returns to the distribution center Check if the maximum load capacity of the vehicle has been exceeded.
[0083]
Next, a value obtained by subtracting the required time between X and Y from the sum of the required time between X and Z and the required time between Z and Y is substituted into T_Delta (1815). Next, it is checked whether the value obtained by adding Delta_T to the vehicle arrival time of the collection and delivery destination that circulates in the transportation of the luggage after Y of the vehicle does not break the time constraint (1816). In FIG. 17, TIME (X, Y) represents the travel time of the vehicle from the base X to Y. Next, D_MIN and T_Delta are compared (1817). If T_Delta is small, the value of T_Delta is substituted for D_MIN, and the value of I is substituted for Pos (1818).
[0084]
Next, 1 is added to I (1819), and the process returns to step 1807 to check the next additional position.
[0085]
FIG. 19 is a flowchart showing details of the initial solution group generation processing (1301) in FIG.
[0086]
Note that a traveling schedule for a plurality of vehicles is registered in one solution. The solution group includes a plurality of solutions.
[0087]
The variable SIZE is set in advance with the number of genes to be registered in the initial population. In addition, the number of delivery destination bases registered in the route is set in the variable LEN.
[0088]
First, 0 is substituted for variable I (1901). Next, while I is smaller than SIZE, the processing from (1903) to (1906) is repeated to generate the number of genes specified by SIZE.
[0089]
First, an area for storing an empty gene in which a value is not set for each element is generated (1903).
[0090]
Next, an array T in which packages of package information are rearranged in a random order is created (1904).
[0091]
Next, the packages registered in the array T are sequentially added to the empty gene in this order by the adding procedure shown in FIG. 14 (1905).
[0092]
Next, 1 is added to the variable I (1906), and the next initial solution is created.
[0093]
FIG. 20 is a flowchart showing details of the solution group improvement (1303) in FIG. Genetic processing is the central processing of GA that changes and improves the solution population.
[0094]
First, the number of solutions registered in the solution group is substituted into the variable SIZE (2001). Next, C_NUM is multiplied by SIZE, which is set in advance, and a maximum integer not exceeding that value is substituted (2002). Next, 1 is substituted into the variable I. If I is less than or equal to C_NUM, the next process is repeated to perform the intersection process (2004).
[0095]
First, two different solutions (genes) are selected from the solution population (2005).
[0096]
Next, cross processing is performed based on the two selected solutions (genes), and a solution (gene) newly generated by the cross processing is added to the solution population (2006).
[0097]
Details of this intersection processing will be described with reference to FIG.
[0098]
Next, 1 is added to I (2007), and the process returns to step 2004 to proceed to the next intersection process.
[0099]
If I exceeds C_NUM in step 2004, the process proceeds to the mutation process. In other words, the variable M_NUM is multiplied by a preset mutation rate in SIZE, and a maximum integer not exceeding the value is substituted (2008).
[0100]
Next, 1 is substituted into the variable I (2009).
[0101]
Next, while I is less than or equal to the value of M_NUM, the next process is repeated (2010).
[0102]
First, one solution (gene) is randomly selected from the solution population (2011).
[0103]
Next, mutation processing is performed on the selected solution, and the solution (gene) is added to the solution population (2012). Details of this processing will be described with reference to FIG.
[0104]
Next, 1 is added from variable I (2213), and the process returns to step 2210 to continue the processing.
[0105]
FIG. 21 is a flowchart showing details of the intersection processing (2006) in FIG.
[0106]
First, the number of packages registered in each solution (gene) is substituted into a variable N (2101).
[0107]
Next, the two solutions (genes) to be crossed are copied to the sequences G1 and G2 (2102). Next, in order to determine the intersection, an integer of 2 or more and N-1 or less is randomly generated and assigned to the variable P (2103).
[0108]
Next, the P1 and subsequent package data indexes of G1 are deleted (2104). That is, -1 is assigned to the element to be deleted. Next, 1 is substituted into the variable I (2105).
[0109]
Next, while I is N or less (2106), the following processing is performed.
[0110]
It is checked whether G2 [I] is not included in the array G1 (2107). If not included, the package information is added to the G1 transportation schedule by the processing procedure shown in FIG. 14 (2108).
[0111]
Next, 1 is added to the variable I (2109), and the next process is started.
[0112]
If the condition is not satisfied in step 2107, the process proceeds to step 2109 to proceed to the next process.
[0113]
If I exceeds N in step 2106, the process ends.
[0114]
FIG. 22 is a flowchart showing details of the mutation process (2012) in FIG.
[0115]
First, the solution (gene) to be mutated is copied to the array G [] (2201). Next, the collection / delivery destination base farthest from the distribution center and the distance from the distribution center are substituted into a variable L (2202).
[0116]
A real number in the range of 0 and 0.3 is randomly generated and assigned to the variable R (2203).
[0117]
Next, the product of the value of the variable L and the value of R is substituted into the variable L1 (2204).
[0118]
Next, in order to determine the mutation location on the gene, an integer from 1 to N is randomly selected and substituted for the variable P (2205).
[0119]
Next, 0 is substituted for variable I and 0 is substituted for J (2206).
[0120]
The value of G [P], that is, the index value of the package information is substituted for the variable K (2207).
[0121]
While I is N or less (2208), the next process is repeated.
[0122]
It is checked whether the distance between the collection / delivery destination base for the package with index K and the collection / delivery destination base for the package with G [I] is L1 or less (2209).
[0123]
If the condition is satisfied, the value of G [I] is substituted for T [J], and -1 is substituted for G [I] (2210).
[0124]
Next, 1 is added to variable J (2211), 1 is also added to I (2212), and the process returns to step 2208 to continue the processing.
[0125]
If the value of I exceeds the value of N in step 2208, the element having the value of -1 in the array G is deleted and packed forward (2213).
[0126]
Next, the collection and delivery destination bases of J packages stored in the array T are sequentially added from the top to the transport schedule of the array G by the processing procedure shown in FIG. 7 (2214).
[0127]
FIG. 23 is a flowchart showing details of the result output process (1004) in FIG. First, the passage base of each transport flight is displayed on the map (2301). Next, a table and a graph are created and displayed together with the schedule obtained by the transportation schedule creation processing and the values of the number of vehicles required and the distance traveled (2302). Next, if there is a print instruction, a graph or a table is printed (2703).
[0128]
【The invention's effect】
As described above, according to the present invention, constraints that must be satisfied when creating a transportation schedule are analyzed in advance, and a set of two packages that cannot be transported by the same vehicle due to violation of these constraints is created in advance. Therefore, when creating a transport route for each vehicle, by avoiding the above-mentioned exclusive combination of packages, it is possible to reduce the number of combinations of loading on the same vehicle when creating a schedule. Improving the response speed of creation. Furthermore, in the schedule creation method applying GA, when adding a package to a schedule that is still being created in an intersection process or a mutation process, an increase in the travel distance of the transport route due to the addition of the package transport to the existing transport route However, when a certain percentage of the mileage of the existing route is exceeded, the addition of the cargo transportation is not performed, thereby suppressing the addition of a remote destination base to the existing route. In addition to reducing the difference in mileage, and once trying to add all the cargo transport destinations, only the cargo that could not be added due to the above conditions was added again. By adding vehicles, the addition of unnecessary transport vehicles is suppressed.
[Brief description of the drawings]
FIG. 1 is a system configuration diagram of the present invention.
FIG. 2 is a diagram showing a configuration of base information included in the storage device of the present invention.
FIG. 3 is a diagram showing a structure of package information included in the storage device of the present invention.
FIG. 4 is a diagram showing a configuration of transport vehicle information included in the storage device of the present invention.
FIG. 5 is a diagram showing a configuration of area definition information included in the storage device of the present invention.
FIG. 6 is a diagram showing a configuration of exclusive luggage information included in the storage device of the present invention.
FIG. 7 is a diagram showing a configuration of a distance table included in the storage device of the present invention.
FIG. 8 is a diagram showing a configuration of transport route information included in the storage device of the present invention.
FIG. 9 is a diagram showing a configuration of gene information used for creating a transportation schedule using a genetic algorithm included in the storage device of the present invention.
FIG. 10 is a flowchart showing the overall processing flow of the present invention.
FIG. 11 is a flowchart showing input processing according to the present invention.
FIG. 12 is a flowchart showing a constraint condition analysis process according to the present invention.
FIG. 13 is a flowchart showing a transportation schedule creation process of the present invention.
FIG. 14 is a flowchart of a process for adding a package to a transportation schedule used in creating a transportation schedule according to the present invention.
FIG. 15 is a flowchart of an additional vehicle check 1 process used in the luggage addition process of the present invention.
FIG. 16 is a flowchart of additional vehicle check 2 processing used in the luggage addition processing of the present invention.
FIG. 17 is a flowchart of package addition check processing 1 used in additional vehicle check processing 1 of the present invention.
FIG. 18 is a flowchart of a package addition check process 2 used in the additional vehicle check process 2 of the present invention.
FIG. 19 is a flowchart of the initial group generation processing of the present invention.
FIG. 20 is a flowchart showing an outline of genetic processing of the present invention.
FIG. 21 is a flowchart showing the intersection processing of the present invention.
FIG. 22 is a flowchart showing a mutation process of the present invention.
FIG. 23 is a flowchart showing a result output process of the present invention.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 101 ... Input device, 102 ... Output device, 103 ... Display device, 104 ... Processing device, 105 ... Storage device, 106 ... Program, 107 ... Input processing unit, 108 ... Restriction condition analysis processing unit, 109 ... Transportation schedule creation unit, DESCRIPTION OF SYMBOLS 110 ... Result output part, 111 ... Base information, 112 ... Luggage information, 113 ... Transportation vehicle information, 114 ... Distance table, 115 ... Road map, 116 ... Exclusive luggage information, 117 ... Transportation route information, 118 ... Gene information, 119 ... vehicle management information.