WEKO3
アイテム
時間制約窓を考慮した利益付き巡回セールスマン問題
https://ipsj.ixsq.nii.ac.jp/records/241486
https://ipsj.ixsq.nii.ac.jp/records/241486de9455be-070f-4727-9ecc-cbe63be7238b
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]()
2026年12月2日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
非会員:¥660, IPSJ:学会員:¥330, MPS:会員:¥0, DLIB:会員:¥0 |
Item type | SIG Technical Reports(1) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2024-12-02 | |||||||||
タイトル | ||||||||||
タイトル | 時間制約窓を考慮した利益付き巡回セールスマン問題 | |||||||||
言語 | ||||||||||
言語 | jpn | |||||||||
資源タイプ | ||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
資源タイプ | technical report | |||||||||
著者所属 | ||||||||||
神戸大学 | ||||||||||
著者所属 | ||||||||||
神戸大学 | ||||||||||
著者所属(英) | ||||||||||
en | ||||||||||
Kobe University | ||||||||||
著者所属(英) | ||||||||||
en | ||||||||||
Kobe University | ||||||||||
著者名 |
池上, 峻
× 池上, 峻
× 山口, 一章
|
|||||||||
著者名(英) |
Shun, Ikegami
× Shun, Ikegami
× Kazuaki, Yamaguchi
|
|||||||||
論文抄録 | ||||||||||
内容記述タイプ | Other | |||||||||
内容記述 | 巡回セールスマン問題とは,頂点と各頂点間の辺の重みが与えられたとき,すべての頂点を一回ずつ通る巡回路の中で路長が最短のものを求める組合せ最適化問題のである.この問題は NP 困難であり,都市が多くなると多くの計算時間を要する.本研究では旅行や観光における経路決定のモデルとして巡回セールスマン問題をもとにした問題について考える.旅行や観光などで観光地を巡る経路を決定する場合,地点の優先順位や各地点の営業時間を考慮する必要がある.本論文では,各地点に訪問した際の利益を最大化する巡回セールスマン問題である TSP with Profit に,各地点における時間窓制約を考慮した巡回セールスマン問題(TSP with Profit and TimeWindows)の二通りの定式化を示す.数理計画ソルバーを用いた実験を行い,定式化の妥当性と有効性を検証する. | |||||||||
論文抄録(英) | ||||||||||
内容記述タイプ | Other | |||||||||
内容記述 | The traveling salesman problem is a combinatorial optimization problem that, given a vertex and the weights of the edges between the vertices, finds the shortest circuit that passes through all vertices once. This problem is NP-hard and requires a lot of computation time when the number of cities is large. In this study, we consider a problem based on the TSP as a model for route determination in travel and tourism. When determining routes to tourist destinations for travel and sightseeing, it is necessary to consider the priority of points and the business hours of each point.In this paper, we present two formulations of the Traveling Salesman Problem with Profit (TSP with Profit), which considers time window constraints at each location, known as the Traveling Salesman Problem with Profit and Time Windows (TSP with Profit and Time Windows). Experiments are conducted to verify the validity and effectiveness of the formulation. | |||||||||
書誌レコードID | ||||||||||
収録物識別子タイプ | NCID | |||||||||
収録物識別子 | AN10505667 | |||||||||
書誌情報 |
研究報告数理モデル化と問題解決(MPS) 巻 2024-MPS-151, 号 6, p. 1-5, 発行日 2024-12-02 |
|||||||||
ISSN | ||||||||||
収録物識別子タイプ | ISSN | |||||||||
収録物識別子 | 2188-8833 | |||||||||
Notice | ||||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
出版者 | ||||||||||
言語 | ja | |||||||||
出版者 | 情報処理学会 |