(57)【特許請求の範囲】
【請求項１】
少なくとも入出力装置と処理装置と記憶装置とを有し、複数の物流センターを含む物流網で出荷拠点から納入拠点への荷物の輸送を行う車両の輸送スケジュールを作成する輸送スケジュール作成システムであって、
物流センターと荷物の出荷・納入拠点の位置情報を含む拠点情報を登録する拠点情報登録手段と、
注文された各荷物の重量、容積、出荷・納入拠点、および出荷・納入の時間制約を含む注文情報を入力する注文情報登録手段と、
前記荷物の出荷・納入拠点の組合せ毎に、前記物流網上での中継拠点を設定する中継拠点情報登録手段と、
物流センター、出荷拠点、納入拠点、荷積み拠点、および／または荷下ろし拠点の各拠点が有する輸送車両数、およびそれらの輸送車両の積載重量上限と積載容積上限を含む輸送車両情報を入力する輸送車両情報登録手段と、
前記中継拠点情報によって分けられた各注文の輸送経路の荷積み拠点と荷下ろし拠点が同一の注文を容器に集約した容器輸送経路情報を生成する容器輸送経路情報生成手段と、
前記容器輸送経路情報の各経路を荷積みと荷下ろしの作業ごとに分割した輸送作業情報を生成するとともに、該輸送作業情報が含む作業開始可能時刻と作業開始限界時刻を、各注文の荷物が最も早く輸送されるスケジュールと最も遅く輸送されるスケジュールに基づいて設定する輸送作業情報生成手段と、
同一注文荷物を共有する別々の容器または経路において、その荷積み作業と荷下ろし作業が実行可能な時間枠が重複しないように、前記輸送作業情報の作業開始可能時刻と作業開始限界時刻を調整する時間枠設定手段と、
前記拠点情報、注文情報、中継拠点情報、輸送車両情報、容器輸送経路情報、および輸送作業情報を用いて、前記輸送作業情報が示す荷積み作業と荷下ろし作業を輸送車両に割り当てることにより、輸送スケジュールを作成する輸送スケジュール作成手段と、
作成した輸送スケジュールを出力するスケジュール出力手段と
を備えたことを特徴とする輸送スケジュール作成システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物流分野におけるトラック等の輸送スケジューリング作成を計算機で行う技術に関するものであり、具体的には計算機を利用した輸送計画の作成システムに関するものである。
【背景技術】
【０００２】
物流分野におけるトラック輸送等のスケジュールを計算機で作成するには、例えば非特許文献１に記載されているような線形計画法などの数理的な計算に基づくものや、スィープ法やNI法と言ったヒューリスティクスに基づくもの、また、非特許文献２に記載されているようなタブーサーチ、SA法(Simulated Annealing：焼きなまし法)、GA(Genetic Algorithm：遺伝的アルゴリズム)などメタヒューリスティクスと呼ばれる確率的手法を適用したものなど、多数の方式が用いられている。
【０００３】
これらの方式を具体的に物流分野に適用した技術で代表的なものとしては、例えば、下記特許文献１及び特許文献２に記載のものが知られている。
【０００４】
特許文献１に記載のものは、複数の配送先への荷物輸送のスケジュール作成を効率化する方式である。この方式では、各荷物の届け先が複数の塊に割付けられ、該塊内での各届け先を結ぶ配送ルートを作成する。これにより、エリア全体での配送時間の短縮を図るものである。
【０００５】
特許文献２に記載のものは、工場や物流センター、配送先などの拠点間の物流網の作成に、線形計画法や整数計画法などの数理的技法を適用したものである。この方式では、該文献の図に示されているように、工場や倉庫、配送先などの拠点をグラフのノードとして、ノード間のアークを荷物が流れるグラフで輸送を表現する。各アークには単位荷物量あたりの輸送コストや、そのアーク上を輸送できる上限荷物量、また、途中の物流センターの中継可能な荷物量上限などを与え、これを線形計画法や整数計画法でモデル化して問題を解き、荷物の出発地から最終目的地まで、どのような経路で輸送すれば物流網全体の輸送コストが最小になるかを決定する。
【非特許文献１】久保幹雄著「ロジスティクス工学」朝倉書店、2001年６月
【非特許文献２】柳浦睦憲、茨木秀俊著「組合せ最適化  −メタ戦略を中心として  −」朝倉書店、2001年1月
【特許文献１】特開平8-115495号公報
【特許文献２】特開2000-182179号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
特許文献１に記載の技術は、車両は車庫などの始発拠点を出発して物流センターまで走行し、その物流センターで荷物を積載して配送先を巡回して出発した物流センターに戻る輸送形態を想定したものである。ここでは、物流センターから配送先への配送で説明しているが、集荷先から物流センターへの集荷を行う場合も同様である。
【０００７】
しかし、実際の輸送では、ダンボールやパレットといった容器に、出発拠点と到着拠点が同一の複数荷物をまとめ、一括輸送したのち、物流センターでそれぞれの納入拠点への荷物として、容器の中身を再構成して輸送することがある。特許文献１のような手法では、物流センターでの容器の中身の再構成を考慮できないため、再構成前の荷物が物流センターに到着していない時刻から、再構成後の容器を輸送してしまうようなスケジュールを作成してしまい、矛盾が発生する可能性がある。また、再構成前後での容器は別々の車両に積載される可能性があるため、スケジュール時刻を決定するのに複数の車両に割り当てられた荷物を考慮しなければならなくなり、スケジュール作成を効率よく行うことができない。
【０００８】
本発明の目的は、物流センターでの容器の中身の再構成前後でのスケジュールの矛盾を回避し、効率的に輸送スケジュールを作成することにある。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明は、物流センターでの容器の中身の構成をスケジュール作成前に予め行い、スケジュールの矛盾が発生しないような容器の中身の再構成の実行可能な時間枠を算出して調整することで、スケジュール作成時に複数車両間での作業時間の依存関係を意識せずにスケジュールの作成を行うことを特徴とする。
【００１０】
すなわち、本発明は、少なくとも入出力装置と処理装置と記憶装置とを有し、複数の物流センターを含む物流網で出荷拠点から納入拠点への荷物の輸送を行う車両の輸送スケジュールを作成する輸送スケジュール作成システムであって、物流センターと荷物の出荷・納入拠点の位置情報を含む拠点情報を登録する拠点情報登録手段と、注文された各荷物の重量、容積、出荷・納入拠点、および出荷・納入の時間制約を含む注文情報を入力する注文情報登録手段と、前記荷物の出荷・納入拠点の組合せ毎に、前記物流網上での中継拠点を設定する中継拠点情報登録手段と、物流センター、出荷拠点、納入拠点、荷積み拠点、および／または荷下ろし拠点の各拠点が有する輸送車両数、およびそれらの輸送車両の積載重量上限と積載容積上限を含む輸送車両情報を入力する輸送車両情報登録手段と、前記中継拠点情報によって分けられた各注文の輸送経路の荷積み拠点と荷下ろし拠点が同一の注文を容器に集約した容器輸送経路情報を生成する容器輸送経路情報生成手段と、前記容器輸送経路情報の各経路を荷積みと荷下ろしの作業ごとに分割した輸送作業情報を生成するとともに、該輸送作業情報が含む作業開始可能時刻と作業開始限界時刻を、各注文の荷物が最も早く輸送されるスケジュールと最も遅く輸送されるスケジュールに基づいて設定する輸送作業情報生成手段と、同一注文荷物を共有する別々の容器または経路において、その荷積み作業と荷下ろし作業が実行可能な時間枠が重複しないように、前記輸送作業情報の作業開始可能時刻と作業開始限界時刻を調整する時間枠設定手段と、前記拠点情報、注文情報、中継拠点情報、輸送車両情報、容器輸送経路情報、および輸送作業情報を用いて、前記輸送作業情報が示す荷積み作業と荷下ろし作業を輸送車両に割り当てることにより、輸送スケジュールを作成する輸送スケジュール作成手段と、作成した輸送スケジュールを出力するスケジュール出力手段とを備えたことを特徴とする。
【発明の効果】
【００１１】
本発明によれば、複数の物流センターが含まれる物流網上の輸送スケジュールを作成することができる。特に、出発拠点と到着拠点が同一の複数荷物を容器にまとめ、一括輸送したのち、物流センターでそれぞれの納入拠点への荷物として、容器の中身を再構成して輸送する場合に、再構成前の荷物が到着していないのに再構成後の容器を輸送してしまうようなスケジュールを作成することがなく、矛盾が発生しないスケジュールを作成することができる。また、再構成前後での容器が別々の車両に積載される場合でも、スケジュール作成を効率よく行うことができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施の形態を図面に従って説明する。
【００１３】
図１は、本実施形態のシステムを示す全体構成図である。本システムは、入力装置（１０１）、プリンタなどの出力装置（１０２）、ディスプレイなどの表示装置（１０３）、処理装置（１０４）、および記憶装置（１０９）を備える。処理装置（１０４）は、入力処理部（１０６）、輸送スケジュール作成部（１０７）、および結果出力部（１０８）を含む一連のプログラム（１０５）を実行する。また、記憶装置（１０９）には、拠点情報（１１０）、拠点間中継情報（１１１）、注文情報（１１２）、輸送車両情報（１１３）、距離テーブル（１１４）、容器輸送経路情報（１１５）、輸送作業情報（１１６）、道路地図（１１７）、および、これらから作成される輸送スケジュール情報（１１８）が格納される。
【００１４】
図２は、記憶装置（１０９）に格納される情報の一例を示したものである。
【００１５】
拠点情報（１１０）には、物流センターや注文の出荷納入拠点などの拠点ごとに、その拠点を一意に識別する拠点ＩＤ（２０１）、その拠点の名称（２０２）、その拠点の住所（２０３）、および、その拠点の緯度（２０４）と経度（２０５）が格納される。拠点間中継情報（１１１）には、荷物を出荷拠点から納入拠点に輸送する場合に、その荷物が途中で経由する中継拠点つまり物流センターの情報が格納されている。具体的には、出荷拠点ＩＤ（２０６）、納入拠点ＩＤ（２０７）、その出荷拠点から納入拠点まで荷物を輸送する場合に経由する中継拠点の数Ｎ（２０８）、および、それら中継拠点のＩＤの配列（２０９〜２１２）が格納される。なお、この例では、出荷拠点は中継拠点０（２０９）、納入拠点は中継拠点Ｎ−１（２１２）としても格納されるものとし、拠点数Ｎ（２０８）は出荷拠点と納入拠点も含めた荷物の積み降ろし作業を行う全拠点の総数として格納されるものとする。
【００１６】
注文情報（１１２）には、注文された荷物を一意に識別する注文ＩＤ（２１３）、その荷物の出荷拠点ＩＤ（２１４）、その荷物の納入拠点ＩＤ（２１５）、その荷物の重量（２１６）と容積（２１７）、出荷拠点から出荷可能になる時刻を示す出荷時刻（２１８）、および、納入拠点への到着の締め切り時刻を示す納入時刻（２１９）が格納される。輸送車両情報（１１３）には、各拠点の保有する車両の情報を格納する。具体的には、車両を保有する拠点の拠点ＩＤ（２２０）、その拠点の保有車両数（２２１）、その保有車両の積載重量上限（２２２）と積載容積上限（２２３）が格納される。距離テーブル（１１４）には、スケジュール作成で必要になる、拠点間の車両などの輸送便での走行距離に関する情報が格納される。具体的には、出発拠点の拠点ＩＤ（２２４）、到着拠点の拠点ＩＤ（２２５）、それらの拠点間の距離（２２６）、およびそれらの拠点間を車両で走行する場合の所要時間（２２７）が格納される。
【００１７】
容器輸送経路情報（１１５）には、注文情報（１１２）の各輸送経路ごとに、荷積み拠点と荷下ろし拠点が同一のものを、ダンボールやパレットなどの容器にまとめた情報を格納する。具体的には、容器を特定するＩＤ（２２８）、その容器の輸送経路の順を表す経路番号（２２９）、経路総数（２３０）、その容器に詰められた注文荷物の総重量（２３１）、現在の空き容積（２３２）、その容器に詰められた注文ＩＤ（２３３）、および、その注文ＩＤの荷物の荷積みを行う中継拠点番号（２３４）が格納される。なお、１つの容器ＩＤに対して複数の注文ＩＤとその中継拠点番号を対応付けるものとする。例えば、注文ＩＤ＝Ｔ００１の荷物についてはその注文情報（１１２）から出荷拠点と納入拠点が分かり、さらに拠点間中継情報（１１１）を参照することで該出荷拠点から該納入拠点に至るまでの中継拠点が拠点０→拠点１→…→拠点Ｎ−１のように分かる（なお、拠点間中継情報（１１１）の拠点０、拠点１、…、拠点Ｎ−１はそれぞれ拠点ＩＤを格納する領域を示しているものであり、実際の中継拠点はそれらの各領域に格納されている拠点ＩＤで特定される）。その拠点０→拠点１の経路で当該注文ＩＤ＝Ｔ００１の荷物は所定の容器に詰められて輸送され、次の拠点１→拠点２の経路では別の容器に詰め替えて輸送され、…というようにして拠点Ｎ−１（納入拠点）まで輸送されるので、例えば拠点０→拠点１の経路で当該注文ＩＤ＝Ｔ００１の荷物を容器ＩＤ＝Ｙ００１の容器に詰めて輸送するのであれば該容器ＩＤかつ該注文ＩＤの容器輸送経路情報のレコード（この場合、該拠点０で示される拠点が荷積みの拠点であるから、中継拠点番号（２３４）には０が格納される）が１つ作られ、次の拠点１→拠点２の経路で当該注文ＩＤ＝Ｔ００１の荷物を容器ＩＤ＝Ｙ００２の容器に詰めて輸送するのであれば該容器ＩＤかつ該注文ＩＤの容器輸送経路情報のレコード（この場合、該拠点１で示される拠点が荷積みの拠点であるから、中継拠点番号（２３４）には１が格納される）が１つ作られ、…というように容器輸送経路情報のレコードが作られる。
【００１８】
さらに、１つの容器は、ある拠点から次の拠点に輸送された後、また荷物が詰め替えられてその拠点から次の拠点へと輸送されていくので、同じ容器ＩＤ（２２８）で、それが輸送されていく経路の順番で経路番号（２２９）を１，２，３，…の順に付けた複数の容器輸送経路情報レコードが作られることになる。また、１つの容器が１つの経路を輸送される際には、その容器に幾つかの注文ＩＤに対応する荷物が詰められるので、同一容器ＩＤ（２２８）かつ同一経路番号（２２９）でその荷物数分の容器輸送経路情報レコードが作られる。それら同一容器ＩＤ（２２８）かつ同一経路番号（２２９）の荷物数分の容器輸送経路情報レコードは、その容器に詰められて輸送される荷物の注文ＩＤごとに作られ、それらの各レコードの経路総数（２３０）と重量（２３１）と空き容積（２３２）はそれぞれ同一である。また、同一容器ＩＤ（２２８）かつ同一経路番号（２２９）の各レコードの注文ＩＤ（２３３）とその中継拠点番号（２３４）が表す実際の経路、つまり荷積み拠点と荷下ろし拠点は全て同一となる。例えば、同一容器ＩＤ＝Ｙ００１かつ同一経路番号の容器輸送経路情報レコードが３レコードあり、１つ目のレコードは注文ＩＤ＝Ｔ００１かつ中継拠点番号＝０、２つ目のレコードは注文ＩＤ＝Ｔ００２かつ中継拠点番号＝２、３つ目のレコードは注文ＩＤ＝Ｔ００３かつ中継拠点番号＝５であったとすると、注文ＩＤ＝Ｔ００１の荷物の経路のうち拠点０→拠点１の実際の経路と、注文ＩＤ＝Ｔ００２の経路のうち拠点２→拠点３の実際の経路と、注文ＩＤ＝Ｔ００３の経路のうち拠点５→拠点６の実際の経路とは同一であるということである。
【００１９】
輸送作業情報（１１６）には、容器輸送経路情報（１１５）の各容器ＩＤとその輸送経路に対して、経路の端点である出発拠点の荷積み作業と到着拠点の荷下ろし作業ごとに分割し、それらの各作業が実行可能な時間枠を表す情報を格納する。具体的には、作業を特定するＩＤ（２３５）、容器ＩＤ（２３６）、容器の経路番号（２３７）、作業を行う拠点のＩＤ（２３８）、荷積みまたは荷下ろし作業を表す作業内容（２３９）、容器重量や容積に応じて積み下ろし作業にかかる作業時間（２４０）、作業が開始できる時刻を表す作業開始可能時刻（２４１）、および、作業を開始しなければならない限界の時刻を表す作業開始限界時刻（２４２）を格納する。容器ＩＤ（２３６）と容器の経路番号（２３７）が与えられれば、容器輸送経路情報（１１５）を参照することで、その容器かつ経路で輸送すべき全注文の注文ＩＤと当該経路の出発拠点が分かる。また、それらの注文の中の１つの注文情報を参照して出荷納入拠点を取得し、さらにその出荷納入拠点に対応する拠点間中継情報（１１１）を参照することで、当該経路の出発拠点に対応する到着拠点も分かる。当該経路の出発拠点ではそれらの注文の荷物の荷積み作業を行い、到着拠点ではそれらの注文の荷物の荷下ろし作業を行うから、輸送作業情報（１１６）は、当該荷積み作業で１レコード、当該荷下ろし作業で１レコードが作成されることになる。これらの各作業毎の作業開始可能時刻（２４１）から作業開始限界時刻（２４２）までの時間枠は、要するに、その作業（荷積みまたは荷下ろし）を開始する時間がその時間枠に入っている必要がある時間帯を表わしているから、各車両にこれらの作業を割り当て、かつ、割り当てたときに上記時間枠の制限を満たしているようにして、輸送スケジュールを作成すればよい。
【００２０】
なお、不図示であるが、道路地図（１１７）は、上記距離テーブル（１１４）の作成に必要な拠点間距離の計算や結果の出力に用いるための輸送区域の道路情報を示す。
【００２１】
図３は、輸送スケジュール作成部（１０７）で作成される輸送スケジュール情報（１１８）の一例を示している。輸送スケジュール情報（１１８）は、本発明に係る方法によって作成される輸送計画中で輸送車両が巡回する拠点での作業を、それら作業の順番に従って並べたものである。具体的には、車両Ｎｏ（３０１）、出発拠点ＩＤ（３０２）、当該車両に割り当てられた作業数（３０３）、および、割り当てられた作業ＩＤ（３０４，３０５，…）からなる。ここでの作業とは、輸送作業情報（１１６）で与えられている輸送作業情報レコードを指し、この例では拠点での荷積みまたは荷下ろし作業をそれぞれ１作業としている。
【００２２】
図４は、図１中の処理装置（１０４）が実行するプログラム（１０５）の概要を示すフローチャートである。まず入力処理（ステップ４０１）で、拠点情報（１１０）、拠点間中継情報（１１１）、注文情報（１１２）、輸送車両情報（１１４）等の輸送スケジュールを作成するために必要な情報をユーザが入力（登録）し、それらの情報に従って容器輸送経路情報（１１５）と輸送作業情報（１１６）を生成する。この処理の詳細は図５で後述する。次の輸送スケジュール作成処理（ステップ４０２）では、入力処理ステップで与えられた条件に合致する輸送スケジュールを作成する。ここで輸送スケジュールの作成とは、入力された全ての注文荷物を、それぞれの出荷拠点から納入拠点に届ける車両が従うスケジュールを決定することを指す。この処理の詳細は図９で後述する。次に、結果出力処理（ステップ４０３）では、作成した輸送スケジュールを出力する。この処理の詳細は図１２で後述する。
【００２３】
図５は、図４中の入力処理（ステップ４０１）の詳細を示すフローチャートである。まず、拠点情報登録処理（ステップ５０１）で、拠点情報（１１０）の登録を行う。次に、注文情報登録処理（ステップ５０２）で、注文情報（１１２）の登録を行う。次に、輸送車両情報登録処理（ステップ５０３）で、輸送車両情報（１１３）の登録を行う。次に、距離テーブル生成処理（ステップ５０４）で、拠点間の距離と車両による走行所要時間を道路地図（１１７）を参照して生成し、距離テーブル（１１４）を生成する。なお、道路地図（１１７）は予め用意されているものとする。次に、拠点間中継情報登録処理（ステップ５０５）で、拠点間中継情報（１１１）の登録を行う。
【００２４】
次に、容器輸送経路情報生成処理（ステップ５０６）では、ステップ５０２，５０５で登録した注文情報（１１２）と拠点間中継情報（１１１）を用いて容器輸送経路情報（１１５）を作成する処理を行う。この処理の詳細は図６で後述する。輸送作業情報生成処理（ステップ５０７）では、ステップ５０６で生成された容器輸送経路情報（１１５）をもとに、車両に割り当てる輸送作業を表す輸送作業情報（１１６）を生成する処理を行う。この処理の詳細は図７に後述する。時間枠設定処理（ステップ５０８）では、ステップ５０７で生成された輸送作業情報（１１６）の作業時間枠（作業開始可能時刻（２４１）と作業開始限界時刻（２４２））を設定する処理を行う。この処理の詳細は図８で後述する。
【００２５】
図６は、図５中の容器輸送経路情報生成処理（ステップ５０６）の詳細を示すフローチャートである。まず、容器輸送経路情報テーブルｃａｓｅを空にする（ステップ６０１）。容器輸送経路情報テーブルｃａｓｅは、作成した容器輸送経路情報（１１５）の各レコードを設定するテーブルである。次に、注文情報テーブルｏｒｄｅｒに登録されている注文情報（１１２）のレコードを容積の大きい順にソートする（ステップ６０２）。注文情報テーブルｏｒｄｅｒは、図５のステップ５０２で登録された注文情報（１１２）の全レコードを格納したテーブルである。次に、ｏｒｄｅｒのインデクス変数ｉに０を代入する（ステップ６０３）。次に、ｉと注文数を比較する（ステップ６０４）。ｉが注文数以上の場合は、全ての注文に対して容器輸送経路情報（１１５）を作成し終えたということであるから、処理を終了する。ｉが注文数未満の場合はステップ６０５に進む。
【００２６】
次に、変数Ｐに、ｏｒｄｅｒ［ｉ］の注文情報レコードの出荷納入拠点ＩＤ（２１４，２１５）と一致する出荷納入拠点ＩＤ（２０６，２０７）を持つ拠点間中継情報（１１１）のレコードを代入する（ステップ６０５）。変数Ｐは図２の拠点間中継情報（１１１）のフォーマットを持ち、ステップ６０５で注文情報ｏｒｄｅｒ［ｉ］の注文に対応する拠点間中継情報が代入されたことになる。次に、中継拠点の位置を示すインデックス変数ｒに０を代入する（ステップ６０６）。次に、ｒとＰの拠点数−１を比較する（ステップ６０７）。ｒの方が小さい場合はステップ６０８に進み、そうでない場合はステップ６１６に進む。
【００２７】
次に、変数ｂｆにＰのｒ番目の中継拠点ＩＤ（Ｐの中継拠点ｒの拠点ＩＤ）を代入し、ｂｔにＰのｒ＋１番目の中継拠点ＩＤ（Ｐの中継拠点ｒ＋１の拠点ＩＤ）を代入し、新規の容器輸送経路情報レコードＮ（ワーク領域）を準備し、該Ｎにｏｒｄｅｒ［ｉ］の注文ＩＤと中継拠点番号ｒを代入する（ステップ６０８）。次に、ワーク用の配列Ｋに、ｃａｓｅの中の容器輸送経路情報レコードのうち、空き容積がｏｒｄｅｒ［ｉ］の容積以上でかつ拠点ｂｆから拠点ｂｔへ輸送する全てのレコードを格納する（ステップ６０９）。次に、Ｋのレコード数を調べる（ステップ６１０）。レコード数が１以上ならステップ６１１に進み、０ならステップ６１３に進む。ステップ６１１に進むのは、要するにｏｒｄｅｒ［ｉ］の注文の荷物を詰めることができる容器が見つかった場合である。なお、図２（ｂ）から分かるように、拠点間中継情報（１１１）の各中継拠点を特定するインデックスは０から開始するが、説明の便宜のため、中継拠点ｒをｒ番目の中継拠点、中継拠点ｒ＋１をｒ＋１番目の中継拠点というように呼ぶことがある（以下、０から開始されるインデックスについては同様）。
【００２８】
配列Ｋに１以上のレコードがある場合、容器輸送経路情報レコードＮに、Ｋ［０］（複数の容器が見つかった場合、最初の１個目を利用する）の、容器ＩＤ、経路番号、経路総数、重量、および空き容積をコピーする（ステップ６１１）。次に、ＮとＫの全レコードに対して、重量に注文重量（ｏｒｄｅｒ［ｉ］の重量）を加算し、空き容積から注文容積（ｏｒｄｅｒ［ｉ］の容積）を減算する（ステップ６１２）。ステップ６１０でＫにレコードがなかった場合は、要するにｏｒｄｅｒ［ｉ］の注文の荷物を詰めることができる容器が見つからなかったということであるから、Ｎの容器ＩＤに新規の容器ＩＤを代入し、経路番号に１を、経路総数に１を、重量に注文重量を、空き容積に容器容積から注文容積を引いたものを、それぞれ代入する（ステップ６１３）。
【００２９】
次に、Ｎを容器輸送経路情報（１１５）のテーブルｃａｓｅに追加する（ステップ６１４）。次にｒに１を加えて（ステップ６１５）、ステップ６０７に戻る。ステップ６０７でｒがＰの拠点数−１以上なら、ｉに１を加えて（ステップ６１６）、ステップ６０４に戻る。なお、上記の配列Ｋは、ポインタ変数を利用して容器輸送経路情報テーブルｃａｓｅ内のレコードを直接アクセスしているので、ステップ６１２における配列Ｋへの修正はそのまま容器輸送経路情報テーブルｃａｓｅ内のレコードに反映されるものとする。
【００３０】
図７は、図５中の輸送作業情報生成処理（ステップ５０７）の詳細を示すフローチャートである。まず、容器輸送経路情報（１１５）の各容器ＩＤとその各経路番号に対し、その経路の出発拠点での荷積み作業と到着拠点での荷下ろし作業の２作業を輸送作業情報ｗｏｒｋに格納する（ステップ７０１）。この処理は、容器輸送経路情報（１１５）の全レコードを容器ＩＤ（２２８）と経路番号（２２９）が同じもの同士でグループ分けし、その１グループに対してその経路の出発拠点での荷積み作業の輸送作業情報レコードと到着拠点での荷下ろし作業の輸送作業情報レコードを作成し、作成した全ての輸送作業情報レコードをｗｏｒｋに格納するものである。この際、輸送作業情報レコードの作業ＩＤ（２３５）は各作業を特定できるＩＤを格納し、容器ＩＤ（２３６）、経路番号（２３７）、作業拠点ＩＤ（２３８）、作業内容（２３９）、および作業時間（２４０）についても容器輸送経路情報やそこから探索した情報から求めた値を格納するものとする。
【００３１】
次に、ステップ７０１で作成したｗｏｒｋの全輸送作業情報レコードの作業開始可能時刻（２４１）に０を、作業開始限界時刻（２４２）にＭａｘＶａｌｕｅを、それぞれ代入する（ステップ７０２）。ここでＭａｘＶａｌｕｅは計算機で扱える整数の最大値である。次に、注文情報インデクス変数ｉに０を代入する（ステップ７０３）。次に、ｉと注文数を比較する（ステップ７０４）。ｉが注文数以上なら処理を終了する。ｉが注文数未満なら以下の処理を実行する。
【００３２】
まず、注文ｏｒｄｅｒ［ｉ］の荷物を最も早く輸送できるスケジュールをｏＦａｓｔに格納し、さらにｏｒｄｅｒ［ｉ］の輸送をこれ以上遅らせることができない最遅のスケジュールをｏＬａｔｅに格納する（ステップ７０５）。これらのスケジュールは、当該注文の出荷時刻と納入時刻、拠点間中継情報、および距離テーブルから算出する。ｏＦａｓｔとｏＬａｔｅのフォーマットは図３の輸送スケジュール情報と同様のものでよいが、特に、注文ｏｒｄｅｒ［ｉ］の荷物を出荷拠点から納入拠点まで中継拠点０→１→…→Ｎ−１と輸送する場合の各中継拠点での荷積み作業と荷下ろし作業の作業ＩＤとその作業開始時刻が格納されていればよい。
【００３３】
次に、注文ｏｒｄｅｒ［ｉ］の荷物を中継する各中継拠点を特定するためのインデックス変数ｒに０を代入する（ステップ７０６）。次に、ｒとｏｒｄｅｒ［ｉ］の中継拠点数を比較する（ステップ７０７）。ｒが中継拠点数−１以上ならステップ７１５に進み、ｉに１を加えて（ステップ７１５）、ステップ７０４に戻る。ステップ７０７でｒが拠点数−１未満なら以下の処理を実行する。なお、以下で「中継拠点ｒ」と言っているのは、注文ｏｒｄｅｒ［ｉ］の注文情報の出荷納入拠点（２１３，２１４）と同じ出荷納入拠点（２０６，２０７）を持つ拠点間中継情報（１１１）の中継拠点０，１，…，Ｎ−１（２０９〜２１２）のうち、インデックスｒで特定される中継拠点ｒを示すものである。
【００３４】
まず、変数Ｗｕに注文ｏｒｄｅｒ［ｉ］の中継拠点ｒ→ｒ＋１の経路を含む容器の中継拠点ｒにおける荷積み作業レコード（ｗｏｒｋに展開されている輸送作業情報レコードのうち、ｏｒｄｅｒ［ｉ］の荷物を詰めてその中継拠点ｒ→ｒ＋１の経路を輸送する容器の容器ＩＤと経路番号を持つ容器輸送経路情報レコードから作成した中継拠点ｒにおける荷積み作業を示す輸送作業情報レコード）を代入する（ステップ７０８）。次に、Ｗｕの作業開始可能時刻（２４１）を、当該作業開始可能時刻（２４１）の現在値とｏＦａｓｔに格納されている当該作業の作業開始時刻とのｍａｘをとって、更新する（ステップ７０９）。同様に、Ｗｕの作業開始限界時刻（２４２）を、当該作業開始限界時刻（２４２）の現在値とｏＬａｔｅに格納されている当該作業の作業開始時刻とのｍｉｎをとって、更新する（ステップ７１０）。次に、変数Ｗｄに注文ｏｒｄｅｒ［ｉ］の中継拠点ｒ→ｒ＋１の経路を含む容器の中継拠点ｒ＋１における荷下ろし作業レコード（ｗｏｒｋに展開されている輸送作業情報レコードのうち、ｏｒｄｅｒ［ｉ］の荷物を詰めてその中継拠点ｒ→ｒ＋１の経路を輸送する容器の容器ＩＤと経路番号を持つ容器輸送経路情報レコードから作成した中継拠点ｒ＋１における荷下ろし作業を示す輸送作業情報レコード）を代入する（ステップ７１１）。次に、Ｗｄの作業開始可能時刻（２４１）を、当該作業開始可能時刻（２４１）の現在値とｏＦａｓｔに格納されている当該作業の作業開始時刻とのｍａｘをとって、更新する（ステップ７１２）。同様に、Ｗｄの作業開始限界時刻（２４２）を、当該作業開始限界時刻（２４２）の現在値とｏＬａｔｅに格納されている当該作業の作業開始時刻とのｍｉｎをとって、更新する（ステップ７１３）。次に、ｒに１を加えて（ステップ７１４）、ステップ７０７に戻る。なお、ステップ７０８から７１３ではｗｏｒｋ内の作業レコードを直接ＷｕやＷｄでアクセスするので、ステップ７０９，７１０，７１２，７１３におけるデータの更新はｗｏｒｋ内の作業レコードの更新となる。
【００３５】
上記の処理により、全ての注文の全ての経路（中継拠点間経路）に対してステップ７０８〜７１０が実行されるので、各拠点間経路の出発拠点での荷積み作業に関する輸送作業情報レコードにおいては、そこで荷積みする全ての注文の最早輸送スケジュールの作業開始時刻のｍａｘを採って作業開始可能時刻（２４１）とし、そこで荷積みする全ての注文の最遅輸送スケジュールの作業開始時刻のｍｉｎを採って作業開始限界時刻（２４２）としている。設定された作業開始可能時刻（２４１）は、それらの注文の荷物が最も早く輸送されるスケジュールのうちで最も遅い時刻であるから、要するにそれらの荷物の荷積み作業が開始できるようになる時刻を示している。また、設定された作業開始限界時刻（２４２）は、それらの注文の荷物が最も遅く輸送されるスケジュールのうちで最も早い時刻であるから、要するにそれらの荷物の荷積み作業を遅くともこの時刻までに開始しなければならない限界の時刻を示している。ステップ７１１〜７１３の荷下ろし側も同様である。
【００３６】
図８は、図５中の時間枠設定処理（ステップ５０８）の詳細を示すフローチャートである。まず、作業開始可能時刻更新リストｕｔｉｍｅａｒｒａｙと作業開始限界時刻更新リストｄｔｉｍｅａｒｒａｙを初期化する（ステップ８０１）。これらの２つのリストは、各作業ＩＤとそれらの作業ＩＤにそれぞれ対応する作業開始可能時刻および作業開始限界時刻を格納するリストであり、初期化処理では現在の輸送作業情報ｗｏｒｋのデータを設定する。
【００３７】
次に、容器ＩＤを特定するインデクスｉに０を代入する（ステップ８０２）。次に、ｉと容器数を比較する（ステップ８０３）。ｉが容器数以上の場合は、全ての容器について処理が終了したということであるから、ｕｔｉｍｅａｒｒａｙとｄｔｉｍｅａｒｒａｙの内容を輸送作業情報ｗｏｒｋ（１１６）に格納して（ステップ８１４）、処理を終了する。ステップ８０３で、ｉが容器数未満の場合は以下を実行する。
【００３８】
まず、容器の経路番号を表す変数ｒに０を代入する（ステップ８０４）。次に、ｒとその容器の経路総数を比較する（ステップ８０５）。ｒが経路総数以上なら、その容器については全経路の処理が終了したということであるから、ｉに１を加えて（ステップ８１３）、ステップ８０３に戻る。ｒが経路総数未満の場合は以下を実行する。
【００３９】
まず、ｉ番目の容器ＩＤの経路ｒに含まれている各注文に対し、その次の輸送経路で輸送される容器経路荷積み作業の輸送作業レコードの配列をＮｗｏｒｋに格納する（ステップ８０６）。いま、ｉ番目の容器ＩＤの経路ｒに含まれている全ての注文を「注文群Ａ」と呼ぶことにすると、注文群Ａの第１の注文について当該注文の次の輸送経路での荷積み作業に対応する輸送作業レコードをＮｗｏｒｋに格納し、同様に、注文群Ａの第２、第３、…の注文についてもそれぞれ次の輸送経路での荷積み輸送作業レコードをＮｗｏｒｋへ格納するということである。これらＮｗｏｒｋに格納された荷積み輸送作業レコードは、上記経路ｒの到着拠点（この拠点を「拠点Ｂ」と呼ぶ）で、ｉ番目の容器ＩＤの容器から荷下ろしされた荷物を次の輸送経路に乗せるための各荷積み作業を表している。次に、変数ｑに、Ｎｗｏｒｋに格納された荷積み輸送作業レコードの荷積み作業開始可能時刻（２４１）の最小値を代入する（ステップ８０７）。この値は、拠点Ｂにおいて注文群Ａの各荷物をそれぞれ次の輸送経路に積み換える際の荷積みが可能になる時刻のうち最も早い時刻を示している。
【００４０】
次に、Ｎｗｏｒｋが指す全容器に対し、その容器に詰められている各荷物の前経路を含む容器の荷下ろし作業配列をＰｗｏｒｋに格納する（ステップ８０８）。次に、変数ｐに、Ｐｗｏｒｋに格納された荷下ろし作業レコードの荷下ろし作業開始限界時刻＋作業時間の最大値を代入する（ステップ８０９）。次に、変数ｄにｐ＋（ｑ−ｐ）／２を代入する（ステップ８１０）。次に、Ｎｗｏｒｋの全作業に対してｕｔｉｍｅａｒｒａｙをｄで更新し、Ｐｗｏｒｋの全作業に対してｄｔｉｍｅａｒｒａｙをｄ−作業時間で更新する（ステップ８１１）。次に、ｒに１を加えて（ステップ８１２）、ステップ８０５に戻る。以上の処理は、要するに、ある中継拠点で荷下ろしをして、次の経路へと荷積みする際の荷下ろし作業と荷積み作業の時間帯を分けることを行っている。これにより、荷下ろしが終わっていないのに荷積みが開始されるようなスケジュールを作成することが無くなる。
【００４１】
図９は、図４中の輸送スケジュール作成処理（ステップ４０２）の詳細を示す処理フローである。
【００４２】
時間枠設定処理（ステップ５０８）により各作業を行うべき時間枠が設定されているので、スケジュールの作成では個々の注文に対する作業時間の矛盾を意識せずに、組み合わせ最適化問題として、非特許文献１や非特許文献２に説明されているような、ヒューリスティクスを用いた技法や、ＧＡ、タブーサーチ、ＳＡ法などのメタヒューリスティクスに分類される技法などが利用できる。本実施形態では、メタヒューリスティクスの中のランダムリスタート法を適用している。つまり、ランダムな条件下で初期解（スケジュール）を作成し、それを改良処理でより良いスケジュールに改良する。この初期解の作成と改良を複数回繰り返し、その中で最良のスケジュールを選択するものである。
【００４３】
まず、変数Ｉに１を設定し、Ｂｅｓｔ＿ＶａｌｕｅにＭａｘ＿Ｖａｌｕｅを設定する（ステップ９０１）。ここでＭａｘＶａｌｕｅは、使用する計算機で表現可能な最大の数値を表す。次に、ＩがＮより小さい場合（ステップ９０２）、次の処理を繰り返す。ここで、Ｎは、ランダムリスタートで初期解の作成と、その初期解の改良を行う回数であり、予め定められている定数である。
【００４４】
まず初期解の作成を行う（ステップ９０３）。この処理の詳細は図１０で説明する。次に、作成した初期解の改良を行う（ステップ９０４）。この処理の詳細は図１１で説明する。次に、スケジュール結果の評価を行う（ステップ９０５）。この評価とは、ステップ９０４で改良されたスケジュール結果から、使用する車両台数およびその走行距離から輸送に要する概算のコストを求める処理である。この計算方法は、車両台数だけで評価する方法や、輸送車両の総走行距離で評価する方法、また、車両台数と予め定めた輸送車両一台あたりの固定費の積と、総走行距離と予め定めた単位距離あたりの変動費の積の和で評価する方法などが、挙げられる。ステップ９０５で算出された評価結果（評価値）は、変数Ｅに代入される。この評価値が、小さい方が、より評価が高いことを意味する。
【００４５】
次に、評価結果が格納されている変数ＥとＢｅｓｔ＿Ｖａｌｕｅの値を比較し（ステップ９０６）、ＥがＢｅｓｔ＿Ｖａｌｕｅよりも小さい場合には、今回のスケジュール結果（輸送スケジュール情報（１１８））がいままでの中でベストの結果であるということだから、Ｅの値をＢｅｓｔ＿Ｖａｌｕｅに代入し（ステップ９０７）、作成したスケジュール結果をＢｅｓｔ＿Ｓｃｈｅｄｕｌｅに記録する（ステップ９０８）。要するに、スケジュール改良処理によって評価がよくなったら、そのときのスケジュールを保存するものである。次に変数Ｉに１を加え、ステップ９０２に戻る。ステップ９０２でＩがＮ以上になれば処理を終える。
【００４６】
図１０は、図９中の初期解作成処理（ステップ９０３）の詳細を示す処理フローである。この処理では、輸送作業情報（１１６）の各作業を何れかの車両に割り当てる初期解を作成する。
【００４７】
まず、輸送作業情報（１１６）の荷積み側の全レコードを配列Ｌに格納する（ステップ１００１）。次に、配列Ｌに格納されている輸送作業レコードをランダムな順序に並べ換える（ステップ１００２）。変数Ｐに配列Ｌに格納した作業数を、作業情報インデクスを表す変数Ｉに０を、それぞれ設定する（ステップ１００３）。ＩとＰの値を比較し（ステップ１００４）、ＩがＰ以上なら処理を終える。ＩがＰ未満の間は、以下の処理を行う。
【００４８】
まず、変数Ｔに、既に作業を割り当てた車両の台数を格納する（ステップ１００５）。次に、車両に作業を割り当てたときの距離増分の最小値を格納する変数ＶにＭａｘ＿Ｖａｌｕｅ、距離増分が最小となるときの車両のインデクスを表す変数Ｘに−１、作業割り当てをチェックしようとしている車両のインデクスを表す変数Ｊに０を、それぞれ代入する（ステップ１００６）。ＪとＴを比較し（ステップ１００７）、ＪがＴ未満の場合には、既に作業が割り当てられているＪ台目の車両にＬ［Ｉ］に格納されている荷積み作業とそれに対応する荷下ろし作業の積載（その作業に係る荷物を荷積みし、輸送して、荷下ろしすること）が可能かチェックする（ステップ１００８）。つまり、これらの作業をその車両に割り当てた場合に、その車両の重量上限や容積上限を超えることなく、かつその作業を割り当てた場合の作業開始時刻の時間枠が守れるかを、チェックする。もしステップ１００８で積載可能と判断された場合には、その荷積み荷下ろし作業をＪ台目の車両に割り当てることによる、Ｊ台目の車両の走行距離増分を変数Ｄに設定する（ステップ１００９）。ＤとＶの値を比較し（ステップ１０１０）、ＤがＶよりも小さくなければ、Ｊに１を加え（ステップ１０１２）て、ステップ１００７に戻り、次の車両のチェックに移る。ステップ１００９でＤの値が小さい場合には、ＸにＪを、ＶにＤの値を、それぞれ設定し（ステップ１０１１）、Ｊに１を加え（ステップ１０１２）、ステップ１００７に戻る。
【００４９】
ステップ１００７でＪがＴ以上の場合には、まず変数Ｘの値が−１かチェックする（ステップ１０１３）。−１でない場合には、荷積み作業Ｌ［Ｉ］とそれに対応する荷下ろし作業を積載可能な車両が見つかっているので、それらの作業をＸ番目の車両に積載し（ステップ１０１７）、変数Ｉに１を加え（ステップ１０１６）、ステップ１００４に戻り、次の荷積み作業の処理に移る。ステップ１０１３で変数Ｘの値が−１の場合には、既に作業の割り当てを行っている車両で積載可能なものが無かったので、荷積み作業Ｌ［Ｉ］の作業拠点の保有する車両を一台輸送用に新たに割り当て、その車両に荷積み作業Ｌ［Ｉ］と対応する荷下ろし作業を割り当て（ステップ１０１４）、ステップ１０１６に進む。
【００５０】
図１１は、図９中の改良処理（ステップ９０４）の詳細を示す処理フローである。まず、変数Ｉに１を代入する（ステップ１１０１）。次に、Ｉが１０に満たない場合（ステップ１１０２）に以下の処理を行う。なお、この値「１０」は、改良処理での作業の再割り当てを実行する回数として予め定めた値である。ステップ１１０２でＩが１０以上になった場合は処理を終了する。
【００５１】
まず、作業が割り当てられている全車両の積載率を算出する（ステップ１１０３）。変数Ｒに１から５までの整数をランダムに一つ選択して設定する（ステップ１１０４）。次に、積載率がＲ番目に悪い車両に積載されている作業を削除し、削除した荷積み作業を配列Ｌに追加する（ステップ１１０５）。次に、配列Ｌに登録されている作業の荷積み拠点と荷下ろし拠点を巡回している他の車両全てを削除し、それらの車両に割り当てられていた作業の荷積み側を配列Ｍに格納する（ステップ１１０６）。次に、配列Ｌに配列Ｍの内容を加える（ステップ１１０７）。次に、この配列Ｌに格納されている荷積み作業の再スケジュールを行う（ステップ１１０８）。つまり、配列Ｌに格納されている作業に対して、図１０の詳細フローで示した方法により積載する車両を割り当てる。次に、変数Ｉに１を加え（ステップ１１０９）、ステップ１１０２に戻る。
【００５２】
図１２は、図４中の結果出力処理（ステップ４０３）の詳細を示すフローである。まず、各車両の通過拠点とルートを地図上に表示し（ステップ１２０１）、次に作成したスケジュールに対して、必要な車両台数、総走行距離などの評価値を算出して表示する（ステップ１２０２）。次に、印刷の指示があれば、上記の情報を印刷装置に印刷する（ステップ１２０３）。
【図面の簡単な説明】
【００５３】
【図１】本実施形態のシステムを示す全体構成図である。
【図２】本実施形態で用いるデータの構造を示す図である。
【図３】本実施形態で用いるスケジュール情報のデータ構造を示す図である。
【図４】本実施形態の全体的な処理を示すフローチャート図である。
【図５】本実施形態の入力処理の詳細を示すフローチャート図である。
【図６】本実施形態の容器輸送経路情報生成処理の詳細を示すフローチャート図である。
【図７】本実施形態の輸送作業情報生成処理の詳細を示すフローチャート図である。
【図８】本実施形態の作業時間枠設定処理の詳細を示すフローチャート図である。
【図９】本実施形態の輸送スケジュール作成処理の詳細を示すフローチャート図である。
【図１０】本実施形態の初期解作成処理の詳細を示すフローチャート図である。
【図１１】本実施形態の改良処理の詳細を示すフローチャート図である。
【図１２】本実施形態の結果出力処理の詳細を示すフローチャート図である。
【符号の説明】
【００５４】
１０１…入力装置、１０２…出力装置、１０３…表示装置、１０４…処理装置、１０９…記憶装置、１０６…入力処理部、１０７…輸送スケジュール作成部、１０８…結果出力部、１０５…プログラム、１１０…拠点情報、１１１…拠点間中継情報、１１２…注文情報、１１３…輸送車両情報、１１４…距離テーブル、１１５…容器輸送経路情報、１１６…輸送作業情報、１１７…道路地図、１１８…輸送スケジュール情報。
【図１】
0005382844.tif 000002
【図２】
0005382844.tif 000003
【図３】
0005382844.tif 000004
【図４】
0005382844.tif 000005
【図５】
0005382844.tif 000006
【図６】
0005382844.tif 000007
【図７】
0005382844.tif 000008
【図８】
0005382844.tif 000009
【図９】
0005382844.tif 000010
【図１０】
0005382844.tif 000011
【図１１】
0005382844.tif 000012
【図１２】
0005382844.tif 000013