TOP特許意匠商標
特許ウォッチ Twitter
10個以上の画像は省略されています。
公開番号2024080649
公報種別公開特許公報(A)
公開日2024-06-13
出願番号2023200007
出願日2023-11-27
発明の名称車両経路選択問題及びその変形例の経路生成
出願人富士通株式会社
代理人個人,個人
主分類G06Q 10/047 20230101AFI20240606BHJP(計算;計数)
要約【課題】 車両経路選択問題及びその変形例の経路生成を提供する。
【解決手段】 実施形態の態様によれば、動作は、車両経路選択問題に関連するデータを受信するステップを含み、前記データは、地理的領域内の複数の車両に関する第1情報と、前記複数の車両がサービスを提供するよう要求される位置のセットに関する第2情報とを含む。動作は、更に、前記データに基づいて多目的クラスタリング問題の式を決定するステップと、前記式をQUBO式に変換するステップと、を含む。動作は、更に、最適化ソルバーマシン上で前記QUBO式を解くことによって二値解を生成するステップを含む。動作は、更に、二値解に基づいて前記位置のセットを位置クラスタに分割し、前記位置クラスタに基づいて前記複数の車両の候補経路のセットを生成するステップを含む。動作は、更に、前記候補経路のセットに基づいて前記複数の車両の少なくとも1つの経路推奨をレンダリングするよう装置を制御するステップを含む。
【選択図】 図1
特許請求の範囲【請求項1】
プロセッサによって実行される方法であって、
車両経路選択問題に関連するデータを受信するステップであって、前記データは、地理的領域内の複数の車両に関する第1情報と、前記複数の車両がサービスを提供するよう要求される位置のセットに関する第2情報とを含む、ステップと、
前記データに基づいて多目的クラスタリング問題の式を決定するステップと、
前記式を二次制約なし二値最適化(QUBO)式に変換するステップと、
最適化ソルバーマシンで前記QUBO式を解くことにより二値解を生成するステップと、
前記二値解に基づいて前記位置のセットを位置クラスタのセットに分割するステップと、
前記位置クラスタのセットに基づいて前記複数の車両の候補経路のセットを生成するステップと、
前記候補経路のセットに基づいて前記複数の車両の少なくとも1つの経路推奨をレンダリングするようにユーザ装置を制御するステップと、
を含む方法。
続きを表示(約 1,000 文字)【請求項2】
前記データは、前記複数の車両に関連する第1制約と、前記位置のセットに関連する第2制約と、を更に含む、請求項1に記載の方法。
【請求項3】
前記第1制約は容量制約であり、前記第2制約は要求制約である、請求項2に記載の方法。
【請求項4】
前記多目的クラスタリング問題は、複数の目的関数と、前記複数の目的関数に適用可能な制約のセットとを含み、
前記複数の目的関数は、前記位置のセットの前記位置クラスタのセットへの最適な分割を得るために最小化される、請求項1に記載の方法。
【請求項5】
前記複数の目的関数は、
前記位置のセットの中の位置の各ペアの間のクラスタ内のペア毎の距離を最小化する距離ベースの目的関数と、
前記位置のセットの中の位置の各ペアの間のクラスタ内のペア毎の角度を最小化する角度ベースの目的関数とを含む、請求項4に記載の方法。
【請求項6】
前記制約のセットは、
前記位置のセットの各位置が、前記位置クラスタのセットの位置クラスタに一意に割り当てられていることを要求する第3制約と、
前記位置クラスタのセットの位置クラスタのペアの間の合計要求の差が要求閾値より下であることを要求する第4制約と、
を含む、請求項4に記載の方法。
【請求項7】
前記QUBO式に関連する重みパラメータの値を初期化するステップであって、前記QUBO式は、前記値に基づいて解かれる、請求項1に記載の方法。
【請求項8】
前記重みパラメータは、前記QUBO式における各々の二次目的関数に関連する重み係数に対応する、請求項7に記載の方法。
【請求項9】
前記位置クラスタのセットの各位置クラスタに対する経路生成問題の目的関数を決定するステップと、
前記位置クラスタのセットの各位置クラスタに対する目的関数の最小化に基づいて前記経路生成問題を解き、前記位置クラスタのセットの対応する位置クラスタに対する候補経路のセットの中の候補経路を生成するステップと、
を更に含む請求項1に記載の方法。
【請求項10】
前記経路生成問題は、セット分割問題である、請求項9に記載の方法。
(【請求項11】以降は省略されています)

