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