مسیریاب‌ها و تخمین ترافیکی

شاید بارها براتون سوال شده باشه که مسیریاب‌ها چه طور از اطلاعات خودروها برای تخمین ترافیک استفاده می‌کنند. در این مقاله کوتاه قصد داریم خیلی ساده به مسئله تخمین ترافیک در نقشه و مسیریاب بلد نگاه کنیم. ترافیک لحظه‌ای مهمترین معیار ترافیکیترافیک لحظه‌ای در واقع همون سرعت خودروها در یک مسیر چند ده متری(یا گاهی چند صدمتری) است. مسافران در طول سفر از نقاط مختلفی گذر میکنند و در طول سفر اطلاعات سرعت GPS و لوکیشن تلفن همراهشون به صورت کاملا ناشناس در اختیار مسیریاب‌ها قرار میگیره. شاید خیلی ساده بشه فرض کرد که اطلاعات سرعت GPS و یک میانگین گیری ساده مشکلاتمون رو حل میکنه و ترافیک مسیر رو بهمون میده، ولی واقعیت اینه که در سرعت‌های پایین ما نمیتونیم از GPS استفاده کنیم چون دقت به شدت پایینی داره. بنابراین در مواقع که ترافیک رخ میده (در واقع مهمترین مواقع کار ما :)‌ ) نمیتونیم دقت خوبی در تخمین زمان سفر یا ترافیک داشته باشیم. اینجاست که سراغ فیزیک دوران مدرسه میریم. سرعت متوسط! در واقع در هر لحظه سرعت متوسط شما در طول سفرتون در یک پنجره‌ی زمانی یک دقیقه‌ای محاسبه میشه و به قسمتی از معبر نسبت داده میشه.پنجره یک دقیقه‌ای برای محاسبه ی سرعت متوسط کاربران در هر قطعه مسیردر طول زمان عبور شما از خیابان‌های مختلف، ممکن هست برخی جاها گوشی اصلا لوکیشن نفرسته. مثلا در کنار ساختمان‌های بلند هستید یا اینترنت شما قطع شده! یا شاید برخی معابر این قدر کوتاه باشند که خطای لوکیشن از اندازه کل معبر بیشتر باشه! در چنین شرایطی مسیریاب از لوکیشن قبل و بعد شما برای تخمین سرعت استفاده میکنه. خلاصه اینکه با استفاده از فاصله‌ی مکانی و زمانی دو لوکیشن ما می‌تونیم یک سرعت متوسط به شما در گذر از یک معبر نسبت بدیم.نکته مهم اینه که برای هر معبری که شما عبور میکنید، ما عددی به عنوان سرعت متوسط به شما نسبت میدیم. این کار با پردازش استریم انجام میشه و ما فیلترهای مختلفی میگذاریم تا داده‌های خراب جدا بشن و دقیقترین داده‌ی ترافیکی برای شما فراهم بشه.حالا که سرعت کاربرامون برای هر قطعه خیابون رو داریم، کافیه بگیم برای هر قطعه میخواهیم چه سرعتی به کاربران اعلام کنیم. در واقع بگیم وضعیت ترافیک هر خیابون چه طوریه. بله درسته! خیابون‌ها از قطعه‌های کوچکتری تشکیل شدند (فاصله‌ی بین هر دو نقطه تقاطع معابر یک قطعه هست) و ما مسئله رو برای این قطعه‌های کوچک حل میکنیم.عبور چهارخودرو از یک قطعه در زمان ۱۰ دقیقهحالا کافیه یک میانگیری وزن‌دار انجام بدیم. بسته به اینکه دوست داریم مدل ما چه قدر حساس باشه میتونیم این میانگیری وزن‌دار رو در نوع‌های گوناگون پیاده کنیم. مثلا میتونیم به صورت نمایی با زمان گذشته وزن دار کنیم. این طوری خودرویی که در زمان دورتر در پنجره ۱۵ دقیقه‌ای عبور کرده تاثیر کمتری روی ترافیک لحظه‌ای خواهد داشت. با بازی با این وزن‌ها میتونیم مدل‌های متفاوت و جالبی بسازیم. خلاصش اینکه ترکیب این سرعتای متوسط به دست اومده باهم ترافیک یک خیابون رو می‌سازه.اما یک نکته دیگر هم هست. اگر در طول این ۱۵ دقیقه دو موتور سوار از ترافیک با سرعت بالا عبور کنند(مثلا از میان ماشین‌ها عبور کنند!) عدد سرعت(ترافیک معبر) تغییر محسوسی میکنه! یا اگر شوماخر در معبر ویراژ بده چی!؟ یا اینکه هاشم اقا با سرعت بسیار پایینی از لاین سوم در حال حرکت باشه!؟افراد باتوجه به نوع خودرو و توانایی‌های رانندگی با سرعت‌های مختلفی می‌تونند در ترافیک حرکت کنند. هدف مسیریاب‌ها اما ارائه‌ی سرعت نرمال حرکت در معبر است. بنابراین به نوعی باید این رفتارهای خارج از عرف(چه سرعت‌های بسیار کم و چه سرعت‌های زیاد، رفتار نامتعارف!) تشخیص داده شوند و اثرگذاری آن‌ها کم شود. برای این‌کار ما به صورت آنلاین توزیع آماری هر قطعه خیابان رو محاسبه می‌کنیم. یعنی چی؟! یعنی با استفاده از اطلاعات گذشتمون یک توزیع از سرعت حرکت خودرو‌ها نگه میداریم و چک میکنیم سرعت‌های جدید کجای این توزیع قرار میگیرند. هر چه قدر نسبت به توزیع آماری فاصله داشته باشند تاثیر نهایی آن‌ها در سرعت لحظه‌ای کمتر میشه.ذخیره سازی وضعیت معابر با مدل‌های ریاضی و به روزرسانی در پنجره‌های یک دقیقه‌ایپس تا اینجای کار بلد اطلاعات خودروها رو به صورت استریم در بازه‌های یک دقیقه‌ای بررسی میکنه و به هر کاربر یک سرعت نسبت میده. بعد از این، از این سرعت‌ها میانگین وزن‌دار میگره و حواسش هم هست که سرعت‌های نامتعارف رو تشخیص بده. ضمنا، تمام اطلاعاتی که نیاز داره در مورد معبرها داشته باشه رو در استیت‌هایی به صورت استریم نگه میداره و در بازه‌های یک دقیقه‌ای اون‌ها رو به‌روزرسانی میکنه.یه سوال دیگه!اگر روی پنجره‌های ۱۵ دقیقه‌ای میانگین می‌گیرید، چه طور میتونید به سرعت،تغییر در ترافیک رو تشخیص بدید!؟ ایا واقعا ۱۵ دقیقه زمان نیاز دارید تا به روزرسانی شوید!؟ جواب،نع! واقعیت اینه که ما به طور مرتب احتمال اینکه تغییر در ترافیک رخ بده رو به صورت آنلاین بررسی می‌کنیم.معمولا بسته به حجم تردد بین یک تا ۳ دقیقه طول میکشه که بلد متوجه بشه ترافیک باز شده یا بلعکس، در نقطه‌ای ترافیک شده.(مثلا فرض کنید بارون ناگهانی شروع شده یا تصادفی رخ داده).تخمین عمر وضعیت ترافیک در یک معبردر واقع برای هر معبر ما در هر لحظه داریم عمر وضعیت ترافیکی حال حاضر رو تخمین میزنیم و به محض اینکه متوجه بشیم احتمال تموم شدن وضعیت قبلی زیاد شده تمام داده‌های گذشتمونو فراموش می‌کنیم و فقط به داده‌های جدید توجه می‌کنیم. اینکه چه طور این موضوع رو محاسبه می‌کنیم رو شاید در پست دیگری شرح بدیم.نکته‌ی جالب توجه در تمام مسیری که گفتم اینه که تقریبا هیچ پارامتری توسط ما قرارداده نشده و سرویس هر موقع شروع به کار کنه اروم اروم استیت‌های بهینه خودش رو پیدا میکنه و نتیجه مطلوب رو نشون میده. مثلا فرض کنید در زمان بارندگی وضعیت ترافیک تغییر کنه. تمام توزیع‌های اماری در عرض ۲ تا ۳ دقیقه‌ وضعیت خودشون رو تغییر میدهند تا با حالت جدید تطابق پیدا کنند( واسه همینه میگیم بلد در هر شرایطی آماده حرکت است! :)‌ ).مگه همه جا کاربر دارید که ترافیک همه‌ی نقاط رو نشون میدید!؟نه هیچ مسیریابی در هر لحظه در همه جا کاربر نداره. سیستم ترافیک لحظه‌ای با همه ی پیچیدگی‌های ساختاری و مدل‌سازی که داره، نمیتونه جوابگوی همه‌ی نیازها باشه. چون در نهایت وابسته به حضور کاربره! برای همین بلد سرعت حدودی معابر با تردد قابل قبول رو طی سه ماه گذشته مرتب بررسی میکنه. میتونید تصور کنید چه حجم دیتای زیادی رو روزانه بلد پردازش میکنه تا معیاری برای سرعت‌ معابر مختلف به دست بیاره. در واقع این معابر شریان‌های اصلی شهرها نیستند ولی تردد از اون‌ها قابل توجه‌ هست و معمولا در ساعات مختلف رفتار ترافیکی مختلفی دارند. ما وابسته به روز هفته(تعطیلی یا غیر تعطیل)، ساعت و رفتارهای ترافیکی، می‌تونیم تخمین نسبتا دقیقی از وضعیت ترافیک در اون نقطه بهتون بدیم.میتونید تخمین بزنید برای کل این پروسه، ما چه توان پردازشی صرف میکنیم تا دقیقترین معیار از ترافیک رو در اختیارتون قرار بدیم؟!نظرتون چیه؟اگر دوست دارید راجع به بخش‌های مختلف بلد بیشتر بدونید و بفهمید چه طور با واحد‌های محاسباتی یا مدل‌های ریاضی سعی می‌کنیم سرویس خوبی به شما ارائه بدیم، همینجا واسمون کامنت بگذارید و سوالاتتون رو بپرسید. من و همکارانم خوشحال میشیم به سوالات و ابهامات شما پاسخ بدیم.