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
0
22
希望休勤務を考慮したシフト作成
nearme_tech
PRO
0
21
Hub Labeling による高速経路探索
nearme_tech
PRO
0
58
Build an AI agent with Mastra
nearme_tech
PRO
0
68
Rustで強化学習アルゴリズムを実装する vol3
nearme_tech
PRO
0
35
Webアプリケーションにおけるクラスの設計再入門
nearme_tech
PRO
1
78
AIエージェント for 予約フォーム
nearme_tech
PRO
2
140
ULID生成速度を40倍にしたった
nearme_tech
PRO
2
51
Amazon AuroraとMongoDBの アーキテクチャを比較してみたら 結構違った件について
nearme_tech
PRO
0
25
Other Decks in Technology
See All in Technology
GeminiとNotebookLMによる金融実務の業務革新
abenben
0
240
Core Audio tapを使ったリアルタイム音声処理のお話
yuta0306
0
150
React開発にStorybookとCopilotを導入して、爆速でUIを編集・確認する方法
yu_kod
1
100
生成AI開発案件におけるClineの業務活用事例とTips
shinya337
0
180
Liquid Glass革新とSwiftUI/UIKit進化
fumiyasac0921
0
300
生成AI時代の開発組織・技術・プロセス 〜 ログラスの挑戦と考察 〜
itohiro73
1
370
「Chatwork」の認証基盤の移行とログ活用によるプロダクト改善
kubell_hr
1
240
さくらのIaaS基盤のモニタリングとOpenTelemetry/OSC Hokkaido 2025
fujiwara3
2
240
無意味な開発生産性の議論から抜け出すための予兆検知とお金とAI
i35_267
0
870
Beyond Kaniko: Navigating Unprivileged Container Image Creation
f30
0
100
KubeCon + CloudNativeCon Japan 2025 Recap Opening & Choose Your Own Adventureシリーズまとめ
mmmatsuda
0
230
高速なプロダクト開発を実現、創業期から掲げるエンタープライズアーキテクチャ
kawauso
1
160
Featured
See All Featured
Java REST API Framework Comparison - PWX 2021
mraible
31
8.7k
Measuring & Analyzing Core Web Vitals
bluesmoon
7
500
Writing Fast Ruby
sferik
628
62k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
17
950
Building a Modern Day E-commerce SEO Strategy
aleyda
42
7.4k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.9k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
32
2.4k
Learning to Love Humans: Emotional Interface Design
aarron
273
40k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.7k
Bash Introduction
62gerente
614
210k
Code Reviewing Like a Champion
maltzj
524
40k
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