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