Item Type |
Article |
ID |
|
Preview |
Image |
|
Caption |
|
|
Full text |
KAKEN_24540140seika.pdf
Type |
:application/pdf |
Download
|
Size |
:172.6 KB
|
Last updated |
:Jan 6, 2017 |
Downloads |
: 359 |
Total downloads since Jan 6, 2017 : 359
|
|
Release Date |
|
Title |
Title |
経路の形を緩和した車両配送問題の多項式時間で解けるクラス
|
Kana |
ケイロ ノ カタチ オ カンワシタ シャリョウ ハイソウ モンダイ ノ タコウシキ ジカン デ トケル クラス
|
Romanization |
Keiro no katachi o kanwashita sharyo haiso mondai no takoshiki jikan de tokeru kurasu
|
|
Other Title |
Title |
Special cases of several routing problems and various relaxations of routes
|
Kana |
|
Romanization |
|
|
Creator |
Name |
小田, 芳彰
|
Kana |
オダ, ヨシアキ
|
Romanization |
Oda, Yoshiaki
|
Affiliation |
慶應義塾大学・理工学部・准教授
|
Affiliation (Translated) |
|
Role |
Research team head
|
Link |
科研費研究者番号 : 90325043
|
Name |
渡辺, 守
|
Kana |
ワタナベ, マモル
|
Romanization |
Watanabe, Mamoru
|
Affiliation |
|
Affiliation (Translated) |
|
Role |
Research team member
|
Link |
|
|
Edition |
|
Place |
|
Publisher |
|
Date |
Issued (from:yyyy) |
2016
|
Issued (to:yyyy) |
|
Created (yyyy-mm-dd) |
|
Updated (yyyy-mm-dd) |
|
Captured (yyyy-mm-dd) |
|
|
Physical description |
|
Source Title |
Name |
科学研究費補助金研究成果報告書
|
Name (Translated) |
|
Volume |
|
Issue |
|
Year |
2015
|
Month |
|
Start page |
|
End page |
|
|
ISSN |
|
ISBN |
|
DOI |
|
URI |
|
JaLCDOI |
|
NII Article ID |
|
Ichushi ID |
|
Other ID |
|
Doctoral dissertation |
Dissertation Number |
|
Date of granted |
|
Degree name |
|
Degree grantor |
|
|
Abstract |
巡回セールスマン問題とは与えられた複数の都市をすべて1回ずつ通り, 出発点に戻ってくるような最短経路を求める問題である。この問題はNP困難のクラスに属し, 都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。この問題やその一般化した問題に対し, どのような条件をみたしていれば多項式時間で解けるのかについて数学の側面から研究を行った。この研究では, 最適解が持つ経路の形の特徴付けとその証明, および具体的に最適解を求めるアルゴリズムの両方が必要である。また, これに関連する円順列, 順列, 集合の均等分割に関する問題にもいくつかの成果を得た。
The Traveling Salesman Problem is the problem to find a shortest route which starts from some city, visits each city exactly once and comes back to the initial city. This problem is one of the most famous NP-hard problems. This shows that when the number of cities increases it becomes to be hard to find a shortest route (optimal solution) in a reasonable time (polynomial time). In this work, we studied those problems from mathematical points of view and found polynomial time solvable cases for the problem and its extended routing problems. In this research area, we need not only characterizations of optimal solutions for those cases together with proofs but also algorithms to compute a shortest routes among all solutions. Also, we worked several problems on balanced partitions for cyclic permutations, permutations and sets of finite integers which relate to the Traveling Salesman Problem.
|
|
Table of contents |
|
Keyword |
|
NDC |
|
Note |
研究種目 : 基盤研究(C)(一般)
研究期間 : 2012~2015
課題番号 : 24540140
研究分野 : 数物系科学
|
|
Language |
|
Type of resource |
|
Genre |
|
Text version |
|
Related DOI |
|
Access conditions |
|
Last modified date |
|
Creation date |
|
Registerd by |
|
History |
|
Index |
|
Related to |
|