سیستم T-Drive :

ارتقای مسیریابی در حین رانندگی با بهره گیری از هوش و اطلاعات رانندگان تاکسی

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

ما بر اساس این نمودار یک الگوریتم مسیر یابی دو مرحله ای طراحی کردیم که با استفاده از آن می توان سریع‌ترین و مناسب ترین مسیر را بنا به نیاز کاربر نهایی محاسبه و انتخاب کرد. ما سیستم خود را بر اساس مجموعه دیتای مربوط به مسیرها در دنیای واقعی که از طریق بیش از ۳۳۰۰۰ تاکسی در یک دوره سه ماهه به دست آمده‌، ایجاد کرده‌ایم و این سیستم را با استفاده از تجربیات غیرواقعی و ارزیابی های میدانی‌، هدایت کرده ایم. در نتیجه ۶۰ الی ۷۰ درصد از مسیرهای پیشنهاد شده توسط متد ما سریعتر از متدهای رقابتی هستند و ۲۰ درصد از مسیرها نتایج مشابهی را نشان داده اند. به طور متوسط ۵۰ درصد از مسیرهایی که ما ارائه کرده‌ایم حداقل ۲۰ درصد سریعتر از روش های رقابتی بوده اند.

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

یک سرویس مسیریابی خوب باید این سه جنبه (مسیرها ، ترافیک و رانندگان) را در نظر بگیرد که بسیار فراتر از محدوده کوتاهترین و سریعترین محاسبات مسیری هستند. برای ارسال تاکسی  و کنترل مسیرها تاکسی ها معمولا مجهز به یک سنسور GPS هستند که به آنها امکان می دهد موقعیت مکانی خود را به سرور در بازه های زمانی مشخص گزارش دهند.

این مسیرهای تاریخی مورد استفاده تاکسی ها که نشان دهنده هوش و تجربه رانندگان است منابع باارزشی به ما نشان می دهد که می توان از آنها مسیرهای مناسب برای رانندگی سریع را یاد گرفت .

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

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

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

سوم اینکه دانش موجود در ابر برای ارائه خدمات به کاربران اینترنتی و رانندگان معمولی در دنیای فیزیکی به کار می رود.

در نهایت اینکه یک برنامه کاربردی موبایل معمولا یک برنامه مبتنی بر GPS را در گوشی در حال اجرا دارد که درخواست کاربر را قبول کرده و با ابر پردازشی ارتباط برقرار کرده و نتایج را در نهایت به کاربر نشان می دهد. این برنامه موبایلی رفتار رانندگی کاربر را از مسیرهای رانندگی اش ( که در لاگ های  GPS ثبت شده است) به تدریج یاد می گیرد و از پردازش ابری برای یافتن سریعترین مسیر استفاده می کند.

البته در این مسیر ما با سه چالش مواجه بوده ایم:

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

۲) پوشش و کم نظیری داده ها: ما قادر به تضمین این امر نیستیم که تعداد تاکسی هایی که در مسیرهای مختلف در هر بخش جاده تردد می کنند تعداد مکفی برای جمع آوری دیتای مورد نیاز ما باشند. به عبارت دیگر نمی توانیم به طور دقیق تخمین بزنیم که الگوی سرعت در هر بخش جاده به چه صورت است.

۳) مشکل پایین بودن نرخ نمونه های مورد استفاده : به منظور ذخیره انرژی و کاهش بار ارتباطی ، تاکسی ها غالبا موقعیت مکانی خود را در فرکانس های بسیار پایین گزارش می کنند مانند ۲ الی ۵  دقیقه در هر نقطه مکانی. این امر سبب افزایش عدم قطعیت مسیرهایی می شود که توسط تاکسی ها پیموده می شود. همانطور که در تصویر شماره ۲ نشان داده شده است این امر می تواند ۴ مسیر احتمالی را برای پیمودن فاصله بین نقاط a و b ایجاد کند.

در عمل تاکسی ها برای صرفه جویی در مصرف انرژی و کاهش بارهای ارتباطی معمولا موقعیت مکانی خود را در فرکانس های بسیار پایین مانند ۲ الی ۵ دقیقه در هر نقطه گزارش می دهند. این امر عدم قطعیت مسیرهایی که توسط تاکسی ها پیموده می شود را افزایش می دهد . در عین حال ما نمی توانیم تضمین کنیم که تعداد مکفی تاکسی در هر زمانی توانسته اند هر یک از بخش های جاده ای را بپیمایند این امر حتی اگر تعداد تاکسی ها زیاد باشد نیز مقدور نخواهد بود. به عبارت دیگر ما نمی توانیم مستقیما الگوی سرعت هر بخش جاده ای را بر اساس مسیرهای تاکسی تخمین بزنیم.

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

