特許ウォッチ

公開番号2024080649
公報種別公開特許公報(A)
公開日2024-06-13
出願番号2023200007
出願日2023-11-27
発明の名称車両経路選択問題及びその変形例の経路生成
出願人富士通株式会社
代理人個人,個人
主分類G06Q 10/047 20230101AFI20240606BHJP(計算;計数)
要約【課題】車両経路選択問題及びその変形例の経路生成を提供する。
【解決手段】実施形態の態様によれば、動作は、車両経路選択問題に関連するデータを受信するステップを含み、前記データは、地理的領域内の複数の車両に関する第1情報と、前記複数の車両がサービスを提供するよう要求される位置のセットに関する第2情報とを含む。動作は、更に、前記データに基づいて多目的クラスタリング問題の式を決定するステップと、前記式をQUBO式に変換するステップと、を含む。動作は、更に、最適化ソルバーマシン上で前記QUBO式を解くことによって二値解を生成するステップを含む。動作は、更に、二値解に基づいて前記位置のセットを位置クラスタに分割し、前記位置クラスタに基づいて前記複数の車両の候補経路のセットを生成するステップを含む。動作は、更に、前記候補経路のセットに基づいて前記複数の車両の少なくとも1つの経路推奨をレンダリングするよう装置を制御するステップを含む。
【選択図】図1
特許請求の範囲【請求項１】
プロセッサによって実行される方法であって、
車両経路選択問題に関連するデータを受信するステップであって、前記データは、地理的領域内の複数の車両に関する第１情報と、前記複数の車両がサービスを提供するよう要求される位置のセットに関する第２情報とを含む、ステップと、
前記データに基づいて多目的クラスタリング問題の式を決定するステップと、
前記式を二次制約なし二値最適化（QUBO）式に変換するステップと、
最適化ソルバーマシンで前記QUBO式を解くことにより二値解を生成するステップと、
前記二値解に基づいて前記位置のセットを位置クラスタのセットに分割するステップと、
前記位置クラスタのセットに基づいて前記複数の車両の候補経路のセットを生成するステップと、
前記候補経路のセットに基づいて前記複数の車両の少なくとも１つの経路推奨をレンダリングするようにユーザ装置を制御するステップと、
を含む方法。
続きを表示（約 1,000 文字）【請求項２】
前記データは、前記複数の車両に関連する第１制約と、前記位置のセットに関連する第２制約と、を更に含む、請求項１に記載の方法。
【請求項３】
前記第１制約は容量制約であり、前記第２制約は要求制約である、請求項２に記載の方法。
【請求項４】
前記多目的クラスタリング問題は、複数の目的関数と、前記複数の目的関数に適用可能な制約のセットとを含み、
前記複数の目的関数は、前記位置のセットの前記位置クラスタのセットへの最適な分割を得るために最小化される、請求項１に記載の方法。
【請求項５】
前記複数の目的関数は、
前記位置のセットの中の位置の各ペアの間のクラスタ内のペア毎の距離を最小化する距離ベースの目的関数と、
前記位置のセットの中の位置の各ペアの間のクラスタ内のペア毎の角度を最小化する角度ベースの目的関数とを含む、請求項４に記載の方法。
【請求項６】
前記制約のセットは、
前記位置のセットの各位置が、前記位置クラスタのセットの位置クラスタに一意に割り当てられていることを要求する第３制約と、
前記位置クラスタのセットの位置クラスタのペアの間の合計要求の差が要求閾値より下であることを要求する第４制約と、
を含む、請求項４に記載の方法。
【請求項７】
前記QUBO式に関連する重みパラメータの値を初期化するステップであって、前記QUBO式は、前記値に基づいて解かれる、請求項１に記載の方法。
【請求項８】
前記重みパラメータは、前記QUBO式における各々の二次目的関数に関連する重み係数に対応する、請求項７に記載の方法。
【請求項９】
前記位置クラスタのセットの各位置クラスタに対する経路生成問題の目的関数を決定するステップと、
前記位置クラスタのセットの各位置クラスタに対する目的関数の最小化に基づいて前記経路生成問題を解き、前記位置クラスタのセットの対応する位置クラスタに対する候補経路のセットの中の候補経路を生成するステップと、
を更に含む請求項１に記載の方法。
【請求項１０】
前記経路生成問題は、セット分割問題である、請求項９に記載の方法。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本開示で議論される実施形態は、車両経路選択問題及びその変形の経路生成に関するものである。
続きを表示（約 1,800 文字）【背景技術】
【０００２】
物流計画と輸送の分野における進歩は、車両経路選択問題（Vehicle Routing Problem （VRP））のような組合せ最適化問題の解の開発につながった。VRPは非決定性多項式時間（Non-deterministic Polynomial-time （NP））ハード最適化問題であり、その解は最適又は効率的経路の決定を含み、車両が原材料の輸送、製品流通、サプライチェーン関連プロセス、顧客位置での商品配送などのサービスを提供するために使用できる。VRPは、車両容量、配送時間枠、分割配送などのようなアプリケーション固有の制約に起因する変形（variant）を有する。VRP変形の例としては、容量制約付きVRP（capacitated VRP （CVRP））、時間枠付きCVRP（CVRP with time-widows （CVRPTW））、在庫経路選択問題（Inventory Routing Problem （IRP））、オープンVRP（Open VRP （OVRP））などがある。特定のVRP変形のソリューションは、他のVRP変形に適用できない場合がある。これは、従来の最適化ソルバーが、特定のVRP変形に適用可能な制約及び特定のVRP変形の複雑さのために、特定のVRP変形を解決するように設計されているためである。更に、組合せ最適化問題を解くように設計され得る特殊なハードウェア又はソフトウェア最適化ソルバーは、物理ハードウェアによって制約され得るか、又は組合せ最適化問題に含まれ得る多くの変数に基づいて制約され得る。ハードウェア又はソフトウェア最適化ソルバーは、より大きな問題インスタンスに対してスケーラブルでない場合がある。
【０００３】
本開示で請求される主題は、任意の欠点を解決する又は上述のような環境でのみ動作する実施形態に限定されない。むしろ、この背景技術は、本開示に記載の幾つかの実施形態が実施され得る一例である技術領域を説明するためにのみ提供される。
【発明の概要】
【０００４】
本発明の態様によると、方法は動作セットを含んでよい。動作セットは、車両経路選択問題に関連するデータを受信するステップを含む。受信データは、地理的領域内の複数の車両に関する第１情報と、複数の輸送車両がサービスを提供することが要求される可能性のある位置のセットに関する第２情報とを含むことができる。動作セットは、更に、受信データに基づいて多目的クラスタリング問題の式を決定し、多目的クラスタリング問題の式を二次制約なし二値最適化（Quadratic Unconstrained Binary Optimization （QUBO））式に変換するステップを含むことができる。動作セットは、更に、最適化ソルバーマシン上でQUBO式を解くことによって二値解を生成するステップを含んでよい。動作セットは、更に、二値解に基づいて前記位置のセットを位置クラスタのセットに分割し、位置クラスタのセットに基づいて全車両又は複数の輸送車両の候補経路のセットを生成するステップを含んでよい。動作セットは、更に、候補経路のセットに基づいて複数の車両の少なくとも１つの経路推奨をレンダリングするよう装置を制御するステップを含んでよい。
【０００５】
実施形態の目的及び利点は、請求項において特に指摘される要素、特徴、及び組み合わせにより少なくとも実現され達成される。
【０００６】
前述の一般的説明及び以下の詳細な説明は両方とも例として与えられ、説明のためであり、請求される本発明の限定ではない。
【図面の簡単な説明】
【０００７】
例示的な実施形態は、以下の添付の図面の使用を通じて更なる特殊性及び詳細事項により記載され説明される。
【０００８】
車両経路問題（VRP）の経路生成及びその変形例に関連する例示的な環境を示す図である。
【０００９】
多目的クラスタリング問題及び経路生成問題の解決に基づくVRP及びVRPの変形の例示的な経路生成システムを示すブロック図である。
【００１０】
VRP及びVRPの変形の経路生成のための実行パイプラインを示す図である。
（【００１１】以降は省略されています）

関連特許