(57)【要約】【課題】輸送ルート（発拠点と着拠点）が確定していない荷物を輸送ルートが確定している荷物に加えた上で、ルート未確定の荷物のルートを確定させトラック車立ての輸送コストをベースとして最適な輸送スケジュールを作成する技術を提供することを目的とする。【解決手段】複数の物流センターを含む物流網で集荷先拠点から配送先拠点への荷物の輸送を行う車両の輸送スケジュールを作成するシステムであって、集荷先・配送先拠点が確定していない荷物について、荷物需要情報と荷物供給情報を登録するようにし、それらの情報に基づいて集荷拠点または配送先拠点が未確定の荷物レコードを荷物情報に追加し、その荷物情報の荷物を輸送車両に割り当てて輸送スケジュールを作成する。その際、集荷拠点または配送先拠点が未確定の荷物レコードが検出されたときには、未確定の拠点を確定する処理を行った上で輸送スケジュールを作成する。【選択図】図１
2008230816.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも入出力装置と処理装置と記憶装置とを有し、複数の物流センターを含む物流網で集荷先拠点から配送先拠点への荷物の輸送を行う車両の輸送スケジュールを作成する調達物流スケジュール作成システムであって、
複数の物流センターと集荷先・配送先拠点の位置情報を含む拠点情報を登録する拠点情報登録手段と、
集荷先・配送先拠点が確定している荷物について、各荷物の荷物量、集荷先・配送先拠点、および集荷・配送の時間制約を含む荷物情報を登録する荷物情報登録手段と、
集荷先・配送先拠点が確定していない荷物について、その荷物の需要拠点と需要量および納入時間制約情報を含む荷物需要情報を登録する荷物需要情報登録手段と、
集荷先・配送先拠点が確定していない荷物について、その荷物の供給拠点と供給量および出発時間制約情報を含む荷物供給情報を登録する荷物供給情報登録手段と、
物流センターが有するトラックなどの輸送車両数、およびそれらの輸送車両の積載量上限の情報を含む輸送車両情報を登録する輸送車両情報登録手段と、
前記荷物需要情報または荷物供給情報に基づいて、集荷拠点または配送先拠点が未確定の荷物レコードを前記荷物情報に追加する荷物情報追加処理手段と、
前記登録した各情報と、集荷拠点または配送先拠点が未確定の荷物レコードが追加された荷物情報を用いて、該荷物情報の荷物を輸送車両に割り当てて輸送スケジュールを作成するとともに、該輸送スケジュールの作成の際に前記集荷拠点または配送先拠点が未確定の荷物レコードが検出されたときには、未確定の集荷拠点または配送先拠点を確定する処理を行った上で輸送スケジュールを作成する輸送スケジュール作成手段と、
作成した輸送スケジュールを出力するスケジュール出力手段と
を備えることを特徴とする調達物流スケジュール作成システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物流分野におけるトラック等の輸送スケジューリング作成を計算機で行う技術に関するものであり、具体的には計算機を利用した輸送計画の作成システムに関するものである。
【背景技術】
【０００２】
物流分野におけるトラック輸送等のスケジュールを計算機で作成するには、例えば非特許文献１に記載されているような線形計画法などの数理的な計算に基づくものや、スィープ法やNI法と言ったヒューリスティクスに基づくもの、また、非特許文献２に記載されているようなタブーサーチ、SA法(Simulated Annealing：焼きなまし法)、GA(Genetic Algorithm：遺伝的アルゴリズム)などメタヒューリスティクスと呼ばれる確率的手法を適用したものなど、多数の方式が用いられている。
【０００３】
これらの方式を具体的に物流分野に適用した技術で代表的なものとしては、例えば、下記特許文献１及び特許文献２に記載のものが知られている。
【０００４】
特許文献１に記載のものは、複数の配送先への荷物輸送のスケジュール作成を効率化する方式である。この方式では、各荷物の届け先が複数の塊に割付けられ、該塊内での各届け先を結ぶ配送ルートを作成する。これにより、エリア全体での配送時間の短縮を図るものである。
【０００５】
特許文献２に記載のものは、工場や物流センター、配送先などの拠点間の物流網の作成に、線形計画法や整数計画法などの数理的技法を適用したものである。この方式では、該文献の図に示されているように、工場や倉庫、配送先などの拠点をグラフのノードとして、ノード間のアークを荷物が流れるグラフで輸送を表現する。各アークには単位荷物量あたりの輸送コストや、そのアーク上を輸送できる上限荷物量、また、途中の物流センターの中継可能な荷物量上限などを与え、これを線形計画法や整数計画法でモデル化して問題を解き、荷物の出発地から最終目的地まで、どのような経路で輸送すれば物流網全体の輸送コストが最小になるかを決定する。
【非特許文献１】久保幹雄著「ロジスティクス工学」朝倉書店、2001年６月
【非特許文献２】柳浦睦憲、茨木秀俊著「組合せ最適化  −メタ戦略を中心として  −」朝倉書店、2001年1月
【特許文献１】特開平8-115495号公報
【特許文献２】特開2000-182179号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記特許文献１に記載の技術では、荷物の輸送ルートは、物流センターから出発し、指定の配送先へ配送されるものとして与えられる。そして、それらの荷物は、物流センターまたは車庫が保有するトラックへ割り当てて、指定された出発拠点から到着拠点に輸送されるようにする。しかし、例えば荷物を輸送する際に使用される入れ物として特定の容器を使用するような場合、荷物の配送終了後はその容器は空容器となり、所定の場所に戻さなければならない。このとき、空容器をどこに輸送するかは未確定で、空容器の需要量だけが確定している場合が多い。また、どの拠点から空容器を輸送してもよく、最終的に需要量を満たすだけの空容器を輸送すればよい。さらに、なるべく近隣の供給拠点から需要拠点への輸送を行うのが望ましい。このような問題に対して、特許文献１に記載のような従来技術では、対応することができない。
【０００７】
特許文献２に記載の技術は輸送の最適化を行うものである。しかし、この方法では線形計画法などの数理的技法を用いているため、上記輸送ルートが確定していない荷物に対してはその輸送ルートを確定することが可能だが、スケジュール作成で要求されるトラック台数の確定や、そのトラックの走行ルートの作成までは行うことができない。また、当然輸送コストを最小にする解を求めるが、コストの計算はトラック台数が含まれていないため輸送コスト算出の精度が悪いという問題点がある。
【０００８】
本発明の目的は、輸送ルート（発拠点と着拠点）が確定していない荷物を輸送ルートが確定している荷物に加えた上で、ルート未確定の荷物のルートを確定させトラック車立ての輸送コストをベースとして最適な輸送スケジュールを作成する技術を提供することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するため、本発明は、少なくとも入出力装置と処理装置と記憶装置とを有し、複数の物流センターを含む物流網で集荷先拠点から配送先拠点への荷物の輸送を行う車両の輸送スケジュールを作成する調達物流スケジュール作成システムであって、複数の物流センターと集荷先・配送先拠点の位置情報を含む拠点情報を登録する拠点情報登録手段と、集荷先・配送先拠点が確定している荷物について、各荷物の荷物量、集荷先・配送先拠点、および集荷・配送の時間制約を含む荷物情報を登録する荷物情報登録手段と、集荷先・配送先拠点が確定していない荷物について、その荷物の需要拠点と需要量および納入時間制約情報を含む荷物需要情報を登録する荷物需要情報登録手段と、集荷先・配送先拠点が確定していない荷物について、その荷物の供給拠点と供給量および出発時間制約情報を含む荷物供給情報を登録する荷物供給情報登録手段と、物流センターが有するトラックなどの輸送車両数、およびそれらの輸送車両の積載量上限の情報を含む輸送車両情報を登録する輸送車両情報登録手段と、前記荷物需要情報または荷物供給情報に基づいて、集荷拠点または配送先拠点が未確定の荷物レコードを前記荷物情報に追加する荷物情報追加処理手段と、前記登録した各情報と、集荷拠点または配送先拠点が未確定の荷物レコードが追加された荷物情報を用いて、該荷物情報の荷物を輸送車両に割り当てて輸送スケジュールを作成するとともに、該輸送スケジュールの作成の際に前記集荷拠点または配送先拠点が未確定の荷物レコードが検出されたときには、未確定の集荷拠点または配送先拠点を確定する処理を行った上で輸送スケジュールを作成する輸送スケジュール作成手段と、作成した輸送スケジュールを出力するスケジュール出力手段とを備えることを特徴とする。
【００１０】
要するに、本発明は、輸送ルート（集荷拠点と配送先拠点）が確定していない荷物の需要量と供給量を入力し、それをもとに輸送ルート未確定の荷物情報として集荷拠点と配送先拠点が確定している荷物情報に追加して、輸送ルートの決定と変更を行いながらスケジュールの作成を行うものである。
【発明の効果】
【００１１】
本発明によれば、輸送ルートが確定していない荷物のルートを確定させ、輸送ルートが確定している荷物との乗せ合わせを行って輸送スケジュールを作成することができる。これにより、空容器などについてその需要と供給に基づいた輸送を実現することができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施の形態を図面に従って説明する。
【００１３】
図１は、本実施形態のシステムを示す全体構成図である。本システムは、入力装置(101)、プリンタなどの出力装置(102)、ディスプレイなどの表示装置(103)、処理装置(104)、および記憶装置(109)を備える。処理装置(104)は、入力処理部(106)、輸送スケジュール作成部(107)、および結果出力部(108)を含む一連のプログラム(105)を実行する。また、記憶装置(109)には、拠点情報(110)、荷物情報(111)、荷物需要情報(112)、荷物供給情報(113)、輸送車両情報(114)、距離テーブル(115)、道路地図（116）および、これらから作成される輸送スケジュール情報(117)が格納される。
【００１４】
図２は、記憶装置（109）に格納される情報の一例を示したものである。
【００１５】
拠点情報（110）には、配送先や物流センターなどの拠点ごとに、その拠点を一意に識別する拠点ID（201）、その拠点の名称（202）、その拠点の住所（203）、および、その拠点の緯度（204）と経度（205）が格納される。荷物情報（111）には、荷物ごとに、その荷物を一意に識別する荷物ID(206)、その荷物の送付元である発拠点のID（207）、その荷物の送り先である着拠点のID（208）、その荷物の荷物量（209）、発拠点から出荷可能になる時間を示す出荷時刻（210）、着拠点への到着の締め切り時刻を示す納入時刻（211）、および荷積み荷下ろし作業時間（212）が格納される。
【００１６】
荷物需要情報(112)の１レコードには、荷物の需要がある拠点ID(213)、その需要量(214)、いつまでにその荷物が納入されなければならないかを示す納入時刻(215)、およびその荷物の荷下ろし作業時間(216)が格納される。荷物供給情報(113)の１レコードには、荷物を供給可能な拠点ID(217)、その供給量(218)、その荷物を積載して車両が出発可能な出発時刻(219)、およびその荷物の荷積み作業時間(220)が格納される。この荷物需要情報(112)と荷物供給情報(113)で言うところの「荷物」は、輸送ルートが決まっておらず（すなわち発拠点と着拠点が確定していないということ）、各拠点で必要な量（需要量）と余った量（供給量）が時間に応じて流動的に変化するものである。例えば、空ケースや空パレットなどの容器類は、各拠点ごとに、ある時点で容器が幾つ必要かを示す需要量と、ある時点で容器が幾つ余るかを示す供給量が確定できる。また、容器類に限らず、例えばネジなどの部品で、各工場拠点ごとに需要量と供給量が時間とともに変化するものがある。なお、本実施形態では、荷物需要情報(112)と荷物供給情報(113)で言うところの「荷物」として「空ケース荷物」を想定して説明する。また、本実施形態では、そのような輸送ルートが決まっておらず拠点ごとに需要量と供給量が時間に応じて流動的に変化するような荷物として、「空ケース荷物」１種類のみを対象とするが、複数種別を対象とすることもできる。その場合は、荷物種別IDで種別を区別できるようにし、荷物需要情報(112)と荷物供給情報(113)をその種別ごとに設けたり、荷物需要情報(112)と荷物供給情報(113)内に荷物種別ID付きで需要量と供給量を記憶して、種別を区別すればよい。
【００１７】
輸送車両情報（114）には、各拠点の保有する車両の情報が格納される。具体的には、拠点ID（221）、その拠点の保有車両数（222）、およびその保有車両の最大積載荷物量（223）が格納される。距離テーブル(115)には、ルート生成で必要になる、拠点間のトラックなどの輸送便での走行距離に関する情報が格納される。具体的には、出発拠点の拠点ID(224)、到着拠点の拠点ID(225)、それらの拠点間の距離(226)、およびそれらの拠点間を輸送車両で走行する場合の所要時間(227)が格納される。なお、不図示だが、道路地図(116)は、上記距離テーブル(115)の作成に必要な拠点間距離の計算や結果の出力に用いるための輸送区域の道路情報である。
【００１８】
図３は、輸送スケジュール作成部(107)で作成される輸送スケジュール情報(117)の一例を示している。輸送スケジュール情報(117)は、本発明に係る方法によって作成される輸送計画中で輸送車両が巡回する拠点や、その順序を示す情報を格納する。具体的には、車両No（301）、発拠点ID（302）、その車両に割り当てられた荷物数（303）、および割り当てられた荷物に関する情報からなる。割り当てられた荷物に関する情報は、荷物ID（304,306,…）と、その荷物IDの荷物に対する作業が荷積みか荷下ろしかを表すフラグ（305,307,…）とを、作業順に並べたものである。輸送スケジュール情報(117)の１レコード中では、同じ荷物IDが必ず２つあり、先にあるほうが荷積み作業、後ろにあるほうが荷下ろし作業を表す作業フラグが格納される。なお、ここでの荷物とは、荷物情報（111）で与えられている配送すべき荷物を含むことは当然であるが、それに加えて、後述する図６で荷物需要情報(112)をもとに追加された荷物（空ケース荷物）をも含むものである。
【００１９】
図４は、図１中の処理装置(104)が実行するプログラム(105)の概要を示すフローチャートである。まず入力処理ステップ(401)で、拠点情報(110)、荷物情報（111）、荷物需要情報(112)、荷物供給情報(113)、輸送車両情報(114)等の輸送スケジュールを作成するために必要な情報をユーザが入力（登録）する。この処理の詳細は図５で後述する。次の輸送スケジュール作成ステップ(402)では、入力処理ステップで与えられた条件に合致する輸送スケジュールを作成する。ここで輸送スケジュールの作成とは、入力された全ての荷物のうち、供給拠点が確定していないものを確定し、かつ、それぞれの荷物を発拠点から着拠点に届けるトラックが従うスケジュールを決定することを指す。この処理の詳細は図７で後述する。次に、結果出力処理ステップ(403)では、作成したルートを出力する。この処理の詳細は図１１で後述する。
【００２０】
図５は、図４中の入力処理ステップ(401)の詳細を示すフローチャートである。まず、拠点情報登録ステップ(501)で、拠点情報(110)の登録を行う。次に、荷物情報登録ステップ(502)で、荷物情報(111)の登録を行う。ここで荷物情報(111)に登録する荷物は、発拠点と着拠点が確定している荷物である。次に荷物需要情報登録ステップ(503)で、荷物需要情報(112)の登録を行う。次に荷物供給情報登録ステップ(504)で、荷物供給情報(113)の登録を行う。荷物需要情報(112)や荷物供給情報(113)に登録する荷物は空ケース荷物であり、要するに空ケースの需要と供給に関する情報を登録するものである。
【００２１】
次に輸送車両情報登録ステップ(505)で、輸送車両情報(114)の登録を行う。次に距離テーブル生成処理ステップ(506)で、拠点間の距離とトラックによる走行所要時間を道路地図(116)を参照して生成し、距離テーブル(115)を生成する。なお、道路地図(116)は予め用意されているものとする。次に、荷物情報追加処理ステップ（507）で、荷物需要情報(112)を元に、荷物情報(111)に、空ケース荷物の追加を行う。この処理の概要は図６で説明する。
【００２２】
図６は、図５中の荷物情報追加処理（ステップ507）の詳細を示すフローチャートである。まず、変数Nに荷物需要情報(112)の件数（レコード数）を代入し、変数Iに０を代入する(ステップ601)。次に、IとNを比較する(ステップ602)。IがN以上のときは処理を終了する。IがN未満の場合は以下に進む。
【００２３】
まず、荷物情報(111)に空レコードを１件追加する(ステップ603)。次に、ステップ603で追加されたレコードの荷物ID(206)に、空ケース荷物であることを示す識別子（この識別子により、荷物IDを見れば、その荷物が空ケース荷物かそうでない通常の荷物かが判別可能となる）に現在の変数Iの値を連結して生成したID（追加荷物Iと呼ぶ）を代入する(ステップ604)。次に、この追加レコードの出発拠点ID(207)にnullを代入する(ステップ605)。このnullは、出発拠点が確定していないことを表す。次に、この追加レコードの着拠点ID(208)、納入時刻(211)、荷物量(209)、および作業時間(212)に、いま処理対象としている荷物需要情報(112)のI番目のレコードの対応するデータ(213,215,214,216)をそれぞれ代入する(ステップ606)。これにより、空ケースの供給元は決まっていないが、空ケースの需要情報に基づく荷物情報が追加されたことになる。次に、変数Iに1を加えて、ステップ602に戻る(ステップ607)。以上により、荷物需要情報(112)に基づく空ケース荷物が、その供給元拠点が確定していない状態で荷物情報(111)に追加されたことになる。
【００２４】
図７は、図４中の輸送スケジュール作成処理（ステップ402）の詳細を示す処理フローである。
【００２５】
一般的に輸送スケジュールの作成は組み合わせ問題であり、非特許文献１や非特許文献２に説明されているような、ヒューリスティクスを用いた技法や、GA、タブーサーチ、SA法などのメタヒューリスティクスに分類される技法が適用されている。本実施形態では、メタヒューリスティクスの中のランダムリスタート法を適用している。つまり、ランダムな条件下で初期解（スケジュール）を作成し、それを改良処理でより良いスケジュールに改良する。この初期解の作成と改良を複数回繰り返し、その中で最良のスケジュールを選択するものである。
【００２６】
まず、変数Iに1を設定し、Best_ValueにMax_Valueを設定する（ステップ701）。ここでMax_Valueは、使用する計算機で表現可能な最大の数値を表す。次に、IがNより小さい場合（ステップ702）、次の処理を繰り返す。ここで、Nは、ランダムリスタートで初期解の作成と、その初期解の改良を行う回数であり、予め定められている定数である。
【００２７】
まず初期解の作成を行う（ステップ703）。この処理の詳細は図８で説明する。次に、作成した初期解の改良を行う（ステップ704）。この処理の詳細は図９で説明する。次に、スケジュール結果の評価を行う（ステップ705）。この評価とは、ステップ704で改良されたスケジュール結果から、使用するトラック台数およびその走行距離から輸送に要する概算のコストを求める処理である。この計算方法は、トラック台数だけで評価する方法や、輸送車両の総走行距離で評価する方法、また、トラック台数と予め定めた輸送車両一台あたりの固定費の積と、総走行距離と予め定めた単位距離あたりの変動費の積の和で評価する方法などが、挙げられる。ステップ705で算出された評価結果（評価値）は、変数Eに代入される。この評価値が小さい方が、より評価が高いことを意味する。
【００２８】
次に、評価結果が格納されている変数EとBest_Valueの値を比較し（ステップ706）、EがBest_Valueよりも小さい場合には、今回のスケジュール結果（輸送スケジュール情報(117)）がいままでの中でベストの結果であるということだから、Eの値をBest_Valueに代入し、供給元拠点が確定している空ケース荷物を含む荷物情報をBest_Loadに記録し、作成したスケジュール結果をBest_Scheduleに記録する（ステップ707）。なお、図中ステップ707のScheduleは図３に示した作成した輸送スケジュールを示し、Load はその輸送スケジュールにおいて、図６で作成したルート未確定荷物の需要供給拠点を確定した荷物情報を示す。要するに、スケジュール改善処理によって評価がよくなったら、そのときのスケジュールとルート確定した荷物情報を保存するものである。次に変数Iに1を加え、ステップ702に戻る。ステップ702でIがN以上になれば処理を終える。
【００２９】
図８は、図７中の初期解作成処理（ステップ703）の詳細を示す処理フローである。この処理では、荷物情報(111)の各荷物を何れかのトラックに割り当てる初期解を作成する。
【００３０】
まず、荷物情報(111)の全荷物のレコードを配列Lにコピーし、拠点別の空ケース荷物の供給状態を示す荷物供給情報(113)の全レコードを配列Sに格納する（ステップ801）。次に、配列Lに格納されている荷物情報レコードをランダムな順序に並べ換える（ステップ802）。変数Pに配列Lに格納した荷物数を、荷物情報インデクスを表す変数Iに0を、それぞれ設定する（ステップ803）。IとPの値を比較し（ステップ804）、IがP以上ならば処理を終える。IがP未満の間は、次の一連の処理を行う。
【００３１】
まず、変数Tに、既に荷物を割り当てたトラックの台数を格納する（ステップ805）。次に、トラックに荷物を割り当てたときの距離増分の最小値を格納する変数VにMax_Value、距離増分が最小となるときのトラックのインデクスを表す変数Xに-1、荷物割り当てをチェックしようとしているトラックのインデクスを表す変数Jに0を、それぞれ代入する（ステップ806）。なお、荷物を特定するインデックスIやトラックを特定するインデックスJは0から開始するが、説明の便宜のため、インデックスIで特定される荷物L[I]をI番目の荷物と呼び、インデックスJで特定されるトラックをJ台目のトラックと呼ぶものとする。JとTを比較し（ステップ807）、JがT未満の場合には、以下の処理を実行する。
【００３２】
まず、荷物L[I]の供給拠点決定処理を実行する（ステップ808）。この処理は、供給拠点が確定していない荷物の供給拠点を需要拠点からの距離や現在の供給量から決定する処理である。この処理の詳細は図９で説明する。
【００３３】
次に、既に荷物が割り当てられているJ台目のトラックに荷物L[I]が積載可能かチェックする（ステップ809）。つまり、当該荷物を当該トラックに積載した場合に、トラックの積載量上限を超えることなく、かつ各荷物の集荷時間および配送時間が守れるかを、チェックする。もしステップ809で積載可能と判断された場合には、その荷物をJ台目のトラックに積載することによる、J台目のトラックの走行距離増分を変数Dに設定する（ステップ810）。DとVの値を比較し（ステップ811）、DがVよりも小さくなければ、Jに1を加え（ステップ813）て、ステップ807に戻り、次のトラックのチェックに移る。ステップ811でDの値が小さい場合には、XにJを、VにDの値を、supに荷物供給拠点の拠点IDを、それぞれ設定し（ステップ812）、Jに１を加え（ステップ813）、ステップ807に戻る。
【００３４】
ステップ807でJがT以上の場合には、まず変数Xの値が0未満かチェックする（ステップ814）。変数Xの値が0未満の場合には、既に荷物の割り当てを行っているトラックで当該荷物L[I]を積載可能なものが無かったということであるから、当該荷物L[I]の発拠点が保有するトラックを一台輸送用に新たに割り当て、そのトラックに当該荷物L[I]を積載する（ステップ815）。ステップ814で０未満でない場合には、当該荷物L[I]を積載可能なトラックが見つかっているということであるから、その荷物を当該X番目のトラックに積載する（ステップ816）。荷物をトラックに積載するというのは、要するに、そのトラックの輸送スケジュール情報（図３）に当該荷物の荷物IDと作業フラグを挿入するということである。
【００３５】
次に、荷物L[I]が空ケース荷物であるか否かチェックする(ステップ817)。空ケース荷物である場合は、荷物L[I]の発拠点の供給量（配列S内の当該拠点の荷物供給情報の供給荷物量(218)）からL[I]の荷物量を引く(ステップ818)。次にIに１を加え(ステップ819)、ステップ804に戻る。
【００３６】
図９は、図８中のステップ808の荷物供給拠点決定処理の詳細を示す処理フローである。
【００３７】
まず、処理対象である荷物情報L[I]を変数mに格納する(ステップ901)。次に、変数mに格納された荷物の供給拠点が確定しているかチェックする(ステップ902)。このチェックは、図５のステップ507で追加された荷物情報の発拠点ID(207)がnullである場合に未確定と判定するものである。供給拠点が確定していれば、その荷物は空ケース荷物ではない通常の荷物であるということであるから、そのまま処理を終了する。供給拠点が未確定の場合（空ケース荷物である場合）、まず拠点情報のインデクスを表す変数bに０を、Ｑに拠点数を、トラックの距離増分の最小値を格納する変数VVにMax_Valueを、決定した供給拠点を格納する変数ssupに-1を、それぞれ代入する(ステップ903)。
【００３８】
次に、bがQ未満であるか比較する(ステップ904)。bがQ以上なら処理を終了する。bがQ未満の場合、次に進む。まず、図８のステップ801で作成した供給量配列S[b]の供給荷物量(218)が、荷物mの荷物量すなわち空ケース荷物mの着拠点(208)における需要荷物量(214)以上であり、かつトラック（図８のステップ808の時点で処理対象としているJ台目のトラック）に積載可能かチェックする(ステップ905)。ここでトラックへの積載可能チェックは、図８のステップ809と同様の処理である。Yesの場合、変数DDに、当該トラックに当該空ケース荷物を積載したときの走行距離増分を格納する(ステップ906)。
【００３９】
次に、VVとDDを比較する(ステップ907)。DDがVVより小さい場合、いま注目している供給拠点がより良い供給拠点であるということであるから、供給拠点ssupにbを、VVにDDを代入するとともに、処理対象である空ケース荷物の荷物情報L[I]中の発拠点ID(207)に当該供給拠点の拠点IDを設定し(ステップ908)、ステップ909に進む。ステップ905でNoの場合、またはステップ907でNoの場合は、ステップ909に進む。bに１を加えて（ステップ909）、ステップ904に戻る。
【００４０】
なお、空ケース荷物の供給量は需要を満たすだけの十分な荷物量があるものとする。従って、ステップ904でNoと判定されて本処理を終了した場合、少なくとも１回はステップ908が実行されているはずであり、処理対象である荷物情報L[I]中の発拠点ID(207)には供給拠点の拠点IDが設定され、供給拠点ssupには必ず有効な拠点インデクスが格納されているはずである。
【００４１】
図１０は、図７中の改良処理（ステップ704）の詳細を示す処理フローである。まず、リスタートの現在の回数を表す変数Iに1を代入する（ステップ1001）。次に、IがM以下の場合（ステップ1002）に以下の処理を行う。ここで、Mは、改良処理での荷物再割り当てを実行する回数として予め設定された定数である。ステップ1002でIがMを超えた場合、処理を終了する。
【００４２】
まず、荷物が割り当てられている全トラックの積載率を算出する（ステップ1003）。変数Rに1から5までの整数をランダムに一つ選択して設定する（ステップ1004）。次に、積載率がR番目に悪いトラックに積載されている荷物を削除し（すなわち当該トラックに対応する輸送スケジュール情報（図３）に登録されている荷物を全て削除する）、削除した荷物の荷物情報を配列L2に格納する（ステップ1005）。次に、配列L2に登録されている荷物の発拠点と着拠点を巡回しているトラック全てを削除し（すなわちそれらのトラックに対応する輸送スケジュール情報（図３）に登録されている荷物を全て削除する）、それらのトラックに積載されていた荷物の荷物情報を配列L3に格納する（ステップ1007）。次に、配列L3の内容を全て配列L2に加える（ステップ1007）。ここまでで、積載率がR番目に悪いトラックとそのトラックが巡回する拠点を巡回する全てのトラックについて、輸送スケジュール情報が削除され、削除された荷物の荷物情報が配列L2に設定されたことになる。
【００４３】
次に、配列L2の要素である荷物情報の中で、図５中の荷物情報追加処理（ステップ507）で作成された空ケース荷物の荷物情報を探索し、探索された全ての空ケース荷物の荷物情報の発拠点ID(207)を取得し、それらの発拠点ID(207)の拠点の荷物供給情報の供給荷物量(218)に、当該空ケース荷物の荷物量(209)を加えるとともに、配列L2の当該空ケース荷物の荷物情報の発拠点ID(207)を全てnullに設定する(ステップ1008)。これにより、上記削除された荷物のうち空ケース荷物の荷物量が荷物供給情報に戻され、空ケース荷物の荷物情報の発拠点ID(207)も確定していない状態に戻されたことになる。
【００４４】
次に、この配列L2に格納されている荷物の再割り当てを行う（ステップ1009）。つまり、配列L2に格納されている荷物情報に対して、図８および図９の詳細フローで示した方法により積載可能なトラックに荷物を割り当てる。これは、図８および図９において配列Lを配列L2に置き換えた処理を行えばよい。次に、変数Iに1を加え（ステップ1010）、ステップ1002に戻る。
【００４５】
図１１は、図４中の結果出力処理（ステップ403）の詳細を示すフローである。まず、各トラックの通過拠点とルートを地図上に表示し（ステップ1101）、次に作成したスケジュールに対して、必要なトラック台数、総走行距離などの評価値を算出して表示する（ステップ1102）。空ケース荷物について、どのような割り当てが為されたか、それにより各拠点の需要量と供給量がどのように変化するかなどの情報を表示しても良い。次に、印刷の指示があれば、上記の情報を印刷装置に印刷する（ステップ1103）。
【００４６】
なお、上記実施形態では、空ケース荷物を荷物情報に追加する際に、需要情報に基づいて発拠点がnullのレコードを追加し、解を作成する段階で供給拠点を決定するようにしているが、逆に初めに供給情報に基づいて着拠点と荷物量がnullのレコードを荷物情報に追加し、解を作成する段階で需要拠点を決定するようにしてもよい。また、上記実施形態では空ケース荷物を例として説明したが、本発明は、空ケース荷物に限らず、発拠点と着拠点が未確定で各拠点ごとに需要量と供給量が決まっているような種々の荷物に適用可能である。
【図面の簡単な説明】
【００４７】
【図１】本実施形態のシステムを示す全体構成図である。
【図２】本実施形態で用いるデータの構造を示す図である。
【図３】本実施形態で用いるスケジュール情報のデータ構造を示す図である。
【図４】本実施形態の全体的な処理を示すフローチャート図である。
【図５】本実施形態の入力処理の詳細を示すフローチャート図である。
【図６】本実施形態の荷物情報追加処理の詳細を示すフローチャート図である。
【図７】本実施形態の輸送スケジュール作成処理の詳細を示すフローチャート図である。
【図８】本実施形態の初期解作成処理の詳細を示すフローチャート図である。
【図９】本実施形態の荷物供給拠点決定処理の詳細を示すフローチャート図である。
【図１０】本実施形態の改良処理の詳細を示すフローチャート図である。
【図１１】本実施形態の結果出力処理の詳細を示すフローチャート図である。
【符号の説明】
【００４８】
101…入力装置、102…出力装置、103…表示装置、104…処理装置、109…記憶装置、106…入力処理部、107…輸送スケジュール作成部、108…結果出力部、105…プログラム、110…拠点情報、111…拠点間中継情報、112…荷物情報、113…分割荷物情報、114…輸送車両情報、115…距離テーブル、116…道路地図、117…輸送スケジュール情報。
【図１】
2008230816.tif 000003
【図２】
2008230816.tif 000004
【図３】
2008230816.tif 000005
【図４】
2008230816.tif 000006
【図５】
2008230816.tif 000007
【図６】
2008230816.tif 000008
【図７】
2008230816.tif 000009
【図８】
2008230816.tif 000010
【図９】
2008230816.tif 000011
【図１０】
2008230816.tif 000012
【図１１】
2008230816.tif 000013