慶應義塾大学学術情報リポジトリ(KOARA)KeiO Associated Repository of Academic resources

慶應義塾大学学術情報リポジトリ(KOARA)

Home  »»  Listing item  »»  Detail

Detail

Item Type Article
ID
KAKEN_24540140seika  
Preview
Image
thumbnail  
Caption  
Full text
KAKEN_24540140seika.pdf
Type :application/pdf Download
Size :172.6 KB
Last updated :Jan 6, 2017
Downloads : 297

Total downloads since Jan 6, 2017 : 297
 
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
Name  
Kana  
Romanization  
Date
Issued (from:yyyy) 2016  
Issued (to:yyyy)  
Created (yyyy-mm-dd)  
Updated (yyyy-mm-dd)  
Captured (yyyy-mm-dd)  
Physical description
1 pdf  
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
text  
Genre
Research Paper  
Text version
publisher  
Related DOI
Access conditions

 
Last modified date
Dec 27, 2016 11:18:22  
Creation date
Dec 27, 2016 11:18:22  
Registerd by
mediacenter
 
History
 
Index
/ Public / Grants-in-Aid for Scientific Research / Fiscal year 2015 / Japan Society for the Promotion of Science
 
Related to
 

Ranking

most accessed items
1st 新自由主義に抗す... (427) 1st
2nd 斎藤隆夫の「粛軍... (340)
3rd 慶應義塾図書館史... (271)
4th 認知文法から考え... (265)
5th M&Aにおける... (263)

most downloaded items
1st <<Qu'... (1470) 1st
2nd 新参ファンと古参... (437)
3rd 731部隊と細菌戦 ... (314)
4th 日本における美容... (268)
5th 新自由主義に抗す... (267)

LINK

慶應義塾ホームページへ
慶應義塾大学メディアセンターデジタルコレクション
慶應義塾大学メディアセンター本部
慶應義塾研究者情報データベース