水売り行商人問題

概要

論文の詳細を見る
最短路問題は、数理計画問題において最も古典的かつ基本的な問題であり、多くの現実問題に応用されている。また、近年、各種の線形制約が付加された制約付き最短路問題に対しても多くの研究がなされているが、これらはすべて枝上の重みに関する制約を扱っている。一方、頂点上の重みに関する制約付き最短路問題、たとえば各頂点での需要が与えられたとき、訪れた頂点の需要量の合計がQ以内であるような最短路を見つける問題などはあまり議論されていない。本研究では、この問題を含むより一般的な問題を「水売り行商人問題」の名のもとに議論する。この水売り行商人問題は元々、供給量の制約を持つルーティング問題の部分問題として現れてきたもので、実用面でも意味のある問題である。本論文では、まず水売り行商人問題の定式化を与え、2つのアルゴリズムを提案する。1つは、現在の頂点と供給能力の残量で状態を構成するDPによる解法で、もう1つは第k最短路を用いた解法である。最後にランダムに生成した問題に対して数値実験を行なった結果を示す。数値実験の結果によれば、第k最短路を用いた解法のほうがDPによる解法に比して一部を除いては速い。
社団法人日本オペレーションズ・リサーチ学会の論文

水売り行商人問題

スポンサーリンク

概要

著者

関連論文

スポンサーリンク