ترافیک شهری در اسنپ - بخش صفر

مقدمه

یکی از مهم‌ترین نیازمندی‌های سرویس اسنپ اطلاع از وضعیت ترافیکی فعلی خیابون‌ها و معابر سطح شهر و همینطور پیش‌بینی وضعیت آن‌ها در دقایق و ساعت‌های آینده و استفاده از این داده‌ها برای ارائه سرویس‌های مختلف نقشه است. توی این پست میخواییم در مورد کاربرد‌‌‌ها، چالش‌ها و چگونگی انجام این کار تو تیم نقشه اسنپ توضیحات کوتاهی بدیم تا دریچه‌ای برای پست‌های آینده باشه.

وضعیت ترافیکی چیست و چه استفاده‌هایی داره؟

منظور ما از وضعیت ترافیکی معابر این است که اگر شما با یک خودرو وارد یک خیابان بشید با چه سرعتی میتونید در اون حرکت کنید. برای مثال یک بخش از اتوبان همت رو در نظر بگیرید. در ساعت‌های مختلف از روز ما شاهد سرعت‌های مختلفی هستیم که از ۸۰ کیلومتر بر ساعت شروع شده و در ساعت‌های اوج ترافیک به زیر ۱۰ کیلومتر در ساعت هم میرسه.

ما با دونستن وضعیت لحظه‌ای خیابون‌ها میتوانیم اون رو به کاربران راننده و مسافر نشون بدیم و همینطور با پیش‌بینی وضعیت ترافیکی میتونیم تخمین خودمون از طول سفر و زمان رسیدن به مقصد رو بهبود بدیم که باعث میشه نه تنها قیمت‌گذاری دقیق‌تری رو داشته باشیم بلکه کاربران مسافر و راننده هم خواهند توانست زمان خودشون رو دقیق‌تر برنامه‌ریزی کنن. این‌ها بخش کوچکی از استفاده‌هایی هستن که میشه از این داده‌ها کرد.

ما برای محاسبه وضعیت ترافیکی خیابون‌ها مثل سایر سرویس‌های مطرح از داده‌های GPS راننده‌ها استفاده می‌کنیم. راننده‌های اسنپ در زمان در دسترس بودن و همینطور در طول سفر در بازه‌های چند ثانیه ای اطلاعات مکانی خودشون رو به سرور‌های اسنپ ارسال می‌کنند. با جمع آوری و تحلیل این داده‌های مکانی ما می‌توانیم یک تخمین از وضعیت ترافیکی معابری که راننده‌های اسنپ در اون‌ها حضور دارن داشته باشیم.

سرویس‌های متنوعی از این داده استفاده میکنند تا بتوانند نتایج دقیقی رو تولید بکنند که چند تا از اونها شامل موارد زیر می باشد:

• محاسبه زمان رسیدن به مقصد (ETA): این سرویس زمان رسیدن از یک نقطه به نقطه‌ی دیگری رو محاسبه میکنه. خروجی این سرویس یکی از مهم‌ترین ورودی‌های سرویس قیمت‌گذاری هستش.
• محاسبه مسیر بهینه (Routing): این سرویس مسیر بهینه برای رسیدن از یک نقطه به نقطه ی دیگری رو محاسبه می‌کنه. راننده با استفاده از این سرویس میتونن در کوتاه‌ترین زمان به مبدا و مقصد سفر برسند.
• پیدا کردن بهینه‌ترین راننده: این سرویس از بین راننده‌های موجود در یک منطقه راننده‌ای رو که در سریع‌ترین زمان ممکن می‌تونه به یک نقطه مشخص برسه رو پیدا می کنه.

استفاده از این داده‌ها به این سادگی‌ها هم نیست، چالش‌های مختلفی وجود داره که در ادامه این پست بیشتر بهشون می‌پردازیم.

چالش‌های موجود در محاسبه وضعیت ترافیکی و استفاده از آن

همانطور که قبل‌تر هم اشاره شد محاسبه وضعیت ترافیکی دارای چالش‌های علمی و فنی متعددی هست که حل کردن هر کدوم از اون‌ها نیاز به صرف زمان و انرژی قابل توجهی داره (طاده در اینجا به‌شکل مفصل در مورد یکی از این چالش‌ها نوشته). توی این بخش به چند تا از بزرگ‌ترین چالش‌ها اشاره می‌کنیم و به‌صورت خلاصه به راهکار‌هایی که براشون داریم اشاره می‌کنیم.

