水売り行商人問題
スポンサーリンク
概要
- 論文の詳細を見る
最短路問題は、数理計画問題において最も古典的かつ基本的な問題であり、多くの現実問題に応用されている。また、近年、各種の線形制約が付加された制約付き最短路問題に対しても多くの研究がなされているが、これらはすべて枝上の重みに関する制約を扱っている。一方、頂点上の重みに関する制約付き最短路問題、たとえば各頂点での需要が与えられたとき、訪れた頂点の需要量の合計がQ以内であるような最短路を見つける問題などはあまり議論されていない。本研究では、この問題を含むより一般的な問題を「水売り行商人問題」の名のもとに議論する。この水売り行商人問題は元々、供給量の制約を持つルーティング問題の部分問題として現れてきたもので、実用面でも意味のある問題である。本論文では、まず水売り行商人問題の定式化を与え、2つのアルゴリズムを提案する。1つは、現在の頂点と供給能力の残量で状態を構成するDPによる解法で、もう1つは第k最短路を用いた解法である。最後にランダムに生成した問題に対して数値実験を行なった結果を示す。数値実験の結果によれば、第k最短路を用いた解法のほうがDPによる解法に比して一部を除いては速い。
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
関連論文
- 汎用並列分枝限定法ツールPUBBを用いた最大クリーク問題の厳密解法(整数計画(1))
- 高次元空間における安定集合多面体(整数計画(1))
- 順序複体のシェリング可能性について(離散数理と連続数理における最適化理論)
- 順序複体のシェラビリティに対する必要条件(組合せ最適化(1))
- Drawing a tree on parallel lines
- NC工作機械の最適工具モジュール設計問題
- 訪問順序制約のある最短路問題の解法
- 訪問順序制約のある最短路問題 : 運搬経路計画問題に対する統一的視点
- 水売り行商人問題
- 双対問題とは?