Special cases of routing problems and their crossings

路由问题及其交叉的特殊情况

• 批准号: 21740082
• 负责人: ODA Yoshiaki
• 金额: $ 2.83万
• 依托单位: Keio University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21740082/
• 关键词: 離散数学; 組合せ論; 巡回セールスマン問題; アルゴリズム; 計算量理論

The Traveling Salesman Problem is one of the most famous NP-hard problems. In this work, we studied polynomial time solvable cases for the problem and its extended problems ; the Vehicle Routing Problem and the Multi-Depot VRP. Especially, we focused on "crossings" for those cases. Also, we studied a problem to obtain a non-crossing Hamiltonian cycle by repeating "flip" operations and analogous problems.

旅行商问题是最著名的NP难问题之一。在这项工作中，我们研究了多项式时间可解的情况下，该问题及其扩展问题，车辆路径问题和多仓库VRP。特别是，我们专注于这些案件的“交叉点”。此外，我们研究了一个问题，以获得一个非交叉的哈密顿回路，通过重复的“翻转”操作和类似的问题。

项目成果

反転に関するいくつかの問題

反转的一些问题

• 发表时间: 2012
• 作者: R. Mukae;A. Nakamoto;Y. Oda;Y. Suzuki;山下登茂;吉田寛;小田芳彰
• 通讯作者: 小田芳彰

K6- Minors in triangulations on the non-orientable surface of genus 3

K6- 属 3 不可定向表面上的三角测量中的次要项

• 发表时间: 2010
• 期刊: Graphs Combin.
• 作者: Raiji Mukae;Atsuhiro Nakamoto;Yoshiaki Oda;Yusuke Suzuki
• 通讯作者: Yusuke Suzuki

複数の倉庫がある車両配送問題の多項式時間で解けるクラス

可以在多项式时间内解决多个仓库的车辆配送问题的类。

• 发表时间: 2010
• 作者: R. Mukae;A. Nakamoto;Y. Oda;Y. Suzuki;山下登茂;吉田寛;小田芳彰;Hiroshi Yoshida;Hiroshi Yoshida;T.Yamashita;小田芳彰
• 通讯作者: 小田芳彰