特許ウォッチ

公開番号2025040766
公報種別公開特許公報(A)
公開日2025-03-25
出願番号2023147780
出願日2023-09-12
発明の名称情報処理プログラム、情報処理方法および情報処理装置
出願人富士通株式会社
代理人弁理士法人酒井国際特許事務所
主分類G06Q 10/083 20240101AFI20250317BHJP(計算;計数)
要約【課題】未知の問題設定がなされたVRPであっても求解すること。
【解決手段】情報処理装置は、特定ノードを出発した複数の移動体が複数のノードを経由して特定ノードに戻る場合の経路であって、複数の移動体がノードを訪問する順番を示す複数の経路の集合に列生成法を適用し、複数の経路の集合から、新たに設定された経路に関する複数の条件を満たす経路を生成し、生成した経路を用いて経路選択問題を生成し、生成した経路選択問題を求解し、経路選択問題の求解結果を出力する。
【選択図】図3
特許請求の範囲【請求項１】
特定ノードを出発した複数の移動体が複数のノードを経由して前記特定ノードに戻る場合の経路であって、前記複数の移動体が前記ノードを訪問する順番を示す複数の前記経路の集合に列生成法を適用し、前記複数の経路の集合から、新たに設定された前記経路に関する複数の条件を満たす前記経路を生成し、
生成した経路を用いて経路選択問題を生成し、
生成した前記経路選択問題を求解し、
前記経路選択問題の求解結果を出力する
処理をコンピュータに実行させることを特徴とする情報処理プログラム。
続きを表示（約 1,100 文字）【請求項２】
前記新たに設定された複数の条件は、各経路に対する他の経路に依存しない制約条件を示す経路制約を含み、
前記経路を生成する処理は、前記経路制約を満たし、前記経路に関する前記目的関数の値が最小となる経路を生成することを特徴とする請求項１に記載の情報処理プログラム。
【請求項３】
前記新たに設定された複数の条件は、経路を通過する移動体数に関する移動体数制約を含み、
前記経路を生成する処理は、前記移動体数制約を満たす範囲において、前記目的関数の値が最小となる経路を生成することを特徴とする請求項２に記載の情報処理プログラム。
【請求項４】
前記新たに設定された複数の条件は、前記経路のコストに関する定義が含まれ、前記経路を生成する処理は、前記定義を基に計算される経路のコストを利用して、前記目的関数の値が最小となる経路を生成することを特徴とする請求項３に記載の情報処理プログラム。
【請求項５】
前記新たに設定された複数の条件は、前記経路の移動時間の定義が含まれ、
前記経路を生成する処理は、前記移動時間に基づく経路のコスト、前記移動時間に基づく前記移動体数制約、前記移動時間に基づく経路制約を更に利用して、前記経路を生成することを特徴とする請求項４に記載の情報処理プログラム。
【請求項６】
特定ノードを出発した複数の移動体が複数のノードを経由して前記特定ノードに戻る場合の経路であって、前記複数の移動体が前記ノードを訪問する順番を示す複数の前記経路の集合に列生成法を適用し、前記複数の経路の集合から、新たに設定された前記経路に関する複数の条件を満たす前記経路を生成し、
生成した経路を用いて経路選択問題を生成し、
生成した前記経路選択問題を求解し、
前記経路選択問題の求解結果を出力する
処理をコンピュータが実行することを特徴とする情報処理方法。
【請求項７】
特定ノードを出発した複数の運搬車が複数のノードを経由して前記特定ノードに戻る場合の経路であって、前記複数の運搬車が前記ノードを訪問する順番を示す複数の前記経路の集合に列生成法を適用し、前記複数の経路の集合から、新たに設定された前記経路に関する複数の条件を満たす前記経路を生成し、
生成した経路を用いて経路選択問題を生成し、
生成した前記経路選択問題を求解し、
前記経路選択問題の求解結果を出力する
処理を実行する制御部を有することを特徴とする情報処理装置。

発明の詳細な説明【技術分野】
【０００１】
本発明は、配送計画問題を求解する情報処理プログラム等に関する。
続きを表示（約 1,300 文字）【背景技術】
【０００２】
配送計画問題（Vehicle Routing Problem、以下VRPと表記する）は、デポと呼ばれる特定の地点から複数の移動体、たとえば運搬車で荷物を配送しデポへ帰還する経路を求める問題である。VRPは、組合せ最適化問題の代表的な問題の一つであり、古典的なVRPから実社会のVRPまで盛んに研究されている。実社会のVRPは、各配送会社固有の問題設定を含むことは珍しくなく、様々なバリエーションがある。
【０００３】
従来では、VRPの様々なバリエーションに対応するために、VRPに予め設定される固有の問題設定を基にして、求解システムを開発する作業を、VRP毎に行っている。
【先行技術文献】
【特許文献】
【０００４】
特開２０２１－１６５１９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
世界中で様々な配送計画問題に対する求解システムに関する研究が行われているが、研究されてきた求解システムは対象のVRPに特化しており、他のバリエーションのVRPに適用することが困難である。
【０００６】
たとえば、VRPを解きたい配送会社にVRPの求解システムを提供するビジネスを想定した場合、その都度、求解システムを開発することが可能だとしても高度な人材と十分な期間が必要であり、ビジネススケールの観点から現実的でない。
【０００７】
１つの側面では、本発明は、未知の問題設定がなされたVRPであっても求解することができる情報処理プログラム、情報処理方法および情報処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
第１の案では、コンピュータが次の処理を実行する。コンピュータは、特定ノードを出発した複数の移動体が複数のノードを経由して特定ノードに戻る場合の経路であって、複数の移動体がノードを訪問する順番を示す複数の経路の集合に列生成法を適用し、複数の経路の集合から、新たに設定された経路に関する複数の条件を満たす経路を生成し、生成した経路を用いて経路選択問題を生成し、生成した経路選択問題を求解し、経路選択問題の求解結果を出力する。
【発明の効果】
【０００９】
本発明は、未知の問題設定がなされたVRPであっても求解することができる。
【図面の簡単な説明】
【００１０】
図１は、列生成法の処理手順を示すフローチャートである。
図２は、局所探索法の処理手順を示すフローチャートである。
図３は、本実施例に係る情報処理装置の処理手順を示すフローチャートである。
図４は、本実施例に係る情報処理装置の構成を示す機能ブロック図である。
図５は、VRP一般形ＤＢのデータ構造の一例を示す図である。
図６は、生成部の処理の一例を説明するための図である。
図７は、実施例の情報処理装置と同様の機能を実現するコンピュータのハードウェア構成の一例を示す図である。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許