چالش اول: مدل کردن داده‌های نقشه

اولین نیازمندی برای کار با داده‌های نقشه مدل کردن این داده‌ها به ساختاری است که توسط کامپیوتر پردازش بشه. روش‌های مختلفی برای این کار وجود داره که مورد استفاده ترینشون تبدیل نقشه به یک گراف جهت داره. استاندارد‌های مختلفی در سطح جهان وجود داره که همه بتونن داده‌های نقشه رو با هم به اشتراک بگذارن. معروف‌ترین و محبوب‌ترین استاندارد هم داده‌های Openstreet Map یا همون OSM هستش. متاسفانه این استاندارد همه نیازمندی‌های موجود ما رو برطرف نمی‌کنه. برای مثال روش تقسیم‌بندی خیابون‌هاش مناسب تحلیل‌های ترافیکی نیستش. علاوه بر اون روشی که این استاندارد داده‌ها رو ذخیره می‌کنه دست ما رو تو استفاده از داده‌های دیگه در کنار هم می‌بنده.

برای حل این مشکل ما از یک استاندارد گرافی دیگه که برای حل این مشکلات ساخته شده استفاده می‌کنیم که بر روی استاندارد داده‌های OSM سوار میشه. توی این روش هر خیابونی یک مشخصه (id) منحصر به فرد داره که در طول زمان تغییری نمی‌کنه. علاوه بر اون، توانایی شناسایی داده‌های مشترک در بین چند داده و استاندارد مختلف رو داره که به ما اجازه میده علاوه بر داده‌های OSM از داده‌های دیگه هم استفاده بکنیم. در پست‌های آتی بیشتر در مورد این ابزار صحبت خواهیم کرد.

چالش دوم: خطای داده‌های GPS

همونطور که می‌دونید، گوشی‌های ما با استفاده از امواج فرستاده شده از ماهواره‌های GPS موقعیت مکانی خودش رو تخمین می‌زنه. متاسفانه به دلایل مختلف ممکنه این تخمین با خطاهایی همراه باشه که از دلایل اون می‌شه به وجود ساختمون‌های بلند، بازتاب محیطی امواج، و همینطور نویز‌های موجود اشاره کرد. زمانی که این اتفاق میوفته ما از مکان دقیق راننده اطلاع نداریم و در نتیجه نمی‌تونیم با قطعیت بفهمیم که راننده در چه خیابونی در حال حرکت هستش.

به تکنیکی که بتونه این مشکل رو حل کنه Map Matching میگن. راه‌ حل‌های مختلفی برای حل این چالش وجود داره که هرکدوم خاصیت‌های خودشون رو دارن. بعضی‌هاشون خیلی سریع هستن ولی دقت کمی دارن و بعضی‌های دیگه دقیق‌تر اما با محاسبات سنگین‌تری هستن. ساده‌ترین راه حل موجود اینه که نقطه‌ی ثبت شده رو به نزدیک‌ترین خیابون متصل کنیم و فرض بگیریم که مکان واقعی راننده توی اون خیابون هستش. متاسفانه این روش از دقت خوبی برخوردار نیست و خیلی جاها مارو دچار مشکل میکنه. در بین راهکار‌های موجود ما به سراغ استفاده از مدل‌های پنهان مارکوف (Hidden Markov Models) رفتیم. توضیح در مورد این که این روش دقیقا چطوری کار میکنه از حوصله این پست خارجه و میذاریمش برای پست‌های بعدی و در زیر یک توضیح خیلی سریع در موردش میدیم.

توی این روش که به اختصار به اسم HMM Map Matching شناخته میشه ما فقط به نقطه فعلی نگاه نمیکنیم بلکه میاییم به موقعیت‌های مکانی قبلی کاربر که مربوط به ثانیه‌ها و دقایق قبل هستش نگاه میکنیم. اینطوری وقتی بین چند گزینه احتمالی شک داریم بهتر میتونیم از انتخاب نهایی موقعیت مکانی کاربر مطمئن بشیم.

چالش سوم: حجم زیاد داده‌ها

یکی دیگه از چالش‌هایی که ما در این مسیر بهش برخوردیم حجم زیاد داده‌های GPS بود که به سمت ما میومد. شکل زیر (تصویر ۶) تصویری از نقاط GPS ای هستش که فقط در طول چند دقیقه و فقط در شهر شیراز به سمت ما ارسال شده. میتونید حدس بزنید که تحلیل این داده‌ها که به ۲.۴ میلیون نقطه در دقیقه میرسن میتونه کار چالش برانگیزی باشه.

