Map matching مرحله غیرجذاب اما ضروری است که ابر نویزی نقاط GPS را به یک مسیر تمیز در طول جادههای واقعی تبدیل میکند. بدون آن، dashboard ناوگان نشان میدهد کامیونها از داخل ساختمانها رد میشوند، یک مدل قیمتگذاری بیمه نمیتواند بزرگراه را از خیابان فرعی تشخیص دهد، و سفر ride-share مثل برنامه پروازی یک کبوتر مست به نظر میرسد. با آن، هر نقطه به یک موقعیت روی قطعهای شناختهشده از گراف جاده تبدیل میشود، با جهت حرکت و فاصله در طول یال متصل به آن.
در این راهنما توضیح میدهم map matching واقعاً چیست، چرا GPS خام کافی نیست، الگوریتمها چگونه کار میکنند و در سیستمهای واقعی کجا ظاهر میشود.
Map matching واقعاً چیست
در سادهترین شکل، map matching دو ورودی میگیرد: یک دنباله مرتبشده زمانی از fix های GPS (طول، عرض، timestamp، اغلب سرعت و heading) و یک شبکه جادهای قابل مسیریابی (معمولاً OpenStreetMap که به یک گراف از یالها و گرهها پردازش شده است). خروجیای تولید میکند که در آن هر fix به یک یال مشخص در آن گراف چسبانده شده، با موقعیت دقیق در طول یال و metadata قطعه متصل به آن.
نتیجه یک polyline است که خیابانهای واقعی را دنبال میکند، بهعلاوه لیستی از قطعات جاده که واقعاً پیموده شدهاند. آن خروجی دوم همان چیزی است که تحلیلهای پاییندستی را باز میکند: محدودیت سرعت در هر قطعه، کلاس جاده، تعداد گردشها، انتساب کشور و منطقه، و فاصله دقیق در هر یال به جای فاصله مستقیم بین fix ها.
یک trace بهتنهایی به شما تقریباً میگوید دستگاه کجا رفته. یک trace match شده به شما میگوید از کدام جادهها استفاده کرد.
چرا GPS خام کافی نیست
GPS با کیفیت مصرفی در شرایط خوب تقریباً ۵ متر دقت دارد و در یک گوشی یا tracker ارزان در استفاده عادی ۱۰ تا ۳۰ متر. سه مسئله ساختاری این را در telemetry محصول واقعی بدتر میکند.
درههای شهری. در مرکز شهرهای متراکم، ساختمانهای بلند خط دید مستقیم به ماهوارهها را مسدود میکنند و سیگنالها را از نمای شیشهای منعکس میکنند. گیرنده یک کپی تأخیری از سیگنال میبیند (multipath) و موقعیتی محاسبه میکند که میتواند یک بلوک کامل از موقعیت واقعی فاصله داشته باشد، اغلب در یک خیابان موازی.
Drift شروع سرد. وقتی یک دستگاه روشن میشود، میتواند ۳۰ تا ۹۰ ثانیه طول بکشد تا ماهوارههای کافی برای یک fix مطمئن پیدا کند. چند نقطه اول هر trace اغلب ۵۰ متر یا بیشتر خطا دارند، که دقیقاً وقتی است که یک خودرو از پارکینگ بیرون میآید یا از depot خارج میشود.
نمونهگیری sparse. Tracker های IoT با باتری اغلب هر ۳۰ ثانیه یا هر دقیقه یک fix لاگ میکنند تا انرژی صرفهجویی کنند. در سرعت بزرگراه این بیش از یک کیلومتر بین نقاط است، و خط مستقیم بینشان به ندرت با مسیر واقعی مطابقت دارد. یک matcher باید شکاف را با مسیریابی از طریق گراف پر کند، نه با کشیدن یک خط.
این خطاها روی هم به این معنی است که هر سیستمی که fix های خام را بهعنوان حقیقت در نظر بگیرد بیسروصدا فاصلهها، جادهها و صورتحسابهای اشتباه تولید میکند.
Map matching چگونه کار میکند
رویکرد غالب در محصول واقعی فرمولبندی Hidden Markov Model است که توسط Newson و Krumm در ۲۰۰۹ رواج یافت. گراف جاده بهعنوان مجموعهای از حالتهای پنهان مدل میشود (دستگاه واقعاً روی کدام یال است) و trace GPS بهعنوان مشاهدات نویزی از آن حالتها. دو احتمال matcher را به جلو میبرند.
Emission probability. برای هر fix، الگوریتم یالهای کاندیدا را در یک شعاع جستجو پیدا میکند (معمولاً ۲۵ تا ۲۰۰ متر) و هر یک را بر اساس اینکه چقدر منطقی است که موقعیت واقعی روی آن یال باشد با توجه به fix مشاهدهشده امتیاز میدهد. امتیاز معمولاً یک Gaussian روی فاصله عمودی از fix به یال است.
Transition probability. برای هر جفت fix متوالی، الگوریتم هر جفت یالهای کاندیدا را بر اساس اینکه چقدر منطقی است در زمان سپریشده از اولی به دومی حرکت کنید امتیاز میدهد. این نیاز به مسیریابی از طریق گراف بین کاندیداها و مقایسه فاصله مسیر با فاصله great-circle بین fix ها دارد. عدم تطابقها جریمه میشوند، پس پرشهای غیرممکن (روی یک رودخانه، در خلاف خیابان یکطرفه، با سرعتهایی که کلاس جاده اجازه نمیدهد) له میشوند.
الگوریتم Viterbi سپس محتملترین دنباله یالها در کل trace را در یک گذر پیدا میکند. هر دو OSRM و Valhalla HMM matcher های محصولی را بر اساس همین رویکرد عرضه میکنند، با گسترشهایی برای trace های sparse، شکافهای زمانی و break point هایی که در آن دستگاه از شبکه خارج شده است.
Map matching کجا ظاهر میشود
Map matching یک قابلیت پشتصحنه است که تقریباً هیچوقت UI ندارد، اما اتاق موتور پشت فهرست بلندی از محصولات است.
- Telemetry ناوگان. ناوگانهای کامیون و ون هر چند ثانیه یک fix لاگ میکنند. Map matching stream را به مایلسنجی در سطح قطعه به ازای هر راننده، هر وسیله نقلیه و هر منطقه تبدیل میکند، که payroll، تطبیق سوخت و انطباق مسیر را تغذیه میکند.
- تحلیل رفتار راننده. رویدادهای ترمز شدید و سرعت بالا فقط وقتی معنادار هستند که محدودیت سرعت قطعهای که راننده روی آن بود را بدانید. این نیاز به یال match شده دارد، نه فقط fix خام.
- بازسازی سفر ride-sharing. وقتی یک مسافر کرایه را به چالش میکشد، پلتفرم سفر را از لاگ GPS راننده بازسازی میکند. یک trace match شده یک polyline در سطح ممیزی در طول خیابانهای واقعی و یک فاصله قابل دفاع میدهد.
- بیمه trip-based. سیاستهای pay-per-mile و رفتارمحور به مایلسنجی دقیق به ازای سفر و قرارگیری در کلاس جاده نیاز دارند. ۵ درصد خطا روی GPS خام تفاوت بین سود و زیان در یک portfolio است.
- ردیابی دارایی IoT. کانتینرهای کالا، اسکوترهای برقی و تجهیزات اجارهای fix های sparse میفرستند. Map matching آنها را با فاصلههای درست به سفرها میدوزد، حتی وقتی fix ها چند دقیقه فاصله دارند.
- تحلیل استفاده از جاده. مقامات شهری و عوارض از trace های match شده برای تخمین جریان، شناسایی قطعات شلوغ و مطالعه سهم حالت بدون نصب سنسورهای فیزیکی استفاده میکنند.
دامها در محصول واقعی
Map matching در دمو تمیز به نظر میرسد و زیر بار دنیای واقعی زشت میشود.
Trace های sparse. وقتی fix ها بیش از یک کیلومتر فاصله دارند، matcher باید به یک مسیر واحد بین آنها متعهد شود. اگر دو مسیر منطقی وجود داشته باشد، گاهی اشتباه برنده میشود. افزایش پنجره کاندیدا کمک میکند ولی runtime را منفجر میکند.
قطعات خارج از جاده. وسایل نقلیه مرتباً شبکه را ترک میکنند: پارکینگها، جادههای خصوصی، فریها، مسیرهای شنی. یک matcher ساده اینها را به نزدیکترین جاده زور میدهد و مایلسنجی phantom تولید میکند. Matcher های محصولی break point ها را تشخیص میدهند و شکافهای match نشده منتشر میکنند نه اینکه حدس بزنند.
جادههای موازی. بزرگراه بهعلاوه frontage road، بزرگراه جداشده با مسیرهای جداگانه و شبکههای شهری متراکم همه کاندیداهایی تولید میکنند که تقریباً مساوی امتیاز میگیرند. سیگنالهای heading و سرعت (وقتی در دسترس باشند) همان چیزی هستند که گره را باز میکنند.
اتصال چندروزه. خودرویی که شبانه پارک میکند دو سفر جداگانه تولید میکند، نه یک trace با شکاف ۱۲ ساعته. تقسیم ورودی به سفرها قبل از matching معمولاً ارزانتر و دقیقتر از اجرای یک گذر غولپیکر Viterbi است.
حریم خصوصی. یک trace match شده یک رکورد با وضوح بالا از مکان و زمان حضور یک شخص است. این داده شخصی تحت GDPR و رژیمهای معادل است. ذخیرهسازی، نگهداری و لاگهای دسترسی باید با حساسیت همخوانی داشته باشند، و تجمیع باید تا حد امکان زود در پایپلاین انجام شود.
Map matching در MapAtlas
MapAtlas Map Matching API یک دنباله از fix های GPS میگیرد و یک polyline چسباندهشده در طول شبکه جادهای برمیگرداند، با شناسههای یال به ازای هر نقطه، metadata قطعه و یک امتیاز اطمینان روی هر match. trace های sparse، تشخیص break point برای قطعات خارج از جاده و موارد رایج محصول واقعی (telemetry ناوگان، بازسازی سفر، ردیابی IoT) را بدون اینکه شما را مجبور کند خوشه OSRM یا Valhalla خودتان را میزبانی کنید مدیریت میکند.
به طور طبیعی با MapAtlas Directions API جفت میشود وقتی نیاز دارید یک مسیر تاریخی match شده را با یک مسیر بهینه مقایسه کنید، و با MapAtlas Geocoding API وقتی نیاز دارید شروع و پایان یک سفر match شده را به آدرسهای قابل خواندن برای انسان برای dashboard یا یک رسید روبهمشتری تبدیل کنید.
یک trace match شده زرقوبرق ندارد. فقط یک polyline است. اما همان polyline ای است که به هر سیستم پاییندستی، از صورتحساب تا تحلیل تا انطباق، اجازه میدهد روی این توافق کنند که دستگاه واقعاً روی کدام جاده بوده است.
سوالات متداول
Map matching چیست؟
Map matching فرآیند گرفتن یک دنباله از نقاط نویزی GPS و همترازسازی آنها با شبکه جادهای زیرین است، بهطوری که هر fix به یک موقعیت روی یک قطعه خیابان واقعی تبدیل میشود. به جای پراکندگی نقاطی که از روی ساختمانها و رودخانهها drift میکنند، یک polyline تمیز دارید که جادههای واقعی را دنبال میکند، با شناسه قطعه، جهت حرکت و فاصله در طول هر یال متصل به هر نقطه.
چرا نمیشود فقط نقاط خام GPS را روی نقشه رسم کرد؟
GPS خام در آسمان باز تقریباً ۵ تا ۳۰ متر دقت دارد و در درههای شهری، تونلها و پارکینگهای طبقاتی بسیار بدتر. انعکاسهای multipath از ساختمانهای بلند، drift شروع سرد و نرخ نمونهگیری به کمی یک fix در هر ۳۰ ثانیه به این معنی است که trace اغلب بیرون جاده مینشیند، بین خیابانهای موازی میپرد یا گردشها را کلاً از دست میدهد. Map matching هر سه مسئله را با استدلال دربارهٔ گراف جاده به جای اعتماد به هر fix بهتنهایی اصلاح میکند.
Hidden Markov Model map matching چگونه کار میکند؟
یک HMM قطعه جاده واقعی در هر گام زمانی را بهعنوان یک حالت پنهان و fix GPS را بهعنوان یک مشاهده نویزی از آن حالت در نظر میگیرد. هر یال کاندیدا نزدیک یک fix یک emission probability بر اساس فاصله میگیرد، و هر جفت کاندیداهای متوالی یک transition probability بر اساس اینکه آیا شبکه جادهای واقعاً اجازه آن حرکت را در سرعت مشاهدهشده میدهد میگیرد. الگوریتم Viterbi سپس trace را پیمایش میکند و محتملترین دنباله یالها را انتخاب میکند. OSRM و Valhalla هر دو HMM matcher های محصولی را بر اساس همین رویکرد عرضه میکنند.
Map matching در محصول واقعی برای چه چیزی استفاده میشود؟
Telemetry ناوگان، تحلیل رفتار راننده، بازسازی سفر ride-sharing، بیمه usage-based و trip-based، ردیابی دارایی IoT و تحلیل استفاده از جاده همه به map matching وابستهاند. هر جا که یک stream از ping های GPS دارید و باید بدانید دستگاه روی کدام جاده بود، چقدر طی کرد و چه گردشهایی زد، map matching مرحلهای است که نقاط خام را به چیزی تبدیل میکند که یک سیستم صورتحساب، یک routing engine یا یک dashboard میتواند روی آن عمل کند.
