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
ルートの質を評価する指標について
Search
NearMeの技術発表資料です
PRO
February 28, 2025
0
19
ルートの質を評価する指標について
NearMeの技術発表資料です
PRO
February 28, 2025
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
Webアプリケーションにおけるクラスの設計再入門
nearme_tech
PRO
1
38
AIエージェント for 予約フォーム
nearme_tech
PRO
2
98
ULID生成速度を40倍にしたった
nearme_tech
PRO
2
30
Amazon AuroraとMongoDBの アーキテクチャを比較してみたら 結構違った件について
nearme_tech
PRO
0
14
GitHub Custom Actionのレシピ
nearme_tech
PRO
0
8
RustでDeepQNetworkを実装する
nearme_tech
PRO
1
12
より良い解に辿り着くカギ-近傍設定の重要性
nearme_tech
PRO
0
79
Rustで作る強化学習エージェント
nearme_tech
PRO
2
75
ビームサーチ
nearme_tech
PRO
0
70
Featured
See All Featured
GraphQLの誤解/rethinking-graphql
sonatard
71
10k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
2.9k
Adopting Sorbet at Scale
ufuk
76
9.3k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
Optimizing for Happiness
mojombo
378
70k
Become a Pro
speakerdeck
PRO
28
5.3k
A designer walks into a library…
pauljervisheath
205
24k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
1.7k
Automating Front-end Workflow
addyosmani
1370
200k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
Done Done
chrislema
184
16k
GitHub's CSS Performance
jonrohan
1030
460k
Transcript
1 2025-02-28 第114回NearMe技術勉強会 Futo Ueno ルートの質を評価する指標について
2 背景 ‧タスクでrouting-apiのパラメータチューニングについて考えていた ‧UXと相乗り数(GpT)はトレードオフの関係にある → UXとGpTのバランスが良いパラメータを探索したい UXの良さとは? → UXのうち「ルートの質」を定量化する⽅法についてお話しします
3 ルートの質 start end pick up start end pick up
start end pick up ⾃然なルートで 相乗りできている やや不⾃然
4 フレシェ距離 X, Y : 0 ≤ t ≤ 1でパラメータ付けられた曲線
α, β : [0, 1]から[0, 1]への単調⾮減少な再パラメータ付け d(‧, ‧) : ユークリッド距離
5 フレシェ距離 X, Y : 0 ≤ t ≤ 1でパラメータ付けられた曲線
→ ルート α, β : [0, 1]から[0, 1]への単調⾮減少な再パラメータ付け → 歩き⽅ d(‧, ‧) : ユークリッド距離 → 普通の距離
6 フレシェ距離の解釈 ⽚⽅が直線だとわかりやすい おそらくこの辺り 「曲線X, Y上をなるべく離れないように歩いた時に、どうしても離れてしまう距離」
7 フレシェ距離によるルートの質の評価 start end pick up start end pick up
start end pick up フレシェ距離 ⼩ フレシェ距離 ⼤ フレシェ距離 ⼤?
8 フレシェ距離の弱点① ‧使う道路が変わると必然的にフレシェ距 離は⼤きくなる ‧使う道路が変わってもルートの質に⼤き く差が⽣じない場合であっても、フレシェ 距離には「異常」として反映されてしまう start end ⾼速
1 ⾼速 2 ⼀般道 + ⾼速
9 フレシェ距離の弱点② start end pick up start end pick up
start end pick up ⽬的地から遠ざかっている ⾏ったり来たりしている ⾃然 → これらのフレシェ距離はそれほど⼤きな値にはならず、⾃然な相乗りとの区別がつかない
10 Geodesic Tortuosity start end ‧始点から終点まで辿り着くために必要な 「最⼩限の移動量」が直線距離 ‧あるルートによる「実際の移動量」が 「最⼩限の移動量」に⽐べてどのくらい嵩んで しまうかを表している
𝑙 𝑅
11 GT による評価 start end pick up 𝑅!"#$% 𝑅!&'& 𝑙
12 GTによる評価 start end 𝑅!"#$% pick up 𝑅!&'& ‧ルートの⻑さに差がなければGTにも 差は⽣じない
→ 使う道路が違ってもルートの質が 同⽔準であることを捉えられている
13 start end pick up start end pick up end
⽬的地から遠ざかっている ⾏ったり来たりしている ⾃然 →⽬的地から遠ざかったり⾏ったり来たりするとGTは悪化する GTによる評価 pick up start
14 「迂回係数」との⽐較 ←概ね連動しているが、 迂回係数が⼤きくなるにつ れて差が⽣じている
15 「迂回係数」との⽐較 → 「元々のルートのGT」 が反映されている
16 今後の課題 ‧時間的な質を反映させた指標 ‧最適化に組み込む (制約や⽬的関数) ‧⽬的地から遠ざかったり⾏ったり来たりする部分を 「強調」するような形に拡張 → ルートの異常検知
17 references ‧https://mist.math.chalmers.se/geodesic-tortuosity/ ‧https://www.researchgate.net/figure/Definition-of-the-geodesic- tortuosity_fig16_312874680
18 Thank you