輸送計画の効率化を極める組み合わせ技術

物流業界において、輸送計画の最適化は長年にわたる課題でした。特に、輸送ルートの選定やスケジュールの調整には、時間とコストが大きくかかり、効率的な輸送組み合わせを見つけることは困難でした。また、総走行距離の削減や運賃の最小化といった要望に応えるためのシステマティックな手法が不足しているという問題もありました。

今回紹介する特許は、複数の輸送ルートを効率的に組み合わせ、最適な輸送計画を迅速に導き出すことができるシステムで、既に実用化されています。この先進的な技術がどのようなものか、詳説していきます。

発明の背景

従来から、車両の積載率を考慮して物品の輸送計画を生成する提案がありました。物品の輸送を複数組み合わせることで効率的な物品の輸送が可能となり、異なる荷主間での共同輸送を行うことで輸送コストを削減できるとされています。しかし、輸送の組み合わせを総当たりで条件合致を判断する方法では、計算量が膨大になり、迅速な組み合わせの提示が困難であることが課題とされていました。

どんな発明？

発明の目的

本発明の輸送組み合わせ列挙システムは、複数の輸送から予め設定された条件を満たす輸送の組み合わせを列挙することを目的としています。システムは、輸送情報を取得するための手段、取得した情報に基づいて組み合わせの候補となる輸送に関する上界又は下界を算出する手段、算出された上界又は下界に基づいて不適切な組み合わせを除外する手段、そして除外された候補以外から条件を満たす組み合わせを列挙する手段を含んでいます。

輸送の組み合わせは、出発地から到着地までの移動を輸送毎に重複せずに行うものであり、設定された条件には組み合わせに含まれる異なる輸送間の移動を含む総移動距離及びその総移動距離に対する輸送のみの移動距離の割合、即ち実移動率に関する条件が含まれます。算出手段は、新たな移動距離を算出し、これに基づいて候補をソートします。その後、ソートされた順番に基づき、組み合わせの候補から除外するか否かを判断します。

発明の詳細

ここからは、本発明の輸送組み合わせ列挙システム（システム10）の機能について説明していきます。システムは、逐次輸送や混載輸送の組み合わせを効率的に算出することができるように設計されています。具体的には、システムは輸送情報を取得し、条件に応じて輸送の組み合わせをソートし、組み合わせの候補を算出します。その後、特定の条件に基づいて、候補の中から不適切な組み合わせを除外し、条件を満たす組み合わせを列挙します。

処理の流れは、まず輸送情報の取得から始まり、ソート、算出、除外、列挙のステップを経て、条件を満たす輸送組み合わせを特定します。このプロセスは、特定の条件（例えば、総走行距離の上限や片道短縮率の目標など）を満たす輸送組み合わせを効率的に算出することを可能にします。

また、システムは輸送の組み合わせに関するさまざまな条件を考慮できるように設計されており、これには運賃条件や混載不可能な輸送の考慮も含まれます。この柔軟性により、ユーザーは特定のニーズに合わせてシステムを利用することができます。

本発明の輸送組み合わせ列挙システムは、特に大量の輸送情報を扱う場合に、総当たり法に比べて大幅な処理速度の向上を実現します。例えば、三角輸送の探索で4,000倍、混載輸送の探索で1,500倍の速度向上が報告されています。この高速化により、複数のマッチング依頼に対して迅速に応答することが可能になります。

このシステムは、輸送組み合わせ列挙プログラムによって実装され、コンピュータ読み取り可能な記録媒体に格納されます。プログラムは、取得モジュール、算出モジュール、除外モジュール、列挙モジュールから構成され、システムの各部と同様の機能をコンピュータ上で実行します。

このように、本発明の輸送組み合わせ列挙システムとプログラムは、輸送計画の効率化、コスト削減、環境負荷の軽減に貢献するための強力なツールとなります。

では、システムの内容について、簡単にではありますが、掘り下げていきます。

【図１】輸送組み合わせ列挙システム

取得部は、輸送に関する情報を取得する機能を担います。この部分では、輸送の出発地、目的地、輸送コスト、輸送時間などのデータが収集されます。取得したデータは、後続の処理の基礎となります。

算出部では、取得した輸送オプションを条件に基づいて分析し、ソートします。例えば、総走行距離の最小化や最適な輸送ルートの特定など、特定の目的に沿った輸送組み合わせの候補を算出します。さらに、輸送組み合わせの上界または下界を計算し、後の処理での選択肢を絞り込むための基準を提供します。

除外部では、算出部で得られた結果を基に、特定の条件を満たさない輸送組み合わせの候補を除外します。このプロセスにより、処理の効率化を図り、最終的な候補リストを精緻化します。除外の基準としては、総走行距離の上限超過、片道短縮率の目標未達、互いに混載できない輸送の組み合わせなどが考慮されます。

