JP3586822B2

JP3586822B2 - Method and system for creating transport relay plan

Info

Publication number: JP3586822B2
Application number: JP35416798A
Authority: JP
Inventors: 隆小野山; 仙久保田; 拓也前川
Original assignee: Hitachi Software Engineering Co Ltd
Current assignee: Hitachi Software Engineering Co Ltd
Priority date: 1998-12-14
Filing date: 1998-12-14
Publication date: 2004-11-10
Anticipated expiration: 2018-12-14
Also published as: JP2000182179A

Description

【０００１】
【発明の属する技術分野】
本発明は、物流システムにおける中継拠点を経由する輸送便（トラック便）の発拠点と着拠点間の中継拠点における荷物の中継計画作成方法およびシステムに係り、特に、宅配便などの効率的な配送のための輸送ルートや中継計画の調整に利用し、物流コストの削減やサービス性の向上を実現する輸送計画を作成する方法およびシステムに関する。
【０００２】
【従来の技術】
物流システムでの輸送計画作成技術として、いわゆる巡回セールス問題に相当する一定地域内に存在する顧客先や部品調達先を効率的に巡回する計画を作成する技術が特開平５−１３５０７０号「配送スケジューリングシステム」等で既に開発されている。しかし、この従来の技術は、日々の輸送量の変動や受発注の変動により、コストを含む目標を最適にするために、毎日新たに巡回計画を作成するものである。
【０００３】
また、輸送計画作成技術としては、最適化プログラミング（茨城俊秀、福島雅夫著岩波書店１９９１年発行）で説明されている線形計画法の解法であるシンプレックス法を用いた最小費用流問題の解決技法も存在している。しかし、最小費用流問題は生産地から消費地への輸送を定式化したものであるが、水流や電気などの流れをモデルにしたものである。
【０００４】
【発明が解決しようとする課題】
しかし、上記の従来技法は以下の問題を抱えている。
（１）毎日、全く新しく輸送計画を作成するために、トラック等の運転手や運送拠点の作業要員の作業予定が大幅に日々変わってしまうため、人間が効率良く対応することは困難であった。例えば、拠点間の長距離トラック便の運行経路を大きく変わると、トラック運転手は道路状況や中継拠点の細かな状況把握が困難である。
【０００５】
（２）巡回セールス問題に相当する計画作成方法は、基本的に組み合わせの問題を解くことに相当するために、適切な解を求めるのに膨大な時間が要していた。
【０００６】
（３）最小費用流問題では、水流や電気などの流れをモデル化したものであり、消費地側から見て最も輸送コストの低い生産地のものを輸送する計画を作成するものであり、通常の荷物輸送のように、発拠点から出た荷物が予め定められた着拠点に輸送する計画を作成できるものではない。また、中継拠点での荷物積換えのコストなども考慮できない方法である。
【０００７】
本発明の目的は、拠点間の輸送計画の大幅な変更をもたらさずに、輸送効率及びサービス性の向上を実現するための、輸送便間での荷物の積換え計画（中継計画）を効率的に作成する方法およびシステムを提供することにある。
【０００８】
【課題を解決するための手段】
本発明は、上記目的を達成するために、入出力装置と処理装置と記憶装置とを備え、発拠点から出発し、中継拠点を経由して着拠点に到着する複数の輸送便について中継拠点における他の輸送便との間での荷物の中継計画を作成する輸送の中継計画作成方法であって、
発拠点から着拠点に運ぶ荷物量の情報を前記入出力装置から受付け、前記記憶装置に拠点間輸送量情報として格納する第１のステップと、中継計画作成当日における前記中継拠点を経由する複数の輸送便のそれぞれについて、拠点間毎の運行コストの情報を含む輸送便情報を前記入出力装置から受付け、前記記憶装置に格納する第２のステップと、前記記憶装置に格納した複数の輸送便に関する前記輸送便情報に基づき、前記中継拠点を経由する輸送便のルートに基づいて設定した輸送パスのテーブルを作成し、各輸送パスに対して前記記憶装置に格納した輸送便情報中の対応する運行コストの情報をコスト、その輸送パスで運行する輸送便の最大積載量を積載上限値として割当てる第３のステップと、作成した輸送パスのテーブルに対し、荷物の積換えが可能な中継拠点における荷物の積換えを表現する仮想輸送パスを追加し、該仮想輸送パスに対し前記入出力装置から入力される中継拠点における中継コストの値をコスト、積換え可能な上限量の値を積載上限値として割当てた拡張輸送パステーブルを作成する第４のステップと、作成した前記拡張輸送パステーブルに展開された仮想輸送パスを含む複数の輸送パスのコスト及び積載上限値に基づき、前記記憶装置に格納した前記拠点間輸送量情報で示される量の荷物を前記積載上限値を超えない条件で各輸送便の発拠点から着拠点に輸送するのに必要な総コストが最小となる荷物の中継計画を作成する第５のステップとを備えることを特徴とする。
【００１１】
本発明の輸送の中継計画作成システムは、入出力装置と処理装置と記憶装置とを備え、発拠点から出発し、中継拠点を経由して着拠点に到着する複数の輸送便について中継拠点における他の輸送便との間での荷物の中継計画を作成する輸送の中継計画作成システムであって、
発拠点から着拠点に運ぶ荷物量の情報を前記入出力装置から受付け、前記記憶装置に拠点間輸送量情報として格納する第１の手段と、中継計画作成当日における前記中継拠点を経由する複数の輸送便のそれぞれについて、拠点間毎の運行コストの情報を含む輸送便情報を前記入出力装置から受付け、前記記憶装置に格納する第２の手段と、前記記憶装置に格納した複数の輸送便に関する前記輸送便情報に基づき、前記中継拠点を経由する輸送便のルートに基づいて設定した輸送パスのテーブルを作成し、各輸送パスに対して前記記憶装置に格納した輸送便情報中の対応する運行コストの情報をコスト、その輸送パスで運行する輸送便の最大積載量を積載上限値として割当てる第３の手段と、作成した輸送パスのテーブルに対し、荷物の積換えが可能な中継拠点における荷物の積換えを表現する仮想輸送パスを追加し、該仮想輸送パスに対し前記入出力装置から入力される中継拠点における中継コストの値をコスト、積換え可能な上限量の値を積載上限値として割当てた拡張輸送パステーブルを作成する第４の手段と、作成した前記拡張輸送パステーブルに展開された仮想輸送パスを含む複数の輸送パスのコスト及び積載上限値に基づき、前記記憶装置に格納した前記拠点間輸送量情報で示される量の荷物を前記積載上限値を超えない条件で各輸送便の発拠点から着拠点に輸送するのに必要な総コストが最小となる荷物の中継計画を作成する第５の手段とを備えることを特徴とする。
【００１４】
【発明の実施の形態】
以下、本発明の一実施の形態を図面を用いて詳細に説明する。
図１は、本発明の一実施の形態を示すシステム構成図である。本システムは運行計画などを入力する入力装置１０１と、計画の表示などを行なう表示装置１０２、計画などを出力する出力装置１０３と処理装置１０４、記憶装置１０５から構成されている。
【００１５】
処理装置１０４は、トラック便の車両車種や発拠点、中継拠点、着拠点、コスト情報を含む輸送便情報を登録する輸送便情報登録処理部１０６と、拠点の所在地や保有トラック数等の情報を含む拠点情報を登録する拠点情報登録処理部１０７と、各荷物を発拠点、着拠点別に集計する集計処理部１０８と、当日のトラック便の運行計画を登録する当日便運行計画登録処理部１０９と、当日の中継拠点の運用計画を登録する中継拠点運用登録処理部１１０と、トラック便の運行計画や積載荷物量等を表示するトラック便表示処理１１１と、中継拠点での荷物積換え可否や積換え可能時間等を表示する中継計画表示処理部１１２と、中継計画の作成を行なう中継計画作成処理部１１３と、中継計画を表示、出力する中継計出力処理部１１４とから構成されている。
【００１６】
記憶装置１０５には、荷物輸送の発拠点と着拠点の拠点間の輸送量を記憶する拠点間輸送量情報１１５と、トラック便別の荷物量を集計するトラック便別集計情報１１６と、拠点の位置などを格納する拠点情報１１７と、各トラック便の車両種別や運行経路を記録するトラック便情報１１８及び当日の各トラック便の運行ダイヤを格納する当日トラック便ダイヤ情報１１９、当日の中継拠点での荷物積換えの可能時間帯などの情報を記録する当日中継拠点運用計画情報１２０及び輸送パステーブル１２１が格納されている。
【００１７】
本実施形態のシステムは、概ね、次のようにして中継計画の作成を行なう。すなわち、拠点間の輸送便の運行計画と中継拠点での積換え可否等の情報を記憶装置１０５に予め記憶すると共に、トラック便の輸送経路を中継拠点単位に分割したグラフを作成する。このグラフのノードは拠点（発拠点、着拠点、中継拠点）を表し、パスはトラック便に対応する。このグラフ中で荷物積換えが可能な拠点を表現している中継拠点に対しては、荷物積換えを行なう仮想的なパスとノードを設定して、そのパスに対しても荷物輸送量の上限とコストを設定し、このパスとノードを追加したグラフを用いた最適な輸送計画を作成することで各中継拠点での荷物積換え計画を作成する。詳細については、グラフを用いた輸送計画作成の方法については、図８および図９等を用いて後述する。
【００１８】
図２は、図１の記憶装置１０５に格納されるデータの構成例を示すものである。拠点間輸送量情報１１５は、図２（ａ）に示すように、発拠点から着拠点に送られる当日の荷物量を記録するものであり、発拠点ＩＤ２０１，着拠点ＩＤ２０２、荷物量２０３の情報から構成されている。
【００１９】
トラック便別集計情報１１６は、図２（ｂ）に示すように、当日運行するトラック便の経由する拠点での荷物量を記録するものであり、トラック便ＩＤ２０４，車両種別２０５、発拠点２０６、発荷物量２０７、着拠点２０８、着荷物量２０９、拠点（１）〜（Ｎ）における拠点２１０毎の荷物量２１１の情報とから構成されている。
【００２０】
拠点情報１１７は、中継拠点の所在地、保有するトラックなどの輸送リソース情報を記録するものであり、図２（ｃ）に示すように、拠点ＩＤ２１２、所在地２１３、トラック台数２１４、運行トラック台数２１５、余裕トラック台数２１６、運転手数２１７、運行運転手数２１８、余裕運転手数２１９、中継可否２２０、中継時間枠２２１、発時間枠２２２、着時間枠２２３の情報から構成されている。
【００２１】
トラック便情報１１８は、各トラック便のＩＤ及び車両種別、発拠点、着拠点及び中継拠点とそれぞれの拠点到着の予定時間枠の制限及び運行コストが登録されるものであり、図２（ｄ）に示すように、トラック便ＩＤ２２４、車両種別２２５、発拠点２２６、発時間枠２２７、着拠点２２８、着時間枠２２９、中継拠点（１）２３０における時間枠（１）２３１、中継拠点（２）における時間枠（２）、運行コスト２３２の情報から構成され、運行コスト２３２は第１拠点間、第２拠点間などの拠点間毎に登録される。
【００２２】
当日トラック便ダイヤ情報１１９には、各トラック便の当日の運行スケジュールが格納される。この当日トラック便ダイヤ情報１１７は、図２（ｅ）に示すように、トラック便ＩＤ２３３、車両種別２３４、発拠点２３５、発時間２３６、着拠点２３７、着時間２３８、各拠点２３９毎の時間２４０の情報で構成されている。
【００２３】
当日中継点運用計画情報１２０には、中継拠点で荷物の積換えの可否の情報が各日付別に記録されると共に、積換えの可能な時間枠及び積換えを行なえる荷物量の上限中継最大量が記録されている。この当日中継点運用計画情報１２０は、図２（ｆ）に示すように、拠点ＩＤ２４１、日付２４２、中継可否２４３、中継開始時期２４４、中継終了時間２４５、中継最大量２４６、中継コスト２４７の情報から構成されている。
【００２４】
図３は、本発明が対象とする輸送計画を模式的に説明する図である。図中のＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇは拠点（発拠点、着拠点、中継拠点）を表し、ａ，ｂ，ｃ，ｄはトラックなどの輸送便を表している。この図では、発拠点Ａを出発したトラック便ａは中継拠点Ｄを経由して着拠点Ｆに到着する。また、トラック便ｂは発拠点Ｂを出発して中継拠点Ｄを経由して着拠点Ｇに至る。トラック便ｃは、発拠点Ｃを出発後、中継拠点Ｄ、Ｅを経由して着拠点Ｇに至る。トラック便ｄは中継拠点Ｅを経由して着拠点Ｇに至るといったモデルを示している。
【００２５】
今、拠点Ａ，Ｂ，Ｃから拠点Ｆ，Ｇへの荷物輸送を例に挙げ、本発明の対象とする中継計画作成方法について説明する。まず、拠点Ａから拠点Ｇへの荷物の輸送は次の３通りがある。トラック便ａから拠点ｄでトラック便ｂに中継する。トラック便ａから拠点Ｄでトラック便ｃに中継する。トラック便ａから拠点Ｄでトラック便ｃに中継した後、更に拠点Ｅでトラック便ｄに中継する。
【００２６】
この３通りの輸送方法の中で、どの方法が最も効率が高いかは単に拠点Ａから拠点Ｇへの荷物量だけで判断できるものではなく、他の拠点間の輸送量や中継を行なうための積換えコストなど多くの要因に依存するものである。本発明はこれらの要因を総合的に判定して、各トラック便間の中継の要否を判定して中継計画を作成する方法である。
【００２７】
図４は、図３で示したトラック便を用いた輸送での拠点間の輸送量の上限と輸送コストを表すものである。発拠点Ａと中継拠点Ｄの間は最大１０ｔの荷物が輸送可能であり、輸送コストは１ｔあたり１２０００円（図中では、１０００円を単位で記述）である。同じようにして直接トラック便で輸送が可能な拠点間の輸送可能量と輸送コストを示している。
【００２８】
図５は、図３に示したトラック便の輸送経路で、トラック便のルートを拠点間単位に分割して、番号付けを行なったものである。図３中のトラック便ａの発拠点Ａから中継拠点Ｄまでのルートには番号「１」、中継拠点Ｄから着拠点Ｆまでのルートには番号「６」を付与している。この番号の付与は全ての拠点間のルートが一意に区別できるものであれば、付与順序は特に指定しない。またこの番号は「１」から連続して割り振るものとする。
【００２９】
図６は、図５に示した輸送経路の情報を、各ルート毎に集計したテーブルである。この輸送パステーブル６００のパスＩＤ６０１には各パスを一意に識別するためのＩＤが格納されている。また、発拠点ＩＤ６０２、着拠点ＩＤ６０３には、それぞれパスで結ぶ拠点のＩＤが格納されている。また、トラック便ＩＤ６０４にはそのパスを運行するトラック便のＩＤが格納されている。コスト６０５には、そのパスで単位量の荷物を輸送するのに要するコストが格納される。また、積載上限６０６にはそのパスを運行するトラックの積載量の上限値が格納される。
【００３０】
図７は、図１の中継計画作成処理部１１３の概略処理フローである。
まず、当日輸送量集計処理７０１では、当日の荷物を発拠点と着拠点単位に集計して記憶装置１０５の拠点間輸送量情報１１５に格納する。トラック便ダイヤ解析処理７０２では、記憶装置１０５に登録された当日トラック便ダイヤ情報１１９を読み込み、図６に示す輸送パステーブル６００を作成する。
【００３１】
中継点展開処理７０３では、輸送パステーブル６００の中で中継可能な拠点に到着するパスに対して、積換えを表現するパスを追加する処理を行なう。詳細は図１１で後述する。展開点結合処理７０４では、中継点展開処理で新たに輸送パステーブル６００に追加したノード間を結合するパスを追加する処理を行なう。この処理の詳細は図１２で後述する。
【００３２】
この中継点拡張処理７０３と中継点結合処理７０４の作用を図８に示す。今、拠点Ｃでの荷物積換えが可能な場合、処理前には（ａ）の状態であったグラフに新たにノードとパスの追加が行なわれず、図８（ｂ）のグラフに拡張する。すなわち、拠点Ｃでの荷物積換えが可能な場合、拠点Ｃに仮想のノードｃ１〜ｃ４を作成し、これらの仮想のノードをｃ１〜ｃ４で荷物積換えが可能であることを示すパスｐ１〜ｐ４を作成する。
【００３３】
この展開処理を図５の輸送パスに適用した場合、全ての拠点での荷物積換えが可能であれば、図９に示すような輸送パスに展開される。図９において、Ｄａｏ，Ｄａｉ，Ｄｂｏ，Ｄｂｉ，Ｄｃｏ，Ｄｃｉは拠点Ｄに作成した仮想のノードを表し、Ｅｃｏ，Ｅｃｉ，Ｅｄｏ，Ｅｄｉは拠点Ｅに作成した仮想のノードを表すものである。そして、矢印線に隣接している数値はパスＩＤを表し、図５の初期の輸送パスに対して「１０」〜「２２」のパス（仮想のパス）が新たに作成されている。このような処理により、図６に示した輸送パステーブル６００は、中継点展開処理７０３により図１０に示すように、パスＩＤ＝「１０」〜「１４」のパスが追加され、展開点結合処理７０４によりパスＩＤ＝「１５」〜「２２」のパスが追加される。この場合、追加されたパスのコスト１００５および積載上限１００６の設定方法については、図１１および図１２で説明する。
【００３４】
中継計画作成処理７０５は図１０のパステーブル１０００に登録された各パスＩＤのパスを用いて、輸送する荷物量を以下の手順で決定するものである。以下、この処理の詳細を説明する。
【００３５】
図２の拠点間輸送量情報１１５を発拠点Ｏ_ｋ，着拠点Ｄ_ｋ，荷物量をＬ_ｋに格納する。ここでインデックス変数ｋは、拠点間輸送量情報として蓄えられている発拠点、着拠点別の荷物に対応するものである。
【００３６】
図１０に示す各パスの輸送コストをＣ_ｉに格納する。更に各パス毎の輸送量の上限はＵ_ｉに格納する。このＣ_ｉ及びＵ_ｉは図１０に示す輸送パステーブル１０００から情報を取出して値を格納するものである。また、パスｉの発拠点をｈｅａｄ（ｉ）、着拠点をｔａｉｌ（ｉ）で表現する。
【００３７】
今、変数ｘ_ｉｋで拠点間輸送量情報１１５のｋ番目に登録されている発拠点と着拠点間の荷物がｉ番目のパスで輸送される輸送量を表すものとする。このとき、次の式（１）を（２）及び（３）の条件下で最も最小化するｘ_ｉｋがコスト最小の輸送計画である。
【００３８】
【数１】

