文献

J-GLOBAL ID：202302273999437809   整理番号：23A3214918

オンライン巡回セールスマン問題とその拡張

Online Traveling Salesman Problem and Its Extensions

著者 (1件)： 河瀬康志 (東大 大学院情報理工学系研究科)
資料名： RAMP数理最適化シンポジウム論文集  (Proceedings of the RAMP Mathematical Optimization Symposium)
巻： 35th  ページ： 101-110  発行年： 2023年11月20日 
JST資料番号： Y0030B  ISSN： 2435-2438  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 巡回セールスマン問題とは,与えられた複数の都市を全て巡り,出発地点に戻ってくる最短の経路を求める問題である.本稿では,訪問する都市が逐次的に与えられるオンライン巡回セールスマン問題について紹介する.この問題は,物流やロボットの動作計画などの応用をもつ.さらに,オンライン巡回セールスマン問題の拡張であるオンラインデマンドバス問題についても紹介する.この問題では,乗客の乗り降りの場所がリクエストとして逐次的に与えられる状況において,乗客を全て運んだ後に出発地点になるべく早く戻ることを目指す.特に,降車地に関する情報が,リクエスト時に与えられる場合と,乗客を乗せた時点で与えられる場合とで,問題の難しさがどのように変わるかについて紹介する.(著者抄録)

シソーラス用語： *巡回セールスマン問題 ,  最短路問題 ,  ネットワーク法 ,  最適化 ,  *オンライン処理 ,  *デマンドバスシステム ,  比率 ,  *組合せ最適化問題 ,  アルゴリズム ,  動作計画 ,  最適戦略 ,  計算アルゴリズム ,  改変
準シソーラス用語： *オンライン最適化 ,  競合比 ,  オンラインアルゴリズム ,  *貪欲アルゴリズム

分類 (2件)： ネットワーク法  (KA03040X) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： オンライン ,  巡回セールスマン問題 ,  拡張