课题基金 / 基金详情

Applying some polynomially solvable cases of the traveling salesman problem to the vehicle routing problem

Applying some polynomially solvable cases of the traveling salesman problem to the vehicle routing problem
将旅行商问题的一些多项式可解的情况应用于车辆路径问题
批准号：
18740058
负责人：
ODA Yoshiaki
金额：
$2.45万
依托单位：
Keio University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2006
资助国家：
日本
项目状态：
已结题
起止时间：
2006 至 2008
来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18740058/
关键词：
組合せ論離散数学アルゴリズム論巡回セールスマン問題計算量理論アルゴリズム国際研究者交流アメリカ : イギリス車両配送問題多項式時間アルゴリズム国際情報交換ニュージーランド

项目摘要

项目成果

ODA Yoshiaki的其他基金

相似基金

相关文献

中文摘要
翻译
巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効率よく解ける状況を考察するとともに、巡回セールスマン問題におけるこれらの条件を車両配送問題に適用した場合に、最適がもつ構造を明らかにした。
英文摘要
巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効率よく解ける状況を考察するとともに、巡回セールスマン問題におけるこれらの条件を車両配送問題に適用した場合に、最適がもつ構造を明らかにした。
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
3-trees with few vertices of degree 3 in circuit graphs
DOI： 10.1016/j.disc.2008.01.002
发表时间： 2009-03-06
期刊： DISCRETE MATHEMATICS
影响因子： 0.8
作者： [Nakamoto, Atsuhiro, Oda, Yoshiaki, Ota, Katsuhiro]
通讯作者： Ota, Katsuhiro
車両配送問題の多項式時間で解けるクラス
可以在多项式时间内解决车辆交付问题的类
DOI： --
发表时间： 2006
期刊：
影响因子： --
作者： [A. Nakamoto, Y. Oda and K. 0ta, 肥田野 久二男, 小田芳彰, 肥田野 久二男, 小田芳彰, Yoshiaki Oda, Yoshiaki Oda, 小田芳彰, Yoshiaki Oda, Y. Oda, Y. Oda and M. Watanabe, Yoshiaki Oda, 小田芳彰]
通讯作者： 小田芳彰
Demidenko conditions and the vehicle routing problem
Demidenko条件和车辆路径问题
DOI： --
发表时间： 2009
期刊：
影响因子： --
作者： [A. Nakamoto, Y. Oda and K. 0ta, 肥田野 久二男, 小田芳彰]
通讯作者： 小田芳彰
The number of flips required to obtain non・crossing convex cycles
获得不交叉凸循环所需的翻转次数
DOI： --
发表时间：
期刊： Lecture Notes in Computer Science (掲載決定)
影响因子： --
作者： [Atsuhiro Nakamoto, Yoshiaki Oda, Katsuhiro Ota, Kunio Hidano, Y. Oda and M. Watanabe]
通讯作者： Y. Oda and M. Watanabe
共 9 条
    Analysis of transient calcium activities in the mammalian central circadian clock
    Special cases of routing problems and their crossings
    • 批准号：
      21740082
    • 项目类别：
      Grant-in-Aid for Young Scientists (B)
    • 资助金额：
      $2.83万
    • 财政年份：
      2009
    • 负责人：
      ODA Yoshiaki
    • 依托单位：
      Keio University
    study of communicative approach for developing literacy of child with hearing and/or speech disorders
    • 批准号：
      14310144
    • 项目类别：
      Grant-in-Aid for Scientific Research (B)
    • 资助金额：
      $8.51万
    • 财政年份：
      2002
    • 负责人：
      ODA Yoshiaki
    • 依托单位：
      National Institute of Special Education
    Innovation of multi-direction program for assisting deaf awareness and social participation of children with speech and/or hearing disorder.
    海外基金