بر اساس مسیرهای از پیش پردازش و پیموده شده توسط تاکسی ها بخش هایی از جاده ها که بیشتر مورد پیمایش قرار گرفته بودند را پیدا کردیم این در حالی بود که این مسیرها علایمی را نیز در برداشتند. دلیل استفاده از “علایم” برای مدل سازی هوش رانندگان تاکسی این است که:: نخست اینکه عدم پیمایش مکرر مسیرها توسط تاکسی ها امکان نمونه برداری گسترده را برای ما فراهم نمی کرد و لذا ما قادر نبودیم مستقیما زمان تردد را برای هر بخش جاده ای محاسبه کنیم اما این در حالی بود که می توانستیم زمان تردد بین دو نقطه دارای علامت را  ( که به طور مکرر توسط تاکسی پیموده شده بود را )محاسبه کنیم. دوم اینکه مفهوم مکان های“ علامت دار“ یک الگوی تفکری طبیعی موجود در ذهن مردم را دنبال می کند. برای مثال الگوی معمولی که بنا بر آن مردم مسیری را به یک راننده معرفی می کنند مانند این عبارت است:” از طریق مسیر جنوبی خیابان ۴۰۵ برو به خیابان چهارم شمال شرقی ، سپس به سمت خیابان I-90 تغییر مسیر بده و از خیابان ۱۱ خارج شو و در نهایت از منطقه Qwest Field بیرون برو”

۳٫۲: تخمین زمان تردد در یک مسیر ( تخمین زمان سفر)

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

و این کار بر اساس شرایط ترافیکی نشان داده شده در نمونه های خام اولیه انجام می شود .

 سپس به تخمین توزیع زمانی تردد در هر برهه زمانی مربوط به هر مکان علامت دار می پردازیم.

Framework‌‌:

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

 متد SC که توسط گوگل و بینگ مپ ارائه شده است، مبتنی بر الگوریتم کوتاهترین مسیر مانند A* است که در آن از محدودیت سرعتی هر بخش جاده استفاده شده است. متد RT نخست سرعت هر بخش را در زمان مشخص بر اساس خوانش GPS از پیمایش تاکسی ها در بخش های جاده یا خوانش سنسورهای جاده ای ، ارزیابی می کند و سپس بر اساس سرعت های تخمین زده شده سریعترین مسیر را محاسبه می کند. باید توجه داشت که متد RT بر اساس شرایط ترافیکی در زمان واقعی طراحی نشده است بلکه سرعت های تخمین زده شده در این روش بر اساس نمونه هایی هستند که در نزدیکترین برهه های زمانی به زمان مورد نظر ثبت شده اند.

برای فعال کردن خدمات مسیریابی رانندگی در محیط ابری برخی مسایل کلیدی مانند کارآمدی و حریم خصوصی نیز مورد بررسی قرار گرفته اند.

برای آشکار کردن عملکرد کارآمدی متد ما ( صرف نظر از طراحی سیستم ) ما سیستم خود را بر روی یک سرور واحد با ۲٫۶۷GHZ CPU  و ۱۶GB RAM ( با استفاده از یک فاکتور ثابت بدون بهینه سازی ) در فضای ابری همانطور که در جدول شماره ۴ نشان داده شده است ، مورد سنجش قرار دادیم. برنامه کاربردی موبایلی بر روی گوشی های هوشمند دارای سیستم عامل ویندوز مجهز به اتصالات GPRS  و ۱GHZ CPU اجرا می شود. که میتواند در هر ثانیه با استفاده از ۳۰ سرور در یک ابر به ۱۰۰۰ درخواست پاسخ دهد.

.۷٫ کارهای مربوطه

۷٫۱٫ خدمات مسیریابی در رانندگی بر روی نقشه های مبتنی بر وب

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

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

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

استفاده از شرایط ترافیکی بهنگام حاصل از سنسورها در یک الگوریتم مسیریابی قادر نیستند که مستقیما و  به گونه ای کارآمد سریعترین مسیر را نشان دهند.

مزیت های این روش نسبت به سایر روش ها:

متد ما از سایر متدها از جهاتی که در ادامه ذکر می شود متفاوت است.

 نخست اینکه هدف ما ارائه خدمات مسیریابی هوشمند به کاربران در عوض پیش بینی مسیر یا مقاصد نهایی آنها است.

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

سوم اینکه در خدمات مسیریابی رفتارهای رانندگی کاربر نهایی ( که قرار است مسیر برای او محاسبه شود) و رانندگان تاکسی مورد توجه قرار داشته و لحاظ می شود.

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

در نهایت باید گفت که بیش از ۶۰ درصد از مسیرهای ارائه شده از سوی سیستم ما سریعتر از مسیرهای عرضه شده از سوی خدمات نقشه آنلاین بوده اند و ۵۰ درصد از این مسیرها حداقل ۲۰ درصد سریعتر از مسیرهای قبلی ارائه شده بوده اند. به طور میانگین متد ما می تواند باعث صرفه جویی ۱۶ درصدی در زمان یک سفر شهری شده و در هر ۳۰ دقیقه رانندگی نیز باعث ۵ دقیقه صرفه جویی شده است.