発明の詳細な説明【技術分野】
【0001】
本開示で議論される実施形態は、車両経路選択問題及びその変形の経路生成に関するものである。
続きを表示(約 1,800 文字)【背景技術】
【0002】
物流計画と輸送の分野における進歩は、車両経路選択問題(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変形を解決するように設計されているためである。更に、組合せ最適化問題を解くように設計され得る特殊なハードウェア又はソフトウェア最適化ソルバーは、物理ハードウェアによって制約され得るか、又は組合せ最適化問題に含まれ得る多くの変数に基づいて制約され得る。ハードウェア又はソフトウェア最適化ソルバーは、より大きな問題インスタンスに対してスケーラブルでない場合がある。
【0003】
本開示で請求される主題は、任意の欠点を解決する又は上述のような環境でのみ動作する実施形態に限定されない。むしろ、この背景技術は、本開示に記載の幾つかの実施形態が実施され得る一例である技術領域を説明するためにのみ提供される。
【発明の概要】
【0004】
本発明の態様によると、方法は動作セットを含んでよい。動作セットは、車両経路選択問題に関連するデータを受信するステップを含む。受信データは、地理的領域内の複数の車両に関する第1情報と、複数の輸送車両がサービスを提供することが要求される可能性のある位置のセットに関する第2情報とを含むことができる。動作セットは、更に、受信データに基づいて多目的クラスタリング問題の式を決定し、多目的クラスタリング問題の式を二次制約なし二値最適化(Quadratic Unconstrained Binary Optimization (QUBO))式に変換するステップを含むことができる。動作セットは、更に、最適化ソルバーマシン上でQUBO式を解くことによって二値解を生成するステップを含んでよい。動作セットは、更に、二値解に基づいて前記位置のセットを位置クラスタのセットに分割し、位置クラスタのセットに基づいて全車両又は複数の輸送車両の候補経路のセットを生成するステップを含んでよい。動作セットは、更に、候補経路のセットに基づいて複数の車両の少なくとも1つの経路推奨をレンダリングするよう装置を制御するステップを含んでよい。
【0005】
実施形態の目的及び利点は、請求項において特に指摘される要素、特徴、及び組み合わせにより少なくとも実現され達成される。
【0006】
前述の一般的説明及び以下の詳細な説明は両方とも例として与えられ、説明のためであり、請求される本発明の限定ではない。
【図面の簡単な説明】
【0007】
例示的な実施形態は、以下の添付の図面の使用を通じて更なる特殊性及び詳細事項により記載され説明される。
【0008】
車両経路問題(VRP)の経路生成及びその変形例に関連する例示的な環境を示す図である。
【0009】
多目的クラスタリング問題及び経路生成問題の解決に基づくVRP及びVRPの変形の例示的な経路生成システムを示すブロック図である。
【0010】
VRP及びVRPの変形の経路生成のための実行パイプラインを示す図である。
(【0011】以降は省略されています)

この特許をJ-PlatPatで参照する

関連特許

富士通株式会社
情報処理装置及び情報処理方法
13日前
富士通株式会社
光通信装置および伝送制御方法
8日前
富士通株式会社
足位置の補正方法、装置及び記憶媒体
16日前
富士通株式会社
情報処理装置,プログラムおよび制御方法
13日前
富士通株式会社
類似度判定方法および類似度判定プログラム
8日前
富士通株式会社
制御方法、制御プログラムおよび情報処理装置
15日前
富士通株式会社
特定プログラム、特定方法および情報処理装置
13日前
富士通株式会社
半導体装置、半導体装置の製造方法及び電子装置
9日前
富士通株式会社
署名支援プログラム、署名支援方法、署名支援装置
9日前
富士通株式会社
データ処理装置、データ処理方法およびプログラム
13日前
富士通株式会社
情報出力プログラム、情報出力方法及び情報処理装置
14日前
富士通株式会社
プロセッサ、命令実行プログラムおよび情報処理装置
16日前
富士通株式会社
構造解析プログラム、構造解析方法および情報処理装置
20日前
富士通株式会社
設計支援プログラム、設計支援方法および設計支援装置
21日前
富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
21日前
富士通株式会社
取引処理プログラム、取引処理方法および情報処理装置
7日前
富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
今日
富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
14日前
富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
13日前
富士通株式会社
演算処理プログラム、演算処理方法および情報処理装置
13日前
富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
13日前
富士通株式会社
情報処理プログラム、情報処理方法、および情報処理装置
16日前
富士通株式会社
機械学習プログラム、機械学習方法、及び、情報処理装置
7日前
富士通株式会社
情報処理プログラム、情報処理方法、および情報処理装置
13日前
富士通株式会社
リソース管理プログラム,管理装置及びリソース管理方法
16日前
富士通株式会社
広告管理プログラム、広告管理方法、および情報処理装置
8日前
富士通株式会社
情報処理プログラム、情報処理方法、および情報処理装置
9日前
富士通株式会社
情報処理プログラム、情報処理方法、および情報処理装置
21日前
富士通株式会社
温度調整プログラム、データ処理装置及びデータ処理方法
9日前
富士通株式会社
情報処理プログラム、情報処理方法、および情報処理装置
9日前
富士通株式会社
データ制御プログラム,データ制御方法および情報処理装置
14日前
富士通株式会社
データ生成プログラム、データ生成方法および情報処理装置
13日前
富士通株式会社
モデル生成方法、画像分類方法及び補助分類モデル訓練装置
6日前
富士通株式会社
データ制御プログラム,データ制御方法および情報処理装置
14日前
富士通株式会社
フロー制御方法、フロー制御プログラム、および情報処理装置
15日前
富士通株式会社
アラート出力プログラム、アラート出力方法及び情報処理装置
14日前
続きを見る