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
75
VRPの近傍操作SWAP*について調べてみた
NearMeの技術発表資料です
PRO
July 05, 2024
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
Architecture Decision Record (ADR)
nearme_tech
PRO
0
8
遺伝的アルゴリズムを実装する
nearme_tech
PRO
1
15
Fractional Derivative!
nearme_tech
PRO
1
14
GitHub Projectsにおける チケットの ステータス更新自動化について
nearme_tech
PRO
1
25
2つの曲線を比較する方法ってあるの? 〜フレシェ距離を試してみた〜 with Python
nearme_tech
PRO
1
97
Constrained K-means Clustering (クラスタサイズの制限をしたK-means法) を調べてみた
nearme_tech
PRO
1
41
新人エンジニアが読んでためになった本
nearme_tech
PRO
2
37
Object–relational mapping and query builder battle 1: Intro to Prisma
nearme_tech
PRO
1
44
深層学習モデルの最適化 -Deep Learning Tuning Playbookを読む-
nearme_tech
PRO
1
62
Other Decks in Technology
See All in Technology
Staff Engineer / 20240827 Yuichiro Masui
shift_evolve
0
150
手軽に始める? おうちサーバーのすゝめ
nyagasan
0
180
Envoy External AuthZとgRPC Extensionを利用した「頑張らない」Microservices認証認可基盤
andoshin11
0
140
#Zenoh 完全に理解した 〜組込み純情篇〜
takasehideki
1
450
20240828_EM_Fest
kzkmaeda
4
360
プロデザ! BY リクルートvol.22_様々なプロダクト経験の中で活きたPdMのスキル
recruitengineers
PRO
3
170
音声AIエージェントの世界とRetell AI入門 / Introduction to the World of Voice AI Agents and Retell AI
rkaga
3
470
ログラスが面白いと思う理由をマネージャーがエモく語ってみる / 20240829 vs LT
yoshikiiida
1
520
AWSを始めた頃に陥りがちなポイントをまとめてみた
oshanqq
1
1.7k
Oracle Database 23ai 新機能 #3 Oracle Globally Distributed Database(GDD)
oracle4engineer
PRO
1
160
目標設定と習慣化で今よりも一歩生産性を上げる
sansantech
PRO
7
2.3k
Oracle Base Database Service:サービス概要のご紹介
oracle4engineer
PRO
0
13k
Featured
See All Featured
Teambox: Starting and Learning
jrom
131
8.7k
Stop Working from a Prison Cell
hatefulcrawdad
266
20k
Fireside Chat
paigeccino
31
2.9k
What's new in Ruby 2.0
geeforr
340
31k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
225
22k
Intergalactic Javascript Robots from Outer Space
tanoku
268
26k
Automating Front-end Workflow
addyosmani
1365
200k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
25
1.3k
The Cost Of JavaScript in 2023
addyosmani
39
5.1k
Making Projects Easy
brettharned
113
5.8k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
502
140k
Mobile First: as difficult as doing things right
swwweet
220
8.8k
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