特許ウォッチ

公開番号2025115798
公報種別公開特許公報(A)
公開日2025-08-07
出願番号2024010447
出願日2024-01-26
発明の名称配送計画装置、配送計画方法、及びプログラム
出願人NTT株式会社,学校法人早稲田大学
代理人弁理士法人ITOH,個人,個人,個人
主分類G06Q 10/047 20230101AFI20250731BHJP(計算;計数)
要約【課題】異質な特性を持つ移動体群を対象とした配送計画を適切に行うための技術を提供する。
【解決手段】配送計画装置において、ある場所から出発する複数の移動体からなる移動体群により複数のノードに対してサービス提供を行うために、移動コストを最小化するように、各移動体の経路を決定するアルゴリズム計算部を備え、前記アルゴリズム計算部は、
各移動体についての、移動体のノードへの最小到達時間と、各移動体についての、ノードにおける移動体の容量に対する相対的需要とを有するノード特徴を、前記移動体群の状態に基づいて、ノード毎に算出するエンコーダと、前記ノード特徴に基づいて、対象移動体に対する目的地ノード毎の確率を算出するデコーダとを備えるように構成する。
【選択図】図3
特許請求の範囲【請求項１】
ある場所から出発する複数の移動体からなる移動体群により複数のノードに対してサービス提供を行うために、移動コストを最小化するように、各移動体の経路を決定するアルゴリズム計算部を備え、
前記アルゴリズム計算部は、
各移動体についての、移動体のノードへの最小到達時間と、各移動体についての、ノードにおける移動体の容量に対する相対的需要とを有するノード特徴を、前記移動体群の状態に基づいて、ノード毎に算出するエンコーダと、
前記ノード特徴に基づいて、対象移動体に対する目的地ノード毎の確率を算出するデコーダと
を備える配送計画装置。
続きを表示（約 780 文字）【請求項２】
前記アルゴリズム計算部は、ある移動体が目的地ノードに到達したときに、当該移動体を前記対象移動体として決定し、当該対象移動体に対する目的地ノードを決定する
請求項１に記載の配送計画装置。
【請求項３】
前記アルゴリズム計算部は、複数の移動体のうち、目的地ノードに到達するまでにかかる時間が最小の移動体における当該時間だけ、前記移動体群において統一されたタイムラインをシフトさせる
請求項１に記載の配送計画装置。
【請求項４】
前記アルゴリズム計算部は、２つの連続するステップで、ある移動体に対する目的地ノードとして、出発地点を選択することにより、当該移動体を非稼働とする
請求項１に記載の配送計画装置。
【請求項５】
エンコーダとデコーダとを含むアルゴリズム計算部を備える配送計画装置が実行する配送計画方法であって、
前記アルゴリズム計算部が、ある場所から出発する複数の移動体からなる移動体群により複数のノードに対してサービス提供を行うために、移動コストを最小化するように、各移動体の経路を決定する計画ステップを備え、
前記計画ステップにおいて、
前記エンコーダが、各移動体についての、移動体のノードへの最小到達時間と、各移動体についての、ノードにおける移動体の容量に対する相対的需要とを有するノード特徴を、前記移動体群の状態に基づいて、ノード毎に算出し、
前記デコーダが、前記ノード特徴に基づいて、対象移動体に対する目的地ノード毎の確率を算出する
配送計画方法。
【請求項６】
コンピュータを、請求項１ないし４のうちずれか１項に記載の配送計画装置におけるアルゴリズム計算部として機能させるためのプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、配送計画問題を解く技術に関連するものである。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
配送計画問題（ＶＲＰ:vehicle routing problem）とは、荷物の集積所（サービスセンター）から各顧客（各ノード）にサービス車両を使用して荷物を配送するときに、どのサービス車両がどの顧客をどの順番で回れば最適か（コストが最も低くなるか）を考える最適化問題である。なお、「配送計画問題」を「配車計画問題」と称してもよい。また、ＶＲＰと同様の問題として、ＴＳＰ（Traveling Salesman Problem）がある。ＶＲＰはＴＳＰの一般化として提案されたものである。
【０００３】
古典的なＶＲＰでは、均質な容量（車両における積載可能量等）を持つ車両群が同じデポ（荷物の集配所等）から出発して、需要のある顧客にサービスを提供するという問題設定がなされる。
【０００４】
ＶＲＰはＮＰ困難問題であることが知られている。従って、厳密な解法は、計算量の大きさを考慮すると、大規模な問題には適用できない。このような課題を解決するために、ＶＲＰにDeep Re-enforcement Learning（DRL、深層強化学習）を適用する多くの従来技術が存在する。ＤＲＬを使用する初期の手法では複数の経路を走行する単一容量の車両を想定して問題設定を単純化している（これを単一ＶＲＰと呼ぶ）。
【先行技術文献】
【非特許文献】
【０００５】
Li, J. et al., 2022. Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem. IEEE Transactions on Cybernetics, pp. 52(12):13572 - 13585..
【発明の概要】
【発明が解決しようとする課題】
【０００６】
近年、現実世界のセッティングに合わせるために、異質な特性を持つ車両群を対象としたＨＶＲＰ(Heterogenous VRP)が提案されている（例えば非特許文献１）。
【０００７】
しかし、従来技術においては、上述した単一ＶＲＰの手法をＨＶＲＰに適用することは困難であった。すなわち、従来技術では、異質な特性を持つ移動体群を対象とした配送計画を適切に行うことができなかった。
【０００８】
本発明は上記の点に鑑みてなされたものであり、異質な特性を持つ移動体群を対象とした配送計画を適切に行うための技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
開示の技術によれば、ある場所から出発する複数の移動体からなる移動体群により複数のノードに対してサービス提供を行うために、移動コストを最小化するように、各移動体の経路を決定するアルゴリズム計算部を備え、
前記アルゴリズム計算部は、
各移動体についての、移動体のノードへの最小到達時間と、各移動体についての、ノードにおける移動体の容量に対する相対的需要とを有するノード特徴を、前記移動体群の状態に基づいて、ノード毎に算出するエンコーダと、
前記ノード特徴に基づいて、対象移動体に対する目的地ノード毎の確率を算出するデコーダと
を備える配送計画装置が提供される。
【発明の効果】
【００１０】
開示の技術によれば、異質な特性を持つ移動体群を対象とした配送計画を適切に行うための技術が提供される。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許