تصویر ۷ یک نمودار خیلی کلی از مسیر داده‌های ترافیکی ما (Traffic Pipeline) هستش. تمام این مراحل باید بتونن اونقدر سریع انجام بشن که داده‌های خروجیشون قابل استفاده به‌صورت زنده باشن. ما در بازه‌های کوتاه ۱۵‌دقیقه ای داده‌های GPS رو جمع میکنیم و این پردازش‌هارو روش انجام میدیم. از اونجایی که سیستم ما به‌صورت واقعی زنده نیست و در بازه‌های کوتاه کارش رو انجام میده بهش پردازش Micro Batch هم گفته میشه.

همونطور که میدونید راه‌های زیادی برای سریع کردن پردازش‌ها وجود داره. یکی از راه‌ها اسکیل (Scale) کردن سرویس‌ها به‌صورت عمودی (Vertically) هستش. در مورد ما هزینه سروری که اونقدری سخت افزار قوی‌ای داشته باشه که بتونه نیاز‌های مارو جواب بده زیاده و روش منطقی‌ای برای ما نیست. پس ما به سمت اسکیل کردن افقی (Horizontally) رفتیم. برای این که بتونیم این کار رو انجام بدیم لازم بود که بتونیم تمام معماریمون رو طوری طراحی کنیم که توانایی پردازش موازی و همزمان داشته باشن. فریمورک‌ها و ابزار‌های مختلفی برای رسیدن به این نتیجه وجود دارن که ما از بین اون‌ها Apache Spark رو انتخاب کردیم و معماری Pipeline مون رو با اون طراحی و پیاده سازی کردیم.

چالش چهارم: ابزار مسیریابی (Routing Engine)

سرویس‌های مختلف نقشه مثل مسیریابی راننده‌ها و تخمین زمان رسیدن به مقصد (ETA) علاوه بر داده‌های ترافیکی نیاز به ابزاری سریع و دقیق جهت مسیریابی دارن. به سرویسی که این وظیفه رو انجام میده Routing Engine گفته میشه. ابزار‌های متن باز مختلفی در این زمینه موجود هستند که هرکدوم از نقاط قوت و ضعف مختلفی دارن. ما تو اسنپ به ابزاری نیاز داریم که بتونه داده‌های ترافیکی زنده رو پردازش بکنه، توانایی اعمال محدودیت‌های ترافیکی مختلف مثل طرح ترافیک رو داشته باشه و در کنار همه ی این‌ها سریع باشه. متاسفانه هیچ‌کدوم از ابزار‌هایی که ما میشناسیم همه‌ی نیازمندی‌های مارو برطرف نمیکنن در نتیجه ما توی اسنپ به سمت استفاده و گسترش این ابزار‌های متن‌باز رفتیم تا با نیازمندی‌های ما منطبق بشه. توی پست‌های بعدی به‌شکل تخصصی‌تر به بررسی این ابزار می‌پردازیم.

پایان

توی این پست با محاسبه وضعیت ترافیکی خیابون‌ها در اسنپ و استفاده از این سرویس به همراه چالش‌هایی که داره به‌شکل کلی آشنا شدید. استفاده از این داده‌ها به موضوعاتی که به اونها اشاره شد محدود نیست و همینطور چالش‌هایی که در مسیر موجود هستند هم بیشتر از اون‌هایی هستند که تا اینجا دیدید. توی این پست تلاش شد که به‌شکل خلاصه با معماری و ادبیات موضوع آشنا بشید تا در پست‌های آینده بتونیم عمیق‌تر و مفصل‌تر به هر کدوم از بخش‌های این سیستم بپردازیم.

در انتها از همتون ممنونم که تا اینجا با ما همراه بودید. امیدوارم که مطالبی که خوندید براتون جذاب بوده باشه. خوشحال می‌شم اگه سوالی دارید یا دوست دارید بیشتر صحبت کنیم کامنت بذارید یا به من پیام بدید.

در ضمن، اگه حس می‌کنین از پروژه‌هایی شبیه به این خوشتون میاد و در نتیجه علاقه دارید به تیم ما ملحق بشید، خوشحال می‌شیم که رزومه‌هاتون رو از طریق آدرس engineering@snapp.cab برای ما ارسال کنید.