Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
VRPの近傍操作SWAP*について調べてみた
Search
NearMeの技術発表資料です
PRO
July 05, 2024
Technology
1
240
VRPの近傍操作SWAP*について調べてみた
NearMeの技術発表資料です
PRO
July 05, 2024
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
並列で⽣成AIにコーディングをやらせる
nearme_tech
PRO
1
50
希望休勤務を考慮したシフト作成
nearme_tech
PRO
0
21
Hub Labeling による高速経路探索
nearme_tech
PRO
0
66
Build an AI agent with Mastra
nearme_tech
PRO
0
69
Rustで強化学習アルゴリズムを実装する vol3
nearme_tech
PRO
0
37
Webアプリケーションにおけるクラスの設計再入門
nearme_tech
PRO
1
81
AIエージェント for 予約フォーム
nearme_tech
PRO
2
150
ULID生成速度を40倍にしたった
nearme_tech
PRO
2
55
Amazon AuroraとMongoDBの アーキテクチャを比較してみたら 結構違った件について
nearme_tech
PRO
0
28
Other Decks in Technology
See All in Technology
How Do I Contact HP Printer Support? [Full 2025 Guide for U.S. Businesses]
harrry1211
0
120
対話型音声AIアプリケーションの信頼性向上の取り組み
ivry_presentationmaterials
1
170
SmartNewsにおける 1000+ノード規模 K8s基盤 でのコスト最適化 – Spot・Gravitonの大規模導入への挑戦
vsanna2
0
140
スタートアップに選択肢を 〜生成AIを活用したセカンダリー事業への挑戦〜
nstock
0
230
LLM時代の検索
shibuiwilliam
2
300
AI時代の開発生産性を加速させるアーキテクチャ設計
plaidtech
PRO
3
160
無意味な開発生産性の議論から抜け出すための予兆検知とお金とAI
i35_267
6
13k
20250705 Headlamp: 專注可擴展性的 Kubernetes 用戶界面
pichuang
0
280
DBのスキルで生き残る技術 - AI時代におけるテーブル設計の勘所
soudai
PRO
52
20k
さくらのIaaS基盤のモニタリングとOpenTelemetry/OSC Hokkaido 2025
fujiwara3
3
450
United Airlines Customer Service– Call 1-833-341-3142 Now!
airhelp
0
170
React開発にStorybookとCopilotを導入して、爆速でUIを編集・確認する方法
yu_kod
1
280
Featured
See All Featured
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
331
22k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
60k
Embracing the Ebb and Flow
colly
86
4.7k
We Have a Design System, Now What?
morganepeng
53
7.7k
Being A Developer After 40
akosma
90
590k
BBQ
matthewcrist
89
9.7k
Optimising Largest Contentful Paint
csswizardry
37
3.3k
Stop Working from a Prison Cell
hatefulcrawdad
271
21k
Six Lessons from altMBA
skipperchong
28
3.9k
Large-scale JavaScript Application Architecture
addyosmani
512
110k
Building Adaptive Systems
keathley
43
2.7k
Docker and Python
trallard
44
3.5k
Transcript
0 2024-07-05 第97回NearMe技術勉強会 Kenji Hosoda VRPの近傍操作SWAP* について調べてみた
1 SWAP*に興味をもった経緯 • VRPにおける近傍操作のアルゴリズムの⼀つ • いくつかのアクティブなVRPのライブラリで取り⼊れられている ◦ https://github.com/VROOM-Project/vroom ☆1.3k ◦
https://github.com/reinterpretcat/vrp ☆329 ◦ https://github.com/PyVRP/PyVRP ☆229 • ⽐較的最近提案されている ◦ 2020年にarxivで提案 ▪ https://arxiv.org/abs/2012.10384 ◦ 2022年にComputers & Operations Researchに掲載 ▪ https://www.sciencedirect.com/science/article/abs/pii/S030505482100349X • 計算時間が愚直な実装に⽐べて → になる
2 https://developers.google.com/optimization/routing/vrp VRP(Vehicle Routing Problem)ついて ⼀連の場所を訪れる複数の⾞両の最適なルートを⾒つける 車庫 (DEPOT) 車両 1
車両 2 車両 3 車両 4
3 VRPの解き⽅ • 混合整数計画法で解く ◦ 厳密な最適化ができ、解の品質が保証される ◦ 計算時間が⾮常に⻑くなる時がある • メタヒューリスティクスで解く
◦ 厳密な最適解ではないが、実⽤的に良好な解を得られる ◦ 計算時間は⽐較的短く、時間制約を設けて解を得ることも可能 ◦ 問題に応じてアルゴリズムを調整しやすい ◦ シミュレーテッドアニーリング / 遺伝的アルゴリズム など
4 https://www.researchgate.net/publication/363632926_A_reinforcement_learning-Variable_neighborhood_search_method_for_the_capacitated_Vehicle_Routing_Problem VRPの近傍操作について • 近傍操作はメタヒューリスティクスの ⼀部として使⽤される ◦ 近傍操作を繰り返すことで局所解 を探索する •
近傍操作の例 • ルート内 ◦ エッジ繋ぎ変え (2-OPT) ◦ ノード移動 (MOVE) • ルート間 ◦ ノード交換 (SWAP) ◦ ノード移転 (RELOCATE)
5 SWAP操作について A B C D DEPOT E F G
H Route1 Route2 SWAP前の2つのルート
6 SWAP操作について A B C D DEPOT E F G
H Route1 Route2 ルート間でノードを交換する
7 SWAP操作について あるルート間のノードペアにおいては、例えば、 ノードEをRoute1のどこに挿⼊するか、ノードCをRoute2のどこに挿⼊するか、 を洗い出して、その中でベストな挿⼊ポイントを⾒つける A B C D DEPOT
E F G H Route1 Route2 A B C D DEPOT E F G H Route1 Route2 …
8 SWAP操作について • 全体としては、 ◦ ルート間のノードペアがΘ(n^2)通り ◦ あるノードペアにおける挿⼊ポイントがΘ(n^2)通り ◦ で、Θ(n^4)通りの動きがある
• 愚直な実装で、計算時間はΘ(n^3) ◦ (ノードペアにおけるベストな挿⼊ポイントの計算は、 ペアの⽚⽅ずつ独⽴に⾏えるのでΘ(n)の計算時間)
9 SWAP*について 1: EをRoute1に付け加えた時のコストを考える A B C D DEPOT E
F G H C 0E CEA C0A Route1 Route2 上の例のコスト差分は、∆(E, 0, A) = C0E + CEA - C0A となる ※ルートのコストは各エッジのコストの和で決まるものとする
10 SWAP*について 1: EをRoute1に付け加えた時のコストを考える A B C D DEPOT E
F G H CAE CEB CAB Route1 Route2 上の例のコスト差分は、∆(E, A, B) = CAE + CEB - CAB となる
11 SWAP*について A B C D DEPOT E F G
H CBE CEC CBC Route1 Route2 上のコスト差分は、∆(E, B, C) = CBE + CEC - CBC となる 1: EをRoute1に付け加えた時のコストを考える
12 SWAP*について A B C D DEPOT E F G
H CCE CED CCD Route1 Route2 上のコスト差分は、∆(E, C, D) = CCE + CED - CCD となる 1: EをRoute1に付け加えた時のコストを考える
13 SWAP*について 上のコスト差分は、∆(E, C, D) = CDE + CE0 -
CD0 となる 1: EをRoute1に付け加えた時のコストを考える A B C D DEPOT E F G H CDE CD0 Route1 Route2 CE0
14 SWAP*について 上のコスト差分は、 ∆(E, B, D) - ∆(C, B, D)
= (CBE + CED - CBD) - (CBC + CCD - CBD) = CBE + CED - CBC - CCD となる 2: Route1ではCを取り除いて、Cの場所をEで置き換えた場合を考える A B C D DEPOT E F G H CBE CBD Route1 Route2 CED CBC CCD
15 SWAP*について この中から最初コストとなるEの配置を選ぶ ↓Cを取り除く場合はこのパタンはない 1: EをRoute1に付け加える場合 2: Cの場所をEで置き換える場合 ここからCを取り除く (差分コストはさらに∆(C,
B, D)だけ引かれる) こちらは既に Cは取り除かれてる
16 SWAP*について この中から最初コストとなるEの配置を選ぶ 1: EをRoute1に付け加える場合 2: Cの場所をEで置き換える場合 この中から最⼩コストとなるTop3を選ぶ ここからCを取り除く (差分コストはさらに∆(C,
B, D)だけ引かれる) Cを取り除く場合にありえないパタンを除く (Top3の中でありえないパタンは最⼤2個なので、最⼩コストのものは残る) 枠の部分はRoute1で取り除くノードに関わらず 事前に計算して使いまわせる (計算量を”n回分”減らせる)
17 SWAP*のアルゴリズム全体像 ルートペアを選出(計算量削減のため近傍のルートペアに限定) https://arxiv.org/abs/2012.10384 ベストな挿入ポイントの Top3を事前計算 各ルート間のノードペアにおいて 最小コスト差分を計算 ベストなルート間のノードペアを選択 ベストなルート間のノードペアを交換
18 SWAP*の適⽤例 https://arxiv.org/abs/2012.10384 32と46を交換
19 SWAP*のパフォーマンス • 計算時間は最⼤32% → 古典的な⽅法に⽐べ劇的に改善 • 15%ほどの解の改善に貢献 • 解の改善が難しくなる後半の探索ほど解の改善に貢献
https://arxiv.org/abs/2012.10384 これは直感に合う
20 Thank you