۱٫ مقدمه
سیستم حمل و نقل هوشمند در سال های اخیر داغ شده است و در نتیجه رویکردهای بسیاری در حمل و نقل هوشمند ارائه شده است. حفاری جریان را می توان برای پشتیبانی از برنامه ریزی ترافیک وسیله نقلیه [ ۱ ، ۲ ]، توصیه مسیر وسیله نقلیه [ ۳ ، ۴ ]، برنامه ریزی مکان ایستگاه مترو [ ۵ ، ۶ ]، مدیریت اضطراری خودرو [ ۷ ، ۸ ] و غیره استفاده کرد. ارزش تجاری را می توان از طریق تجزیه و تحلیل مسیر خودرو به دست آورد [ ۹ ، ۱۰]. در حال حاضر روش های تحلیلی مختلفی برای مسیر حرکت خودرو وجود دارد. به عنوان مثال، از طریق داده های مسیر تاریخی وسایل نقلیه، پیش بینی جریان ترافیک شهری، استخراج نقاط مورد علاقه در شهر، پیش بینی نقاط پرتاب دوچرخه های مشترک، و حتی برنامه ریزی نقاط خدمات حمل و نقل عمومی شهری از طریق تجزیه و تحلیل تراکم مسیر تاکسی و تشخیص نقطه توقف.
تجزیه و تحلیل مسیر وسیله نقلیه به تجزیه و تحلیل الگوی سفر شهروندان و غیره کمک می کند. Tang et al. [ ۱۱ ] الگوهای سفر ادغام خودرو مسافران را با استفاده از یک الگوریتم پیشبینی هدف تطبیق جزئی (P-PPM) برای استخراج الگوهای حرکت مکرر از دادههای مسیر و تعیین اطمینان قوانین حرکت، تجزیه و تحلیل کرد. این روش کل زمان سفر را به عنوان هدف منطبق در نظر می گیرد. ژو و همکاران [ ۱۲] مطالعه مسیر اطلاعات زمینه و اطلاعات عصاره یافت شده مانند اطلاعات موقعیت مکانی از طریق تجزیه و تحلیل اولین مورد برای تأیید دانش است، با این حال، مدیریت تحرک یک مشکل مهم این است که چگونه یک برنامه سفر دقیق را یاد بگیریم، بنابراین آنها پیشنهاد کردند. یک مسیر از روش توصیه شده سفر رمزگذار و رمزگشا. این یک رویکرد سرتاسر جدید است که مسیرهای تاریخی را به عنوان بردار رمزگذاری میکند و در عین حال ویژگیهای ذاتی نقاط مورد علاقه (POI) و الگوهای تبدیل بین POIها را به تصویر میکشد. مکانیسم توجه تاریخی در وظیفه توصیه سفر متوالی به متوالی روش برای بهبود اثربخشی گنجانده شده است. زو و همکاران [ ۱۳] یک مدل توصیه خدمات جغرافیایی (GSRM) را پیشنهاد کرد که تقریباً شامل سه مرحله اساسی است. ابتدا، توالی موقعیت با خوشه بندی موقعیت های GPS به دست می آید. برای بهبود کارایی، یک مدل برنامهنویسی با الگوریتم توزیعشده برای تسریع خوشهبندی اتخاذ میکنیم. دوم، توالی موقعیت برای استخراج اطلاعات مکانی و زمانی از مسیرهای خوشهای. الگوریتم MiningMP طوری طراحی شده است که مکان احتمالی بعدی که کاربر به آن سفر خواهد کرد پیش بینی می شود. سپس می توان یک چارچوب جامع برای GSRM ایجاد کرد و با در نظر گرفتن اطلاعات مکان، خدمات توصیه های جغرافیایی مناسب را ارائه کرد. الگوریتم MiningMP با در نظر گرفتن توالی مکان و سایر اطلاعات معنایی مرتبط، خدمات توصیه های جغرافیایی مناسب را ارائه می دهد.
پیشبینی جریان ترافیک میتواند به هدایت جریان ترافیک و مسائل دیگر کمک کند. لی و همکاران [ ۱۴ ] یک مدل شبکه کانولوشنال گراف همبستگی داده چند سنسور جدید (MDCGCN) پیشنهاد کرد. مدل MDCGCN از دوره های کوتاه مدت، روزانه و هفتگی تشکیل شده است و هر بخش از دو بخش تشکیل شده است: (۱) مکانیسم تطبیقی مرجع و (۲) بلوک پیچشی همبستگی داده های چند سنسوری. بخش اول می تواند تفاوت بین داده های دوره ای را از بین ببرد و به طور موثر کیفیت ورودی داده ها را بهبود بخشد. بخش دوم می تواند به طور موثر همبستگی زمانی و مکانی پویا ناشی از تغییر رابطه حالت ترافیک بین جاده ها را به تصویر بکشد. هو و همکاران [ ۱۵] مدل پیشبینی جریان ترافیک کوتاهمدت را مورد مطالعه قرار داد که یک معماری محاسباتی لبه ترافیک سهلایه Cloud-Edge-IOT و یک روش پیشبینی جریان ترافیک کوتاهمدت مبتنی بر همبستگی مکانی-زمانی پیشنهاد شده است که از تجزیه و تحلیل مؤلفههای اصلی (PCA) استفاده میکند. ) برای تجزیه و تحلیل همبستگی تقاطع. واحد بازگشتی دروازهای کانولوشن (CONVL-GRU) و GRU دو جهته (Bi-GRU) برای استخراج ویژگیهای مکانی-زمانی و دورهای جریانهای ترافیکی استفاده میشود. شما و همکاران [ ۱۶] یک مدل اتوماتای سلولی (CA) بهبود یافته را برای آشکار کردن پیشبینی جریان ترافیک در تقاطعهای علامتدار پیشنهاد کرد. تراکم ترافیک و سرعت متوسط برای مطالعه ویژگیها و تکامل فضایی جریان ترافیک در تقاطعهای علامتدار بر اساس مدل CA محاسبه میشوند. بر این اساس، یک مدل بهینهسازی کنترل قوانین ترافیک جدید و یک مدل CA با سیستم سیگنال ترافیک خودسازماندهی پیشنهاد شدهاست. الگوریتم بهینه سازی گربه آفتابگردان (SCO) برای پیش بینی جریان به طور موثر استفاده شد. این الگوریتم با ترکیب الگوریتم بهینه سازی گل آفتابگردان (SFO) با الگوریتم بهینه سازی ازدحام گربه ها (CSO) طراحی شده است. علاوه بر این، تابع تناسب اندام برای هدایت قوانین کنترل ارزیابی شبیه سازی ترافیک مدل CA طراحی شده است.
به طور خلاصه، مطالعات فوق به دقت داده های مسیر بستگی دارد. با این حال، به دلیل محافظت از سیگنال یا دلایل دیگر، تعداد زیادی از نقاط مسیر اغلب گم می شوند یا بخش های مسیر ناپیوسته در مسیر ظاهر می شوند. بنابراین، ما یک مدل مکعب داده مسیر (TDC) خواهیم ساخت. Ψ{ tn، pn، vn} برای ذخیره داده های مسیر تاکسی ها، و بازیابی شرایط رانندگی وسیله نقلیه در هر لحظه در شبکه جاده ها از طریق روش فشرده سازی سلسله مراتبی، که در آن tnزمان است، pnمی ایستد موقعیت وسیله نقلیه، و vnنشان دهنده سرعت خودرو است. یک روش ردیابی سلسله مراتبی (HTB) بر اساس مسیر تاریخی تاکسی برای مطالعه بازیابی مسیر گمشده و اطلاعات از دست رفته طراحی خواهد شد. با توجه به خاص بودن تاکسی، داده های مسیر آن اساساً در شبکه جاده ها هستند و تاکسی می تواند مقدار زیادی از داده های مسیر را برای تجزیه و تحلیل داده ها ارائه دهد. جدول ۱ پارامترهای اصلی ذکر شده در این مقاله را نشان می دهد.
در این مقاله، شرایط ترافیک در هر زمانی از تاریخ با فشرده سازی و رقیق سازی داده ها به دست می آید تا داده های مسیر ناقص خودرو را یکپارچه کرده و کمک دقیق تری برای تجزیه و تحلیل داده های مسیر ارائه دهد. سهم اصلی این مقاله به شرح زیر است:
-
ما با تجزیه و تحلیل دادههای مسیر تاکسیها، یک مکعب داده با ویژگیهای مکانی-زمانی میسازیم، دادههای مسیر هر روز را در مکعب ذخیره میکنیم و در نهایت دادههای چند روزه را در یک مدل TDC ادغام میکنیم.
-
ما داده های مسیر هر لایه را از طریق TDC تعیین شده تجزیه و تحلیل می کنیم و لایه های داده را با روش های HTB-p، HTB-v، و HTB-KF فشرده می کنیم. وضعیت ترافیکی شبکه راه را در زمان معینی به دست آورید.
-
در نهایت، روش نازکسازی برای تأیید تأثیر روشهای HTB-p، HTB-v، و HTB-KF و ترافیک واقعی شبکه جادهای تاریخی، و مقایسه با روشهای پیشبینی وضعیت ترافیک موجود و استراتژیهای تکمیل مسیر استفاده میشود.
بقیه این مقاله به شرح زیر سازماندهی شده است. بخش ۲ روش های پیش بینی جریان ترافیک و استراتژی مسیر تکمیل را معرفی می کند. بخش ۳ مدل مکعب داده مسیر را بر اساس داده های مسیر تاکسی ناقص ارائه می دهد. بخش ۴ یک الگوریتم ردیابی سلسله مراتبی را برای بازیابی داده های مسیر تاریخی وسایل نقلیه معرفی می کند. بخش ۵ سه آزمایش را برای تأیید روش های ما و نتیجه گیری در بخش ۶ انجام می دهد.
۲٫ بررسی ادبیات
در حال حاضر، روشهای محبوبتر فناوری استخراج مسیر تاریخی خودرو شامل روش تکمیل مسیر مبتنی بر تحلیل زمینه، روش تکمیل تفاوت و استفاده از روش یادگیری عمیق برای پیشبینی مسیر است. این روشها معنای دادههای مسیر را توضیح میدهند و الگوی دادههای مسیر را از دیدگاههای نظری مختلف بررسی میکنند، که پایهای برای مدیریت و مدلسازی دادههای مکانی-زمانی و کشف دانش شبکه راهها میگذارد [ ۱۷ ].
۲٫۱٫ تجزیه و تحلیل مسیر خودرو مبتنی بر زمینه
تجزیه و تحلیل داده های مسیر بر اساس اطلاعات زمینه یکی از روش های اصلی برای پردازش داده های مسیر در مراحل اولیه است که به مقدار زیادی اطلاعات داده های مسیر تاریخی نیاز دارد. زو و همکاران [ ۱۸ ] اطلاعات زمینه مسیر را مطالعه کرد و از یک روش خوشهبندی برای گروهبندی مسیر یک دوره خاص، بازیابی ویژگیهای جاده و پیشبینی وضعیت جاده از طریق مسیر مشابه بهدستآمده استفاده کرد. دای و همکاران [ ۱۹] ویژگی های گمشده داده های مسیر متحرک را تجزیه و تحلیل کرد و داده ها را از طریق داده های مسیر فرکانس نمونه برداری از زمین به طور دقیق مکان یابی و تکمیل کرد. با توجه به صرفه جویی در تجهیزات نمونه برداری، وسایل نقلیه به ندرت از تجهیزاتی با فرکانس نمونه برداری بالا استفاده می کنند، بنابراین در داده های مسیر با فرکانس نمونه برداری کم، نادرستی ها و نقاط گم شده زیادی وجود دارد. کاهش و رتبه بندی عدم قطعیت مبتنی بر زمینه (CURR) برای استنباط نقاط مسیر از دست رفته و نقاط دقت پایین طراحی شده است. موسی و همکاران [ ۲۰ ] یک سخت افزار نمونه گیری مسیر دو دستگاهی را بر اساس فرکانس نمونه برداری کم و دقت ضعیف داده های مسیر پیشنهاد کرد. این سخت افزار مسیر را با اجزای الکتریکی و با ترکیب داده های زمینه مسیر GPS موجود تکمیل می کند. یانسن و همکاران [ ۲۱] یک روش پیشبینی مسیر کشتی را پیشنهاد کرد که اطلاعات زمینه مسیر معنایی و شبکههای بیزی پویا را ترکیب میکند. این روش از شبکه بیزی برای محاسبه احتمال بین مسیر کشتی و مسیر نمونه برای پیش بینی مسیر کشتی استفاده می کند. مزیت این روش در رتبهبندی احتمال مسیرهای مختلف با روش آمار احتمالی است تا مسیر کشتیها را تحلیل کرده و موقعیت آنها را در نوبت بعدی پیشبینی کند. دینگ و همکاران [ ۲۲] یک چارچوب آنلاین پیشبینی مسیر خودرو در دو سطح طراحی کرد. این روش پیشبینی خطمشی سطح بالا را با استنتاج زمینه سطح پایین ترکیب میکند. شبکه حافظه بلند مدت (LSTM) برای پیشبینی استراتژیهای رانندگی (به عنوان مثال، به جلو، تسلیم، چپ، راست، و غیره) با استفاده از مشاهدات تاریخی مستمر آن استفاده میشود. سپس این استراتژی برای هدایت فرآیند بهینه سازی سطح پایین بر اساس استدلال زمینه استفاده می شود. بلیز و همکاران [ ۲۳ ] رفتارهای رانندگی رانندگان را با توجه به اطلاعات زمینه مسیر وسیله نقلیه استنباط کرد تا اطلاعات بیشتری از مسیر وسیله نقلیه به صورت جداگانه به دست آورد. یو و همکاران [ ۲۴] یک شبکه توجه آگاه از زمینه پویا و ایستا (DSCAN) را پیشنهاد کرد. DSCAN از مکانیسم توجه استفاده می کند تا به صورت پویا مشخص کند که کدام خودروهای اطراف در حال حاضر مهم تر هستند. یک شبکه محدودیت نیز برای طراحی DSCAN به منظور در نظر گرفتن اطلاعات استاتیک محیط استفاده می شود.
۲٫۲٫ روش تکمیل نقطه از دست رفته مسیر بر اساس الگوریتم درونیابی
استراتژی تکمیل دادههای مسیر عمدتاً تکمیل بخش گمشده دادههای مسیر از طریق درونیابی و سایر استراتژیها برای نقاط شکست یا اطلاعات گمشده موجود در دادههای نمونهگیری مسیر است. لی و همکاران [ ۲۵ ] یک روش درونیابی مبتنی بر فیلتر تطبیقی هسته فاصله نابرابر دو جهتی برای حل مشکل از دست دادن داده در اندازهگیری مسیر آزمایشی خودرو پیشنهاد کرد. نمونه های آموزشی فیلتر تطبیقی با توجه به داده های قبل و بعد از بخش داده های گمشده اندازه گیری مسیر طراحی شده اند. پس از آموزش، از فیلتر تطبیقی هسته برای پیش بینی داده های از دست رفته دو جهته استفاده می شود. کروز و همکاران [ ۲۶] مسیر وسایل نقلیه ترافیکی را بر اساس مجموعه داده های واقعی تجزیه و تحلیل کرد که مشکلات پراکندگی و ناقص بودن آنها را ثابت کرد و مانع پیش بینی مکان شد. در این زمینه، روشی برای مقابله با مشکل داده های از دست رفته پیشنهاد شده است. همچنین نحوه ترکیب این روش با پیش بینی کننده های مبتنی بر شبکه های عصبی بازگشتی را مورد بحث قرار می دهد. به طور خاص، اندازهگیریهای دقیق برای محاسبه مقادیر از دست رفته در مجموعه تست با معرفی فاصله بین مکان پیشبینیشده و مکان بعدی ثبتشده تنظیم شدند. وی و همکاران [ ۲۷] روشی مبتنی بر فیلتر ذرات (PF) برای بازسازی مسیر وسیله نقلیه در خطوط اصلی سیگنال با استفاده از دادههای تشخیص پراکنده پیشنهاد کرد. ابتدا تقاطع های جاده اصلی به چندین واحد جاده تقسیم می شوند و تخمین زمان سفر واحد به یک مسئله برنامه ریزی درجه دوم تبدیل می شود. سپس، PF برای بازسازی مسیر ناقص خودرو بین بهروزرسانیهای متوالی اعمال میشود. به طور خاص، به منظور محاسبه و به روز رسانی وزن ذرات اولیه، با در نظر گرفتن ساختار خط لوله سیگنال و ویژگی های نوسازی خودرو، سه معیار مهم اندازه گیری نمونه برداری، یعنی دقت تنظیم زمان سفر، محدودیت سرعت اتصال صندوق عقب و سفر طراحی شد. امکان تنظیم زمان چی و همکاران [ ۲۸] بازسازی مسیر پراکنده را بر اساس داده های ALPR مطالعه کرد. با توجه به آستانه معقول زمان سفر، این روش فعالیت های سفر چندگانه وسایل نقلیه را تقسیم می کند و مسیر ناقص وسیله نقلیه را شناسایی می کند. بر اساس نظریه منشور فضا-زمان، یک الگوریتم بهبود یافته K-shorttest path (KSP) برای تولید مسیر نامزد استفاده می شود. مسیر نامزد با شاخص تصمیم گیری بهینه توسط مدل رمزگذار خودکار انتخاب می شود و بازسازی مسیر خودرو محقق می شود. تانگ و همکاران [ ۲۹] یک چارچوب جدید مبتنی بر اینترنت برای استخراج مسیر و بازیابی داده های از دست رفته داده های سفر اتوبوس پیشنهاد کرد. در این چارچوب، یک الگوریتم اتصال مسیر جدید برای حل مشکلی که زمانی رخ میدهد که یک مسیر به اشتباه به چند خوشه در برخی موارد تقسیم میشود، گنجانده شده است. در فرآیند بازیابی داده های از دست رفته، یک روش درون یابی خطی متنی برای داده های از دست رفته در داخل مسیر و درون یابی میانه برای داده های از دست رفته خارج از مسیر طراحی شده است. شیائو و همکاران [ ۳۰] یک چارچوب جدید برای رگرسیون انتقال یکپارچه بر اساس محیط های شهری، با استفاده از یادگیری انتقال به عنوان راه حل اصلی برای ساخت مجموعه داده های مسیر ریز دانه در طول زمان از کار افتادن GNSS، پیشنهاد کرد. این چارچوب مشکل داده های مسیر ناقص ناشی از از دست دادن سیگنال GPS را با ساخت یک استراتژی فیلتر کردن داده برای محاسبه نقاط گمشده مسیر و درون یابی رتروگراد حل می کند.
۲٫۳٫ پیش بینی مسیر بر اساس یادگیری عمیق
با استفاده از فناوری یادگیری عمیق در زمینه پیشبینی مسیر خودرو، ابزارهای تجزیه و تحلیل مسیر خودرو متنوعتر و متنوعتر میشوند. لین و همکاران [ ۳۱ ] یک چارچوب اختصاصی رادار توزیع شده با مدل های یادگیری عمیق (DL) به نام شبکه رادار پیش بینی برای پیش بینی مسیرهای آینده در زوایای برد دوتایی (RA) پیشنهاد کرد. یک نقشه نمایش احتمالی از نمودار اصلی رادار RA ترسیم شده است تا عدم قطعیت مسیر تخمینی را نشان دهد. هوی و همکاران [ ۳۲] یک مدل یادگیری عمیق جدید برای برخورد با مسیرهای خودرو به عنوان مدل شهروندان درجه یک به نام TrajNet پیشنهاد کرد. این مدل وابستگی فضایی جریان های ترافیکی را با انتشار اطلاعات در طول مسیرهای واقعی نشان می دهد. به منظور بهبود کارایی آموزش، از مسیرهای چندگانه در یک دسته استفاده شده برای آموزش با ساختار آزمایشی برای استفاده مجدد از محاسبات مشترک استفاده میشود. TrajNet یک مکانیسم توجه فضایی را طراحی کرد تا به طور تطبیقی همبستگیهای دینامیکی بین بخشهای مختلف جاده را به تصویر بکشد، و پیچیدگی علی گشاد شده را برای گرفتن وابستگی زمانی طولانی برد. شما و همکاران [ ۳۳] یک روش تولید درخت الگوی مسیر مبتنی بر یادگیری عمیق را پیشنهاد کرد. مدلهای شبکه عصبی کانولوشنال یادگیری عمیق (CNN) و شبکه عصبی بازگشتی (RNN) برای تولید مسیر و پیشبینی استفاده میشوند. لیو و همکاران [ ۳۴ ] مسیر GPS تاکسی را برای تجزیه و تحلیل ویژگی های ترافیک در پکن استخراج کرد. ضریب شلوغی هر طرف مسیر کشویی به عنوان زمان مصرف لغزش در واحد فاصله تعریف می شود. با تجزیه و تحلیل توزیع ضریب تراکم تمام مسیرهای تاکسی. جیانگ و همکاران [ ۳۵ ] سه شبکه عصبی عمیق طراحی کرد: حافظه کوتاه و بلند (LSTM)، واحد بازگشتی دروازهای (GRU) و رمزگذار خودکار پشتهای (SAE) برای پیشبینی موقعیت و سرعت خودروی جلویی. یائو و همکاران [ ۳۶] مسئله خوشهبندی مسیر را با یادگیری نمایش کمبعدی مسیر بررسی کرد. ابتدا از ویژگی تغییرناپذیر زمان پنجره کشویی برای استخراج ویژگی فضای کشویی استفاده می شود. از طریق ماژول استخراج ویژگی، هر مسیر به یک توالی ویژگی برای توصیف حرکت جسم تبدیل میشود و در ادامه از رمزگذار خودکار ترتیب به ترتیب برای یادگیری طول ثابت نمایش عمق استفاده میشود. نمایش آموخته شده به خوبی ویژگیهای حرکتی شی را رمزگذاری میکند، که منجر به خوشههای تغییرناپذیر مکانی و زمانی میشود. گائو و همکاران [ ۳۷] یک روش پیش بینی مسیر برای قصد دوچرخه سواران در سناریوهای ترافیک واقعی پیشنهاد کرد. این روش مبتنی بر شبکه پویا بیزی (DBN) و حافظه کوتاه و بلند مدت (LSTM) است. پیش بینی نیات ورزشی دوچرخه سواران به دلیل عدم قطعیت های بالقوه بسیار دشوار است. DBN برای استنباط توزیع نیات دوچرخه سواران در تقاطع ها برای بهبود زمان پیش بینی استفاده می شود. کائوتر و همکاران [ ۳۸ ] مسئله پیشبینی مسیر وسیله نقلیه را در افق گسترده مورد مطالعه قرار داد. در بزرگراه، رانندگان انسان به طور مداوم سرعت و مسیر خود را با توجه به رفتار وسایل نقلیه مجاور خود تنظیم می کنند. بنابراین، مسیر وسیله نقلیه بسیار مرتبط است.
در روش های فوق، داده های مسیر به صورت خطی پردازش می شوند، یعنی داده های مسیر با توجه به زمان قبل و بعد در دو بعد تجزیه و تحلیل می شوند. با این حال، داده های مسیر واقعی را می توان به عنوان توزیع نقاط گسسته مختلف در یک موقعیت در دوره ها و روزهای متعدد در نظر گرفت. شکل ۱ چهار نوع داده مسیر را توصیف می کند که در آن محور x طول جغرافیایی، y عرض جغرافیایی و z نشان دهنده زمان است. شکل ۱ a وضعیت مسیر کامل را نشان می دهد، یعنی قسمت داده کامل است. شکل ۱ b نشان می دهد که یک نقطه از مسیر گم شده است. شکل ۱ ج افت مسیر را در دوره های متعدد نشان می دهد. شکل ۱d این است که مسیر مشابه تحلیل شده و مسیر پیش بینی می شود.
۳٫ مدل مکعب داده مسیر بر اساس مسیر ناقص خودرو
در این بخش، شکل جدیدی از ذخیره سازی داده های مسیری را معرفی خواهیم کرد. داده های مسیر دارای ویژگی های مکانی-زمانی هستند، بنابراین ساختار ذخیره سازی معمولاً است Tra<T,P>، که در آن T زمان تنظیم شده در نقطه مسیر و P مجموعه مختصات طول و عرض جغرافیایی است. ساختار ذخیره سازی مدل خط سیر سنتی عمدتاً بر اساس متغیرهای موقعیت است P(lat,lon)و سری های زمانی T(t0,t1,t2,t3,…,tn)، بنابراین یک بخش مسیر پیوسته برای ذخیره سازی تشکیل می شود. جهت مسیر را می توان با سری های زمانی قضاوت کرد. ویژگی داده های مکانی – زمانی این است که اطلاعات موقعیت را می توان از عوامل زمانی به دست آورد یا متغیرهای زمانی را می توان از اطلاعات موقعیت به دست آورد. این نوع ساختار داده که می تواند به طور متقابل برون یابی شود، ویژگی منحصر به فرد داده های مکانی-زمانی را تشکیل می دهد.
۳٫۱٫ ساختار داده مسیر با ضریب سرعت نقطه ای
اطلاعات سرعت نقاط مسیر به ویژه به عنوان عاملی از داده های مسیر وسیله نقلیه مهم است. اطلاعات سرعت نقطه مسیر وسیله نقلیه می تواند شکل خودرو را در لحظه منعکس کند. به عنوان مثال، هرچه مقدار سرعت بیشتر باشد، وضعیت ترافیک شبکه جاده بهتر است و هر چه مقدار سرعت کمتر باشد، وضعیت ترافیک شبکه جاده بدتر است. با این حال، دانش بالقوه دیگری از اطلاعات سرعت وجود دارد که می توان آن را استخراج کرد که موقعیت وسیله نقلیه است. بنابراین، این بخش رابطه بین اطلاعات سرعت نقطه مسیر وسیله نقلیه و اطلاعات موقعیت و اطلاعات وضعیت شبکه جاده را شرح می دهد.
از شکل ۲ الف، میتوانیم چندین نقطه مسیر پیوسته را ببینیم، و اطلاعات موقعیت نقاط مسیر را میتوان با توجه به اطلاعات زمانی، که دانش سنتی استخراج مسیر خودرو است، استنتاج کرد. در شکل ۲ ب که رابطه بین اطلاعات سرعت نقطه مسیر و زمان را می توان به دست آورد. با توجه به فراوانی اکتساب مسیر، نقاط مسیر حالت های نقطه ای گسسته ای را ارائه می دهند. ما می توانیم شتاب را پیدا کنیم a(pi,pj)بین هر دو نقطه در مسیر در هر زمان از معادله ( ۱ ).
جایی که viسرعت اولیه است، vjسرعت پایانی است، tj−tiنشان دهنده زمان استفاده است. وضعیت رانندگی وسیله نقلیه را می توان با تغییر شتاب بین هر نقطه مسیر به دست آورد. فرمول فاصله بین دو نقطه در شبکه راهها معادله ( ۲ ) است.
که در آن x و y به ترتیب مختصات نقشه دو نقطه مسیر مجاور در شبکه راه را نشان می دهند، d(pi,pj)است Manhattanفاصله بین نقاط مسیر مجاور (فاصله منهتن به این دلیل استفاده می شود که از ظاهر شدن دو نقطه مجاور در یک مسیر پیوسته در دو جاده جلوگیری می کند). رابطه بین اطلاعات موقعیت و اطلاعات سرعت نقاط مسیر با رابطه ( ۳ ) بیان می شود.
جایی که (v′+vi)اختلاف سرعت بین نقاط مسیر است، (t′−ti)اختلاف زمانی بین نقاط مسیر است. روابط ریاضی بین position، velocityو timeنقاط مسیر توسط معادلات (۱) – (۳) ایجاد می شود.
۳٫۲٫ مدل مکعب داده مسیر
این بخش مدل مکعب داده مسیر را برای ذخیره موقعیت، سرعت و زمان نقاط مسیر توصیف می کند. هدف، نمایش بهتر ویژگی های زمانی و مکانی داده های مسیر است. نمایش سرعت نقاط مسیر برای بازیابی دقیق تر موقعیت نقاط از دست رفته در مسیر است که در بخش ۴ معرفی خواهد شد .
شکل ۳ مدل مکعب داده مسیر را نشان می دهد که در آن posموقعیت نقطه مسیر است، velنشان دهنده سرعت نقطه مسیر است، timeمهر زمان نقطه مسیر است، هر ردیف نشان دهنده یک بخش مسیر پیوسته در واحد زمان است، هر قطعه مکعب نشان دهنده اطلاعات نقاط مسیر است. در این مقاله، مدل مکعب داده مسیر بر اساس مقاله [ ۳۹ ] بر حسب واحد دقیقه ایجاد می شود.
مکعب از سه قسمت تشکیل شده است: موقعیت مسیر، سرعت و زمان. ما دو مکعب واحد زمان را از سطح طراحی می کنیم، بنابراین هر لایه به ترتیب تاریخ و ساعت را نشان می دهد. اطلاعات نقاط مسیر را در هر ستون از مکعب داده ها قرار دهید. ما مشخص می کنیم که نقاط مسیر در هر جاده در یک قطعه ذخیره شوند (نقاط موقعیت جاده را می توان با دو تقاطع مجاور مجموعه داده شبکه جاده تعیین کرد)، بنابراین، هر ستون نشان دهنده همان جاده است. هر ردیف به صورت یک مسیر پیوسته در واحد زمان نمایش داده می شود.
از شکل ۳ مشاهده می شود که هر واحد زمانی به شکل بلوک های داده ذخیره می شود و مهر زمانی ذخیره شده در هر لایه، داده در همان واحد زمان است. هدف از این طراحی به دلیل ویژگی های داده های مسیر است. مقدار داده های مسیر در هر لحظه کوچک و پراکنده است. بنابراین، اگر از مهر زمانی به عنوان واحد زمانی برای ذخیره سازی استفاده شود، فضای زیادی هدر خواهد رفت.
شایان ذکر است که از آنجایی که اطلاعات طول و عرض جغرافیایی در شبکه جاده واقعی در هنگام ذخیره لزوماً مجاور یکدیگر نیستند (یعنی رابطه توپولوژی وجود ندارد)، یک اشاره گر به ماژول کوچک در هر لایه به نام اضافه می شود. Topology−Pointer (TP)، اشاره گر به شناسه موقعیت بعدی در مجاورت آن اشاره می کند. مجموعه ای را مشخص می کنیم Point= { loc,vel,time,TP} برای نشان دادن نقاط در یک مسیر. بنابراین، TDC دارای ویژگی های نمایش برداری است.
همچنین شایان ذکر است که انتخاب واحد زمان نیاز به تأیید آزمایشی دارد، اما نمیتوانیم تضمین کنیم که وسایل نقلیه در همان جاده در واحد زمان حرکت نکنند. بنابراین، این مقاله پردازش هایی را انجام داده است. بر اساس تحقیقات قبلی ما، تغییر وضعیت شبکه جاده ای در ۱۰ تا ۱۵ دقیقه مناسب است، اما ذخیره داده ها در چنین فاصله زمانی هنوز پراکنده است. بنابراین، واحد زمان مکعب داده را به ۳۰-۶۰ دقیقه افزایش می دهیم، بنابراین اگر همان نقطه مسیر در همان جاده در واحد زمان ظاهر شد، میانگین سرعت مکعب را طبق رابطه ( ۴ ) محاسبه کرده و ذخیره کنید.
جایی که v e l (vمن،vj)میانگین سرعت شبکه جاده ای است که بین رئوس بیان می شود vمنو vj. v eل۱سرعت نقطه مسیر در یک زمان معین است. سرعت های نقطه مسیر در تمام واحدهای زمانی و در همان جاده جمع و میانگین می شوند. به این ترتیب تمام داده های مسیر در مکعب داده ذخیره می شوند.
۴٫ روش ردیابی سلسله مراتبی بر اساس مکعب داده های مسیر
در این بخش، یک الگوریتم ردیابی سلسله مراتبی (HTB) بر اساس داده های مسیر مکانی-زمانی معرفی می شود. این روش شامل یک روش احتمال بیزی است که برای بازیابی نقاط از دست رفته یا بخش های مسیر از دست رفته در مسیر استفاده می شود. هدف از طبقه بندی داده های مسیر بر اساس سلسله مراتب زمانی، کشف ویژگی های مکانی-زمانی پنهان در مسیر است.
شکل ۴ نمودار مسیر یک وسیله نقلیه را در چهار روز نشان می دهد که از آن می توان دریافت که یک مسیر یا مسیرهای متفاوت در چهار روز اتفاق افتاده است. هدف از الگوریتم HTB تمرکز بر مسیرهای مشابهی است که در یک دوره زمانی در تاریخ های مختلف ظاهر می شوند و این مسیرها توسط مدل TDC طبقه بندی و ذخیره می شوند. در دادههای مسیر، اطلاعات زمانی معمولاً از بین نمیروند یا گم نمیشوند و آنچه تجهیزات معمولاً ثبت میکنند، اطلاعات زمانی است که دادهها تولید میشوند (به ویژه دادههای مسیری که تحت شرایط فرکانس ثابت جمعآوری میشوند). حتی در مورد فرکانس نابرابر باز هم بازه زمانی مشخصی وجود دارد. بنابراین، مهم ترین بازیابی اطلاعات، اطلاعات موقعیت و اطلاعات سرعت نقاط مسیر است.
۴٫۱٫ بازیابی موقعیت مسیر بر اساس مدل TDC
در مجموعه داده های مسیر واقعی، اغلب نقاط مسیری با موقعیت های مسیر نادرست وجود دارد که اغلب توسط سیگنال های تجهیزات ناپایدار یا وسایل نقلیه در فضای مسدود شده توسط سیگنال ها ایجاد می شوند. بنابراین، از دست رفتن یا افست اطلاعات موقعیت مسیر در این مقاله را می توان با TDC و الگوریتم موقعیت ردیابی سلسله مراتبی (HTB-p) تکمیل کرد. فرآیند محاسبه HTB-p به شرح زیر خواهد بود.
تعریف ۱٫
با توجه به یک مجموعه داده از دست رفته M، با توجه به ویژگی های داده مسیر، یک قطعه مسیر پیوسته P وجود دارد <pi,pm,pj>، جایی که pmنقطه مسیر گم شده است، سپس اطلاعات زمانی نقطه می تواند محدوده زمانی داده های از دست رفته را از زمان piو زمان از pj.
تعریف ۱ محدوده زمانی داده های از دست رفته را نشان می دهد. به طور مشابه، منطقه موقعیت مسیر گم شده را می توان با توجه به بخش های اطلاعات موقعیت جلو و عقب داده های مسیر گم شده تعیین کرد.
تعریف ۲٫
با توجه به یک مجموعه داده از دست رفته M، یک قطعه مسیر پیوسته P وجود دارد <pi,pm,pj>، جایی که pmنقطه مسیر گم شده است، سپس اطلاعات موقعیت نقطه می تواند ناحیه موقعیت داده های از دست رفته را از موقعیت piو موقعیت از pj.
تعریف ۲ ناحیه موقعیت داده های از دست رفته را نشان می دهد. با توجه به تعریف ۱، تعریف ۲ و TDC، اطلاعات داده های مسیر همه داده های از دست رفته در یک دوره زمانی مشابه در تاریخ را می توان به دست آورد. اطلاعات مربوط به داده های از دست رفته به صورت سلسله مراتبی از TDC استخراج می شود. شکل ۵ نمونه هایی از اطلاعات موقعیت از دست رفته و جابجایی موقعیت نقاط مسیر را نشان می دهد.
هسته الگوریتم HTB-p فرآیند محاسبه اطلاعات در بازه زمانی استخراج شده توسط TDC است. الگوریتم HTB-p به دو مرحله تقسیم می شود. ۱٫ با عدم وجود داده های نقطه تنظیم مسیر پیمایش، مطابقت با داده های موجود در TDC و جستجو، در طول زمان مربوطه برای به دست آوردن لایه TDC مربوطه، و نقاط مسیر تلفات مربوط به اطلاعات داده در TDC را برمی گرداند، با این اطلاعات به عنوان کلمه کلیدی را به عنوان یک شرط جستجو، سپس تمام اطلاعات داده مسیر در سطوح مختلف را در یک زمان بازگردانید. ۲٫ تمام اطلاعات واجد شرایط به دست آمده از TDC برای احتمال مشروط محاسبه می شود. با توجه به شرایط زمان و سرعت، آمار احتمال تمامی شناسه های جاده ممکن انجام می شود. در نهایت، شناسه جاده با احتمال بالاتر به داده های مسیر گمشده برگردانده می شود. و موقعیت به عنوان اطلاعات موقعیت نقطه مسیر از دست رفته مشخص می شود. الگوریتم ۱ یک روش HTB-p را با اطلاعات موقعیت نقطه مسیر گمشده معرفی می کند.
الگوریتم ۱ HTB-p |
- ۱:
-
ورودی: TDC، M
- ۲:
-
خروجی: Tra<P,V,T>
- ۳:
-
مقداردهی اولیه تیr a < P، V، تی>، MapSet p r o b
- ۴:
-
برای M انجام دهید
- ۵:
-
جستجو کردن مپ( من من هستم ) _از TDC
- ۶:
-
مقایسه کنید تیمن e _در هر سطح
- ۷:
-
اگر تیمن e _ = = م( من من هستم ) _ سپس
- ۸:
-
محاسبه پr (پمن| v , t )= پr (پمن) پr ( v |پمن) پr ( t |پمن، v )پr ( v ) Pr ( t | v )
- ۹:
-
p r o b.قرار دادن( پمن، پr (پمن| v , t ))
- ۱۰:
-
پایان اگر
- ۱۱:
-
گرفتن پمنبا حداکثر پrارزش از p r o b
- ۱۲:
-
تیr a < P، V، تی>= پمن
- ۱۳:
-
TDC = تیr a < P، V، تی>
- ۱۴:
-
پایان برای
- ۱۵:
-
TDC را برگردانید
|
جایی که M مجموعه مسیر را ندارد، تیr a < P، V، تی>شامل موقعیت، سرعت و زمان با یک نقطه در مسیر است. مپ( من من هستم ) _نقطه خط سیر زمان از دست دادن است، پrنشان دهنده احتمال موقعیت نامزد است. p r o bاحتمال هر موقعیت نامزد را ذخیره می کند. م( من من هستم ) _زمان از دست دادن نقطه مسیر است، پمنشناسه نقطه اشتباه است. خطوط ۴-۶ به دست آوردن شناسه نقاط مسیر از مجموعه مسیر گمشده M به نوبه خود و به دست آوردن تمام اطلاعات مسیر در همان لایه زمانی در TDC با مقایسه با زمان در TDC را توصیف می کند. خطوط ۷ تا ۹ بلوک داده مسیر را با همان زمان در مجموعه M از TDC پیدا می کنند، تمام اطلاعات مسیر را در بلوک برمی گردانند، همه نقاط نامزد در TDC را از طریق احتمال شرطی بیزی محاسبه می کنند. خط ۱۱-۱۵ در نهایت مقدار را با حداکثر احتمال برمی گرداند و اطلاعات نقاط گم شده را به TDC تکمیل می کند. از آنجایی که تنها یک حلقه در الگوریتم وجود دارد، پیچیدگی زمانی الگوریتم است O(n)، که در آن n تعداد نقاط مسیر گم شده است.
۴٫۲٫ بازیابی سرعت مسیر بر اساس مدل TDC
یک روش HTB-v در این بخش معرفی خواهد شد که هدف آن تکمیل نقاط مسیر بدون اطلاعات سرعت اندازه گیری شده در مسیر است. از آنجایی که اطلاعات شناخته شده شامل اطلاعات موقعیت و اطلاعات زمان است، اطلاعات سرعت گمشده با توجه به ویژگی های ساختاری TDC محاسبه می شود. ابتدا، نقاط موقعیت با اطلاعات سرعت گمشده را می توان با توجه به اطلاعات موقعیت به دست آورد. در این فرآیند، موقعیت مجموعه نقطه مسیر سرعت گمشده را می توان از طریق ماژول طبقه بندی موقعیت TDC طبقه بندی کرد تا موقعیت دقیق را غربال کند. ثانیا، زمان مجموعه نقطه مسیر گمشده با لایه زمانی تقسیم بر مکعب داده مطابقت داده می شود و مجموعه نقطه مسیر گمشده به لایه زمانی مربوطه تقسیم می شود.
تعریف ۳٫
با توجه به یک مجموعه داده سرعت گمشده M، با توجه به ویژگی های داده مسیر، یک قطعه مسیر پیوسته P وجود دارد. <pi,pm,pj>، جایی که pmنقطه مسیر سرعت گم شده است، سپس اطلاعات موقعیت نقطه را می توان از آن به دست آورد pi (position)و pj (position)، اطلاعات زمانی نقطه می تواند محدوده زمانی داده های از دست رفته را به دست آورد pi (time)و pj (time).
تعریف ۳ اطلاعات موقعیت و محدوده زمانی داده های از دست رفته را می دهد. در زیر باید اطلاعات سرعت گمشده در نقطه مسیر را محاسبه کنیم. هنوز باید احتمال بلوک مسیر را در TDC با کمک فرمول احتمال شرطی بیزی محاسبه کنیم و در نهایت مقدار احتمال حداکثر سرعت را برگردانیم و نتیجه به نقطه گمشده خاص برگردانده شود. الگوریتم ۲ فرآیند بازیابی نقاط مسیر با اطلاعات سرعت از دست رفته توسط الگوریتم HTB را شرح می دهد.
الگوریتم ۲ HTB-v |
- ۱:
-
ورودی: TDC، M
- ۲:
-
خروجی: تیr a < P، V، تی>
- ۳:
-
مقداردهی اولیه تیr a < P، V، تی>، MapSet p r o b
- ۴:
-
برای M انجام دهید
- ۵:
-
جستجو کردن مv( پیش از اینها ) _ _ _ _ _از TDC
- ۶:
-
مقایسه کنید p o s i t i o nدر TDC
- ۷:
-
اگر p o s i t i o n = = مv( پیش از اینها ) _ _ _ _ _ سپس
- ۸:
-
جستجو کردن مv( من من هستم ) _از TDC
- ۹:
-
مقایسه کنید تیمن e _در هر سطح
- ۱۰:
-
اگر تیمن e _ = = م( من من هستم ) _ سپس
- ۱۱:
-
محاسبه پr (پمن| p , t )= پr (پمن) پr ( v |پمن) پr ( t |پمن، ص )پr ( v ) Pr(t|v)
- ۱۲:
-
prob.قرار دادن( pi، Pr(pi|p,t))
- ۱۳:
-
پایان اگر
- ۱۴:
-
پایان اگر
- ۱۵:
-
گرفتن piبا حداکثر Prارزش از prob
- ۱۶:
-
Tra<P,V,T>= pi
- ۱۷:
-
TDC = Tra<P,V,T>
- ۱۸:
-
پایان برای
- ۱۹:
-
TDC را برگردانید
|
جایی که M مجموعه مسیر را ندارد، Tra<P,V,T>شامل موقعیت، سرعت و زمان با یک نقطه در مسیر است. Mv(position)موقعیت نقطه مسیر تلفات است، Mv(time)نقطه خط سیر زمان از دست دادن است، Prنشان دهنده احتمال موقعیت نامزد است. probاحتمال هر موقعیت نامزد را ذخیره می کند. M(time)زمان از دست دادن نقطه مسیر است، piشناسه نقطه اشتباه است. خطوط ۴-۹ به دست آوردن شناسه نقاط مسیر از مجموعه مسیر گمشده M به نوبه خود، و به دست آوردن تمام اطلاعات مسیر در همان لایه زمانی در TDC با مقایسه با زمان در TDC را توصیف می کند. خطوط ۱۰-۱۲ بلوک داده مسیر را با همان زمان در مجموعه M از TDC پیدا می کند، تمام اطلاعات مسیر را در بلوک برمی گرداند، همه نقاط نامزد در TDC را از طریق احتمال شرطی بیزی محاسبه می کند. خط ۱۵-۱۹ در نهایت مقدار را با حداکثر احتمال برمیگرداند و اطلاعات نقاط گمشده را به TDC تکمیل میکند. از آنجایی که تنها یک حلقه در الگوریتم وجود دارد، پیچیدگی زمانی الگوریتم است O(n)، که در آن n تعداد نقاط مسیر گم شده است.
۴٫۳٫ موقعیت مسیر و بازیابی سرعت بر اساس مدل TDC
روش احیای حالت شبکه جاده ای در صورت وجود اطلاعات موقعیت ممتد و مفقود و سرعت مسیر در قطعه مسیر در این بخش معرفی می شود. Kalman-Filtering (KF) [ ۴۰ ] و انواع آن می توانند به طور موثر مسیر گمشده را بازیابی کنند، اما استراتژی بازیابی برای از دست دادن مسیر چند وسیله نقلیه در بخش جاده و جریان ترافیک شبکه جاده هنوز نیاز به بهبود دارد. بنابراین، این بخش یک الگوریتم عقبگرد سلسله مراتبی HTB-KF را معرفی می کند که KF و TDC را ترکیب می کند.
ابتدا اطلاعات موقعیت از دست رفته در داده های مسیر برای اولین بار توسط الگوریتم KF بازیابی می شود. اطلاعات بازیابی شده به مجموعه مسیر گمشده و TDC بازگردانده می شود. اطلاعات موقعیت در TDC و مسیر از دست رفته با هم مقایسه می شوند و اطلاعات موقعیت و اطلاعات زمان یک بار با هم تطبیق داده می شوند. در مرحله دوم، اطلاعات سرعت نقاط مسیر از دست رفته اختصاص داده می شود. نتیجه تطبیق اطلاعات موقعیت بازیابی شده توسط KF با TDC به نقطه مسیر گمشده برگردانده می شود، مقدار اطلاعات سرعت تطبیق از بلوک TDC پیدا می شود، برهم نهی احتمال از طریق اطلاعات موقعیت جلو-عقب و اطلاعات زمانی انجام می شود، و در نهایت اطلاعات سرعت با بیشترین احتمال به نقطه مسیر گمشده برگردانده می شود. معادلات (۵) و (۶) فرآیند داده های مسیر KF را توصیف می کنند. شایان ذکر است که این مقاله اطلاعات موقعیت و اطلاعات سرعت نقاط مسیر از دست رفته را به صورت جداگانه با هم مقایسه میکند، بنابراین تنها یک عنصر واحد از بازیابی اطلاعات هنگام استفاده از روش KF در نظر گرفته میشود. مکانیزم ردیابی در این بخش برای تأیید اطلاعات گم شده اضافه می شود.
که در آن A ماتریس انتقال حالت و w نویز فرآیند است. ماتریس انتقال حالت A با توجه به فرمول سینماتیک تعیین می شود، B ماتریسی است که بخشی از تأثیرگذاری بر تغییر حالت سیستم را بر عهده می گیرد.
که در آن z مقدار پیش بینی شده را نشان می دهد و H ماتریس تبدیل از مقدار اندازه گیری شده فعلی به مقدار اندازه گیری پیش بینی شده است. e نشان دهنده نویز است. در این مقاله، موقعیت مسیر گمشده برای اولین بار با کمک KF [ ۴۰ ] پیشبینی میشود. اطلاعات سرعت داده های مسیر گمشده توسط اطلاعات موقعیت بازیابی شده و TDC اختصاص داده می شود. اطلاعات موقعیت پس از تخصیص مجدداً توسط TDC بررسی می شود. الگوریتم ۳ فرآیند محاسبه HTB-KF را شرح می دهد.
جایی که M مجموعه مسیر را ندارد، Tra<P,V,T>شامل موقعیت، سرعت و زمان با یک نقطه در مسیر است. خطوط ۴-۶ قضاوت اولیه موقعیت مسیر گمشده را با استفاده از KF توصیف می کنند. خطوط ۷-۱۷ اطلاعات موقعیت به دست آمده از طریق KF را محاسبه می کنند تا اطلاعات سرعت نقاط مسیر گم شده را استنتاج کنند. خط ۱۸ برای بررسی مجدد موقعیت به دست آمده توسط KF است تا خطا را بیشتر کاهش دهد. خطوط ۱۹-۲۳ نتیجه نهایی را برمی گرداند و در TDC ذخیره می کند. پیچیدگی زمانی الگوریتم HTB-KF است O(n2)، که در آن n تعداد نقاط مسیر گم شده است.
الگوریتم ۳ HTB-KF |
- ۱:
-
ورودی: TDC، M
- ۲:
-
خروجی: Tra<P,V,T>
- ۳:
-
مقداردهی اولیه Tra<P,V,T>، MapSet prob
- ۴:
-
برای M انجام دهید
- ۵:
-
محاسبه M توسط KF
- ۶:
-
پایان برای
- ۷:
-
برای M با اطلاعات موقعیت انجام دهید
- ۸:
-
جستجو کردن مv( پیش از این نیست ) _ _ _ _از TDC
- ۹:
-
مقایسه کنید p o s i t i o nدر TDC
- ۱۰:
-
اگر p o i s t i o n = = م( پیش از اینها ) _ _ _ _ _ سپس
- ۱۱:
-
جستجو کردن Mv( من من هستم ) _از TDC
- ۱۲:
-
مقایسه کنید تیمن e _در هر سطح
- ۱۳:
-
اگر تیمن e _ = = م( من من هستم ) _ سپس
- ۱۴:
-
محاسبه پr (پمن| p , t )= پr (پمن) پr ( v |پمن) پr ( t |پمن، ص )پr(v)Pr(t|v)
- ۱۵:
-
prob.قرار دادن( pi، Pr(pi|p,t))
- ۱۶:
-
پایان اگر
- ۱۷:
-
پایان اگر
- ۱۸:
-
HTB-p
- ۱۹:
-
گرفتن piبا حداکثر Prارزش از prob
- ۲۰:
-
Tra<P,V,T>= pi
- ۲۱:
-
TDC = Tra<P,V,T>
- ۲۲:
-
پایان برای
- ۲۳:
-
TDC را برگردانید
|
۵٫ تجربی
در این قسمت فرآیند آزمایشی و تنظیمات پارامتر به طور مفصل معرفی می شود. در این مقاله سه نوع آزمایش انجام خواهد شد. اولین آزمایش اعتبار سنجی الگوریتم پیشنهادی HTB-p برای بازیابی نقاط اطلاعات موقعیت از دست رفته در مجموعه داده مسیر است. آزمایش دوم تأیید الگوریتم HTB-v برای بازیابی نقاط اطلاعاتی سرعت گمشده در مجموعه داده مسیر است. آزمایش سوم تأیید الگوریتم HTB-KF برای بازیابی نقاط اطلاعاتی مکان و سرعت از دست رفته در مجموعه داده مسیر است.
۵٫۱٫ تنظیم آزمایش
تمامی آزمایش ها در جاوا، پایتون و تمامی الگوریتم ها بر روی حافظه ۱۶G، سیستم عامل ویندوز ۱۰ ۶۴ بیتی و پردازنده مرکزی Intel i5 @3.30 GHz اجرا می شوند. دادههای شبکه جادهای در این مقاله از دادههای نقشه پکن، دادههای نقشه شانگهای و دادههای نقشه نیویورک OpenStreetMap ( https://www.openstreetmap.org ) (دسترسی در ۵ دسامبر ۲۰۲۰) آمده است. دادههای مسیر وسیله نقلیه سه ماهه است. و اندازه ۵۷ G با تاکسی پکن در ۲۰۱۲٫۴ و ۲۰۱۳٫۶–۲۰۱۳٫۷ (کمیسیون ارتباطات شهرداری پکن)، یک روز و اندازه ۳۳۲ مگابایت با تاکسی شانگهای در سال ۲۰۰۷ ( https://cse.hkust.edu.hk/scrg/ ، در ۱ فوریه ۲۰۲۲ قابل دسترسی است)، و اندازه آن ۱۱۹ گیگابایت است، رکورد سفر تاکسی زرد نیویورک در سال ۲۰۱۹ ( https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page، قابل دسترسی در ۱ فوریه ۲۰۲۲). جدول ۲ اطلاعات مجموعه داده را نشان می دهد. تجسم با استفاده از Mapbox API ( https://studio.mapbox.com/ ، در ۱ فوریه ۲۰۲۲ قابل دسترسی است). از آنجایی که مجموعه داده خودرو در نیویورک فقط دارای اطلاعات موقعیت است و اطلاعات سرعت ندارد، تأیید بر اساس بازیابی اطلاعات سرعت استفاده نخواهد شد. با این حال، میانگین سرعت وسیله نقلیه هنوز هم پس از پردازش اطلاعات موقعیت و اطلاعات زمان قابل دستیابی است، بنابراین می توان از آن برای تأیید بخش ۵٫۴ استفاده کرد.
۵٫۲٫ تأیید موقعیت مسیر گمشده بر اساس روش ردیابی سلسله مراتبی TDC
در ابتدا، جزئیات مسیر سه جاده اصلی در سه مجموعه داده نمونه استخراج شده است، همانطور که در شکل ۶ نشان داده شده است.
نمادهای خاکستری در شکل ۶ نقاط اطلاعاتی موقعیت مسیر هستندΨ{ pn} از مجموعه مسیر اصلی حذف می شود، اما این نقاط اطلاعات زمان و اطلاعات سرعت را حفظ می کنند. در ادامه نتایج بازیابی موقعیت الگوریتم پیشنهادی HTB-p و الگوریتم تکمیل موقعیت مسیر موجود را مقایسه میکند. شکل ۷ مقایسه تجربی HTB-p بر اساس TDC با سایر الگوریتم های بازیابی موقعیت مسیر را نشان می دهد.
از شکل ۷ تأثیر الگوریتم KF، الگوریتم درون یابی و الگوریتم HTB-p را بر بازیابی مسیر نشان داده و آن را با مسیر واقعی GPS مقایسه کنید. شکل ۷ a بازسازی یک مسیر پیوسته بر اساس تاکسی ها در پکن را نشان می دهد. با توجه به چهار موقعیت مسیر گمشده انتخاب شده در شکل ۶ الف، می توان دید که اطلاعات موقعیت بازیابی شده توسط HTB-p بهتر از الگوریتم KF و Interpolation است. شکل ۷ ب بازسازی یک مسیر پیوسته بر اساس تاکسی در شانگهای را نشان می دهد. با توجه به موقعیت پنج مسیر گمشده انتخاب شده در شکل ۶ ب. شکل ۷c بازسازی یک مسیر پیوسته بر اساس تاکسی ها در نیویورک را نشان می دهد. با توجه به شش موقعیت مسیر گمشده انتخاب شده در شکل ۶ ج.
تأثیر الگوریتم درون یابی بهتر است زیرا نقاطی با اطلاعات موقعیت مفقود پیوسته وجود دارد، بنابراین چندین عملیات درونیابی مورد نیاز است که تأثیر ضعیفی دارد. اگرچه تاثیر KF بهتر از الگوریتم درون یابی است، اما هسته محاسباتی آن پیش بینی نتایج این زمان بر اساس نتایج محاسبه قبلی است. بنابراین، زمانی که نقاط مسیر پیوسته از دست رفته وجود داشته باشد، اثر بازیابی الگوریتم KF به نتایج محاسبه قبلی بستگی دارد. HTB-p نه تنها نقاط موقعیت مسیر گمشده را با توجه به اطلاعات نقطه جلو و عقب مسیر محاسبه می کند، بلکه نیاز به ارزیابی و مقایسه احتمال موقعیت تاریخی از طریق شرایط داده های تاریخی دارد. بنابراین، HTB-p نتایج محاسباتی خوبی دارد.جدول ۳ میانگین خطای اقلیدسی (MEE) را بین موقعیت به دست آمده توسط سه الگوریتم و موقعیت واقعی نشان می دهد، بعد [m] است، میانگین تمام فواصل خطا در جدول ۳ نشان داده شده است .
معادله ( ۷ ) فرآیند محاسبه MEE را توصیف می کند. جایی که n تعداد نقاط مسیر از دست رفته است، ( xf، yf) نقطه موقعیت تخمینی است، ( xm، xm) موقعیت نقاط مسیر گمشده واقعی است.
جدول ۳ می تواند میانگین خطای بین مقدار پیش بینی شده و مقدار واقعی سه الگوریتم را مشاهده کند. فاصله خطای الگوریتم درون یابی بسیار بیشتر از الگوریتم KF و الگوریتم HTB-p است. رابطه خاصی بین اثر الگوریتم تکمیل مسیر و خود مجموعه داده وجود دارد. از جدول ۳ قابل مشاهده استکه خطای مسیر تاکسی ها بر اساس خطای متوسط مربوط به مسافت و زمان با توجه به اطلاعات مسیر قبل و بعد از نقاط مسیر گم شده است. هنگامی که اطلاعات مسیر، نقاط مسیر گمشده جلو-عقب شناخته شده باشد، اثر مسیر درونیابی بهتر است. هنگامی که موقعیت های اطلاعات مسیر عقب عقب نقاط مسیر از دست رفته است، اثر بازیابی HTB-p بهتر است.
۵٫۳٫ راستیآزمایی سرعت مسیر گمشده براساس روش سلسله مراتبی TDC Trace-Back
این بخش به انتخاب سه مسیر متوالی از سه نمونه مسیر برای تأیید ادامه خواهد داد. مطابق شکل ۶ ، اطلاعات سرعت نقاط از دست رفته در شکل حذف شده و اطلاعات موقعیت به مجموعه داده اضافه می شود. آزمایش های این بخش اطلاعات سرعت را تأیید می کند Ψ{ vn} بازیابی و میزان خطای نمونه سه الگوریتم برای نقاط مسیر از دست رفته در سه مجموعه داده.
شکل ۸ بازیابی اطلاعات موقعیت را توسط الگوریتم KF، الگوریتم درون یابی و الگوریتم HTB-v نشان می دهد و شکل ۸ a بازیابی سرعت را بر اساس مسیر خودروی پکن نشان می دهد. از شکل می توان دریافت که وقتی اطلاعات سرعت نقاط مسیر پیوسته از دست رفته باشد، اثر KF بهتر از Interpolation است و اثر HTB-v مشابه اثر KF است. به طور مشابه، از شکل ۸ ب مشاهده می شود که تأثیر الگوریتم درون یابی بدتر است، در حالی که تأثیر الگوریتم KF و HTB-v بهتر است. جدول ۴ میزان خطا را نشان می دهد ϕالگوریتم برای بازیابی سرعت مسیر.
معادله ( ۸ ) فرآیند محاسبه را شرح می دهد ϕ. جایی که velfمقدار سرعت تخمینی است، velaمقدار سرعت داده های مسیر واقعی است.
از جدول ۴ می توان دریافت که سه الگوریتم سرعت دو مجموعه داده را بازیابی می کنند. نرخ خطای الگوریتم درون یابی به طور قابل توجهی بیشتر از الگوریتم های دیگر است (درصد داده های واکنش در جدول به میزان خطای بین مقدار سرعت واقعی و مقدار سرعت بازیابی شده اشاره دارد)، به عنوان مثال، در t12، میزان خطای درون یابی ۲۰٫۶ درصد است، در حالی که میزان خطای KF و HTB-v به ترتیب ۹٫۲ درصد و ۸٫۹ درصد است. دلیل آن این است که وقتی نقاط مسیر مفقود پیوسته وجود داشته باشد، الگوریتم درون یابی نمی تواند به طور موثر داده ها را پردازش کند (الگوریتم درون یابی به اطلاعات مسیر قبل و بعد از نقاط مسیر از دست رفته بستگی دارد). بازیابی الگوریتم های KF و HTB-v بهتر است، اما ϕارزش هنوز بزرگ است دلیل اصلی به دلیل مجموعه نمونه آموزشی است. بخش ۵٫۴ تمام مجموعه دادههای مسیر را آموزش و مدلسازی میکند.
۵٫۴٫ تأیید موقعیت و سرعت مسیر گمشده بر اساس روش ردیابی سلسله مراتبی TDC
این بخش با آموزش تمام نمونههای مجموعه مسیر، دادههای بخشهای مسیر چندگانه در مسیر را تکمیل و تأیید میکند. در این بخش ۷۰ درصد از سه مجموعه داده به عنوان مجموعه آموزشی و ۳۰ درصد به عنوان مجموعه تست بازیابی برای تأیید استفاده می شود. گروهی از آزمایشها اطلاعات موقعیت و سرعت ۵%، ۱۰%، ۱۵%، ۲۰%، ۲۵% و ۳۰% از مجموعه دادهها را از طریق مجموعه دادههای آموزش و ردیابی حذف میکنند، دادههای زمانی را حفظ میکنند و آن را بازیابی میکنند. . گروه دیگر تغییر تعداد مجموعه های نمونه آموزشی برای بازیابی اطلاعات مسیر در مجموعه داده های باقی مانده است.
در مرحله اول، HTB-KF با الگوریتم تکمیل مسیر موجود مقایسه می شود. از شکل ۹ نشان می دهد که بازیابی سه مجموعه داده مسیر توسط الگوریتم های مختلف، و اثر بازیابی الگوریتم از طریق MEE.
این آزمایش الگوریتمهای KF، LSTM، MDCGCN، Interpolation و HTB-KF را برای بازیابی مسیر با آموزش دادههای سه مجموعه مسیر مقایسه میکند. از شکل ۹ الف مشاهده می شود که با افزایش تعداد مجموعه داده های مسیر ترمیم شده، الگوریتم های HTB-KF و MDCGCN اثرات بازیابی بهتری دارند. دلیل اینکه الگوریتم درون یابی پرس و جو مسیر را بازیابی می کند این است که برای درون یابی نیاز به تکیه بر اطلاعات نقاط مسیر مجاور نقاط مسیر از دست رفته دارد. با این حال، هنگامی که بخش هایی از مسیر گمشده در مجموعه داده وجود دارد، اثر بازیابی ضعیف است. برای بازیابی تعداد زیادی از بخش های مسیر مناسب نیست. اثر بازیابی الگوریتمهای KF و LSTM کمی بدتر از MDCGCN و HTB-KF است.
شکل ۹ ب بازیابی مجموعه داده مسیر خودرو شانگهای را توسط الگوریتم نشان می دهد. همان HTB-KF و MDCGCN اثرات بهتری دارند. شکل ۹ ج بازیابی مجموعه داده های مسیر خودروی نیویورک را توسط الگوریتم نشان می دهد. با این حال، تأثیر شکل ۹ ب بدتر از شکل ۹ ج است. دلیل آن این است که مجموعه داده های مسیر در شانگهای تنها یک روز فرصت دارند و حجم نمونه آن کوچکتر از پکن و نیویورک است. بنابراین، اثر بازسازی کلی بدتر از دو مجموعه نمونه دیگر است. با این حال، حتی اگر اندازه نمونه مجموعه داده کافی نباشد، الگوریتم HTB-KF هنوز اثر بازیابی رضایت بخشی دارد.
شکل ۱۰ نشان دهنده بازیابی اطلاعات سرعت در بخش های مسیر دو مجموعه داده توسط الگوریتم های مختلف است. شکل ۱۰ a اطلاعات را در مسیر مجموعه در پکن بازیابی می کند. از شکل می توان دریافت که با افزایش تعداد نمونه های ترمیم شده، میزان خطای الگوریتم های KF، LSTM، MDCGCN و HTB-KF نیز افزایش می یابد، اما شیب رشد کمتر از الگوریتم های دیگر است.
شکل ۱۰ ب اطلاعات سرعت را در مجموعه مسیر شانگهای بازیابی می کند. از شکل مشاهده می شود که با افزایش تعداد نمونه ها، میزان خطای الگوریتم نیز در حال افزایش است. در مقایسه با شکل ۱۰ a، میزان خطا ϕبیشتر است زیرا تعداد نمونه های آموزشی در شانگهای کم است، بنابراین میزان خطای اطلاعات بازیابی شده توسط الگوریتم بیشتر است. میزان خطا ϕالگوریتم درون یابی بالاتر از الگوریتم های دیگر است. دلیل اصلی این است که ماهیت نظریه ترمیم آن مستلزم نبود اطلاعات مسیر، اطلاعات مسیر جلو و عقب است.
آزمایش زیر تأیید میکند که الگوریتم HTB-KF سرعت خودرو را بر اساس مجموعه دادههای مسیر پکن و مجموعه دادههای مسیر شانگهای بازیابی میکند. این آزمایش یک تقاطع را در هر مجموعه مسیر تعیین می کند تا قابل مشاهده ترین تقاطع باشد. شکل ۱۱ نشان میدهد که مجموعه تاریخهای BJ تقاطع جاده دونگسانهوان و جاده گوانگکو (۱۱۶°۴۶’۸۰٫۴۸″ شرقی، ۳۹°۸۹’۹۱٫۳۳″ شمالی) و مجموعههای تاریخ SH تقاطع جاده Jiujiang و جاده میانی هنان (۱۲۱°۴۹) را انتخاب میکند. ′۱۷٫۶۹ اینچ شرقی، ۳۱°۲۴′۲۴٫۱۷ اینچ شمالی).
شکل ۱۱ a مقایسه منحنی داده های واقعی و مقدار تکمیل را در ساعت ۹:۰۰ تا ۱۱:۰۰ در یک روز خاص در مجموعه داده های پکن با نرخ از دست دادن داده ۲۰٪ (فاصله زمانی ۵ دقیقه) نشان می دهد، شکل ۱۱b مقایسه منحنی داده های واقعی و مقدار تکمیل را در ساعت ۱۸:۰۰ تا ۲۰:۰۰ در یک روز خاص در مجموعه داده های شانگهای با نرخ از دست دادن داده ۲۰٪ (فاصله زمانی ۵ دقیقه) نشان می دهد. از نمودار می توان دریافت که نتیجه تکمیل روش HTB-KF بسیار نزدیک به وضعیت واقعی زمین است و می تواند تغییرات دینامیکی سرعت ترافیک در شرایط پیچیده ساعات شلوغی اولیه و اواخر را به تصویر بکشد. نتایج تکمیل در مقایسه با حقیقت زمین بسیار آرام در نوسان است. به طور خلاصه، روشهای HTB-KF ارائهشده در این مقاله میتوانند وضعیت ترافیک را به طور منطقی درونیابی کنند.
۶٫ نتیجه گیری
در نتیجه، یک مکعب داده مسیر جدید (TDC) برای مدلسازی، تحلیل و پردازش دادههای مسیر در این مقاله معرفی میشود. سه الگوریتم ردیابی سلسله مراتبی بر اساس مدل TDC برای بازیابی اطلاعات از دست رفته در مسیر و برای بازیابی جریان ترافیک مسیر گمشده طراحی شدهاند. زیرا اطلاعات موقعیت و اطلاعات سرعت در اطلاعات مسیر می تواند به طور موثر منیفولد ترافیک را در آن زمان توضیح دهد. در نهایت، در بخش تجربی، ترمیم مسیر الگوریتمهای HTB-p، HTB-v و HTB-KF تأیید میشود. در مرحله اول، روش HTB-p بازیابی موقعیت از دست رفته نقاط مسیر منفرد در بخش مسیر را با روش HTB-p تأیید میکند (مجموعههای نمونه آموزشی کمی در این آزمایش وجود دارد و همه مجموعههای مسیر پردازش نمیشوند)، و MEE و میزان خطای آن کمتر از روشهای دیگر است. در مرحله دوم، روش HTB-v برای بازیابی اطلاعات سرعت نقاط مسیر منفرد در بخش مسیر تأیید میشود. از طریق مقایسه تجربی می توان نتیجه گرفت که روش HTB-v اثر ترمیم بهتری دارد. ثالثاً، بازیابی اطلاعات بخش مسیر گمشده توسط الگوریتم HTB-KF تأیید میشود. همچنین تأیید شده است که الگوریتم HTB-KF می تواند شرایط رانندگی را بازیابی کند، و مشخص شده است که الگوریتم HTB-KF هنوز توانایی بازیابی خوبی دارد که مجموعه آموزشی نمونه محدود است. می توان نتیجه گرفت که روش HTB-v اثر ترمیم بهتری دارد. ثالثاً، بازیابی اطلاعات بخش مسیر گمشده توسط الگوریتم HTB-KF تأیید میشود. همچنین تأیید شده است که الگوریتم HTB-KF می تواند شرایط رانندگی را بازیابی کند، و مشخص شده است که الگوریتم HTB-KF هنوز توانایی بازیابی خوبی دارد که مجموعه آموزشی نمونه محدود است. می توان نتیجه گرفت که روش HTB-v اثر ترمیم بهتری دارد. ثالثاً، بازیابی اطلاعات بخش مسیر گمشده توسط الگوریتم HTB-KF تأیید میشود. همچنین تأیید شده است که الگوریتم HTB-KF می تواند شرایط رانندگی را بازیابی کند، و مشخص شده است که الگوریتم HTB-KF هنوز توانایی بازیابی خوبی دارد که مجموعه آموزشی نمونه محدود است.
در کار آینده که زاویه انحراف اطلاعات مسیر را به عنوان عاملی از اطلاعات مسیر اضافه خواهیم کرد و سعی می کنیم قسمت گمشده مجموعه داده های مسیر را با حجم نمونه آموزشی کمتر تکمیل کنیم.