論文

1987年

訪問順序制約のある最短路問題-運搬経路計画問題に対する統一的視点-(共著)

日本経営工学会誌
  • 鈴木 久敏
  • ,
  • 野村 重信

38
5
開始ページ
320
終了ページ
325
記述言語
日本語
掲載種別
出版者・発行元
社団法人日本経営工学会

通常の最短路問題についてはDijkstra法などの効率的な解法が知られているが, 本研究では頂点を訪問する順序に先行関係のある最短路問題について考察する.たとえば, 1台のトラックで都市u_1にある荷物を都市u_2にある荷物を都市v_2にそれぞれ運ぼうとすると, v_1を訪れる以前にu_1を訪れ, v_2以前にu_2を訪れなければならい.従来, 野村-中井〔7〕〜〔9〕はさまざまなタイプの運搬経路計画問題を議論しているが, これらの問題もすべてここで提案する訪問順序制約のある最短路問題として統一的に定式化できることを示す.最後に, この訪問順序制約のある最短路問題がNP完全であることを示す.

リンク情報
CiNii Articles
http://ci.nii.ac.jp/naid/110003934699
CiNii Books
http://ci.nii.ac.jp/ncid/AN00187973
ID情報
  • ISSN : 0386-4812
  • CiNii Articles ID : 110003934699
  • CiNii Books ID : AN00187973

エクスポート
BibTeX RIS