列挙部では、除外されずに残った輸送組み合わせの候補から、条件を満たす組み合わせを特定し、列挙します。このプロセスでは、実車率の最大化や運賃の最適化など、特定の目標に基づいた輸送組み合わせが選択されます。

処理の流れ

【図１１】輸送組み合わせ列挙システム１０が行う動作方法

1. 輸送情報の取得 (S01、取得ステップ)
・情報収集: 輸送に関連する全てのデータ、例えば出発地、目的地、輸送コスト、時間、輸送容量、特別な輸送条件などが集められます。 ・データ標準化: 取得した情報は、後続の処理で扱いやすいように標準化されます。これには、地理的位置情報の正規化や、輸送コストの単位統一などが含まれます。

2. 条件に基づくソートと算出 (S02、算出ステップ)
・ソート処理: 輸送オプションは、総走行距離の最小化、コスト効率、時間効率など、特定の目標に基づいてソートされます。これにより、最適な組み合わせの探索が容易になります。 ・上界・下界の算出: 特定の輸送組み合わせにおける総走行距離の上限や下限、片道短縮率の範囲などが計算されます。これは、不適切な組み合わせを早期に排除するための基準となります。

3. 不適切な組み合わせの除外 (S04、除外ステップ)
・条件不一致の検出: 算出された上界・下界を基に、設定された条件（総走行距離の上限超過、片道短縮率の目標未達など）を満たさない組み合わせが特定されます。 ・除外処理: 条件に合致しない輸送組み合わせは、候補リストから削除されます。これにより、処理対象となる組み合わせの数が減少し、効率的な探索が可能になります。

4. 輸送組み合わせの特定と列挙 (S06、列挙ステップ)
・条件満足の判断: 除外されずに残った輸送組み合わせから、全ての設定条件を満たすものが選択されます。 ・組み合わせの列挙: 条件を満たす輸送組み合わせは、最終的なリストとして列挙されます。このリストは、最適な輸送計画の立案に直接使用されます。

繰り返し処理
・複数の候補検討: S02からS06までの処理は、輸送ｒ₁、ｒ₂、ｒ₃の各候補について繰り返されます。これにより、可能な組み合わせの全範囲が探索されます。 ・条件の動的調整: 処理の進行に伴い、条件（例えば総走行距離の上限）の調整が行われる場合があります。これにより、より多くの有効な組み合わせが発見される可能性があります。

本発明の明細書には様々な輸送態様に応じて輸送の組み合わせの列挙システムが開示されていますが、今回は逐次輸送について簡単にみていきます。

【図２】逐次輸送の例

逐次輸送は、輸送組み合わせ列挙システムにおいて、複数の輸送を時間的に連続して組み合わせる方法といえます。この方法は、特定の輸送ｒ₁、ｒ₂、ｒ₃を効率的に組み合わせることに焦点を当てており、それぞれの輸送が特定の順序で実行されることを前提としています。

＜逐次輸送の特徴＞

連続性: 逐次輸送は、一連の輸送が順序を追って実行されることを特徴とします。各輸送は、前の輸送が完了した後に次々と開始されます。

依存関係: 輸送間の時間的および空間的な依存関係が重要です。後続の輸送は、前の輸送の終了地点を起点とするため、輸送ルートの計画において連鎖的な影響を考慮する必要があります。

＜技術的処理＞

輸送情報の取得: 逐次輸送を計画する際には、各輸送の出発地、目的地、所要時間、輸送能力などの基本情報が収集されます。

組み合わせの候補のソート: 輸送組み合わせの効率化を図るため、可能な輸送組み合わせが特定の基準（例えば総走行距離の最小化）に基づいてソートされます。

条件に基づく除外: 特定の条件（総走行距離の上限、時間制約など）を満たさない輸送組み合わせは、早期に除外されます。これにより、最終的な選択肢が絞り込まれます。

＜効率化と最適化＞

輸送計画の最適化: 逐次輸送では、総走行距離の最小化、時間効率の最大化、コスト削減などを目的とした最適化が行われます。

動的な条件調整: 輸送計画の過程で新たな情報が得られた場合、条件の調整が行われることがあります。このように複数の輸送オプション間で最適な組み合わせを迅速に特定することにより、輸送計画の効率化を実現します。特に、総走行距離の最小化や時間効率の最大化を目指す場合、逐次輸送の計画は複雑になりがちですが、このシステムにより、条件を満たす輸送の組み合わせを効率的に算出できます。また、条件に基づくソートと除外処理により、計算量を削減し、高速な結果提供を実現しています。

【図３】逐次輸送の例

