特許ウォッチ

公開番号2025094408
公報種別公開特許公報(A)
公開日2025-06-25
出願番号2023209916
出願日2023-12-13
発明の名称経路探索方法及び配送計画装置
出願人株式会社日立製作所
代理人藤央弁理士法人
主分類G01C 21/34 20060101AFI20250618BHJP(測定;試験)
要約【課題】出発地及び目的地が特定された後の経路探索に要する時間を短縮しつつ、通行規制が反映された経路を生成する。
【解決手段】道路データと規制データとに基づいてラベルデータを生成する事前探索手順と、ラベルデータに基づいて地点間の経路を決定する経路決定手順と、を含み、事前探索手順は、道路データに基づいて、複数のノードからなるハブの情報を生成する手順と、道路データ及び規制データに基づいて、ノードごとに、各ノードとハブとの間に経路を設定した場合にハブにおいて通行可能な方向をラベルデータとして保持する手順と、を含み、経路決定手順は、ハブと、ハブに進入する経路と、ハブから退出する経路と、の組合せのうち、ハブにおける通行方向と、ハブに進入する場合にハブにおいて通行可能な方向と、ハブから退出する場合にハブにおいて通行可能な方向と、が矛盾しない組合せに対応する経路を、地点間の経路として決定する手順を含む。
【選択図】図1
特許請求の範囲【請求項１】
プロセッサと、記憶装置と、を有する計算機システムが実行する経路探索方法であって、
前記記憶装置は、道路ネットワークの情報を含む道路データと、前記道路ネットワークに設定された通行規制の情報を含む規制データと、を保持し、
前記経路探索方法は、
前記プロセッサが、前記道路データと前記規制データとに基づいてラベルデータを生成する事前探索手順と、
前記プロセッサが、前記ラベルデータに基づいて地点間の経路を決定する経路決定手順と、を含み、
前記事前探索手順は、
前記プロセッサが、前記道路データに基づいて、前記道路ネットワークの複数のノードからなるハブの情報を生成する第１手順と、
前記プロセッサが、前記道路データ及び前記規制データに基づいて、前記道路ネットワークに含まれるノードごとに、前記各ノードと前記ハブとの間に経路を設定した場合に前記ハブにおいて通行可能な方向を前記ラベルデータとして保持する第２手順と、を含み、
前記経路決定手順は、
前記プロセッサが、前記ハブと、前記ハブに進入する経路と、前記ハブから退出する経路と、の組合せのうち、前記ハブにおける通行方向が、前記ハブに進入する場合に前記ハブにおいて通行可能な方向と、前記ハブから退出する場合に前記ハブにおいて通行可能な方向と、のいずれにも含まれる組合せに対応する経路を、前記地点間の経路として決定する第３手順を含むことを特徴とする経路探索方法。
続きを表示（約 3,500 文字）【請求項２】
請求項１に記載の経路探索方法であって、
前記第２手順は、
前記プロセッサが、前記道路データ及び前記規制データに基づいて、前記道路ネットワーク内の各ノードを出発して前記ハブに至る経路が前記ハブと接続するノードを示す出発地側の接続点の位置、及び、前記出発地側の接続点から前記ハブ内を通行可能な方向を含む出発地側ラベルを生成し、前記出発地側ラベルの情報を前記ラベルデータに含めて保持する手順と、
前記プロセッサが、前記道路データ及び前記規制データに基づいて、前記ハブを出発して前記道路ネットワーク内の各ノードに至る経路が前記ハブと接続するノードを示す目的地側の接続点の位置、及び、前記目的地側の接続点まで前記ハブ内を通行可能な方向を含む目的地側ラベルを生成し、前記目的地側ラベルの情報を前記ラベルデータに含めて保持する手順と、を含み、
前記第３手順は、
出発地ノード及び目的地ノードが決定した場合、前記プロセッサが、前記ラベルデータに基づいて、前記出発地ノードから前記ハブに至る経路の前記出発地側ラベルと、前記ハブから前記目的地ノードに至る経路の前記目的地側ラベルと、の組合せを選択する手順と、
前記プロセッサが、前記選択された組合せにおいて、前記出発地側の接続点から前記目的地側の接続点までの通行方向が、前記出発地側の接続点から前記ハブ内を通行可能な方向と、前記目的地側の接続点まで前記ハブ内を通行可能な方向と、のいずれにも含まれる場合に、前記ハブと前記出発地側ラベルと前記目的地側ラベルとの組合せに対応する経路を、前記出発地ノードから前記目的地ノードまでの経路として決定する手順と、を含むことを特徴とする経路探索方法。
【請求項３】
請求項２に記載の経路探索方法であって、
前記第２手順において、前記プロセッサは、前記各ノードを出発して前記ハブに至る経路のコスト、及び、前記ハブを出発して前記各ノードに至る経路のコストを算出して、それぞれ、出発地側ラベル及び目的地側ラベルに含めて前記ラベルデータに保持し、
前記第３手順において、前記プロセッサは、前記出発地側の接続点から前記目的地側の接続点までの通行方向が、前記出発地側の接続点から前記ハブ内を通行可能な方向と、前記目的地側の接続点まで前記ハブ内を通行可能な方向と、のいずれにも含まれる組合せのうち、前記ハブ内の前記出発地側の接続点から前記目的地側の接続点までの経路のコストと、前記出発地側ラベルに対応する経路のコストと、前記目的地側ラベルに対応する経路のコストと、の合計が最小となる組合せに対応する経路を、前記出発地ノードから前記目的地ノードまでの経路として決定することを特徴とする経路探索方法。
【請求項４】
請求項１に記載の経路探索方法であって、
前記ハブは、リンクによって連結された複数のノードによって表現される道路区間であることを特徴とする経路探索方法。
【請求項５】
請求項１に記載の経路探索方法であって、
前記規制データは、対象のノードと、前記対象のノードに進入する側の隣接ノードである進入側ノードと、前記対象のノードから退出する側の隣接ノードである退出側ノードと、の組合せと、前記進入側ノードから前記対象のノードに進入して前記退出側ノードに退出する通行に対する規制と、を対応付ける情報を含むことを特徴とする経路探索方法。
【請求項６】
請求項１に記載の経路探索方法であって、
前記規制データは、条件ごとに前記道路ネットワークに設定された通行規制の情報を含み、
前記事前探索手順において、前記プロセッサは、前記条件ごとに前記ラベルデータを生成し、
前記経路決定手順において、前記プロセッサは、経路探索の対象の条件に合致する前記ラベルデータに基づいて経路を決定することを特徴とする経路探索方法。
【請求項７】
請求項６に記載の経路探索方法であって、
前記条件は、時間帯又は通行する車両の種別の少なくとも一方を含むことを特徴とする経路探索方法。
【請求項８】
プロセッサと、記憶装置と、を有する配送計画装置であって、
前記記憶装置は、道路ネットワークの情報を含む道路データと、前記道路ネットワークに設定された通行規制の情報を含む規制データと、を保持し、
前記プロセッサは、
前記道路データと前記規制データとに基づいてラベルデータを生成する事前探索手順と、
前記プロセッサが、前記ラベルデータに基づいて地点間の経路を決定する経路決定手順と、を実行し、
前記事前探索手順において、前記プロセッサは、
前記道路データに基づいて、前記道路ネットワークの複数のノードからなるハブの情報を生成する第１手順と、
前記道路データ及び前記規制データに基づいて、前記道路ネットワークに含まれるノードごとに、前記各ノードと前記ハブとの間に経路を設定した場合に前記ハブにおいて通行可能な方向を前記ラベルデータとして保持する第２手順と、を実行し、
前記経路決定手順において、前記プロセッサは、
前記ハブと、前記ハブに進入する経路と、前記ハブから退出する経路と、の組合せのうち、前記ハブにおける通行方向が、前記ハブに進入する場合に前記ハブにおいて通行可能な方向と、前記ハブから退出する場合に前記ハブにおいて通行可能な方向と、のいずれにも含まれる組合せに対応する経路を、前記地点間の経路として決定する第３手順を実行することを特徴とする配送計画装置。
【請求項９】
請求項８に記載の配送計画装置であって、
前記第２手順において、前記プロセッサは、
前記道路データ及び前記規制データに基づいて、前記道路ネットワーク内の各ノードを出発して前記ハブに至る経路が前記ハブと接続するノードを示す出発地側の接続点の位置、及び、前記出発地側の接続点から前記ハブ内を通行可能な方向を含む出発地側ラベルを生成し、前記出発地側ラベルの情報を前記ラベルデータに含めて保持し、
前記道路データ及び前記規制データに基づいて、前記ハブを出発して前記道路ネットワーク内の各ノードに至る経路が前記ハブと接続するノードを示す目的地側の接続点の位置、及び、前記目的地側の接続点まで前記ハブ内を通行可能な方向を含む目的地側ラベルを生成し、前記目的地側ラベルの情報を前記ラベルデータに含めて保持し、
前記第３手順において、プロセッサは、
出発地ノード及び目的地ノードが決定した場合、前記ラベルデータに基づいて、前記出発地ノードから前記ハブに至る経路の前記出発地側ラベルと、前記ハブから前記目的地ノードに至る経路の前記目的地側ラベルと、の組合せを選択し、
前記選択された組合せにおいて、前記出発地側の接続点から前記目的地側の接続点までの通行方向が、前記出発地側の接続点から前記ハブ内を通行可能な方向と、前記目的地側の接続点まで前記ハブ内を通行可能な方向と、のいずれにも含まれる場合に、前記ハブと前記出発地側ラベルと前記目的地側ラベルとの組合せに対応する経路を、前記出発地ノードから前記目的地ノードまでの経路として決定することを特徴とする配送計画装置。
【請求項１０】
請求項９に記載の配送計画装置であって、
前記第２手順において、前記プロセッサは、前記各ノードを出発して前記ハブに至る経路のコスト、及び、前記ハブを出発して前記各ノードに至る経路のコストを算出して、それぞれ、出発地側ラベル及び目的地側ラベルに含めて前記ラベルデータに保持し、
前記第３手順において、前記プロセッサは、前記出発地側の接続点から前記目的地側の接続点までの通行方向が、前記出発地側の接続点から前記ハブ内を通行可能な方向と、前記目的地側の接続点まで前記ハブ内を通行可能な方向と、のいずれにも含まれる組合せのうち、前記ハブ内の前記出発地側の接続点から前記目的地側の接続点までの経路のコストと、前記出発地側ラベルに対応する経路のコストと、前記目的地側ラベルに対応する経路のコストと、の合計が最小となる組合せに対応する経路を、前記出発地ノードから前記目的地ノードまでの経路として決定することを特徴とする配送計画装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、経路探索技術に関し、特に、物流事業における配送計画作成時の経路探索技術に関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
物流分野における経路探索技術に関して、例えば、特開２０２３－０９５００５号公報（特許文献１）及びＵＳ２０１５／０３４７６２９（特許文献２）に開示の技術が知られている。
【０００３】
特許文献１には、「車両が配送拠点から出発し配送先間のルートの距離を走行して配送拠点に戻るまでの総走行距離の総和を定式化した目的関数を、最小とする巡回ルートを作成する配送計画立案方法は、１の配送拠点からＮ個の配送先に荷物を配送する場合、目的関数を求める前に、１の配送先からそれ以外のＮ－１個の配送先へ向かうＮ－１個のルートのうち、最長のルートから距離の降順で０％を超える除外割合までのルートをあらかじめ除外して目的関数を算出する。」と記載されている。
【０００４】
特許文献２には、任意のノードとハブとの間の経路を事前に探索しておき、出発地ノード及び目的地ノードが決定した場合に、それぞれのノードとの間の経路が既に探索されているハブを探す、ハブラベリングの技術が記載されている。
【先行技術文献】
【特許文献】
【０００５】
特開２０２３－０９５００５号公報
米国特許出願公開第２０１５／０３４７６２９号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
物流事業において配送計画を作成する場合、計画の入力として物流拠点間の経路情報マトリクスが必要となる。このとき、拠点の数の２乗に近い数の経路を探索する必要がある。個人宅への配送も想定される場合、地図上の任意の地点が配送先となる可能性があるため、事前に拠点間の経路を探索しておくことが困難であり、配送先が決定した後に短時間で多数の経路探索を行う必要がある。さらに、配送経路周辺で車両の給油又は充電が必要となる場合に、どのタイミングで給油拠点又は充電拠点に立ち寄るのが最適であるかがわからないため、上記の物流拠点に周辺の給油拠点又は充電拠点も加えた多数の拠点間の経路を探索する必要があり、さらに時間を要する。
【０００７】
特許文献１によれば、拠点間の距離に基づいて予め経路を除外することによって計算量が削減される。しかし、実際には、配送時刻の制約などによって、遠方の拠点間の経路が最適となる場合もあるため、距離に基づいて経路を除外せずに拠点間の経路探索を高速化することで計算時間を短縮することが望ましい。
【０００８】
特許文献２に記載されたハブラベリングの技術によれば、任意のノード間の全組み合わせを事前探索するのではなく、任意のノードからハブまでの経路、及び、ハブから任意のノードまでの経路が事前探索される。そして、出発地ノード及び目的地ノードが決定した場合に、決定した出発地ノードからの経路、及び、決定した出発地ノードまでの経路がいずれも事前に探索されているハブを探し、コスト最小のハブを通る経路が最短経路となる。これによって、出発地ノード及び目的地ノードが決定した後の計算時間が短縮される。
【０００９】
しかし、ハブラベリングは、上記の通り、ハブの前後で分割して事前探索をする方式であるため、ハブの前後に跨る通行規制がある場合に、その通行規制に対応した経路探索を行うことができない。例えばハブに相当する交差点において右折禁止などの通行規制がある場合に、そのハブを起点としてどの方向に通行可能であるかは、どの方向からそのハブに進入したかが分からない限り、特定することができない。このため、ハブラベリングによって探索された経路が、実際には通行できない場合がありうる。
【課題を解決するための手段】
【００１０】
上記の課題の少なくとも一つを解決するため、本発明は、プロセッサと、記憶装置と、を有する計算機システムが実行する経路探索方法であって、前記記憶装置は、道路ネットワークの情報を含む道路データと、前記道路ネットワークに設定された通行規制の情報を含む規制データと、を保持し、前記経路探索方法は、前記プロセッサが、前記道路データと前記規制データとに基づいてラベルデータを生成する事前探索手順と、前記プロセッサが、前記ラベルデータに基づいて地点間の経路を決定する経路決定手順と、を含み、前記事前探索手順は、前記プロセッサが、前記道路データに基づいて、前記道路ネットワークの複数のノードからなるハブの情報を生成する第１手順と、前記プロセッサが、前記道路データ及び前記規制データに基づいて、前記道路ネットワークに含まれるノードごとに、前記各ノードと前記ハブとの間に経路を設定した場合に前記ハブにおいて通行可能な方向を前記ラベルデータとして保持する第２手順と、を含み、前記経路決定手順は、前記プロセッサが、前記ハブと、前記ハブに進入する経路と、前記ハブから退出する経路と、の組合せのうち、前記ハブにおける通行方向が、前記ハブに進入する場合に前記ハブにおいて通行可能な方向と、前記ハブから退出する場合に前記ハブにおいて通行可能な方向と、のいずれにも含まれる組合せに対応する経路を、前記地点間の経路として決定する第３手順を含むことを特徴とする。
【発明の効果】
（【００１１】以降は省略されています）

関連特許