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
SIGSPATIAL2020 参加報告
Search
fumihiko takahashi
PRO
December 14, 2020
Research
3
780
SIGSPATIAL2020 参加報告
fumihiko takahashi
PRO
December 14, 2020
Tweet
Share
More Decks by fumihiko takahashi
See All by fumihiko takahashi
単一の深層学習モデルによる不確実性の定量化の紹介 ~その予測結果正しいですか?~
ftakahashi
PRO
3
600
明日使えるかもしれないLoss Functionsのアイディアと実装
ftakahashi
PRO
16
3.7k
時系列予測にTransformerは有効か?
ftakahashi
PRO
2
220
ドライブレコーダーの映像で Scene Text Recognitionする
ftakahashi
PRO
0
1.2k
ドライブレコーダーの Scene Text Recognitionにおける Multi-task Learning
ftakahashi
PRO
1
3.2k
JapanTaxi R&Dの取り組み事例
ftakahashi
PRO
0
74
jsai2019.pdf
ftakahashi
PRO
0
390
Attention機構を使った 配車車両未確定状態における タクシー到着時間予測
ftakahashi
PRO
1
69
Other Decks in Research
See All in Research
資産間の相関関係を頑健に評価する指標を用いたファクターアローケーション戦略の構築
nomamist
0
190
さくらインターネット研究所 アップデート2025年
matsumoto_r
PRO
0
500
Intrinsic Self-Supervision for Data Quality Audits
fabiangroeger
0
480
Dynamic World, Near real-time global 10 m land use land cover mapping
satai
3
200
Scale-Aware Recognition in Satellite images Under Resource Constraints
satai
3
170
o1 pro mode の調査レポート
smorce
0
150
研究テーマのデザインと研究遂行の方法論
hisashiishihara
1
380
CARMUI-NET:自動運転車遠隔監視のためのバーチャル都市プラットフォームにおける通信品質変動機能の開発と評価 / UBI85
yumulab
0
120
ノンパラメトリック分布表現を用いた位置尤度場周辺化によるRTK-GNSSの整数アンビギュイティ推定
aoki_nosse
0
260
Individual tree crown delineation in high resolution aerial RGB imagery using StarDist-based model
satai
3
190
20241226_くまもと公共交通新時代シンポジウム
trafficbrain
0
500
言語モデルによるAI創薬の進展 / Advancements in AI-Driven Drug Discovery Using Language Models
tsurubee
2
290
Featured
See All Featured
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
104
19k
The Language of Interfaces
destraynor
157
25k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
41
2.2k
Building a Scalable Design System with Sketch
lauravandoore
462
33k
Gamification - CAS2011
davidbonilla
81
5.2k
The World Runs on Bad Software
bkeepers
PRO
67
11k
KATA
mclloyd
29
14k
Code Reviewing Like a Champion
maltzj
522
40k
Rebuilding a faster, lazier Slack
samanthasiow
80
8.9k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
GitHub's CSS Performance
jonrohan
1030
460k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
9
750
Transcript
2020.12.10 齋藤 智輝 高橋 文彦 株式会社 Mobility Technologies SIG SPATIAL2020
参加レポート
• 名前:高橋文彦 • 略歴 ◦ 2015年4月 ヤフー株式会社 入社 ◦ 2018年8月
JapanTaxi株式会社 入社 ◦ 2020年4月 株式会社MobilityTechnologies • 領域 ◦ データサイエンス、自然言語処理 • 過去の主な仕事 ◦ ECサイトの検索精度改善 ◦ 形態素解析ツールの開発 ◦ MLを使った お迎え時間予測のロジック、APIの開発 ◦ SceneTextRecognitionの研究開発(画像処理) ◦ マネージャー(10人程度組織) ◦ 論文書いたり • 趣味 ◦ ボードゲーム、一蘭
3 04 論文紹介 Part 2 by 高橋
4 Grab-Posisi-L: A Labelled GPS Trajectory Dataset for Map Matching
in Southeast Asia Links: • Paper • Movie Xiaocheng Huang et al. GrabTaxi Holdings, National University of Singapore
5 ▪マップマッチの正解データセットを作成・公開 ▪いくつかのアプリケーションでの応用を紹介 Summary
6 ▪既存のデータセットの課題 ▪ 場所が限定的 ▪ 中国・アメリカが多い ▪ 街の一部のエリアのみを対象 ▪ 規模が小さい
▪ GPSのsampling rateが低い ▪ 付加情報(方向・GPS精度・速度など)がない Background
7 ▪GPSデータ ▪ Grabのドライバー端末 ▪ シンガポール、ジャカルタ ▪ 2019年4月 ▪ GPS精度,
進行方向, 速度 ▪ mode: 車, バイク ▪ 地図はOSMを使用 ▪統計 ▪ 84,000 軌跡 ▪ 1,003,510 km ▪ 30,104 時間 Dataset
8 1.GPSをHMMでマップマッチ 2.JOSMを使って可視化 3.マップマッチ結果を削除挿入変更で校正 Route Annotation
9 ▪本データセットを使ったいくつかの応用を紹介 1.地図推定 2.マップマッチのロジック改善 3.渋滞検知と予測 4.軌跡補完と次の目的地予測 5.GPSデータから移動手段(車 or バイク)を推定する 6.都市計画
Application
10 ▪背景 ▪ GPSの点のマッチ先の道路候補を、半径d以内の道路と決めている ▪ 半径dが小さすぎる場合精度が低下、大きすぎる場合計算量が膨大になるトレードオフ ▪改善案 ▪ GPSの点ごとに、GPS精度(accuracy level)を使って半径dを動的に変更
▪ 半径d = accuracy level * 2 Application – マップマッチのロジック改善
11 Spatio-Temporal Hierarchical Adaptive Dispatching for Ridesharing Systems Links: •
Paper • Movie Chang Liu et al. Shanghai Jiao Tong University, Didi Chuxing
12 ▪相乗りサービスにおいてプーリング間隔を調整して利益を最大化 ▪ 空間をクラスタリングし、クラスタ毎にオンラインで配車間隔を調整するアルゴリズムを提案 ▪実サービスのデータでシミュレーションし、利益が向上することを確認 Summary
13 ▪一般的な相乗りサービスでは、一定の間 隔で注文をプーリングして配車 ▪配車間隔が長いと、 ▪ より利益の高い組み合わせを作れるが ▪ 注文キャンセルが発生し損失 ▪注文数は空間的にも時間的にも不均一に 分布
▪時空間ごとに配車間隔を調整して利益を 最大化 Background
14 1.配車傾向ごとに空間をクラスタリング (Spatial Clustering) 2.クラスター毎に利益が最大化されるタイミングで配車 (Adaptive Interval) Hierarchical Adaptive Framework
15 ▪配車傾向ごとに空間をクラスタリング ▪方法 1. 過去の相乗り配車履歴から共有配車グラフを作成 2. エッジの重みの分散が閾値以下になるように、クラスタ内の重みの合計を最大化する Framework - Spatial
Clustering
16 ▪利益が最大化されるタイミングで配車 ▪ ただし、将来の利益はわからない ▪アルゴリズム ▪ 1/e-ADI algorithm ▪ 秘書問題として解く
▪ 閾値時間までは配車せず、前回配車からこれまでで利 益が最大になったタイミングで配車 ▪ BI-ADI algorithm ▪ 将来の利益を過去の統計データを利用 ▪ 利益が最大になるタイミングで配車 Framework - Adaptive Interval
17 Framework - Adaptive Interval - Algorithm
18 ▪いずれの設定でも提案手法の方が利益が高い Results unit time intervalごとの利益 最大配車間隔ごとの利益
19 Succinct Trit-array Trie for Scalable Trajectory Similarity Search Links:
• Paper • Movie Shunsuke Kanda et al. RIKEN AIP, Kyoto University, Nagoya University
20 ▪LSHとtrieを使って類似経路検索を高速化・省メモリ化 ▪既存手法に比べて12~34倍高速化、メモリを1/10~1/17 Summary
21 Highly Efficient and Scalable Multi-hop Ride-sharing Links: • Paper
• Movie Yixin Xu et al. The University of Melbourne
22 ▪乗り継ぎ方式の相乗りサービスの取り組み ▪ 実現するための2つのアルゴリズムを提案 ▪車両数が中程度あるときに配車失敗数を4割減らした Summary Vehicle-first algorithm Station-first algorithm