図３（ａ）に示すように、算出部１２は、取得部１１から入力した輸送情報に基づいて、輸送ｒ₁の到着地ｔ₁から、輸送ｒ₂としての組み合わせの候補である別の輸送の出発地までの距離ｅ₁を算出します。この距離ｅ₁は、組み合わせの候補である別の輸送を新たに組み合わせに含めた場合の当該候補の出発地までの新たな移動距離です。算出部１２は、上記の算出を、組み合わせの候補である全ての別の輸送について行います。ここでは、算出部１２のアルゴリズムは以下のようなものになります。

１ ． Ｃ ← φ
２ ． ｆｏｒ ｂ₂ ｉｎ 拠点リスト：
３ ． 　枝刈り１
４ ． 　ｆｏｒ ｒ₂ ｉｎ ｂ₂ 出発の輸送リスト：
５ ． 　　枝刈り２
６ ． 　　ｆｏｒ ｂ₃ ｉｎ 拠点リスト：
７ ． 　　　枝刈り３
８ ． 　　　ｆｏｒ ｒ₃ ｉｎ ｂ₃ 出発の輸送リスト：
９ ． 　　　　枝刈り４
１ ０ ． 　　ｉｆ Ｌ≦実車率 ａｎｄ 総走行距離≦Ｔ
１ １ ． 　　　Ｃ ← Ｃ ∪ ｛ （ ｒ₁ ， ｒ₂ ， ｒ₃ ） ｝
１ ２ ． Ｃを出力

算出部１２は、算出した移動距離ｅ₁が短い順に、組み合わせの候補である別の輸送をソートします。即ち、算出部１２は、出発地が輸送ｒ₁の到着地ｔ₁に近い順に別の輸送をソートします。また、出発地及び到着地（拠点）の少なくとも何れかが、複数の輸送間で共通する場合には、出発地及び到着地の少なくとも何れかに当該複数の輸送を対応付けて、出発地及び到着地の少なくとも何れか毎（拠点毎）に移動距離を算出してもよいでしょう。

続いて、ソートされた順番かつ別の輸送の出発地（拠点）ｂ₂毎に以下の処理が行われます（アルゴリズムの２～１１のｆｏｒ文での繰り返しに相当）。

まず、以下のように枝刈り（枝刈り１）が行われます（アルゴリズムの３に相当）。算出部１２は、輸送ｒ₁の移動距離ｄ₁と、算出した距離ｅ₁との和ｄ₁＋ｅ₁を総走行距離の下界として算出します。続いて、除外部１３は、算出部１２によって算出された総走行距離の下界と、総走行距離の上限Ｔとを比較して、以下の式を満たすか否かを判断します。

ｄ₁＋ｅ₁＞Ｔ

上記の式を満たしていると判断した場合、除外部１３は、別の輸送を図２に示す輸送ｒ₂として含めた組み合わせは、条件を満たさないものとして列挙する組み合わせの候補から除外（枝刈り）します。

また、算出部１２は、算出した距離ｅ₁と総走行距離の上限Ｔとから、以下の値を実車率の上界として算出します。

続いて、除外部１３は、算出部１２によって算出された実車率の上界と、実車率の目標Ｌとを比較して、以下の式を満たすか否かを判断します。

上記の実車率の上界は、ｅ₁に関して単調減少です。

上記の式を満たしていると判断した場合、除外部１３は、別の輸送を図２に示す輸送ｒ₂として含めた組み合わせは、条件を満たさないものとして列挙する組み合わせの候補から除外（枝刈り）します。

また、算出部１２は、別の輸送の出発地から輸送ｒ₁の出発地ｂ₁までの距離（図３（ａ）に示す距離ｘ）を算出します。算出部１２は、輸送ｒ₁の移動距離ｄ₁と、算出した距離ｅ₁と、算出した距離ｘとの和ｄ₁＋ｅ₁＋ｘを総走行距離の下界として算出します。続いて、除外部１３は、算出部１２によって算出された総走行距離の下界と、総走行距離の上限Ｔとを比較して、以下の式を満たすか否かを判断します。

ｄ₁＋ｅ₁＋ｘ＞Ｔ

上記の式を満たしていると判断した場合、除外部１３は、別の輸送を図２に示す輸送ｒ２として含めた組み合わせは、条件を満たさないものとして列挙する組み合わせの候補から除外（枝刈り）します。

続いて、ソートされた順番かつ別の輸送毎に以下の処理が行われます（アルゴリズムの４～１１のｆｏｒ文での繰り返しに相当）。まず、以下のように枝刈り（枝刈り２）が行われます（アルゴリズムの５に相当）。

