車両運行計画作成方法及び装置
【課題】点在する複数の配送拠点より積荷を集荷し、配送先へ納入する近距離配送における車両の回転率を向上させかつ、配送コストを削減する配車計画を立案する車両運行計画作成方法及び装置を提供することを課題とする。
【解決手段】配送オーダデータの入力および選択を促す計画作成データの選択処理工程と、配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理工程と、車両収入と車両運用コストとの差を合計したものを目的関数とし該目的関数を最大化する探索処理を用い配送オーダデータとマスタデータから探索シナリオに基づき車両運行計画を作成する最適運行計画作成処理工程とを有し、計画作成データの選択処理工程とデータ読み込み処理工程では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加える。
【解決手段】配送オーダデータの入力および選択を促す計画作成データの選択処理工程と、配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理工程と、車両収入と車両運用コストとの差を合計したものを目的関数とし該目的関数を最大化する探索処理を用い配送オーダデータとマスタデータから探索シナリオに基づき車両運行計画を作成する最適運行計画作成処理工程とを有し、計画作成データの選択処理工程とデータ読み込み処理工程では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加える。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、製造・流通業などにおける配送拠点(倉庫、工場、物流センター)に保管される製品などの運送物を、配送拠点で保有するトラック、トレーラなどの輸送手段により効率的に納入先へ配送するための車両運行計画技術に関するものである。
【背景技術】
【0002】
近年、物流の効率化・コスト削減を求める気運が高まっている。こういう気運の高まりに対して、配車計画の自動作成や作成支援を行う為の技術や装置が、種々見受けられる様になってきている。物流システムでの輸送スケジュール作成技術は、いわゆる巡回セールスマン問題やビークルルーティング問題に相当し、一定地域内に存在する顧客先の効率的な巡回計画を作成する技術がすでに開発されている。
【0003】
例えば、特許文献1に開示されている技術では、3段階にわたる求解法をとっており、品目データと、物流拠点データと、車両および車庫データとを少なくとも管理するマスター管理手段と、該マスター管理手段内のデータに基づいて、輸送依頼に応じた運行ルートの設定を行う運行ルート設定手段と、を備え、該手段が、前記データに基づき、輸送依頼に応じて1台の車両に積載し得る品目群を運行データの1つのセットとして、発着地別に複数セット作成するセット作成部と、複数のセットのうち、各隣接セット間を直列に連結可能な運行ルートの候補を複数設定するセット連結部と、運行ルートの候補のうち、輸送依頼を満足し、かつ複数の評価指標うち予め定めた1つの評価指標を最小化する運行ルートを選択するルート選択部によって構成されており、各種の制約条件を充足しつつ、かつ、所定の目標、例えば車両総台数の最小化を迅速に立案することのできる配車装置を提供している。
【0004】
また、特許文献2に開示されている技術では、物流センターから配送先への荷物輸送と、集荷先から物流センターへの荷物輸送を混載した車両の集配送先での時間制約を守った効率的な輸送スケジュールを作成する輸送計画作成方法およびシステムを提供することを目的としており、輸送スケジュールを作成する際、物流センターや集配送先拠点の位置情報を入力し、輸送すべき荷物の荷物量、集配送先、到着時刻の時間制約を含む荷物情報を入力し、輸送車両の積載量限界を含む輸送車両情報を入力する。更に輸送スケジュール作成時に各車両の巡回先拠点での、到着の遅延が猶予される最大時間と積載可能な集荷荷物と配送荷物の最大量のテーブルを作成し、複数車両の巡回拠点からなる輸送スケジュールへの荷物の集配送先拠点の追加可否の判定を前記テーブルにより行って、前記時間制約を守った条件下で前記各情報を用いて輸送車両のスケジュール作成を行っている。
【0005】
さらに、特許文献3に開示されている技術では、優先したい目的に応じた車両引き当て及び積み合わせを行うとともに、車両の得る収入と、車両にかかるコストの差を目的関数として、その目的関数を最大化するようにしている。このため、複数の配送拠点に対応して、空車走行の削減および車両回転率の向上が図れ、効率的でコスト最小かつ現実に配送可能な車両運行計画を作成することが可能である。また、目的関数の最適化処理方法を複数提案するとともに、最適化処理方法の選択および選択した最適化処理方法の探索順を規定する探索シナリオを導入したことにより、車両運行計画の対象変化に柔軟に対応できる効果と、複数配送拠点に対応することによって生じた探索空間の増大に対して、計画作成時間を短縮する効果もある。
【0006】
前記特許文献と「発明を実施するための最良の形態」において参照する非特許文献も含めて、以下に参照文献を記載する。
【特許文献1】特開2000−36093号公報
【特許文献2】特開2003−285930号公報
【特許文献3】特開2005−122679号公報
【非特許文献1】「組合せ最適化-メタ戦略を中心として-」、柳浦睦憲、茨木俊秀著、朝倉書店、2001年
【発明の開示】
【発明が解決しようとする課題】
【0007】
鉄鋼製品、重機機械等の大重量物の配送、特に200〜300Km以内に納入先、配送拠点である工場、物流センター、委託倉庫が複数点在するような近距離配送では、配送拠点、倉庫等での集荷、納入先への配送である運行サイクルを効率的に行い車両数、空車走行を削減することが、コスト低減の重要な点となる。以上の車両2台による簡単な例は、図32のような配送である。図32では、車両1と車両2とも配送拠点において集荷作業を行い、車両1は納入先A、Bに配送を行い、その後倉庫で集荷作業を行い、納入先Cに配送し、配送拠点に戻る。車両2では納入先D、Eに配送を行い、その後、一旦配送拠点に戻り、再度集荷作業を行い、納入先Fに配送を行い、配送拠点に戻るという運行サイクルをとる。図では、実線矢印で荷物を積んでの配送、破線矢印で積荷なしすなわち積荷を降ろして空車状態での走行をそれぞれ表している。
【0008】
しかし、特許文献1および特許文献2で開示された技術では、複数の納入先に対して最適な配送経路を作成するのが目的であるため、上述のような倉庫も含めた複数の配送拠点に対しての考慮はされていない。
【0009】
また、特許文献3で開示された技術では、上記問題は解消されているものの、新規に車両運行計画を作成する際には、新規計画対象の配送オーダーデータ、車両のみを対象として探索処理を行い最適化を図るため、特定の車両に注目すると、無駄な走行となっていることがある。図33は、ある車両1台の運行計画の例を示す図である。
【0010】
この例は、ある車両1台の動きを示すものであり、前回の計画において策定された一連の動き(配送拠点A(車両拠点)から納入先A(1)、納入先Aから配送拠点B(2)、配送拠点Bから納入先B(3)、納入先Bから配送拠点A(車両拠点)に戻る(4))と、新規の計画において策定された一連の動き(配送拠点A(車両拠点)から配送拠点B(5)、配送拠点Bから納入先C(6)、納入先Cから配送拠点A(車両拠点)に戻る(7))とを示している。
【0011】
図32と同様に、実線矢印で荷物を積んでの配送、破線矢印で積荷なしすなわち積荷を降ろして空車状態での走行をそれぞれ表しており、走行する場所間の距離を線分の長さでおおよそ表している(例えば、納入先Bから配送拠点A(車両拠点)(4)までの距離は、配送拠点Bから納入先B(3)までの距離の約3倍ほど長い)。前回計画時の最終運行サイクル((3)〜(4))における納入先Bから配送拠点A(車両拠点)への戻り走行(4)と、新規計画時の初回運行サイクル((5)〜(7))における、配送拠点A(車両拠点)から配送拠点Bへの走行(5)とが、ともに空車であるため無駄な走行となっていることが分る。
【0012】
このように、近接した逆方向のルートでともに空車となるケースでは、無駄な走行計画になってしまっている。そこで例えば、図33で示した例では、図34に示した走行ルートをとれば、無駄のない走行計画となる。
【0013】
すなわち、図33に示す納入先Bから配送拠点A(車両拠点)に戻る(4)ルートの代わりに、図34に示すように納入先Bから配送拠点Bに寄り(4)、配送する荷物を積込み、配送拠点A(車両拠点)(5)へ、さらに納入先Cに配送(6)し、配送拠点A(車両拠点)(7)に戻るというルートをとれば、空車で無駄に走行することなく、かつ最短距離で配送することができる。
【0014】
本発明は上記課題を解決し、点在する複数の配送拠点より積荷を集荷し、配送先へ納入する近距離配送における車両の回転率を向上させかつ、配送コストを削減する配車計画を立案する車両運行計画作成方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【0015】
請求項1に係る発明は、複数の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する方法において、運ぶべき荷物に関するデータすなわち配送オーダデータの入力および選択を促す計画作成データの選択処理工程と、前記配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理工程と、各車両が得る車両収入と、各車両を運用する際にかかる車両運用コストとの差を合計したものを目的関数とし、該目的関数を最大化する探索処理を用い、前記配送オーダデータと前記マスタデータから前記探索シナリオに基づき、車両運行計画を作成する最適運行計画作成処理工程と、作成した車両運行計画を出力するための車両運行計画出力工程とを有し、前記計画作成データの選択処理工程と前記データ読み込み処理工程では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えることを特徴とする車両運行計画作成方法である。
【0016】
また請求項2に係る発明は、複数の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する装置において、運ぶべき荷物に関するデータすなわち配送オーダデータの入力および選択を促す計画作成データの選択処理手段と、前記配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理手段と、各車両が得る車両収入と、各車両を運用する際にかかる車両運用コストとの差を合計したものを目的関数とし、該目的関数を最大化する探索処理を用い、前記配送オーダデータと前記マスタデータから前記探索シナリオに基づき、車両運行計画を作成する最適運行計画作成処理手段と、作成した車両運行計画を出力するための車両運行計画出力手段とを備え、前記計画作成データの選択処理手段と前記データ読み込み処理手段では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えることを特徴とする車両運行計画作成装置である。
【発明の効果】
【0017】
本発明によれば、優先したい目的に応じた車両引き当て及び積み合わせを行うとともに、車両の得る収入と、車両にかかるコストの差を目的関数として、その目的関数を最大化するようにしたので、複数の配送拠点に対応して、空車走行の削減および車両回転率の向上が図れ、効率的でコスト最小かつ現実に配送可能な車両運行計画を作成することが可能である。また、目的関数の最適化処理方法を複数提案するとともに、最適化処理方法の選択および選択した最適化処理方法の探索順を規定する探索シナリオを導入したことにより、車両運行計画の対象変化に柔軟に対応できる効果と、複数配送拠点に対応することによって生じた探索空間の増大に対して、計画作成時間を短縮する効果もある。
【0018】
さらに、新規に車両運行計画を作成する際に、新規計画対象の配送オーダーデータ、車両などのデータに、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えて探索処理を行うようにしたので、更なる最適化が実現できる。
【発明を実施するための最良の形態】
【0019】
以下、本発明を実施するための最良の形態について図面を用いて説明する。 図2は、本発明の装置構成の一例を示す図である。同図において、1は車両運行計画作成計算機、2はマスタ管理サーバ、3は受発注システム、4はプリンタ、5はコンピュータネットワークを示す。1〜4の装置・システムは、それぞれコンピュータネットワーク5に接続されている。車両運行計画作成計算機1は、データ読み込み手段、最適車両運行計画作成手段及び車両運行計画出力手段とキーボード、マウス、ディスプレイを備えたパーソナル・コンピュータもしくはワークステーションである。なお、本構成例では1台のみ例示であるが、配送する品種毎、支社、配送拠点等に対応して複数台で構成しても構わない。
【0020】
マスタ管理サーバ2は、車両運行計画作成に必要なマスタ類を記憶、管理するための計算機である。車両運行計画作成計算機1中のデータ読み込み手段からの要求によって、必要なマスタ類を車両運行計画作成計算機1に送信する。また、マスタ類の変更、修正などを行う。
【0021】
受発注システム3は、車両運行計画作成計算機1中のデータ読み込み手段からの要求によってオーダデータを送信する。また、車両運行計画作成計算機1中の車両運行計画出力手段から送信された車両運行計画を受信し、課金処理、出荷するオーダの確保、倉庫への出荷指示および運送会社への指示等の処理を行う。受発注システム3は、本装置例では独立した外部システムとしているが、車両運行計画作成計算機1、マスタ管理サーバ2などの内部システムとしても構わない。このことは、マスタ管理サーバ2、以下のプリンタ4などについても同様である。
【0022】
プリンタ4は、車両運行計画作成計算機1で作成された車両運行計画を印刷する。また、受発注システム3およびマスタ管理サーバ2の出力にも利用する。
【0023】
車両運行計画作成計算機1の内部で行う処理・手順を、図1に示す。 計画作成データの選択処理10では、運ぶべき荷物の配送予定日等を入力することにより、運ぶべき荷物に関するデータ(以下、配送オーダデータと記す)を選択する。
【0024】
データ読み込み処理11では、前記計画作成データの選択処理10によって選択された配送オーダデータと車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込み、次ステップ最適運行計画作成処理12に入力するためのデータを作成する。
【0025】
最適運行計画作成処理12では、データ読み込み処理11で作成された入力データより最適な車両運行計画を作成する。ここでの処理の詳細は後述する。
【0026】
車両運行計画表示処理13では、最適運行計画作成処理12で作成され運行計画をディスプレイ等に表示する。また、必要であれば図2のプリンタ4に結果を印刷させる処理を行う。
【0027】
車両運行計画送信処理14では、作成された車両運行計画を図2の受発注システム3に送信する処理を行う。 以上が、車両運行計画作成計算機1内での処理の概要である。
【0028】
以下に、配送オーダデータと車両運行計画に必要なマスタデータについて詳説する。先ず、配送オーダデータは、計画作成データ選択処理10によって選択されたデータとして、具体的には図2の受発注システム3に要求して受け取る。配送オーダデータは配送される荷物に関するデータであり、配送オーダデータの項目の一例を、図3に示す。配送オーダデータの項目には、配送される荷物の注文ID番号、納入先を判別するための納入先コード、配送する荷物の種類を判別するための製品コード、製品の種別を判別するための品種コード、配送拠点を示す拠点コード、納入時刻を示す時刻指定、製品の重量、サイズ等の情報が含まれている。
【0029】
次に、車両運行計画に必要なマスタデータは、図2のマスタ管理サーバ2に対して、車両運行計画作成に必要なマスタデータを要求して受け取る。このマスタデータには、例えば以下に示す種々のものがある。
【0030】
図4は、車両マスタと呼ばれるデータの項目の一例を示す。この車両マスタには、個々の車両を区別する車両No、所属する運送会社区分、所属する配送拠点を示す拠点コード、最大積載重量、荷台長、荷台幅等の利用できる車両の仕様に関する情報、その車両が利用できる時間帯、使用するために必要なコスト(固定費、燃料費)など個々の車両に関する情報が含まれている。配送計画作成時にコストの計算を行うとき、これらの情報を用いる。
【0031】
図5は、距離マスタと呼ばれるデータの項目の一例を示す。この距離マスタには、配送拠点から納入先、または納入先間の距離と移動速度に関するデータが含まれている。これらデータは、配送計画立案時に、配送時間の計算に用いる。
【0032】
図6は、納入先マスタと呼ばれるデータの項目の一例を示す。この納入先マスタには納入先に関するデータが含まれている。納入先マスタに含まれている項目には、納入先での荷物の降ろし時間、納入先において荷物の降ろしが可能な時間帯等がある。これらも、距離マスタと同様に、配送計画立案時に、配送時間の計算に用いる。
【0033】
図7は、運賃マスタと呼ばれるデータの項目の一例を示す。この運賃マスタには、配送距離に応じた品種毎の配送料金データに関する情報が含まれている。配送計画作成時において、各車両の得る収入を計算するときにこれらの情報を用いる。
【0034】
図8は、配送拠点マスタと呼ばれるデータの項目の一例を示す。この配送拠点マスタには、それぞれの配送拠点での積み込み時間に関してのデータが含まれている。これらは、配送計画立案時に配送時間の計算に用いる。
【0035】
図9は、仮想コストマスタと呼ばれるデータの項目の一例を示す。この仮想コストマスタには、後述する仮想コストに関してのデータが含まれており、この例では項目名称とそのコストの値とを対応付けている。これらデータは、配送計画立案時においては、目的関数の仮想コストの算出に用いる。以上、配送オーダデータと車両運行計画に必要なマスタデータの一例を説明してきたが、これに限られるものでなく、配送形態によって適宜変更・追加されるべきものである。
【0036】
車両の運行サイクル(以下、トリップとも称する)は、図11に示すように、配送拠点(倉庫など)での集荷作業、そして納入先への配送作業、さらに配送作業終了後の配送拠点への回送作業までの一連の作業を1運行サイクル(1トリップ)とするものであり、車両毎に単数または複数の運行サイクルが計画される。図12は、複数の運行サイクルが所定就労時間に収まった場合、これと反対に図13は、複数の運行サイクルが所定就労時間を超過してしまった場合を示している。
【0037】
なお、本発明では、新規に車両運行計画を作成する際に、新規計画対象の配送オーダーデータ、車両などのデータに、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えて、後述する探索処理を行い最適化を図る。新規計画の実施のタイミングが遅い場合(前回計画の終了時間に近い場合)は、最終運行サイクルの戻り走行のみが変更可能とするものの、実施のタイミングが早ければ、最終運行サイクルの行きまで変更可能とする。更に実施のタイミングが早ければ、更に前の運行サイクルの輸送経路(車両と荷物との組合せを含む)の見直しも可能として、最適化を図る。
【0038】
見直し範囲の特定に際しては、見直し対象の最早時刻の指定、運行サイクル及び行き戻りの指定などを行う。具体的な例では、前記車両マスタでの「所属する配送拠点を示す拠点コード」を見直し範囲の前回計画の運行サイクルの出発拠点の拠点コードにするとか、「その車両が利用できる時間帯」におけるスタート時間(最早時刻)を前回計画の運行サイクルでの該当時間に置き換えるなどの処理を行う。
【0039】
先に挙げた図1の最適運行計画作成処理12では、決められた制約条件を満たし、かつ与えられた目的関数を最大化(もしくは最小化)する組合せ最適問題として定式化することを基本としている。そしてこのような、組合せ最適化問題は多くの場合、近似解法と呼ばれる手法を用いて解いている。この組合せ最適化問題の近似解法に関しては、様々な手法が提案されており、その詳細は例えば、非特許文献1に記載されている。
【0040】
本発明において目的関数は、(1)式に示すものとなる。
【0041】
【数1】
各車両毎に車両収入と車両運行コストを求め、全車両合計した金額を目的関数にし、これを最大にしようとするものである。そして、(1)式における車両収入は、(2)式に示すものとなる。
【0042】
【数2】
(2)式の内、配送料金(タリフ)は、いわゆる配送運賃収入であり、一般には積荷の種類と配送拠点からの距離に応じて決まっている。鉄鋼製品であるコイルの場合では、配送先の基準距離比例定額テーブルに従った、コイル重量比例で料金が決まっている(図7参照)。
【0043】
次の仮想収入は、ボーナスとして仮想的に収入に組入れるものである。ボーナスとしては、以下のものがある(図9(1)参照)。
(1)燃料費補正ボーナス: 例えば、使用車両の店社毎の配送距離毎の定額値を決めておき加算する。
(2)車両固定費補正ボーナス: 例えば、使用車両の店社毎の定額の値を決めておき加算する。
(3)配送料金補正ボーナス: 例えば、使用車両の店社毎の補正係数を、該当車両の配送料金に掛ける。
(4)配送先集約ボーナス: 例えば、1車両の1トリップに割り当てたオーダにおいて、同じ配送先のオーダ数−1に定額を掛ける。
(5)店社収益ボーナス: 例えば、使用車両の店社毎の店社収益重み係数を該当車両の収益に掛け、さらに店社収益バイアスを加算する。
(6)異距離積み合せボーナス(負) : 例えば、同一車両に配車した配送先間で直近の配送先から最遠の配送先間の移動時間に比例値(マイナス値)を掛ける。
(7)車両使用の負のボーナス: 例えば、使用車両数により負のボーナスを加えるもの。
以上のような仮想収入を導入することにより、仮想収入が大きい車両は目的関数が大きくなるため、優先的に選択されるようになる。
【0044】
次に、(1)式における車両運行コストは、(3)式に示すものとなる。
【0045】
【数3】
(3)式の内、輸送コストは、輸送に直接かかるコストとして計上されるものであり、次のようなものが上げられる(図3〜図9参照)。
燃料費コスト: 車種クラス毎に走行に要する燃料費である。
走行時間コスト: 配送にかかる時間に関するコストである。
固定費コスト: 車両を利用する上で必要となる費用である。
【0046】
次の仮想コストは、制約条件を越えた場合のペナルティとして仮想的にコストに組入れるものである。ペナルティとしては、例えば以下のものがある(図9(2)参照)。
積載重量超過ペナルティ: トリップ毎に、車種クラス毎の最大積載量を超過した重量に比例する。
荷台サイズ超過ペナルティ: トリップ毎に、車種クラス毎の荷台長さを超過した積荷長(該当車種クラスに可能な全ての積み方で最小となる長さ)に比例する。
時刻指定遅延ペナルティ: 配送時刻が、配送指定終了時刻の配送余裕時間前の時刻より遅延した時間に比例する。
車輌利用可能時刻超過ペナルティ: 全トリップ終了時の帰還時刻が、車輌毎の利用可能終了時刻を越えた時間に比例する。
最大配送先数超過ペナルティ: トリップ毎に、最大配送先数を超過した場合、その配送先数全てに比例する。
以上のような仮想コスト(ペナルティ)を導入することにより、実行不可能領域にまで探索が可能となり、より効率的な最適化計算を行うことが出来る。ただし、解としてはペナルティの値が0のものを採用する。
【0047】
図10は、図1の最適運行計画作成処理12の処理フローを示す図である。ステップ20のデータ読み込みでは、最適運行計画作成手段で必要なデータを読み込み、最適運行計画作成処理の初期化を行う。読み込まれるデータは、前述した配送オーダデータ、車両マスタデータ、納入先マスタデータ、距離マスタデータ、運賃マスタデータ、拠点マスタデータ、仮想コストマスタデータおよび後述する探索シナリオである。
次にステップ21の探索シナリオ解釈では、読み込まれたデータのうち探索シナリオの解釈を行う。探索シナリオとは、初期解作成、各種探索単位による最適化処理、繰り返し回数、条件分岐、終了条件等を記述したものであり、人が事前に最適化する対象に応じて戦略的に入力・記憶させておく。
【0048】
各種探索単位による最適化処理には、1オーダ(1つの積荷)と1車両内の1運行サイクル、1車両内の1運行サイクル内の同一納入先のオーダをまとめたものと1車両内の1運行サイクル、1車両と1車両内の1運行サイクル、1車両と同一ではない1車両、1車両とそれぞれ同一ではない2車両等の探索単位による最適化処理がある。
【0049】
図14に探索シナリオの一例を記述したプログラムを示す。この探索シナリオを探索シナリオ解釈21では、図15のように処理フローとして解釈する。 この探索シナリオの例では、M個の初期解を作成し、作成した初期解を探索単位を変えながらの最適化をN回行うものである。図14のLOOP内のCARGOは、図15のステップ31(積荷を探索単位とした最適化処理31)に対応し、以下同様にDESTINはステップ32(納入先を探索単位とした最適化処理32)、TRUCKはステップ33(1車両と1車両を探索単位とした最適化処理33)、TRUCK1by2はステップ34(2車両と1車両を探索単位とした最適化処理34)、TRIPはステップ35(運行サイクルを探索単位とした最適化処理35)およびTRIP_DIVはステップ36(運行サイクルの平準化36)にそれぞれ対応している。
【0050】
図15の積荷を探索単位とした最適化処理31と納入先を探索単位とした最適化処理32では、配送ロットの集約、調整を行う。図15の1車両と1車両を探索単位とした最適化処理33と1車両と2車両を探索単位とした最適化処理34では、利用する車両の種類の調整を行う。図15の運行サイクルを探索単位とした最適化処理35および運行サイクルの平準化36では、運行サイクルの調整を行う。
【0051】
ステップ22では、ステップ21で解釈された最適化方法を実行する。
ステップ23では、探索シナリオによって探索された中から評価関数の値がもっとも良いものを選択し、最適運行計画作成処理を終了する。
以上が、本発明の核となる最適運行計画作成処理の概略処理フローである。では、図15の探索シナリオの処理フローを用いて、それぞれの探索方法(ステップ31〜36)について、詳述する。
【0052】
ステップ30は、探索の基になる初期解をまず作成する。本発明の場合では、配送オーダデータを車両マスタで与えられた車両に積み付ける処理を行う。初期解は、例えば以下の4ステップを経て作成する。
(1)配送オーダデータを、納入先単位にグルーピングする。
(2)納入先単位にグルーピングしたデータを、拠点から近い順にソートする。
(3)(2)でソートされた順番に、車両マスタによって与えられた車両をランダムに並べ、積載重量を超えるまで割り付ける。
(4)(3)を荷物がなくなるまで繰り返す。車両が足らなくなった場合は、車両マスタ中に定義した傭車用の車両データを新たに生成して、荷物の積み付けを行う。
【0053】
また、上記初期解作成の過程では、配送オーダデータおよびマスタデータにある次に示すような制約条件を満足するように処理を進める。
指定による積載可否: 例えば、店社指定(図3参照)と呼ばれるものは、指定された店社(輸送業者)以外の車両への積載を禁止するものがある。この他、車種クラス指定、荷姿(荷造りされた物の外見・形状)指定などがある。
【0054】
荷降し・荷積み制約: 配送する荷物を荷降し・荷積みする場所によって、荷降し・荷積みにかかる時間または作業不可時間帯といった制約がある。
配車優先制約: 先に説明した固定傭車、臨時傭車及び路線業者といった利用可能な配車の間に、配車計画を行う上での優先制約が種々ある。
不通地域の積み合わせ禁止: 1トリップ(運送1サイクル)内で積み合せられる配送先の組合せで配送先間の往来が出来ない配送先の積み合せは不可とする。これは例えば、道路事情、地理的な制約による不通地域、店社(運送業者)の営業区域による制約などがある。
トリップ毎最遠配送距離制限: トリップ回数毎に配送可能な距離の最大制限を設け、制限を超える積み合わせは不可とする。
以上が主な制約条件であるが、この他、積荷長制限など配送条件等により種々の制限がある。
【0055】
図15のステップ31(積荷を探索単位とした最適化処理31)では、積荷をJob、車両の中の運行サイクルをAgentとみなすと、図16に示す処理フローとなる。先ず、ステップ200でケースに対応した初期解作成を行う。
【0056】
次のステップ201では、全Jobと全Agentの組合せを作成し、その組合せ順をランダムに作成する。これを模式的に示したのが、図17である。JobがJ1〜JMのM個、AgentがA1〜ANのN個あるとすると、M×N個のJobとAgentの組合せを作り、その組合せをランダムに並べるというものである。
【0057】
次に、ランダムな並びの先頭(ステップ202)から順次、“あるJob”と “あるAgent”の組み合わせを取り出して入れ替え処理1(ステップ203)を行う。この入れ替え処理を、模式的に示したのが図18である。Agent:A1のJob:J1をAgent:A2に移動させる。そして、評価関数の計算(ステップ204)を行い、評価値が改善されたら(ステップ205)、以下のステップ206は行わず順番を一つ増やし(ステップ214)、ランダム順序個数を超える(ステップ215)まで繰り返す。
【0058】
ステップ205で評価値が改善されなかったら、ステップ206で新たな入れ替え処理2を行う。図19に示す処理であり、Agent:A2の中のJob をランダムに1つ選択(ここでは、Job:J2)し、Job:J1が元いたAgent:A1に移動させる。そして、評価関数の計算(ステップ207)を行い、評価値が改善されたら(ステップ208)、以下のステップ209は行わず順番を一つ増やし(ステップ214)、ランダム順序個数を超える(ステップ215)まで繰り返す。
【0059】
ステップ208で評価値が改善されなかったら、ステップ209で更なる入れ替え処理3を行う。図20に示す処理であり、Agent:A2の中のJob をランダムに1つ選択(ここでは、Job:J3)し、Job:J1が元いたAgent:A1に移動させる。そして、評価関数の計算(ステップ210)を行い、評価値が改善されたら(ステップ211)、以下のステップ212は行わず順番を一つ増やし(ステップ214)、ランダム順序個数を超える(ステップ215)まで繰り返す。
【0060】
ステップ211で評価値が改善されなかったら、ステップ212でAgent:A2の中にJobが残っているかどうかを判断し、残っていればステップ206に戻し、残っていなければこの探索では評価値が良くならないと判断して、Jobを移動前のAgentに戻し(ステップ211)、他の組合せの探索に戻る。
【0061】
ステップ215では、ランダム順序個数全ての組合せについて探索を行ったかどうかを判断し、全てにあたってみて評価値に改善があれば、更なる改善を求めてステップ203に戻る。また、全てにあたってみたが評価値に改善がなければ(ステップ216)、そこで探索終了とする。
【0062】
図15のステップ32(納入先を探索単位とした最適化処理32)では、納入先単位でまとめた荷物をJob、1車両の中のサイクルをAgentとみなすことで、図16の処理フローと同様になる。
【0063】
図15のステップ33(1車両と1車両を探索単位とした最適化処理33)のフローは、図21のようになる。図23に示すように、車両同士での探索である。 初期解の読込み300では、先の最適化処理で最適化された解、もしくは初期解作成処理で作成された解を読み込む。そして、ステップ301では、読み込まれた初期解の評価関数を式(1)に基づいて計算する。
【0064】
次のステップ303では、全ての車両同士の組み合わせを作成し、その組み合わせ順をランダムに並べる。以上を模式的に示したものが図22である。車両同士の組合せでは、自分自身との組み合わせは作成しないので、N × N−1のランダム並び順が作成されることになる。
【0065】
次に、ランダムな並び(ステップ304)の先頭から順次、組み合わせた車両をお互いに交換する処理を行う(ステップ305)。
【0066】
そして、評価関数の計算(ステップ306)で、解の改善がされたら(ステップ307)、ステップ308の処理を行わず順序を1つ進め(ステップ309)、ランダム順序個数を超えるまで繰り返す。
【0067】
評価値の改善がされなかった場合は、交換した車両を元に戻し(ステップ308)、順序を1つ進め(ステップ309)、ランダム順序個数を超えるまで繰り返す。
【0068】
ステップ311では、ランダム順序個数全ての組合せについて探索を行ったかどうかを判断(ステップ310)した後、全てにあたってみて評価値に改善があれば、更なる改善を求めてステップ305に戻る。また、全てにあたってみたが評価値に改善がなければ、そこで最終的な改善解を出力(ステップ312)して、探索終了とする。
【0069】
図15のステップ34(2車両と1車両を探索単位とした最適化処理34)のフローは、図24のようになる。 図26に探索のイメージを示す。
【0070】
初期解の読込み(ステップ400)では、先の最適化処理で最適化された解、もしくは初期解作成処理で作成された解を読み込む。読み込まれた初期解の評価関数を、式(1)に基づいて計算する(ステップ401)。
【0071】
ステップ402では、全ての車両同士の組み合わせを作成する。ステップ403では、ステップ402で作られた組み合わせと、車両の組み合わせを作成し、その組み合わせ順をランダムに並べる。以上を模式的に示したものが図25である。車両同士の組合せでは、自分自身との組み合わせは作成しないので、N × N−1 ×N−2のランダム並び順が作成されることになる。
【0072】
次に、ランダムな並び(ステップ404)の先頭から順次、2台の車両荷積んである全ての荷物を、1車両荷移動し、1車両の積荷を2車両の一方に移動する(ステップ405)。2車両のうち一方の選択はランダムに行う。以上を模式的にあらわしたものが、図26である。
【0073】
そして評価関数の計算(ステップ406)で、解の改善がされたら(ステップ407)、ステップ408の処理を行わず順序を1つ進め(ステップ409)、ランダム順序個数を超えるまで繰り返す。
【0074】
評価値の改善がされなかった場合は、交換した車両を元に戻し(ステップ408)、順序を1つ進め(ステップ409)、ランダム順序個数を超えるまで繰り返す。
【0075】
ステップ411では、ランダム順序個数全ての組合せについて探索を行ったかどうかを判断(ステップ410)した後、全てにあたってみて評価値に改善があれば、更なる改善を求めてステップ405に戻る。また、全てにあたってみたが評価値に改善がなければ、そこで最終的な改善解を出力(ステップ412)して、探索終了とする。
【0076】
図15のステップ35(運行サイクルを探索単位とした最適化処理35)では、運行サイクルをJob、車両をAgentとみなすことにより、図16の処理フローと同様となる。
【0077】
図15のステップ36(運行サイクルの平準化36)は、図27のように移動元車両のTripを他の車両に移動させることによって、平準化するものである。その処理フローを、図28に示す。
【0078】
ステップ501では、移動元車両の順序をランダムに並べる(図29参照)。
Tripと車両の全ての組み合わせを作成し、図30に示すようにその順序をランダムに並べる(ステップ502)。途中は割愛するが、ステップ515で、移動元車両の順序個数を越えれば、評価関数を計算(ステップ516)して、探索終了とする。
【0079】
図15のステップ37では、一連の探索単位による最適化処理が所定回数行われたかを判別する。指定回数行われていない場合は、ステップ31に戻り、再度最適化処理により解の改善を行う。所定回数行われた場合は、最善解を保存する(ステップ38)。
【0080】
ステップ39では、初期解が所定の回数作られたかを判別する。所定の回数作成されていない場合は、初期解を作成し、最適化処理を行う。所定の回数初期化が作成された場合は、探索シナリオによる処理を終了する。
【0081】
以上説明したように、本発明では、最適化処理方法の選択および選択した最適化処理方法の探索順を探索シナリオと呼んでおり、計画対象の違いにより探索シナリオを種々変化させることができる。各最適化処理単体でもよいし、それらいずれかの組合せでも良く、車両運行計画の対象変化に柔軟に対応できる利点がある。さらに、複数配送拠点を計画対象に加えることにより探索範囲が増加するが、計画対象の違いにより最適な探索シナリオを選ぶことにより、計算時間の短縮も期待できる。
【0082】
図31は、本発明の効果の一例を示している。ケースAは、鉄鋼製品であるコイルを198個配送する場合であり、ケースB、CおよびDはコイル数が、それぞれ278個、229個、182個の場合である。車両台数、積載率および配送にかかるコスト(ケースDの実績値にて、正規化)を、実績値と本発明による計画値と比較している。車両台数の内、実数は実際に用意した(すべき)車両台数を示し、のべ数は複数トリップ分を含めた車両台数を示している。そして、のべ数を実数で割ったものを回転率として示している。この回転率は、複数トリップがなければ1.00であり、複数トリップが多くなるほど値が大きくなり、それだけ車両を効率良く使用していることとなる。積載率は、複数トリップ分を含めた各車両への荷物の積載率の平均値を示している。さらに、燃料費・残業費・時間超過費用・固定費などの合計を、配送にかかるコストとして示している。
【0083】
実績に比べて本発明による車両運行計画では、配送にもちいる車両は、1〜4台(平均で2.5台)削減できるとともに、配送コストも、1.75〜4.07%(平均で3.24%)削減できるという効果がある。
【0084】
また、新規に車両運行計画を作成する際に、新規計画対象の配送オーダーデータ、車両などのデータに、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えて、探索処理を行うことにより最適化が図られる。例えば、最終運行サイクルの戻り走行のみ変更すれば、前述の図33がこれも前述の図34のように最適化が図られる。同様の例として図35は納入先を1つ増やした例であり、前回計画対象(納入先Bから配送拠点A(車両拠点)に戻る(4)まで)と異なる配送オーダーデータ、車両のみを対象として探索処理を行った場合である。これに対して、本発明を適用して最終運行サイクルの戻り走行(4)までを新規計画対象に加えた場合は、図35での走行(6)・(7)のような長距離走行や無駄な空車走行がなくなり最適化ができている(図36参照)。
【図面の簡単な説明】
【0085】
【図1】車両運行計画作成計算機処理フローを示す図である。
【図2】装置構成の一例を示す図である。
【図3】配送オーダデータ項目の一例を示す図である。
【図4】車両マスタ項目の一例を示す図である。
【図5】距離マスタ項目の一例を示す図である。
【図6】納入先マスタ項目の一例を示す図である。
【図7】運賃マスタ項目の一例を示す図である。
【図8】拠点マスタ項目の一例を示す図である。
【図9】仮想収入・コストマスタ項目の一例を示す図である。
【図10】最適運行計画作成処理の処理フローを示す図である。
【図11】運行サイクル(トリップ)を説明する図である。
【図12】所定就労時間内に配送作業が終了する例を示す図である。
【図13】所定就労時間内に配送作業が終了しない例を示す図である。
【図14】探索シナリオの一例を記述したプログラムを示す図である。
【図15】図14の探索シナリオの処理フローを示す図である。
【図16】積荷を探索単位とした最適化処理における詳細処理フローの一例を示す図である。
【図17】JobとAgentのランダムな組合せ順作成を説明する図である。
【図18】Jobの入れ替え処理1を説明する図である。
【図19】Jobの入れ替え処理2を説明する図である。
【図20】Jobの入れ替え処理3を説明する図である。
【図21】1車両と1車両を探索単位とした最適化処理における詳細処理フローの一例を示す図である。
【図22】車両同士のランダムな組み合わせ順の作成を示す図である。
【図23】車両の交換処理を示す図である。
【図24】2車両と1車両を探索単位とした最適化処理における詳細処理フローの一例を示す図である。
【図25】2車両と1車両同士のランダムな組み合わせ順の作成を示す図である。
【図26】2車両と1車両の交換処理を示す図である。
【図27】運行サイクルの平準化を示す図である。
【図28】運行サイクルの平準化における詳細処理フローの一例を示す図である。
【図29】移動元車両のランダムな順序の作成を示す図である。
【図30】Tripと車両同士のランダムな組み合わせ順の作成を示す図である。
【図31】本発明の効果の一例を示す図である。
【図32】配送の一例を説明する図である。
【図33】ある車両1台の運行計画の例を示す図である。
【図34】図33の例における無駄のない運行計画の例を示す図である。
【図35】ある車両1台の運行計画の他の例を示す図である。
【図36】図34の例に本発明を適用した運行計画の例を示す図である。
【符号の説明】
【0086】
1 車両運行計画作成計算機
2 マスタ管理サーバ
3 受発注システム
4 プリンター
5 コンピュータネットワーク
10 計画作成データの選択処理
11 データ読み込み処理
12 最適運行計画作成処理
13 車両運行計画表示処理
14 車両運行計画送信処理
【技術分野】
【0001】
本発明は、製造・流通業などにおける配送拠点(倉庫、工場、物流センター)に保管される製品などの運送物を、配送拠点で保有するトラック、トレーラなどの輸送手段により効率的に納入先へ配送するための車両運行計画技術に関するものである。
【背景技術】
【0002】
近年、物流の効率化・コスト削減を求める気運が高まっている。こういう気運の高まりに対して、配車計画の自動作成や作成支援を行う為の技術や装置が、種々見受けられる様になってきている。物流システムでの輸送スケジュール作成技術は、いわゆる巡回セールスマン問題やビークルルーティング問題に相当し、一定地域内に存在する顧客先の効率的な巡回計画を作成する技術がすでに開発されている。
【0003】
例えば、特許文献1に開示されている技術では、3段階にわたる求解法をとっており、品目データと、物流拠点データと、車両および車庫データとを少なくとも管理するマスター管理手段と、該マスター管理手段内のデータに基づいて、輸送依頼に応じた運行ルートの設定を行う運行ルート設定手段と、を備え、該手段が、前記データに基づき、輸送依頼に応じて1台の車両に積載し得る品目群を運行データの1つのセットとして、発着地別に複数セット作成するセット作成部と、複数のセットのうち、各隣接セット間を直列に連結可能な運行ルートの候補を複数設定するセット連結部と、運行ルートの候補のうち、輸送依頼を満足し、かつ複数の評価指標うち予め定めた1つの評価指標を最小化する運行ルートを選択するルート選択部によって構成されており、各種の制約条件を充足しつつ、かつ、所定の目標、例えば車両総台数の最小化を迅速に立案することのできる配車装置を提供している。
【0004】
また、特許文献2に開示されている技術では、物流センターから配送先への荷物輸送と、集荷先から物流センターへの荷物輸送を混載した車両の集配送先での時間制約を守った効率的な輸送スケジュールを作成する輸送計画作成方法およびシステムを提供することを目的としており、輸送スケジュールを作成する際、物流センターや集配送先拠点の位置情報を入力し、輸送すべき荷物の荷物量、集配送先、到着時刻の時間制約を含む荷物情報を入力し、輸送車両の積載量限界を含む輸送車両情報を入力する。更に輸送スケジュール作成時に各車両の巡回先拠点での、到着の遅延が猶予される最大時間と積載可能な集荷荷物と配送荷物の最大量のテーブルを作成し、複数車両の巡回拠点からなる輸送スケジュールへの荷物の集配送先拠点の追加可否の判定を前記テーブルにより行って、前記時間制約を守った条件下で前記各情報を用いて輸送車両のスケジュール作成を行っている。
【0005】
さらに、特許文献3に開示されている技術では、優先したい目的に応じた車両引き当て及び積み合わせを行うとともに、車両の得る収入と、車両にかかるコストの差を目的関数として、その目的関数を最大化するようにしている。このため、複数の配送拠点に対応して、空車走行の削減および車両回転率の向上が図れ、効率的でコスト最小かつ現実に配送可能な車両運行計画を作成することが可能である。また、目的関数の最適化処理方法を複数提案するとともに、最適化処理方法の選択および選択した最適化処理方法の探索順を規定する探索シナリオを導入したことにより、車両運行計画の対象変化に柔軟に対応できる効果と、複数配送拠点に対応することによって生じた探索空間の増大に対して、計画作成時間を短縮する効果もある。
【0006】
前記特許文献と「発明を実施するための最良の形態」において参照する非特許文献も含めて、以下に参照文献を記載する。
【特許文献1】特開2000−36093号公報
【特許文献2】特開2003−285930号公報
【特許文献3】特開2005−122679号公報
【非特許文献1】「組合せ最適化-メタ戦略を中心として-」、柳浦睦憲、茨木俊秀著、朝倉書店、2001年
【発明の開示】
【発明が解決しようとする課題】
【0007】
鉄鋼製品、重機機械等の大重量物の配送、特に200〜300Km以内に納入先、配送拠点である工場、物流センター、委託倉庫が複数点在するような近距離配送では、配送拠点、倉庫等での集荷、納入先への配送である運行サイクルを効率的に行い車両数、空車走行を削減することが、コスト低減の重要な点となる。以上の車両2台による簡単な例は、図32のような配送である。図32では、車両1と車両2とも配送拠点において集荷作業を行い、車両1は納入先A、Bに配送を行い、その後倉庫で集荷作業を行い、納入先Cに配送し、配送拠点に戻る。車両2では納入先D、Eに配送を行い、その後、一旦配送拠点に戻り、再度集荷作業を行い、納入先Fに配送を行い、配送拠点に戻るという運行サイクルをとる。図では、実線矢印で荷物を積んでの配送、破線矢印で積荷なしすなわち積荷を降ろして空車状態での走行をそれぞれ表している。
【0008】
しかし、特許文献1および特許文献2で開示された技術では、複数の納入先に対して最適な配送経路を作成するのが目的であるため、上述のような倉庫も含めた複数の配送拠点に対しての考慮はされていない。
【0009】
また、特許文献3で開示された技術では、上記問題は解消されているものの、新規に車両運行計画を作成する際には、新規計画対象の配送オーダーデータ、車両のみを対象として探索処理を行い最適化を図るため、特定の車両に注目すると、無駄な走行となっていることがある。図33は、ある車両1台の運行計画の例を示す図である。
【0010】
この例は、ある車両1台の動きを示すものであり、前回の計画において策定された一連の動き(配送拠点A(車両拠点)から納入先A(1)、納入先Aから配送拠点B(2)、配送拠点Bから納入先B(3)、納入先Bから配送拠点A(車両拠点)に戻る(4))と、新規の計画において策定された一連の動き(配送拠点A(車両拠点)から配送拠点B(5)、配送拠点Bから納入先C(6)、納入先Cから配送拠点A(車両拠点)に戻る(7))とを示している。
【0011】
図32と同様に、実線矢印で荷物を積んでの配送、破線矢印で積荷なしすなわち積荷を降ろして空車状態での走行をそれぞれ表しており、走行する場所間の距離を線分の長さでおおよそ表している(例えば、納入先Bから配送拠点A(車両拠点)(4)までの距離は、配送拠点Bから納入先B(3)までの距離の約3倍ほど長い)。前回計画時の最終運行サイクル((3)〜(4))における納入先Bから配送拠点A(車両拠点)への戻り走行(4)と、新規計画時の初回運行サイクル((5)〜(7))における、配送拠点A(車両拠点)から配送拠点Bへの走行(5)とが、ともに空車であるため無駄な走行となっていることが分る。
【0012】
このように、近接した逆方向のルートでともに空車となるケースでは、無駄な走行計画になってしまっている。そこで例えば、図33で示した例では、図34に示した走行ルートをとれば、無駄のない走行計画となる。
【0013】
すなわち、図33に示す納入先Bから配送拠点A(車両拠点)に戻る(4)ルートの代わりに、図34に示すように納入先Bから配送拠点Bに寄り(4)、配送する荷物を積込み、配送拠点A(車両拠点)(5)へ、さらに納入先Cに配送(6)し、配送拠点A(車両拠点)(7)に戻るというルートをとれば、空車で無駄に走行することなく、かつ最短距離で配送することができる。
【0014】
本発明は上記課題を解決し、点在する複数の配送拠点より積荷を集荷し、配送先へ納入する近距離配送における車両の回転率を向上させかつ、配送コストを削減する配車計画を立案する車両運行計画作成方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【0015】
請求項1に係る発明は、複数の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する方法において、運ぶべき荷物に関するデータすなわち配送オーダデータの入力および選択を促す計画作成データの選択処理工程と、前記配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理工程と、各車両が得る車両収入と、各車両を運用する際にかかる車両運用コストとの差を合計したものを目的関数とし、該目的関数を最大化する探索処理を用い、前記配送オーダデータと前記マスタデータから前記探索シナリオに基づき、車両運行計画を作成する最適運行計画作成処理工程と、作成した車両運行計画を出力するための車両運行計画出力工程とを有し、前記計画作成データの選択処理工程と前記データ読み込み処理工程では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えることを特徴とする車両運行計画作成方法である。
【0016】
また請求項2に係る発明は、複数の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する装置において、運ぶべき荷物に関するデータすなわち配送オーダデータの入力および選択を促す計画作成データの選択処理手段と、前記配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理手段と、各車両が得る車両収入と、各車両を運用する際にかかる車両運用コストとの差を合計したものを目的関数とし、該目的関数を最大化する探索処理を用い、前記配送オーダデータと前記マスタデータから前記探索シナリオに基づき、車両運行計画を作成する最適運行計画作成処理手段と、作成した車両運行計画を出力するための車両運行計画出力手段とを備え、前記計画作成データの選択処理手段と前記データ読み込み処理手段では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えることを特徴とする車両運行計画作成装置である。
【発明の効果】
【0017】
本発明によれば、優先したい目的に応じた車両引き当て及び積み合わせを行うとともに、車両の得る収入と、車両にかかるコストの差を目的関数として、その目的関数を最大化するようにしたので、複数の配送拠点に対応して、空車走行の削減および車両回転率の向上が図れ、効率的でコスト最小かつ現実に配送可能な車両運行計画を作成することが可能である。また、目的関数の最適化処理方法を複数提案するとともに、最適化処理方法の選択および選択した最適化処理方法の探索順を規定する探索シナリオを導入したことにより、車両運行計画の対象変化に柔軟に対応できる効果と、複数配送拠点に対応することによって生じた探索空間の増大に対して、計画作成時間を短縮する効果もある。
【0018】
さらに、新規に車両運行計画を作成する際に、新規計画対象の配送オーダーデータ、車両などのデータに、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えて探索処理を行うようにしたので、更なる最適化が実現できる。
【発明を実施するための最良の形態】
【0019】
以下、本発明を実施するための最良の形態について図面を用いて説明する。 図2は、本発明の装置構成の一例を示す図である。同図において、1は車両運行計画作成計算機、2はマスタ管理サーバ、3は受発注システム、4はプリンタ、5はコンピュータネットワークを示す。1〜4の装置・システムは、それぞれコンピュータネットワーク5に接続されている。車両運行計画作成計算機1は、データ読み込み手段、最適車両運行計画作成手段及び車両運行計画出力手段とキーボード、マウス、ディスプレイを備えたパーソナル・コンピュータもしくはワークステーションである。なお、本構成例では1台のみ例示であるが、配送する品種毎、支社、配送拠点等に対応して複数台で構成しても構わない。
【0020】
マスタ管理サーバ2は、車両運行計画作成に必要なマスタ類を記憶、管理するための計算機である。車両運行計画作成計算機1中のデータ読み込み手段からの要求によって、必要なマスタ類を車両運行計画作成計算機1に送信する。また、マスタ類の変更、修正などを行う。
【0021】
受発注システム3は、車両運行計画作成計算機1中のデータ読み込み手段からの要求によってオーダデータを送信する。また、車両運行計画作成計算機1中の車両運行計画出力手段から送信された車両運行計画を受信し、課金処理、出荷するオーダの確保、倉庫への出荷指示および運送会社への指示等の処理を行う。受発注システム3は、本装置例では独立した外部システムとしているが、車両運行計画作成計算機1、マスタ管理サーバ2などの内部システムとしても構わない。このことは、マスタ管理サーバ2、以下のプリンタ4などについても同様である。
【0022】
プリンタ4は、車両運行計画作成計算機1で作成された車両運行計画を印刷する。また、受発注システム3およびマスタ管理サーバ2の出力にも利用する。
【0023】
車両運行計画作成計算機1の内部で行う処理・手順を、図1に示す。 計画作成データの選択処理10では、運ぶべき荷物の配送予定日等を入力することにより、運ぶべき荷物に関するデータ(以下、配送オーダデータと記す)を選択する。
【0024】
データ読み込み処理11では、前記計画作成データの選択処理10によって選択された配送オーダデータと車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込み、次ステップ最適運行計画作成処理12に入力するためのデータを作成する。
【0025】
最適運行計画作成処理12では、データ読み込み処理11で作成された入力データより最適な車両運行計画を作成する。ここでの処理の詳細は後述する。
【0026】
車両運行計画表示処理13では、最適運行計画作成処理12で作成され運行計画をディスプレイ等に表示する。また、必要であれば図2のプリンタ4に結果を印刷させる処理を行う。
【0027】
車両運行計画送信処理14では、作成された車両運行計画を図2の受発注システム3に送信する処理を行う。 以上が、車両運行計画作成計算機1内での処理の概要である。
【0028】
以下に、配送オーダデータと車両運行計画に必要なマスタデータについて詳説する。先ず、配送オーダデータは、計画作成データ選択処理10によって選択されたデータとして、具体的には図2の受発注システム3に要求して受け取る。配送オーダデータは配送される荷物に関するデータであり、配送オーダデータの項目の一例を、図3に示す。配送オーダデータの項目には、配送される荷物の注文ID番号、納入先を判別するための納入先コード、配送する荷物の種類を判別するための製品コード、製品の種別を判別するための品種コード、配送拠点を示す拠点コード、納入時刻を示す時刻指定、製品の重量、サイズ等の情報が含まれている。
【0029】
次に、車両運行計画に必要なマスタデータは、図2のマスタ管理サーバ2に対して、車両運行計画作成に必要なマスタデータを要求して受け取る。このマスタデータには、例えば以下に示す種々のものがある。
【0030】
図4は、車両マスタと呼ばれるデータの項目の一例を示す。この車両マスタには、個々の車両を区別する車両No、所属する運送会社区分、所属する配送拠点を示す拠点コード、最大積載重量、荷台長、荷台幅等の利用できる車両の仕様に関する情報、その車両が利用できる時間帯、使用するために必要なコスト(固定費、燃料費)など個々の車両に関する情報が含まれている。配送計画作成時にコストの計算を行うとき、これらの情報を用いる。
【0031】
図5は、距離マスタと呼ばれるデータの項目の一例を示す。この距離マスタには、配送拠点から納入先、または納入先間の距離と移動速度に関するデータが含まれている。これらデータは、配送計画立案時に、配送時間の計算に用いる。
【0032】
図6は、納入先マスタと呼ばれるデータの項目の一例を示す。この納入先マスタには納入先に関するデータが含まれている。納入先マスタに含まれている項目には、納入先での荷物の降ろし時間、納入先において荷物の降ろしが可能な時間帯等がある。これらも、距離マスタと同様に、配送計画立案時に、配送時間の計算に用いる。
【0033】
図7は、運賃マスタと呼ばれるデータの項目の一例を示す。この運賃マスタには、配送距離に応じた品種毎の配送料金データに関する情報が含まれている。配送計画作成時において、各車両の得る収入を計算するときにこれらの情報を用いる。
【0034】
図8は、配送拠点マスタと呼ばれるデータの項目の一例を示す。この配送拠点マスタには、それぞれの配送拠点での積み込み時間に関してのデータが含まれている。これらは、配送計画立案時に配送時間の計算に用いる。
【0035】
図9は、仮想コストマスタと呼ばれるデータの項目の一例を示す。この仮想コストマスタには、後述する仮想コストに関してのデータが含まれており、この例では項目名称とそのコストの値とを対応付けている。これらデータは、配送計画立案時においては、目的関数の仮想コストの算出に用いる。以上、配送オーダデータと車両運行計画に必要なマスタデータの一例を説明してきたが、これに限られるものでなく、配送形態によって適宜変更・追加されるべきものである。
【0036】
車両の運行サイクル(以下、トリップとも称する)は、図11に示すように、配送拠点(倉庫など)での集荷作業、そして納入先への配送作業、さらに配送作業終了後の配送拠点への回送作業までの一連の作業を1運行サイクル(1トリップ)とするものであり、車両毎に単数または複数の運行サイクルが計画される。図12は、複数の運行サイクルが所定就労時間に収まった場合、これと反対に図13は、複数の運行サイクルが所定就労時間を超過してしまった場合を示している。
【0037】
なお、本発明では、新規に車両運行計画を作成する際に、新規計画対象の配送オーダーデータ、車両などのデータに、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えて、後述する探索処理を行い最適化を図る。新規計画の実施のタイミングが遅い場合(前回計画の終了時間に近い場合)は、最終運行サイクルの戻り走行のみが変更可能とするものの、実施のタイミングが早ければ、最終運行サイクルの行きまで変更可能とする。更に実施のタイミングが早ければ、更に前の運行サイクルの輸送経路(車両と荷物との組合せを含む)の見直しも可能として、最適化を図る。
【0038】
見直し範囲の特定に際しては、見直し対象の最早時刻の指定、運行サイクル及び行き戻りの指定などを行う。具体的な例では、前記車両マスタでの「所属する配送拠点を示す拠点コード」を見直し範囲の前回計画の運行サイクルの出発拠点の拠点コードにするとか、「その車両が利用できる時間帯」におけるスタート時間(最早時刻)を前回計画の運行サイクルでの該当時間に置き換えるなどの処理を行う。
【0039】
先に挙げた図1の最適運行計画作成処理12では、決められた制約条件を満たし、かつ与えられた目的関数を最大化(もしくは最小化)する組合せ最適問題として定式化することを基本としている。そしてこのような、組合せ最適化問題は多くの場合、近似解法と呼ばれる手法を用いて解いている。この組合せ最適化問題の近似解法に関しては、様々な手法が提案されており、その詳細は例えば、非特許文献1に記載されている。
【0040】
本発明において目的関数は、(1)式に示すものとなる。
【0041】
【数1】
各車両毎に車両収入と車両運行コストを求め、全車両合計した金額を目的関数にし、これを最大にしようとするものである。そして、(1)式における車両収入は、(2)式に示すものとなる。
【0042】
【数2】
(2)式の内、配送料金(タリフ)は、いわゆる配送運賃収入であり、一般には積荷の種類と配送拠点からの距離に応じて決まっている。鉄鋼製品であるコイルの場合では、配送先の基準距離比例定額テーブルに従った、コイル重量比例で料金が決まっている(図7参照)。
【0043】
次の仮想収入は、ボーナスとして仮想的に収入に組入れるものである。ボーナスとしては、以下のものがある(図9(1)参照)。
(1)燃料費補正ボーナス: 例えば、使用車両の店社毎の配送距離毎の定額値を決めておき加算する。
(2)車両固定費補正ボーナス: 例えば、使用車両の店社毎の定額の値を決めておき加算する。
(3)配送料金補正ボーナス: 例えば、使用車両の店社毎の補正係数を、該当車両の配送料金に掛ける。
(4)配送先集約ボーナス: 例えば、1車両の1トリップに割り当てたオーダにおいて、同じ配送先のオーダ数−1に定額を掛ける。
(5)店社収益ボーナス: 例えば、使用車両の店社毎の店社収益重み係数を該当車両の収益に掛け、さらに店社収益バイアスを加算する。
(6)異距離積み合せボーナス(負) : 例えば、同一車両に配車した配送先間で直近の配送先から最遠の配送先間の移動時間に比例値(マイナス値)を掛ける。
(7)車両使用の負のボーナス: 例えば、使用車両数により負のボーナスを加えるもの。
以上のような仮想収入を導入することにより、仮想収入が大きい車両は目的関数が大きくなるため、優先的に選択されるようになる。
【0044】
次に、(1)式における車両運行コストは、(3)式に示すものとなる。
【0045】
【数3】
(3)式の内、輸送コストは、輸送に直接かかるコストとして計上されるものであり、次のようなものが上げられる(図3〜図9参照)。
燃料費コスト: 車種クラス毎に走行に要する燃料費である。
走行時間コスト: 配送にかかる時間に関するコストである。
固定費コスト: 車両を利用する上で必要となる費用である。
【0046】
次の仮想コストは、制約条件を越えた場合のペナルティとして仮想的にコストに組入れるものである。ペナルティとしては、例えば以下のものがある(図9(2)参照)。
積載重量超過ペナルティ: トリップ毎に、車種クラス毎の最大積載量を超過した重量に比例する。
荷台サイズ超過ペナルティ: トリップ毎に、車種クラス毎の荷台長さを超過した積荷長(該当車種クラスに可能な全ての積み方で最小となる長さ)に比例する。
時刻指定遅延ペナルティ: 配送時刻が、配送指定終了時刻の配送余裕時間前の時刻より遅延した時間に比例する。
車輌利用可能時刻超過ペナルティ: 全トリップ終了時の帰還時刻が、車輌毎の利用可能終了時刻を越えた時間に比例する。
最大配送先数超過ペナルティ: トリップ毎に、最大配送先数を超過した場合、その配送先数全てに比例する。
以上のような仮想コスト(ペナルティ)を導入することにより、実行不可能領域にまで探索が可能となり、より効率的な最適化計算を行うことが出来る。ただし、解としてはペナルティの値が0のものを採用する。
【0047】
図10は、図1の最適運行計画作成処理12の処理フローを示す図である。ステップ20のデータ読み込みでは、最適運行計画作成手段で必要なデータを読み込み、最適運行計画作成処理の初期化を行う。読み込まれるデータは、前述した配送オーダデータ、車両マスタデータ、納入先マスタデータ、距離マスタデータ、運賃マスタデータ、拠点マスタデータ、仮想コストマスタデータおよび後述する探索シナリオである。
次にステップ21の探索シナリオ解釈では、読み込まれたデータのうち探索シナリオの解釈を行う。探索シナリオとは、初期解作成、各種探索単位による最適化処理、繰り返し回数、条件分岐、終了条件等を記述したものであり、人が事前に最適化する対象に応じて戦略的に入力・記憶させておく。
【0048】
各種探索単位による最適化処理には、1オーダ(1つの積荷)と1車両内の1運行サイクル、1車両内の1運行サイクル内の同一納入先のオーダをまとめたものと1車両内の1運行サイクル、1車両と1車両内の1運行サイクル、1車両と同一ではない1車両、1車両とそれぞれ同一ではない2車両等の探索単位による最適化処理がある。
【0049】
図14に探索シナリオの一例を記述したプログラムを示す。この探索シナリオを探索シナリオ解釈21では、図15のように処理フローとして解釈する。 この探索シナリオの例では、M個の初期解を作成し、作成した初期解を探索単位を変えながらの最適化をN回行うものである。図14のLOOP内のCARGOは、図15のステップ31(積荷を探索単位とした最適化処理31)に対応し、以下同様にDESTINはステップ32(納入先を探索単位とした最適化処理32)、TRUCKはステップ33(1車両と1車両を探索単位とした最適化処理33)、TRUCK1by2はステップ34(2車両と1車両を探索単位とした最適化処理34)、TRIPはステップ35(運行サイクルを探索単位とした最適化処理35)およびTRIP_DIVはステップ36(運行サイクルの平準化36)にそれぞれ対応している。
【0050】
図15の積荷を探索単位とした最適化処理31と納入先を探索単位とした最適化処理32では、配送ロットの集約、調整を行う。図15の1車両と1車両を探索単位とした最適化処理33と1車両と2車両を探索単位とした最適化処理34では、利用する車両の種類の調整を行う。図15の運行サイクルを探索単位とした最適化処理35および運行サイクルの平準化36では、運行サイクルの調整を行う。
【0051】
ステップ22では、ステップ21で解釈された最適化方法を実行する。
ステップ23では、探索シナリオによって探索された中から評価関数の値がもっとも良いものを選択し、最適運行計画作成処理を終了する。
以上が、本発明の核となる最適運行計画作成処理の概略処理フローである。では、図15の探索シナリオの処理フローを用いて、それぞれの探索方法(ステップ31〜36)について、詳述する。
【0052】
ステップ30は、探索の基になる初期解をまず作成する。本発明の場合では、配送オーダデータを車両マスタで与えられた車両に積み付ける処理を行う。初期解は、例えば以下の4ステップを経て作成する。
(1)配送オーダデータを、納入先単位にグルーピングする。
(2)納入先単位にグルーピングしたデータを、拠点から近い順にソートする。
(3)(2)でソートされた順番に、車両マスタによって与えられた車両をランダムに並べ、積載重量を超えるまで割り付ける。
(4)(3)を荷物がなくなるまで繰り返す。車両が足らなくなった場合は、車両マスタ中に定義した傭車用の車両データを新たに生成して、荷物の積み付けを行う。
【0053】
また、上記初期解作成の過程では、配送オーダデータおよびマスタデータにある次に示すような制約条件を満足するように処理を進める。
指定による積載可否: 例えば、店社指定(図3参照)と呼ばれるものは、指定された店社(輸送業者)以外の車両への積載を禁止するものがある。この他、車種クラス指定、荷姿(荷造りされた物の外見・形状)指定などがある。
【0054】
荷降し・荷積み制約: 配送する荷物を荷降し・荷積みする場所によって、荷降し・荷積みにかかる時間または作業不可時間帯といった制約がある。
配車優先制約: 先に説明した固定傭車、臨時傭車及び路線業者といった利用可能な配車の間に、配車計画を行う上での優先制約が種々ある。
不通地域の積み合わせ禁止: 1トリップ(運送1サイクル)内で積み合せられる配送先の組合せで配送先間の往来が出来ない配送先の積み合せは不可とする。これは例えば、道路事情、地理的な制約による不通地域、店社(運送業者)の営業区域による制約などがある。
トリップ毎最遠配送距離制限: トリップ回数毎に配送可能な距離の最大制限を設け、制限を超える積み合わせは不可とする。
以上が主な制約条件であるが、この他、積荷長制限など配送条件等により種々の制限がある。
【0055】
図15のステップ31(積荷を探索単位とした最適化処理31)では、積荷をJob、車両の中の運行サイクルをAgentとみなすと、図16に示す処理フローとなる。先ず、ステップ200でケースに対応した初期解作成を行う。
【0056】
次のステップ201では、全Jobと全Agentの組合せを作成し、その組合せ順をランダムに作成する。これを模式的に示したのが、図17である。JobがJ1〜JMのM個、AgentがA1〜ANのN個あるとすると、M×N個のJobとAgentの組合せを作り、その組合せをランダムに並べるというものである。
【0057】
次に、ランダムな並びの先頭(ステップ202)から順次、“あるJob”と “あるAgent”の組み合わせを取り出して入れ替え処理1(ステップ203)を行う。この入れ替え処理を、模式的に示したのが図18である。Agent:A1のJob:J1をAgent:A2に移動させる。そして、評価関数の計算(ステップ204)を行い、評価値が改善されたら(ステップ205)、以下のステップ206は行わず順番を一つ増やし(ステップ214)、ランダム順序個数を超える(ステップ215)まで繰り返す。
【0058】
ステップ205で評価値が改善されなかったら、ステップ206で新たな入れ替え処理2を行う。図19に示す処理であり、Agent:A2の中のJob をランダムに1つ選択(ここでは、Job:J2)し、Job:J1が元いたAgent:A1に移動させる。そして、評価関数の計算(ステップ207)を行い、評価値が改善されたら(ステップ208)、以下のステップ209は行わず順番を一つ増やし(ステップ214)、ランダム順序個数を超える(ステップ215)まで繰り返す。
【0059】
ステップ208で評価値が改善されなかったら、ステップ209で更なる入れ替え処理3を行う。図20に示す処理であり、Agent:A2の中のJob をランダムに1つ選択(ここでは、Job:J3)し、Job:J1が元いたAgent:A1に移動させる。そして、評価関数の計算(ステップ210)を行い、評価値が改善されたら(ステップ211)、以下のステップ212は行わず順番を一つ増やし(ステップ214)、ランダム順序個数を超える(ステップ215)まで繰り返す。
【0060】
ステップ211で評価値が改善されなかったら、ステップ212でAgent:A2の中にJobが残っているかどうかを判断し、残っていればステップ206に戻し、残っていなければこの探索では評価値が良くならないと判断して、Jobを移動前のAgentに戻し(ステップ211)、他の組合せの探索に戻る。
【0061】
ステップ215では、ランダム順序個数全ての組合せについて探索を行ったかどうかを判断し、全てにあたってみて評価値に改善があれば、更なる改善を求めてステップ203に戻る。また、全てにあたってみたが評価値に改善がなければ(ステップ216)、そこで探索終了とする。
【0062】
図15のステップ32(納入先を探索単位とした最適化処理32)では、納入先単位でまとめた荷物をJob、1車両の中のサイクルをAgentとみなすことで、図16の処理フローと同様になる。
【0063】
図15のステップ33(1車両と1車両を探索単位とした最適化処理33)のフローは、図21のようになる。図23に示すように、車両同士での探索である。 初期解の読込み300では、先の最適化処理で最適化された解、もしくは初期解作成処理で作成された解を読み込む。そして、ステップ301では、読み込まれた初期解の評価関数を式(1)に基づいて計算する。
【0064】
次のステップ303では、全ての車両同士の組み合わせを作成し、その組み合わせ順をランダムに並べる。以上を模式的に示したものが図22である。車両同士の組合せでは、自分自身との組み合わせは作成しないので、N × N−1のランダム並び順が作成されることになる。
【0065】
次に、ランダムな並び(ステップ304)の先頭から順次、組み合わせた車両をお互いに交換する処理を行う(ステップ305)。
【0066】
そして、評価関数の計算(ステップ306)で、解の改善がされたら(ステップ307)、ステップ308の処理を行わず順序を1つ進め(ステップ309)、ランダム順序個数を超えるまで繰り返す。
【0067】
評価値の改善がされなかった場合は、交換した車両を元に戻し(ステップ308)、順序を1つ進め(ステップ309)、ランダム順序個数を超えるまで繰り返す。
【0068】
ステップ311では、ランダム順序個数全ての組合せについて探索を行ったかどうかを判断(ステップ310)した後、全てにあたってみて評価値に改善があれば、更なる改善を求めてステップ305に戻る。また、全てにあたってみたが評価値に改善がなければ、そこで最終的な改善解を出力(ステップ312)して、探索終了とする。
【0069】
図15のステップ34(2車両と1車両を探索単位とした最適化処理34)のフローは、図24のようになる。 図26に探索のイメージを示す。
【0070】
初期解の読込み(ステップ400)では、先の最適化処理で最適化された解、もしくは初期解作成処理で作成された解を読み込む。読み込まれた初期解の評価関数を、式(1)に基づいて計算する(ステップ401)。
【0071】
ステップ402では、全ての車両同士の組み合わせを作成する。ステップ403では、ステップ402で作られた組み合わせと、車両の組み合わせを作成し、その組み合わせ順をランダムに並べる。以上を模式的に示したものが図25である。車両同士の組合せでは、自分自身との組み合わせは作成しないので、N × N−1 ×N−2のランダム並び順が作成されることになる。
【0072】
次に、ランダムな並び(ステップ404)の先頭から順次、2台の車両荷積んである全ての荷物を、1車両荷移動し、1車両の積荷を2車両の一方に移動する(ステップ405)。2車両のうち一方の選択はランダムに行う。以上を模式的にあらわしたものが、図26である。
【0073】
そして評価関数の計算(ステップ406)で、解の改善がされたら(ステップ407)、ステップ408の処理を行わず順序を1つ進め(ステップ409)、ランダム順序個数を超えるまで繰り返す。
【0074】
評価値の改善がされなかった場合は、交換した車両を元に戻し(ステップ408)、順序を1つ進め(ステップ409)、ランダム順序個数を超えるまで繰り返す。
【0075】
ステップ411では、ランダム順序個数全ての組合せについて探索を行ったかどうかを判断(ステップ410)した後、全てにあたってみて評価値に改善があれば、更なる改善を求めてステップ405に戻る。また、全てにあたってみたが評価値に改善がなければ、そこで最終的な改善解を出力(ステップ412)して、探索終了とする。
【0076】
図15のステップ35(運行サイクルを探索単位とした最適化処理35)では、運行サイクルをJob、車両をAgentとみなすことにより、図16の処理フローと同様となる。
【0077】
図15のステップ36(運行サイクルの平準化36)は、図27のように移動元車両のTripを他の車両に移動させることによって、平準化するものである。その処理フローを、図28に示す。
【0078】
ステップ501では、移動元車両の順序をランダムに並べる(図29参照)。
Tripと車両の全ての組み合わせを作成し、図30に示すようにその順序をランダムに並べる(ステップ502)。途中は割愛するが、ステップ515で、移動元車両の順序個数を越えれば、評価関数を計算(ステップ516)して、探索終了とする。
【0079】
図15のステップ37では、一連の探索単位による最適化処理が所定回数行われたかを判別する。指定回数行われていない場合は、ステップ31に戻り、再度最適化処理により解の改善を行う。所定回数行われた場合は、最善解を保存する(ステップ38)。
【0080】
ステップ39では、初期解が所定の回数作られたかを判別する。所定の回数作成されていない場合は、初期解を作成し、最適化処理を行う。所定の回数初期化が作成された場合は、探索シナリオによる処理を終了する。
【0081】
以上説明したように、本発明では、最適化処理方法の選択および選択した最適化処理方法の探索順を探索シナリオと呼んでおり、計画対象の違いにより探索シナリオを種々変化させることができる。各最適化処理単体でもよいし、それらいずれかの組合せでも良く、車両運行計画の対象変化に柔軟に対応できる利点がある。さらに、複数配送拠点を計画対象に加えることにより探索範囲が増加するが、計画対象の違いにより最適な探索シナリオを選ぶことにより、計算時間の短縮も期待できる。
【0082】
図31は、本発明の効果の一例を示している。ケースAは、鉄鋼製品であるコイルを198個配送する場合であり、ケースB、CおよびDはコイル数が、それぞれ278個、229個、182個の場合である。車両台数、積載率および配送にかかるコスト(ケースDの実績値にて、正規化)を、実績値と本発明による計画値と比較している。車両台数の内、実数は実際に用意した(すべき)車両台数を示し、のべ数は複数トリップ分を含めた車両台数を示している。そして、のべ数を実数で割ったものを回転率として示している。この回転率は、複数トリップがなければ1.00であり、複数トリップが多くなるほど値が大きくなり、それだけ車両を効率良く使用していることとなる。積載率は、複数トリップ分を含めた各車両への荷物の積載率の平均値を示している。さらに、燃料費・残業費・時間超過費用・固定費などの合計を、配送にかかるコストとして示している。
【0083】
実績に比べて本発明による車両運行計画では、配送にもちいる車両は、1〜4台(平均で2.5台)削減できるとともに、配送コストも、1.75〜4.07%(平均で3.24%)削減できるという効果がある。
【0084】
また、新規に車両運行計画を作成する際に、新規計画対象の配送オーダーデータ、車両などのデータに、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えて、探索処理を行うことにより最適化が図られる。例えば、最終運行サイクルの戻り走行のみ変更すれば、前述の図33がこれも前述の図34のように最適化が図られる。同様の例として図35は納入先を1つ増やした例であり、前回計画対象(納入先Bから配送拠点A(車両拠点)に戻る(4)まで)と異なる配送オーダーデータ、車両のみを対象として探索処理を行った場合である。これに対して、本発明を適用して最終運行サイクルの戻り走行(4)までを新規計画対象に加えた場合は、図35での走行(6)・(7)のような長距離走行や無駄な空車走行がなくなり最適化ができている(図36参照)。
【図面の簡単な説明】
【0085】
【図1】車両運行計画作成計算機処理フローを示す図である。
【図2】装置構成の一例を示す図である。
【図3】配送オーダデータ項目の一例を示す図である。
【図4】車両マスタ項目の一例を示す図である。
【図5】距離マスタ項目の一例を示す図である。
【図6】納入先マスタ項目の一例を示す図である。
【図7】運賃マスタ項目の一例を示す図である。
【図8】拠点マスタ項目の一例を示す図である。
【図9】仮想収入・コストマスタ項目の一例を示す図である。
【図10】最適運行計画作成処理の処理フローを示す図である。
【図11】運行サイクル(トリップ)を説明する図である。
【図12】所定就労時間内に配送作業が終了する例を示す図である。
【図13】所定就労時間内に配送作業が終了しない例を示す図である。
【図14】探索シナリオの一例を記述したプログラムを示す図である。
【図15】図14の探索シナリオの処理フローを示す図である。
【図16】積荷を探索単位とした最適化処理における詳細処理フローの一例を示す図である。
【図17】JobとAgentのランダムな組合せ順作成を説明する図である。
【図18】Jobの入れ替え処理1を説明する図である。
【図19】Jobの入れ替え処理2を説明する図である。
【図20】Jobの入れ替え処理3を説明する図である。
【図21】1車両と1車両を探索単位とした最適化処理における詳細処理フローの一例を示す図である。
【図22】車両同士のランダムな組み合わせ順の作成を示す図である。
【図23】車両の交換処理を示す図である。
【図24】2車両と1車両を探索単位とした最適化処理における詳細処理フローの一例を示す図である。
【図25】2車両と1車両同士のランダムな組み合わせ順の作成を示す図である。
【図26】2車両と1車両の交換処理を示す図である。
【図27】運行サイクルの平準化を示す図である。
【図28】運行サイクルの平準化における詳細処理フローの一例を示す図である。
【図29】移動元車両のランダムな順序の作成を示す図である。
【図30】Tripと車両同士のランダムな組み合わせ順の作成を示す図である。
【図31】本発明の効果の一例を示す図である。
【図32】配送の一例を説明する図である。
【図33】ある車両1台の運行計画の例を示す図である。
【図34】図33の例における無駄のない運行計画の例を示す図である。
【図35】ある車両1台の運行計画の他の例を示す図である。
【図36】図34の例に本発明を適用した運行計画の例を示す図である。
【符号の説明】
【0086】
1 車両運行計画作成計算機
2 マスタ管理サーバ
3 受発注システム
4 プリンター
5 コンピュータネットワーク
10 計画作成データの選択処理
11 データ読み込み処理
12 最適運行計画作成処理
13 車両運行計画表示処理
14 車両運行計画送信処理
【特許請求の範囲】
【請求項1】
複数の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する方法において、
運ぶべき荷物に関するデータすなわち配送オーダデータの入力および選択を促す計画作成データの選択処理工程と、
前記配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理工程と、
各車両が得る車両収入と、各車両を運用する際にかかる車両運用コストとの差を合計したものを目的関数とし、該目的関数を最大化する探索処理を用い、前記配送オーダデータと前記マスタデータから前記探索シナリオに基づき、車両運行計画を作成する最適運行計画作成処理工程と、
作成した車両運行計画を出力するための車両運行計画出力工程とを有し、
前記計画作成データの選択処理工程と前記データ読み込み処理工程では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えることを特徴とする車両運行計画作成方法。
【請求項2】
複数の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する装置において、
運ぶべき荷物に関するデータすなわち配送オーダデータの入力および選択を促す計画作成データの選択処理手段と、
前記配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理手段と、
各車両が得る車両収入と、各車両を運用する際にかかる車両運用コストとの差を合計したものを目的関数とし、該目的関数を最大化する探索処理を用い、前記配送オーダデータと前記マスタデータから前記探索シナリオに基づき、車両運行計画を作成する最適運行計画作成処理手段と、
作成した車両運行計画を出力するための車両運行計画出力手段とを備え、
前記計画作成データの選択処理手段と前記データ読み込み処理手段では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えることを特徴とする車両運行計画作成装置。
【請求項1】
複数の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する方法において、
運ぶべき荷物に関するデータすなわち配送オーダデータの入力および選択を促す計画作成データの選択処理工程と、
前記配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理工程と、
各車両が得る車両収入と、各車両を運用する際にかかる車両運用コストとの差を合計したものを目的関数とし、該目的関数を最大化する探索処理を用い、前記配送オーダデータと前記マスタデータから前記探索シナリオに基づき、車両運行計画を作成する最適運行計画作成処理工程と、
作成した車両運行計画を出力するための車両運行計画出力工程とを有し、
前記計画作成データの選択処理工程と前記データ読み込み処理工程では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えることを特徴とする車両運行計画作成方法。
【請求項2】
複数の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する装置において、
運ぶべき荷物に関するデータすなわち配送オーダデータの入力および選択を促す計画作成データの選択処理手段と、
前記配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理手段と、
各車両が得る車両収入と、各車両を運用する際にかかる車両運用コストとの差を合計したものを目的関数とし、該目的関数を最大化する探索処理を用い、前記配送オーダデータと前記マスタデータから前記探索シナリオに基づき、車両運行計画を作成する最適運行計画作成処理手段と、
作成した車両運行計画を出力するための車両運行計画出力手段とを備え、
前記計画作成データの選択処理手段と前記データ読み込み処理手段では、前回計画時の少なくとも最終運行サイクルを加えたものを対象として加えることを特徴とする車両運行計画作成装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【図30】
【図31】
【図32】
【図33】
【図34】
【図35】
【図36】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【図30】
【図31】
【図32】
【図33】
【図34】
【図35】
【図36】
【公開番号】特開2010−150020(P2010−150020A)
【公開日】平成22年7月8日(2010.7.8)
【国際特許分類】
【出願番号】特願2008−331803(P2008−331803)
【出願日】平成20年12月26日(2008.12.26)
【出願人】(000001258)JFEスチール株式会社 (8,589)
【Fターム(参考)】
【公開日】平成22年7月8日(2010.7.8)
【国際特許分類】
【出願日】平成20年12月26日(2008.12.26)
【出願人】(000001258)JFEスチール株式会社 (8,589)
【Fターム(参考)】
[ Back to top ]