【００３９】
【数２】

【００４０】
【数３】

【００４１】
この（２）と（３）の条件下で（１）式で表現される輸送コストを最小化する変数ｘ_ｉｋを決定する問題は、一般的な線形計画問題である。したがって、従来から知られているＳｉｍｐｌｅｘ法やＫａｒｍａｋａｒ法を適用することでコストを最小化して輸送を実現するための各パス上の荷物輸送量を表す変数ｘ_ｉｋの値を求めることができる。
【００４２】
図１１は、中継点展開処理７０３の詳細処理手順を示すフロー図である。図１１において、まず、図１０の輸送パステーブル１０００に登録されている全てのパスが展開処理を行なったかを判定する（ステップ１１０１）。もし、未処理のパスが残っていない場合には処理を終える。
【００４３】
未処理のパスが残っていた場合には、そのパスを取出し（ステップ１１０２）、以下の処理を行なう。
【００４４】
取出したパスの着拠点ＩＤでの荷物積換えが可能か否かを判定する（ステップ１１０３）。この判定は、記憶装置１０５に格納されている当日中継拠点運用計画情報１２０を参照することにより行なう。
【００４５】
もし、パスの着拠点の中継可否が否の場合には、取出したパスを処理済にして（ステップ１１１０）、次の未処理のパスの処理を行なう（ステップ１１０１）。中継可否が可の場合には、着拠点ＩＤを仮想のノードに変更するために輸送パステーブル１０００に現われていないＩＤを２つ取得する。この一方をパスの着拠点ＩＤに設定する（ステップ１１０４）。
【００４６】
次に、輸送パステーブル１０００に新たなパスを１つ登録する（ステップ１１０５）。
【００４７】
前ステップで元のパスの着拠点ＩＤに設定した拠点ＩＤを発拠点ＩＤとし、取得したもう一方のＩＤを着拠点ＩＤとする。
【００４８】
新たに登録したパスに対して、注目していたパスのトラック便ＩＤを設定する（ステップ１１０６）。次に、新しいパスのコストには「０」を登録する（ステップ１１０７）。また、積載上限には記憶装置１０５の当日中継拠点運用計画情報１２０に登録されている中継最大量２４６を登録する（ステップ１１０８）。
【００４９】
次に、元の着拠点ＩＤと同一の発拠点ＩＤを有し、元のパスと同一のトラック便ＩＤである接続パスが輸送パステーブル１０００中にあれば、その発拠点ＩＤを新たに登録したパスの着拠点ＩＤの値に置き換える（ステップ１１０９）。次に、現在着目していたパスを処理済に変え（ステップ１１１０）、次の未処理のパスの処理に移る。
【００５０】
図１２は、展開点結合処理７０４の詳細処理手順を示すフロー図である。図１２において、輸送パステーブル１０００に登録されている全てのパスに結合処理を行なったか判定する（ステップ１２０１）。もし、未処理のパスが残っていない場合には処理を終える。
【００５１】
未処理のパスが残っていた場合には、そのパスの着拠点ＩＤを中継点展開処理７０３で変更したか否かを判定する（ステップ１２０２）。もし、変更していなければ次の未処理のパスの処理に移る。変更していた場合には以下の処理を行なう。
【００５２】
現在着目しているパスの、中継点展開処理７０３で変更する以前の着拠点ＩＤと同一の発拠点ＩＤを有するパスをパステーブル１０００から全て求める（ステップ１２０３）。この求めたパステーブルに対して、次の処理をすべて行なう。未処理のパステーブルがなくなれば、この部分処理を終える（ステップ１２０４）。
【００５３】
パステーブルのトラック便ＩＤが着拠点ＩＤを変更したパスのトラック便ＩＤと等しいか否かを判定する（ステップ１２０５）。等しい場合には、このパスは処理済として次の未処理のパスの処理に移る。
【００５４】
トラック便ＩＤが等しくない場合には新しいパスをパステーブル１０００に追加する（ステップ１２０６）。このとき、発拠点ＩＤは中継点展開処理で変更した着拠点ＩＤを設定する。着拠点ＩＤには、ステップで取出したパスの発拠点ＩＤを設定する。またコストには、記憶装置１０５に格納されている当日中継拠点運用計画情報１２０に格納されているコスト２４７を設定する。積載上限も当日中継拠点運用計画情報１２０に格納されている中継最大量２４６を格納する。
【００５５】
【発明の効果】
以上のように、本発明によれば、輸送拠点間を運行するトラック便情報と、当日の拠点間の荷物輸送量を入力することで、各輸送拠点から輸送する荷物を、どのトラック便に乗せるかと共に、トラック便の経由する中継拠点での荷物の積換え計画もトラック便のコストと中継拠点での積換えコストの合計コストを最小とするものを作成することができる。これにより、拠点間の輸送計画の大幅な変更をもたらさずに、輸送効率及びサービス性の向上を実現するための輸送便間での荷物の積換え計画を効率的に作成し、輸送効率の向上などに貢献することが可能になる。
【図面の簡単な説明】
【図１】本発明の実施の形態を示すシステム構成図である。
【図２】記憶情報の詳細を示した図である。
【図３】本発明の対象とするトラック便輸送の経路を模式的に示した図である。
【図４】トラック便輸送のコストを模式的に示した図である。
【図５】トラック輸送のパスを模式的に示した図である。
【図６】トラック輸送のパス情報を格納したパステーブルを示した図である。
【図７】中継計画作成処理の概略処理フロー図である。
【図８】中継点拡張処理の概要を示す図である。
【図９】中継点拡張処理の例を示す図である。
【図１０】中継点拡張処理後のパステーブルの例である。
【図１１】中継点展開処理の処理フロー図である。
【図１２】展開点結合処理の処理フロー図である。
【符号の説明】
１０１…入力装置、１０２表示装置、１０３…出力装置、１０４…処理装置、１０５…記憶装置、１０６…輸送便情報登録処理部、１０７…拠点情報登録処理部、１０８…集計処理部、１０９…当日便運行計画登録処理部、１１０…中継拠点運用登録処理部、１１１…トラック便表示処理、１１２…中継計画表示処理部、１１３…中継計画作成処理部、１１４…中継計出力処理部、１１５…拠点間輸送量情報、１１６…トラック便別集計情報、１１７…拠点情報、１１８…トラック便情報、１１９…当日トラック便ダイヤ情報、１２０…当日中継拠点運用計画情報、１２１…輸送パステーブル。[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a method and system for creating a package relay plan at a relay base between a departure base and a destination base of a transport flight (truck service) via a relay base in a distribution system, and in particular, to efficient delivery of home delivery and the like. The present invention relates to a method and a system for creating a transportation plan that is used for adjusting a transportation route and a relay plan for the purpose of reducing distribution costs and improving serviceability.
[0002]
[Prior art]
Japanese Patent Laid-Open No. 5-135070 discloses a technique for creating a transportation plan in a physical distribution system, which is a technique for efficiently making a tour of customers and parts suppliers located in a certain area corresponding to a so-called traveling sales problem. It has already been developed as a "system". However, according to this conventional technique, a new tour plan is created every day in order to optimize a target including costs due to fluctuations in daily transportation volume and fluctuations in orders.
[0003]
In addition, as a transportation plan creation technique, there is also a technique for solving a minimum cost flow problem using a simplex method which is a solution of a linear programming method described in optimization programming (published by Toshihide Ibaraki, Masao Fukushima, Iwanami Shoten, 1991). Existing. However, the least-cost flow problem is a formulation of transportation from a production area to a consumption area, but is based on the flow of water and electricity.
[0004]
[Problems to be solved by the invention]
However, the above conventional technique has the following problems.
(1) Every day, since a completely new transportation plan is created, the work schedules of truck and other drivers and the work staff of the transportation base change greatly every day, and it is difficult for humans to respond efficiently. . For example, if the operation route of a long-distance truck flight between bases is greatly changed, it is difficult for the truck driver to grasp the road conditions and the detailed situation of the relay base .
[0005]
(2) Since the planning method corresponding to the traveling sales problem basically corresponds to solving a combination problem, it took an enormous amount of time to find an appropriate solution.
[0006]
(3) The minimum cost flow problem is a model of the flow of water flow, electricity, etc., which creates a plan for transporting the production site with the lowest transportation cost from the viewpoint of the consuming area. It is not possible to create a plan for transporting luggage that has left the departure point to a predetermined destination, as in the case of luggage transportation. In addition, this method cannot take into account the cost of transshipment at the relay base .
[0007]
SUMMARY OF THE INVENTION An object of the present invention is to efficiently carry out a transshipment plan (transit plan) of luggage between transportation flights in order to realize an improvement in transportation efficiency and serviceability without causing a significant change in a transportation plan between bases. It is an object of the present invention to provide a method and a system for creating the same.
[0008]
[Means for Solving the Problems]
In order to achieve the above object, the present invention includes an input / output device, a processing device, and a storage device, and a plurality of transport flights departing from a departure point and arriving at a destination via a relay point at a relay point. A method of creating a transit plan for a transit that creates a transit plan for a package with another transit flight,
A first step of receiving, from the input / output device, information on the amount of luggage to be carried from the departure base to the destination base, and storing the information as inter-base transport amount information in the storage device; A second step of receiving, from the input / output device, transport service information including operation cost information for each of the transport flights and storing the information in the storage device, and a plurality of transport flights stored in the storage device. Based on the transportation information, create a table of transportation paths set based on the routes of transportation via the relay point, and for each transportation path, a corresponding operation in the transportation information stored in the storage device. the cost of the information cost, a third step of assigning the maximum load of the transport service that runs in its transport path as maximum stack height with respect to the table transport path created, Adding a virtual transportation path expressing the transshipment of luggage at a transit base where goods can be transshipped, and calculating the value of the transit cost at the transit base input from the input / output device to the virtual transportation path, A fourth step of creating an extended transportation path table in which the value of the possible upper limit is assigned as the loading upper limit, and the cost and loading of a plurality of transportation paths including the virtual transportation path developed in the created extended transportation path table based on the upper limit value, necessary for the luggage amount represented by the inter-base transport volume information stored in the storage device from the source base of each transport service in conditions that do not exceed the maximum stack height for transportation to the destination site total A fifth step of creating a package relay plan with a minimum cost .
[0011]
A transportation relay plan creation system according to the present invention includes an input / output device, a processing device, and a storage device, and a plurality of transportation flights departing from a departure base and arriving at a destination via a relay base at the relay base. A transport relay plan creation system for creating a relay plan for a package with a transport flight of
First means for receiving, from the input / output device, information on the amount of luggage to be carried from the departure base to the destination base, and storing the information as inter-base transport amount information in the storage device; For each of the transportation services, a second means for receiving transportation service information including operation cost information for each base from the input / output device and storing the information in the storage device, and a plurality of transportation services stored in the storage device. Based on the transportation information, create a table of transportation paths set based on the routes of transportation via the relay point, and for each transportation path, a corresponding operation in the transportation information stored in the storage device. cost cost information, and third means for assigning a maximum load capacity of transport service that runs in its transport path as maximum stack height with respect to the table transport path created, luggage transshipment A virtual transport path expressing the transshipment of luggage at a possible relay point is added, and the value of the relay cost at the relay point input from the input / output device for the virtual transport path is calculated as the cost, A fourth means for creating an extended transportation path table in which values are assigned as loading upper limit values, and a cost and loading upper limit value of a plurality of transportation paths including virtual transportation paths developed in the created extended transportation path table, The total cost required to transport the amount of cargo indicated by the inter-base transport volume information stored in the storage device from the departure point to the destination point of each transport flight under a condition not exceeding the loading upper limit value is minimized. And a fifth means for creating a package relay plan.
[0014]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings.
FIG. 1 is a system configuration diagram showing an embodiment of the present invention. The system includes an input device 101 for inputting an operation plan and the like, a display device 102 for displaying a plan and the like, an output device 103 for outputting a plan and the like, a processing device 104, and a storage device 105.
[0015]
The processing device 104 stores a transportation service information registration processing unit 106 for registering transportation service information including vehicle type, departure base, relay base , arrival base , and cost information of truck service, and information such as the location of the base and the number of trucks owned. A base information registration processing unit 107 for registering base information including the same, a tally processing unit 108 for totalizing each package for each departure base and destination base, and a same-day flight operation plan registration processing unit 109 for registering a truck flight operation plan of the day. A relay base operation registration processing unit 110 for registering an operation plan of the relay base on the day, a truck flight display processing 111 for displaying a truck flight operation plan, a loaded luggage amount, and the like; A relay plan display processing unit 112 for displaying a changeable time and the like, a relay plan creation processing unit 113 for creating a relay plan, and a relay meter output processing unit 114 for displaying and outputting a relay plan. It has been made.
[0016]
The storage device 105 stores inter-base transportation amount information 115 that stores the amount of transportation between the bases of the luggage transportation origin and destination, truck-based totaling information 116 that totals the baggage amount of each truck, Location information 117 for storing the position and the like, truck flight information 118 for recording the vehicle type and operation route of each truck flight, and truck flight schedule information 119 for storing the flight schedule of each truck flight on the day, and a relay base for the day. On the day, the relay base station operation plan information 120 and the transport path table 121 that record information such as a possible time period of the luggage transfer are stored.
[0017]
The system according to the present embodiment generally creates a relay plan as follows. That is, information such as the operation plan of the transportation service between the bases and whether or not transshipment is possible at the relay base is stored in the storage device 105 in advance, and a graph in which the transportation route of the truck service is divided for each relay base is created. The nodes in this graph represent bases (departure bases, destination bases, relay bases) , and paths correspond to truck flights. In this graph, a virtual path and node for carrying out transshipment are set for the transit points that represent transshipment-possible bases in this graph, and the upper limit of the luggage transport volume for that path as well. And a cost, and create an optimal transportation plan using the graph to which the path and the node are added, thereby creating a luggage transfer plan at each relay station. For details, a method of creating a transportation plan using a graph will be described later with reference to FIGS.
[0018]
FIG. 2 shows a configuration example of data stored in the storage device 105 of FIG. As shown in FIG. 2A, the inter-base transport amount information 115 records the amount of luggage on the day sent from the departure point to the destination, and includes information on the departure point ID 201, the destination ID 202, and the luggage amount 203. It is composed of
[0019]
As shown in FIG. 2 (b), the total information 116 for each truck flight records the luggage amount at the base where the truck service operated on the day passes, and includes the truck flight ID 204, the vehicle type 205, the departure base 206, It is composed of a baggage amount 207, a destination base 208, a baggage amount 209, and information on a baggage amount 211 for each base 210 in the bases (1) to (N).
[0020]
The base information 117 records the transport resource information such as the location of the relay base and the trucks owned. As shown in FIG. 2C, the base ID 212, the location 213, the number of trucks 214, the number of operating trucks 215, The number of spare trucks 216, the number of drivers 217, the number of operating drivers 218, the number of spare drivers 219, the relay availability 220, the relay time frame 221, the departure time frame 222, and the arrival time frame 223 are configured.
[0021]
The truck service information 118 is for registering the ID of each truck service, the vehicle type, the departure base, the destination base, the relay base, the limit of the scheduled time frame for arrival at each base, and the operation cost, and FIG. as shown in, truck ID 224, vehicle type 225, originating base 226, the calling time frame 227, Chakukyoten 228, wearing time frame 229, the relay base (1) time frame at 230 (1) 231, the relay base (2) The operation cost 232 is registered for each base such as between the first base and the second base.
[0022]
On the day's truck flight schedule information 119 , the day's operation schedule of each truck flight is stored. As shown in FIG. 2 (e), this day's truck flight schedule information 117 includes a truck flight ID 233, a vehicle type 234, a departure base 235, a departure time 236, a arrival base 237, a arrival time 238, and a time 240 for each base 239. It consists of information.
[0023]
In the same day relay point operation plan information 120 , information on whether or not transshipment of luggage is possible at the transit base is recorded for each date, the time frame in which transshipment is possible, and the maximum amount of transit that can be transshipped. Is recorded. As shown in FIG. 2 (f), the relay point operation plan information 120 on the day includes information on the base ID 241, date 242, relay availability 243, relay start time 244, relay end time 245, relay maximum amount 246, and relay cost 247. It is composed of
[0024]
FIG. 3 is a diagram schematically illustrating a transportation plan targeted by the present invention. In the figure, A, B, C, D, E, F, and G represent bases (departure bases, destination bases, and relay bases) , and a, b, c, and d represent transportation services such as trucks. In this figure, track flights a was starting the originating site A is to arrive to the destination base F via the relay bases D. In addition, truck b is via a relay bases D starting origination offices B leading to the wearing base G. Truck c is, after starting the originating site C, leading to wear bases G via the relay bases D, E. Truck d shows the model, such as leading to wear bases G via a relay base E.
[0025]
Now, a method of preparing a relay plan according to the present invention will be described, taking as an example the transportation of luggage from locations A, B, and C to locations F and G. First, there are the following three types of transportation of luggage from the base A to the base G. The route is relayed from the truck service a to the truck service b at the base d. The route is relayed from the truck service a to the truck service c at the base D. After relaying from the truck service a to the truck service c at the base D, the relay is further relayed to the truck service d at the base E.
[0026]
Of these three transportation methods, which one is the most efficient can be determined not only by the amount of luggage from the base A to the base G, but also for the transportation amount between other bases and for relaying. It depends on many factors, including transshipment costs. The present invention is a method of comprehensively determining these factors, determining whether or not relay between truck flights is necessary, and creating a relay plan.
[0027]
FIG. 4 shows the upper limit of the amount of transportation between the bases and the transportation cost in the transportation using the truck service shown in FIG. A maximum of 10 tons of luggage can be transported between the departure point A and the relay point D, and the transportation cost is 12,000 yen per t (in the figure, 1000 yen is described in units). In the same manner, the transportable amount and transportation cost between bases that can be directly transported by truck are shown.
[0028]
FIG. 5 is a diagram illustrating the transportation route of the truck service shown in FIG. 3, in which the route of the truck service is divided into units between bases and numbered. Figure 3 in the truck route to the number from the originating site A of a to the relay base D of "1", the route from the relay base D to the destination base F has granted a number "6". The order of the numbers is not particularly specified as long as the routes between all the bases can be uniquely distinguished. This number is assigned continuously from "1".
[0029]
FIG. 6 is a table in which the information on the transportation routes shown in FIG. 5 is totaled for each route. The path ID 601 of the transport path table 600 stores an ID for uniquely identifying each path. In the departure point ID 602 and the destination point ID 603, IDs of points connected by paths are stored. Also, the truck flight ID 604 stores the ID of the truck flight that operates the pass. The cost 605 stores the cost required to transport a unit amount of package on the path. The loading upper limit 606 stores the upper limit of the loading capacity of the truck that runs the path.
[0030]
FIG. 7 is a schematic processing flow of the relay plan creation processing unit 113 of FIG.
First, in the day's transportation volume totalization processing 701, the day's luggage is totaled for each departure base and destination base and stored in the inter-base transportation volume information 115 of the storage device 105. In the truck flight schedule analysis processing 702, the same day truck flight schedule information 119 registered in the storage device 105 is read, and the transport path table 600 shown in FIG. 6 is created.
[0031]
In the relay point developing process 703, a process of adding a path representing transshipment to a path arriving at a relayable base in the transport path table 600 is performed. Details will be described later with reference to FIG. In the development point connection processing 704, processing for adding a path that connects the nodes newly added to the transport path table 600 in the relay point development processing is performed. Details of this processing will be described later with reference to FIG.
[0032]
The operation of the relay point extension processing 703 and the relay point combining processing 704 is shown in FIG. If the baggage transfer at the site C is now possible, no new nodes and paths are added to the graph in the state of (a) before the processing, and the graph is expanded to the graph of FIG. 8B. In other words, when luggage transfer at the site C is possible, virtual nodes c1 to c4 are created at the site C, and the paths p1 to l4 indicate that these virtual nodes can be transshipped at c1 to c4. Create p4.
[0033]
When this developing process is applied to the transportation path shown in FIG. 5, if the transfer of luggage is possible at all the bases, the transportation path is developed as shown in FIG. In Figure 9, Da o, Dai, Db o, Dbi, Dc o, Dci represents the virtual node created based in D, Ec o, Eci, Edo , Edi those representing the virtual node created based in E It is. Numerical values adjacent to the arrow lines indicate path IDs, and paths (virtual paths) “10” to “22” are newly created with respect to the initial transport path in FIG. By such processing, as shown in FIG. 10, in the transport path table 600 shown in FIG. 6, the paths with the path IDs “10” to “14” are added as shown in FIG. In step 704, paths with path IDs “15” to “22” are added. In this case, a method of setting the cost 1005 and the upper limit 1006 of the added path will be described with reference to FIGS.
[0034]
The relay plan creation processing 705 is to determine the amount of cargo to be transported by the following procedure using the path of each path ID registered in the path table 1000 of FIG. Hereinafter, the details of this processing will be described.
[0035]
Originating site _{O k} inter-base transport volume information 115 of FIG. 2, Chakukyoten _{D k,} luggage amount stored in _{L k.} Here, the index variable k corresponds to the luggage for each departure base and destination stored in the inter-base transport amount information.
[0036]
The transportation cost of each path shown in FIG. 10 and stored in C _i. Further the upper limit of the transport volume of each pass are stored in U _i. These C _i and U _i are obtained by extracting information from the transport path table 1000 shown in FIG. 10 and storing values. The origin of the path i is represented by head (i), and the destination is represented by tail (i).
[0037]
It is assumed that the variable x _ik represents the amount of transportation of the luggage between the origin and destination registered in the k-th location in the inter-base transportation amount information 115 on the i-th path. At this time, _xik that minimizes the following equation (1) under the conditions of (2) and (3) is the transportation plan with the minimum cost.
[0038]
(Equation 1)

[0039]
(Equation 2)

[0040]
(Equation 3)

[0041]
The problem of determining the variable x _ik that minimizes the transportation cost expressed by the expression (1) under the conditions of (2) and (3) is a general linear programming problem. Therefore, the value of the variable x _ik representing the amount of cargo transported on each path for realizing transportation by minimizing cost by applying the conventionally known Simplex method or Karmakar method can be obtained.
[0042]
FIG. 11 is a flowchart showing a detailed processing procedure of the relay point development processing 703. In FIG. 11, first, it is determined whether or not all the paths registered in the transport path table 1000 of FIG. 10 have undergone the expansion processing (step 1101). If there are no unprocessed paths, the process ends.
[0043]
If an unprocessed path remains, the path is extracted (step 1102), and the following processing is performed.
[0044]
It is determined whether or not luggage transfer using the destination base ID of the taken out path is possible (step 1103). This determination is made by referring to the relay site operation plan information 120 on the day stored in the storage device 105.
[0045]
If it is not possible to relay at the destination of the path, the extracted path is processed (step 1110), and the next unprocessed path is processed (step 1101). If relaying is possible, two IDs that do not appear in the transport path table 1000 are acquired to change the destination base ID to a virtual node. One of them is set as the destination base ID of the path (step 1104).
[0046]
Next, one new path is registered in the transport path table 1000 (step 1105).
[0047]
The base ID set as the destination base ID of the original path in the previous step is set as the source base ID, and the other acquired ID is set as the destination base ID.
[0048]
For the newly registered path, the track flight ID of the path of interest is set (step 1106). Next, “0” is registered as the cost of the new path (step 1107). In addition, the maximum relay amount 246 registered in the relay base operation plan information 120 of the storage device 105 on the day is registered as the upper limit of the load (step 1108).
[0049]
Next, if a connection path having the same departure base ID as the original destination base ID and the same truck flight ID as the original path is present in the transport path table 1000, the departure base ID is newly registered. The value is replaced with the destination ID of the path (step 1109). Next, the currently focused path is changed to the processed path (step 1110), and the process proceeds to the next unprocessed path.
[0050]
FIG. 12 is a flowchart showing a detailed processing procedure of the development point combining processing 704. In FIG. 12, it is determined whether the combining process has been performed on all the paths registered in the transport path table 1000 (step 1201). If there are no unprocessed paths, the process ends.
[0051]
If an unprocessed path remains, it is determined whether or not the destination ID of the path has been changed in the relay point development processing 703 (step 1202). If not changed, the process moves to the next unprocessed path. If it has been changed, the following processing is performed.
[0052]
From the path table 1000, all paths having the same departure point ID as the destination point ID of the currently focused path before being changed in the relay point development processing 703 are obtained (step 1203). The following processes are all performed on the obtained path table. When there is no unprocessed path table, the partial processing is completed (step 1204).
[0053]
It is determined whether the track flight ID of the path table is equal to the track flight ID of the path whose destination base ID has been changed (step 1205). If they are equal, this path is regarded as processed, and the process proceeds to the next unprocessed path.
[0054]
If the truck flight IDs are not equal, a new path is added to the path table 1000 (step 1206). At this time, the destination base ID set in the relay point development process is set as the source base ID. As the destination base ID, the source base ID of the path taken out in the step is set. As the cost, the cost 247 stored in the relay station operation plan information 120 on the day stored in the storage device 105 is set. The loading upper limit also stores the maximum relay amount 246 stored in the relay base operation plan information 120 on the day.
[0055]
【The invention's effect】
As described above, according to the present invention, by inputting the information of the truck service operating between the transportation bases and the amount of the baggage transport between the bases on the day , the luggage transported from each transportation base can be loaded on any truck service. At the same time, a transshipment plan for the luggage at the transit base via the truck service can be created so as to minimize the total cost of the truck service and the transshipment cost at the transit base. As a result, without significantly changing the transportation plan between bases, we will efficiently create a transshipment plan for cargo between transportation flights to improve transportation efficiency and serviceability, and improve transportation efficiency It is possible to contribute to such.
[Brief description of the drawings]
FIG. 1 is a system configuration diagram showing an embodiment of the present invention.
FIG. 2 is a diagram showing details of stored information.
FIG. 3 is a diagram schematically showing a route of truck service to which the present invention is applied.
FIG. 4 is a diagram schematically showing the cost of truck transportation.
FIG. 5 is a diagram schematically showing a truck transport path.
FIG. 6 is a diagram showing a path table storing path information for trucking.
FIG. 7 is a schematic process flowchart of a relay plan creation process.
FIG. 8 is a diagram illustrating an outline of a relay point extension process.
FIG. 9 is a diagram illustrating an example of a relay point extension process.
FIG. 10 is an example of a path table after a relay point extension process.
FIG. 11 is a processing flowchart of a relay point expanding process.
FIG. 12 is a processing flowchart of a development point combining process.
[Explanation of symbols]
101: input device, 102 display device, 103: output device, 104: processing device, 105: storage device, 106: transportation information registration processing unit, 107: base information registration processing unit, 108: aggregation processing unit, 109: the day Flight operation plan registration processing unit, 110: relay base operation registration processing unit, 111: truck flight display processing, 112: relay plan display processing unit, 113: relay plan creation processing unit, 114: relay total output processing unit, 115: base Inter-transportation amount information, 116: total information by truck service, 117: base information, 118: truck flight information, 119: truck flight schedule information of the day, 120: relay base operation plan information of the day, 121: transport path table.

Claims

A plurality of transportation services including an input / output device, a processing device, and a storage device, departing from a departure point, and arriving at a destination via a relay point, relaying the baggage to another transportation service at the relay point. A method of creating a transit plan for transportation,
A first step of receiving, from the input / output device, information on the amount of luggage to be carried from the departure base to the destination base, and storing the information as the inter-base transport amount information in the storage device;
A second step of receiving, from the input / output device, transportation information including information on operation costs for each of the plurality of transportation flights passing through the relay base on the day when the relay plan is created, and storing the information in the storage device; When,
Based on the transportation information on a plurality of transportations stored in the storage device, a table of transportation paths set based on the route of the transportation via the relay point is created, and the storage device is created for each transportation path. A third step of allocating the information of the corresponding operation cost in the transportation service information stored in the cost as the cost, and the maximum loading capacity of the transportation service operated by the transportation path as the loading upper limit value ,
To table created transport path, in a relay base to add a virtual transport path representing the transshipment of cargo in transshipment capable relay base load is input from the input device to the virtual transport path A fourth step of creating an extended transportation path table in which the value of the relay cost is assigned as the cost and the value of the transmissible upper limit is assigned as the loading upper limit ;
Based on the costs and loading upper limit values of a plurality of transportation paths including the virtual transportation paths developed in the created extended transportation path table, the load of the amount of cargo indicated by the inter-base transportation amount information stored in the storage device is loaded. A fifth step of creating a package relay plan that minimizes the total cost of transporting from the departure point to the destination point of each transport flight under conditions that do not exceed the upper limit value. How to create a relay plan.

A plurality of transportation services including an input / output device, a processing device, and a storage device, departing from a departure point, and arriving at a destination via a relay point, relaying the baggage to another transportation service at the relay point. A transportation relay plan creation system for creating a plan,
First means for receiving, from the input / output device, information on the amount of luggage to be carried from the departure base to the destination base, and storing the information as inter-base transportation amount information in the storage device;
A second means for receiving, from the input / output device, transportation information including information on operation costs for each of the plurality of transportation flights via the relay base on the day of the relay plan creation from the input / output device, and storing the information in the storage device; When,
Based on the transportation information on a plurality of transportations stored in the storage device, a table of transportation paths set based on the route of the transportation via the relay point is created, and the storage device is created for each transportation path. A third means for allocating the information of the corresponding operation cost in the transportation information stored in the cost as the cost, and assigning the maximum loading amount of the transportation service operated by the transportation path as the loading upper limit value,
To the created transport path table, add a virtual transport path expressing transshipment of luggage at the transit base where transshipment of luggage is possible, and at the transit base input from the input / output device for the virtual transport path. Fourth means for creating an extended transportation path table in which the value of the relay cost is assigned as the cost, and the value of the upper limit of transhipment is assigned as the upper limit of loading;
Based on the costs and loading upper limit values of a plurality of transportation paths including the virtual transportation paths developed in the created extended transportation path table, the load of the amount of cargo indicated by the inter-base transportation amount information stored in the storage device is loaded. Fifth means for creating a package relay plan that minimizes the total cost required to transport from the departure point to the destination point of each transport flight under conditions not exceeding the upper limit value. Relay plan creation system.