図３（ｂ）に示すように、算出部１２は、算出した距離ｅ₁と輸送の移動距離ｄ₁，ｄ₂とから、以下の値を実車率の上界として算出します。当該実車率の上界の算出は、ある地点からの別の地点へ向かう移動距離と、別の地点からある地点へ向かう逆方向の移動距離とが同一である（距離が対称である）ことを前提とするものです（以下に示すｄ₃の上界の式でこの距離の対称性が必要となります）。

続いて、除外部１３は、算出部１２によって算出された実車率の上界と、実車率の目標Ｌとを比較して、以下の式を満たすか否かを判断します。

上記の実車率の上界は、ｄ₂に関して単調増加となります。

上記の値が実車率の上界であることは以下のように示されます。

また、上記のｄ₃，ｅ₂，ｅ₃に関しての単調性は以下のように示されます。

上記の式を満たしていると判断した場合、除外部１３は、別の輸送を図２に示す輸送ｒ₂として含めた組み合わせは、条件を満たさないものとして列挙する組み合わせの候補から除外（枝刈り）します。

また、算出部１２は、別の輸送の到着地から輸送ｒ₁の出発地ｂ₁までの距離（図３（ｂ）に示す距離ｘ）を算出します。算出部１２は、輸送ｒ₁の移動距離ｄ₁と、算出した距離ｅ₁と、別の輸送の移動距離ｄ₂と、算出した距離ｘとの和ｄ₁＋ｅ₁＋ｄ₂＋ｘを総走行距離の下界として算出する。続いて、除外部１３は、算出部１２によって算出された総走行距離の下界と、総走行距離の上限Ｔとを比較して、以下の式を満たすか否かを判断します。

ｄ₁＋ｅ₁＋ｄ₂＋ｘ＞Ｔ

上記の式を満たしていると判断した場合、除外部１３は、別の輸送を図２に示す輸送ｒ₂として含めた組み合わせは、条件を満たさないものとして列挙する組み合わせの候補から除外（枝刈り）します。

上記の枝刈りによって除外されなかった別の輸送を輸送ｒ₂として、続いて、輸送ｒ₁と輸送ｒ₂との組み合わせに対して、続いて、輸送ｒ₃についての枝刈りが行われます。続いての枝刈りは、輸送ｒ₁と輸送ｒ₂との組み合わせ毎に行われます。

上記の繰り返しが全て終了したら、列挙部１４は、列挙する輸送の組み合わせの集合Ｃに含まれる全ての輸送ｒ₁，ｒ₂，ｒ₃の組み合わせを示す情報を、条件を満たす全ての輸送の組み合わせとして列挙（全列挙）します（アルゴリズムの１２に相当）。例えば、列挙部１４は、荷主の端末に、荷主の輸送ｒ₁に組み合わせ可能な輸送として、輸送ｒ₂，ｒ₃の情報を送信します。以上が、逐次輸送の組み合わせを算出する場合の輸送組み合わせ列挙システム１０の機能となります。

特徴

効率性: 総当たり法に比べて、条件を満たす輸送組み合わせを効率的に算出することができます。特に、三角輸送や混載輸送の探索において顕著な処理速度の向上が報告されています。

柔軟性: 運賃や混載不可能な輸送を考慮するなど、複数の条件を設定し、それに基づく組み合わせの算出が可能です。

スケーラビリティ: 複数のマッチング依頼や複数ユーザからの相次ぐマッチング依頼に迅速に応答できます。

実装

このシステムは、輸送組み合わせ列挙プログラムによって実装され、取得モジュール、算出モジュール、除外モジュール、列挙モジュールを含むプログラムがコンピュータ読み取り可能な記録媒体に格納されます。これにより、上述した機能がコンピュータ上で実行されます。

応用

この発明は、輸送業界における効率的な輸送計画の作成、コスト削減、環境負荷の軽減に貢献する可能性があります。また、実車率の最大化や片道短縮率の最適化など、輸送効率の向上を図ることが可能です。

ここがポイント！

この特許発明の主なポイントは、次の３点に集約されます。

輸送情報の詳細な取得と分析
出発地と到着地を含む輸送情報を利用し、効率的な組み合わせを算出します。

条件に基づく組み合わせの最適化
総移動距離及び実移動率を考慮した条件に基づき、最適な輸送組み合わせを特定します。

計算効率の向上
上界又は下界の算出により、不要な組み合わせを迅速に除外し、計算効率を大幅に向上させます。

未来予想

本発明により、輸送計画の作成と最適化がより迅速かつ正確に行われるようになります。これにより、物流コストの削減、輸送効率の向上、環境への負荷低減が実現可能となり、物流業界全体のサステナビリティへの貢献が期待されます。また、異なる荷主間での共同輸送の促進により、業界内の協力体制強化にも寄与することが予想されます。

この特許により提供されるシステムは、共同輸送マッチングシステムTranOpt（トランオプト）として既に実用化されています。

特許の概要