تطبیق نقشه برای مسیرهای GPS با فرکانس بالا نمونه برداری شهری

خلاصه

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

کلید واژه ها:

تطبیق نقشه ; مسیر GPS ; فرکانس نمونه برداری بالا ؛ شبکه جاده ای

1. معرفی

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

در چند دهه گذشته، بسیاری از روش های تطبیق نقشه پیشنهاد شده است. این روش ها را می توان به روش های هندسی، توپولوژیکی و پیشرفته [ 1 ] و یا می توان آنها را به روش های محلی و جهانی تقسیم کرد [ 2 ]. برای سناریوهای کاربردی مختلف، روش‌های تطبیق نقشه مسیر بلادرنگ، روش‌های تطبیق نقشه مسیر آفلاین، روش‌های تطبیق نقشه مسیر GPS، سایر روش‌های تطبیق نقشه مسیر مکان، روش‌های تطبیق نقشه مسیر با نمونه‌برداری کم، تطبیق نقشه مسیر با نمونه‌برداری بالا، تطبیق نقشه مسیر با نمونه‌برداری بالا، وجود دارد. روش‌های تطبیق نقشه مسیر، و روش‌های تطبیق نقشه مسیر داخلی [ 3 ، 4 ]. با این حال، مطالعات کمی در مورد مسیرهای نمونه برداری با فرکانس بالا در شبکه های جاده های شهری وجود دارد.

در حال حاضر، داده‌های GPS در فواصل زمانی کوتاه، مانند 1 یا 5 ثانیه، در مناطق شهری به دلیل پیشرفت در فناوری GPS و توسعه فناوری پردازش داده‌های بزرگ به دست می‌آیند [ 5 ]. این فاصله کوتاه منجر به داده های عظیم مسیر نمونه برداری با فرکانس بالا برای وسایل نقلیه (مانند اتوبوس و تاکسی) و عابران پیاده شده است. از آنجایی که معمولاً اجسام متحرک در تقاطع‌های جاده‌ای با سرعت کم متوقف می‌شوند یا با سرعت کم حرکت می‌کنند، در تقاطع‌های جاده‌ها نقاط مسیر متعددی وجود دارد. علاوه بر این، به دلیل پیچیدگی تطبیق نقاط مسیر در تقاطع جاده، احتمال عدم تطابق بیشتر خواهد بود. یک مثال تطبیق نادرست در شکل 1 نشان داده شده است .

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

برای پرداختن به مشکل نگاشت مسیر تقاطع، این مطالعه یک روش تطبیق مسیر تقسیم‌بندی شده را پیشنهاد می‌کند. اولاً، مسیر در موقعیت تقاطع جاده قطع می شود و به مجموعه ای از بخش های مسیر تقاطع (شامل نقاط مسیر تقاطع) و بخش های مسیر غیر تقاطع (به استثنای نقاط مسیر تقاطع) تقسیم می شود. ثانیا، قوانین تطبیق اختصاصی و روش‌های پردازش برای بخش تقاطع پیشنهاد شده‌اند، و تطبیق بخش مسیر غیرتقاطع با استفاده از روش تطبیق کلاسیک «نگاه به آینده» [ 8 ] انجام می‌شود. در نهایت، تطبیق نقشه برای کل مسیر موفقیت آمیز است.

2. آثار مرتبط

در حال حاضر، دو روش اصلی تطبیق نقشه وجود دارد: تطبیق محلی و تطبیق سراسری.

2.1. روش های تطبیق محلی

الگوریتم‌های تطبیق محلی یک استراتژی حریصانه را دنبال می‌کنند که به‌طور متوالی راه‌حل را از قسمتی که قبلاً همسان شده است گسترش می‌دهد [ 9 ]. کلید چنین روش‌های تطبیق محلی، یافتن یک نقطه یا بخش بهینه محلی در یک شبکه جاده‌ای است. متداول ترین روش تطبیق محلی، روش مبتنی بر هندسه است [ 10 ، 11 ]، که در آن تطبیق مسیر بر اساس محدودیت هایی مانند فاصله و جهت انجام می شود. دارای یک اثر تطبیق مطلوب برای مسیرهای نمونه برداری با فرکانس بالا (یک نقطه مسیر یا بیشتر را می توان در یک جاده تطبیق داد)، اما در اطمینان از دقت تطبیق بالا برای مسیرهای نمونه با فرکانس پایین مشکل دارد. برای افزایش دقت تطبیق، برخی از روش‌های جدید توسعه یافته‌اند، مانند تطبیق نقشه توپولوژی [5 ، 8 ]، تطبیق نقشه مبتنی بر ویژگی مکانی-زمانی [ 2 ، 12 ]، و تطبیق نقشه مبتنی بر وزن [ 13 ، 14 ، 15 ، 16 ، 17 ]. در مطالعه ای توسط Brakatsoulas و همکاران. [ 8 ]، یک روش تطبیق افزایشی با استفاده از استراتژی تطبیق “نگاه به آینده” پیشنهاد شده است. با این روش، یک رابطه توپولوژیکی بین جاده منطبق با نقطه بعدی و آن با نقطه فعلی ایجاد می شود تا جاده مطابق با نقطه فعلی را اصلاح کند. وانگ و همکاران [ 5] یک الگوریتم اصلاحی مبتنی بر فیلتر کالمن را برای بهبود دقت تطبیق الگوریتم توپولوژیکی سنتی در بخش‌های جاده‌ای پیچیده، مانند تقاطع‌ها و جاده‌های موازی، پیشنهاد می‌کند. آنها همچنین از یک الگوریتم تطبیق نقشه موازی برای بهبود کارایی پردازش تطبیق نقشه استفاده می کنند. لو و همکاران، یک الگوریتم تطبیق نقشه مکانی-زمانی برای مسیرهای GPS با نرخ نمونه‌برداری پایین پیشنهاد کرده‌اند [ 2 ]. نویسندگان تجزیه و تحلیل زمانی را با داده های سرعت و زمان سفر مدل می کنند تا دقت آن را بهبود بخشند. Hsueh و Chen رویکرد مشابهی را پیشنهاد کرده‌اند – تطبیق STD – که فاکتور جهت زمان واقعی را به تطبیق ST اضافه می‌کند [ 12 ].

در سال های اخیر، روش های تطبیق نقشه های مبتنی بر وزن بیشتری پیشنهاد شده است. هاشمی و کریمی [ 14 ] یک الگوریتم تطبیق نقشه مبتنی بر وزن پویا را پیشنهاد می کنند. عوامل آن از فاصله بین نقطه GPS و بخش های جاده، تفاوت بین عنوان نقطه GPS و جهت بخش های جاده و تفاوت بین جهت نقاط متوالی GPS و جهت بخش های جاده تشکیل شده است. وزن دینامیک آن از دقت موقعیت، سرعت و مسافت طی شده از نقاط GPS قبلی محاسبه می شود. شرات و همکاران [ 15] همچنین چهار عامل تأثیرگذار تطبیق نقطه GPS، مجاورت، سینماتیک، پیش‌بینی قصد چرخش، اتصال را ایجاد کرده و سپس یک الگوریتم تطبیق نقشه مبتنی بر وزن دو بعدی پویا را با ترکیب ضرایب وزن پویا و عرض جاده برای فعال کردن خط خط توسعه می‌دهد. شناسایی سطح هو و همکاران [ 16 ] یک روش تطبیق ترکیب اطلاعات (IF) را بر اساس متا اطلاعات مربوط به شی متحرک پیشنهاد می کند که شامل چهار زمینه است: مکان، سرعت، جهت و مهر زمانی. این روش در رسیدگی به موارد مبهم تاثیر بهتری دارد. ژائو و همکاران [ 17] از سرعت، اختلاف بلبرینگ، فاصله عمود بر و همبستگی فضایی به عنوان ضریب تأثیر تطبیق نقطه GPS استفاده کنید. آنها به صورت پویا وزن هر عامل را بر اساس تئوری Dempster-Shafer تخمین می زنند.

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

2.2. روش های تطبیق جهانی

به طور نسبی، روش‌های تطبیق جهانی با هدف شناسایی شبکه جاده‌ای مشابه با مسیر بر اساس تمام نقاط مسیر کل بخش مسیر، و سپس تلاش برای یافتن مسیری نزدیک به مسیر نمونه‌برداری در بین تمام مسیرهای موجود در شبکه جاده‌ها هستند. 9 ]. شباهت‌های میان پاره‌های خط چندگانه با استفاده از فاصله Frechet [ 8 ، 18 ، 19 ، 20 ]، با استفاده از دنباله مشترک طولانی (LCS) [ 6 ]، یا با استفاده از تابع احتمال [ 21 ، 22 ، 23 ] در روش‌های تطبیق کلی اندازه‌گیری می‌شوند. یین و ولفسون [ 19] یک نقشه شبکه با استفاده از فاصله Frechet در بین مسیرهای نسبی به عنوان وزن یک بخش جاده ترسیم کنید. علاوه بر این، الگوریتم کوتاه ترین مسیر Dijkstra برای محاسبه کوتاه ترین مسیر برای به دست آوردن جاده منطبق نهایی استفاده شده است. برکاتسولاس و همکاران [ 8 ] مفهوم فاصله متوسط فریشت را برای شناسایی مسیر کلی با استفاده از نمودار فضای آزاد مسیرهای نسبی بخش‌های مختلف جاده پیشنهاد می‌کند. زو و همکاران [ 6 ] مسیرهای منطبق با نامزد را برای کل مسیر با استفاده از یک مسیر جداگانه در بخش‌ها ایجاد کرد و سپس بهترین مسیر را بر اساس LCS بدست آورد. میلارد بال و همکاران [ 21] از یک تابع شبه درستنمایی سه بخشی که از احتمال هندسی، احتمال توپولوژیکی و احتمال زمانی تشکیل شده است، استفاده کنید تا بهترین تطابق را از مجموعه کاندید دریافت کنید. کناپن و همکاران [ 22 ] ابتدا ردیابی GPS را به ترتیب زمانی تقسیم کنید و سپس حداکثر احتمال مسیرهای جزئی را بر اساس یک نمودار جهت دار غیر چرخه ای پیدا کنید. علاوه بر این، Rappos و همکاران. [ 23 ] یک روش تطبیق نقشه جهت‌داده نیرو پیشنهاد کرده‌اند که از یک مدل نیروی جذاب با توجه به فاصله و زاویه بین نقطه GPS و لبه جاده و طول لبه جاده استفاده می‌کند.

تحقیقات دیگر بر اساس مدل پنهان مارکوف (HMM) برای تطبیق نقشه است. Newson و Krumm [ 24 ] یک نقشه HMM را برای تطبیق داده های مکان با نویز و پراکندگی پیشنهاد می کنند. از زمان تحقیقات آنها، بسیاری از مطالعات در مورد این روش بهبود یافته است. کولر و همکاران [ 25 ] تطبیق نقشه سریع (FMM) بر اساس HMM را پیشنهاد می کند که الگوریتم Viterbi را با یک Dijkstra دو طرفه جایگزین می کند و از یک ارزیابی تنبل برای کاهش تعداد محاسبات مسیر پرهزینه استفاده می کند. یانگ و همکاران [ 26 ] همچنین تطبیق سریع نقشه را ارائه می‌کند، الگوریتمی که مدل مارکوف پنهان را با پیش محاسبه ادغام می‌کند. چی و همکاران [ 7] یک مدل حوزه تصمیم اتصال ارائه می دهد که برای بهبود الگوریتم تطبیق نقشه بر اساس HMM استفاده می شود. این به طور موثر میزان خطای تطبیق اتصالات را کاهش می دهد. علاوه بر این، در تطبیق زمان واقعی، HMM نیز بیشتر استفاده می شود. یک الگوریتم تطبیق نقشه افزایشی جدید بر اساس HMM برای تطبیق زمان واقعی پیشنهاد شده است [ 27 ، 28 ]. برای داده های مکان نادرست و پراکنده، Jagadeesh و Srikanthan [ 29 ] یک راه حل جدید تطبیق نقشه ارائه می کنند که رویکرد پرکاربرد مبتنی بر HMM را با مفهوم انتخاب مسیر رانندگان ترکیب می کند. الگیزاوی و همکاران [ 30 ] HMM معمولی مورد استفاده در تطبیق نقشه را برای تطبیق داده‌های بسیار پراکنده تلفن همراه با یک احتمال تطبیقی گسترش می‌دهد.

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

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

3. تطبیق بخش مسیر تقاطع

3.1. طبقه بندی نقطه مسیر تقاطع

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

تعریف 1.

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

تعریف 2.

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

تعریف 3.

(بخش جاده). این یک لبه شبکه جاده ای است که توسط تقاطع ها و نقاط مختصاتی که این لبه را تشکیل می دهند، کشیده شده است.

تعریف 4.

(نقاط مسیر تقاطع). این یک نقطه مسیر است که در مجاورت تقاطع تنظیم شده است. با توجه به خطاها در اکتساب داده های مسیر، نقاط مسیر تقاطع در این مطالعه همه نقاط مسیری هستند که در ناحیه دایره ای متمرکز بر نقطه تقاطع در شعاع خطای اکتساب قرار می گیرند. این با معادله (1) نشان داده می شود:

پ = {پ من (ایکس من ، y من) | (ایکس من - ایکس o) 2 + (y من - y o) 2 ——————\sqrt \leq ε}

(1)

که در آن P مجموعه ای از نقاط مسیر تقاطع است. (x _i , y _i ) و (x _o , y _o ) به ترتیب مختصات نقطه مسیر p _i و گره تقاطع هستند. و ε شعاع خطا است.

تعریف 5.

(بخش مسیر تقاطع). این یک بخش مسیر است که از نقاط مسیر تقاطع به ترتیب تشکیل شده است.

تعریف 6.

(نقطه ورودی). این اولین نقطه از نقاط مسیر تقاطع است.

تعریف 7.

(نقطه خروجی). این آخرین نقطه از نقاط مسیر تقاطع است.

تعریف 8.

(بخش راه ورودی). این یک بخش جاده منطبق قبل از ورود مسیر به تقاطع است و باید جاده مطابق با نقطه ورودی باشد.

تعریف 9.

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

شکل 2 نمونه هایی از مفاهیم فوق را نشان می دهد.

بعد، تطبیق نقطه مسیر تقاطع مورد نیاز است. سه مکان وجود دارد که نقاط مسیر تقاطع باید با آنها مطابقت داشته باشد: بخش جاده ورودی، بخش جاده خروجی و تقاطع. بنابراین، روابط بین نقاط مسیر تقاطع و تقاطع و بخش های جاده مربوط به تقاطع را می توان تا زمانی که بخش های ورودی و خروجی مسیر در تقاطع تعیین شده است طبقه بندی کرد. آنها به چهار نوع زیر طبقه بندی می شوند:

نوع 1 (نقطه داخلی). نقطه مسیر تقاطع در زاویه بین بخش جاده ورودی و بخش جاده خروجی قرار دارد، مانند نقطه p _k در شکل 2 .
نوع 2 (نقطه مربوط به جاده ورودی). نقطه مسیر تقاطع در زاویه بین بخش جاده ورودی و هر بخش جاده دیگری قرار دارد، به جز بخش خروجی، مانند نقاط p _s و p _i در شکل 2 .
نوع 3 (نقطه مربوط به جاده خروجی). نقطه مسیر تقاطع در زاویه بین بخش جاده خروجی و هر بخش جاده دیگری قرار دارد، به جز بخش ورودی، مانند نقطه p _e در شکل 2 .
نوع 4 (نقطه بیرونی). نقطه مسیر تقاطع در زاویه بین دو بخش جاده دیگر قرار دارد، به جز بخش های ورودی و خروجی، مانند نقطه p _j در شکل 2 .

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

3.2. قوانین تطبیق

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

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

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

همانطور که در شکل 3 نشان داده شده است ، از آنجایی که نقطه p ₁ در زاویه بین بخش جاده ورودی r ₁ و هر بخش جاده دیگر r ₂ قرار دارد، p ₁ یک نقطه مرتبط با جاده ورودی است و مستقیماً با r ₁ مطابقت دارد . از آنجایی که نقطه p ₂ در زاویه بین دو بخش دیگر جاده r ₂ و r ₃ قرار دارد، p ₂ یک نقطه بیرونی است و با تقاطع o مطابقت دارد . از نقطه p ₃در زاویه بین بخش جاده ورودی r ₁ و بخش جاده خروجی r ₄ قرار دارد، نقطه p ₃ یک نقطه داخلی است و با محاسبه کمترین فاصله از p ₃ تا r ₁ و آن از p _{3 با}r ₄ مطابقت دارد. به r ₄ . از آنجایی که نقطه p ₄ در زاویه بین بخش خروجی جاده r ₄ و هر بخش جاده دیگر r ₃ قرار دارد، p ₄یک نقطه مربوط به خارج از جاده است و مستقیماً با r ₄ مطابقت دارد .

3.3. تنظیم ناهنجاری

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

شکل 4 یک مثال ناهنجاری از تطبیق نقطه مسیر تقاطع را نشان می دهد.

از قوانین II-IV می توان دریافت که نقاط مسیری که با بخش های ورودی و خروجی مطابقت دارند را می توان با تقاطع تنظیم کرد. چنین تنظیمی برای مواردی که با تقاطع مطابقت دارند اعمال نمی شود. طبق قانون I، نقاط مسیری که با بخش ورودی مطابقت دارند را می توان بر روی تقاطع و بخش خروجی تنظیم کرد و آنهایی که با بخش خروجی مطابقت دارند را می توان به تقاطع و بخش ورودی تنظیم کرد.

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

قانون V: بخش‌های جاده‌ای که با نقاط مسیر تقاطع مطابقت داده می‌شوند، دقیقاً دنباله «بخش جاده ورودی- تقاطع-بخش جاده خروجی» را دنبال می‌کنند.

قانون V را می توان با روش زیر انجام داد. فرض کنید که بخش جاده ورودی r _s ، بخش جاده خروجی r _e ، تقاطع o است ، و بخش های جاده منطبق عبارتند از { r _i |1 ≤ i ≤ n ، r _i ∈ { r _s ، r _e ، o }}، هر عنصر در مجموعه { r _i } باید از موقعیت 1 تا n − 1 با چهار وضعیت زیر مدیریت شود:

اگر r _i = r _e و r _i +1 = o، آنگاه r _i = o .
اگر r _i = r _e و r _i +1 = r _s ، آنگاه r _i = o، r _i +1 = o .
اگر r _i = o و r _i +1 = r _s ، آنگاه r _i +1 = o .
در هیچ شرایط دیگری تنظیمی انجام نمی شود.

به عنوان مثال، یک قطعه مسیر تقاطع حاوی نه نقطه است که به صورت ( p ₁ , p ₂ , p ₃ , p ₄ , p ₅ , p ₆ , p ₇ , p ₈ , p ₉ ) بیان می شود. فرض کنید که طبق قوانین مسابقه I–IV، دنباله بخش جاده همسان ( r _s , r _s , o , o , r _e , o , r _{s است}, r _e , r _e ). سپس در دنباله دو نابهنجاری ( r _e , o ) و ( o , r _s ) وجود دارد زیرا o باید قبل از r _e باشد و r باید قبل از o باشد _.بنابراین، طبق قانون V، ( r _e , o ) به ( o , o ) و ( o , r _s ) به ( o , o ) تنظیم می شود. بنابراین، کل توالی بخش جاده تنظیم شده به صورت (ر _س ، ر _س ، ای ، ای ، _ای ، ای ، ای ، ر _ای ، ر ای ) .

3.4. الگوریتم تطبیق بخش مسیر تقاطع

تطبیق بخش مسیر تقاطع در الگوریتم 1 نشان داده شده است. این چارچوب الگوریتم تطبیق بخش مسیر تقاطع (InterectTrajMatch) را تشریح می کند. اولاً، الگوریتم فهرست مجموعه‌های فاصله نامزد بین هر نقطه مسیر تقاطع در P و بخش‌های جاده مربوط به تقاطع R را محاسبه می‌کند. ثانیاً، الگوریتم بخش‌های جاده مربوط به تقاطع R را بر اساس مقدار فاصله در dlist مرتب می‌کند و سپس دو بخش جاده را با کمترین فاصله بدست می‌آورد. ثالثاً، الگوریتم بخش‌های جاده منطبق را با استفاده از قوانین I–IV پیدا می‌کند و آن را به مجموعه‌های rmlist بخش جاده‌های منطبق اضافه می‌کند.. در نهایت، پس از به دست آوردن تطبیق بخش‌های جاده از تمام نقاط مسیر، الگوریتم بخش‌های جاده مطابق قانون V را تنظیم می‌کند و در نتیجه RM را برمی‌گرداند.

الگوریتم 1 الگوریتم تطبیق بخش مسیر تقاطع (InterectTrajMatch)

ورودی: نقاط مسیر تقاطع P = { p _i | i = 1, … , n }, بخش جاده ورودی r _s , بخش جاده خروجی r _e , نقطه تقاطع o , بخش جاده مربوط به تقاطع R = { r _i | i = 1، … ، m }

خروجی: توالی بخش جاده منطبق RM = { rm _i | i = 1، … ، n }

1: dlist را به عنوان یک لیست خالی مقداردهی کنید. // dlist لیستی از فواصل
نامزد است . // rmlist فهرستی از بخش‌های جاده منطبق با نامزد است

3: برای i = 1 تا n انجام دهید //Traversing P

4: برای j = 1 تا m انجام دهید //Traversing R

5: d = Distance( p _i , r _j ) ;

6: dlist .add( d );

7: پایان برای

8: R .sort( dlist ); //مرتب سازی

R

بر اساس مقدار فاصله در dlist

9: GetShortestTwoSections( R , ref r ₁ , ref r ₂ ); // دو بخش جاده با کمترین فاصله را دریافت کنید

10: rm = MatchbyRule1234( r ₁ , r ₂ , r _e , r _s , o ); //بخش جاده منطبق را با قانون I، II، III، IV پیدا کنید

11: rmlist .add( rm );

12: پایان برای

13: RM = AdjustbyRule5( rmlist ); //تنظیم بخش جاده مطابق قانون V.

14: بازگشت

R M

;

3.5. تطبیق بخش جاده ورودی و بخش جاده خروجی

تطبیق صحیح بخش ورودی و خروجی جاده بسیار مهم است. این امر بر اجرای صحیح الگوریتم 1 تأثیر می گذارد. همانطور که در تعاریف 8 و 9 تعریف شده است، بخش جاده ورودی قبل از ورود مسیر به تقاطع مطابقت داده می شود که معمولاً با نقطه ورودی مطابقت داده می شود و بخش جاده خروجی پس از حرکت مسیر مطابقت داده می شود. از تقاطع که معمولاً با نقطه خروجی مطابقت دارد. با این حال، از آنجایی که نقطه ورودی به نقطه بعدی خود بسیار نزدیک است، مطابق با روش «نگاه به جلو»، مطابق شکل 1 ، تطبیق جاده نقطه ورودی اغلب اشتباه است.. بنابراین، بخش جاده ورودی به عنوان جاده ای تعریف می شود که با نقطه قبلی نقطه ورودی مطابقت دارد. بدیهی است که این امر مستلزم آن است که جاده تطبیق نقطه ورودی با جاده تطبیق نقطه قبلی خود یکسان باشد. این در نمونه برداری با فرکانس بالا قابل دستیابی است، اما در مورد نمونه برداری با فرکانس متوسط یا فرکانس پایین و برخی موارد استثنایی، فاصله بین نقطه ورودی و نقطه قبلی آن زیاد است، بنابراین جاده تطبیق نقطه ورودی و قبلی آن نقطه همان بخش جاده نیستند، همانطور که در شکل 5 نشان داده شده است.

همانطور که در شکل 5 a نشان داده شده است، نقاط p _s تا p _e در همسایگی ε تقاطع o هستند، بخش جاده منطبق در نقطه قبلی نقطه ورودی p _s-₁r _s’ است و تقاطع مجاور r _{s “} o” است . بنابراین، باید قضاوت کرد که آیا نقطه p _s و نقاط بعدی آن به جای o در همسایگی ε -o’ هستند یا خیر . وقتی p _sدر همسایگی ε -o’ نیست ، نقطه ورودی ps در _شکل 5 a یک نقطه تقاطع نیست. همانطور که در شکل 5 ب نشان داده شده است، نقطه ورودی p _s در شکل 5 a به p _s- 1 _تبدیل شده است ، و نقطه مسیر تقاطع، ps جدید _به p e _است . علاوه بر این، به دلیل رابطه مجاور بین r _s و r _s ، بخش جاده منطبق p _s-₁ همچنان r _{s است.}به جای r _i ، طبق روش «به جلو نگاه کن».

3.6. شعاع خطا ε

شعاع خطا ε شامل خطای موقعیت یابی نقطه مسیر و خطای داده های جاده است. این شعاع خطا با رابطه (2) نشان داده می شود:

ε = ε ل + ε r

(2)

جایی که $ε_{l}$ خطای موقعیت یابی است که با تکنیک موقعیت یابی مشخص می شود. $ε_{r}$ خطای داده‌های جاده است که عمدتاً ناشی از تفاوت بین عرض واقعی جاده و داده‌های خط جاده است و محاسبه آن در رابطه (3) نشان داده شده است [ 7 ]:

ε r = 0.5 \times w s i n α 2

(3)

جایی که $w$ عرض جاده است، $α$ زاویه بین دو جاده متقاطع است. به منظور ساده تر شدن محاسبه، به طور کلی زاویه 90 درجه در نظر گرفته می شود.

شعاع خطا ε بر کارایی و دقت روش تطبیق تقاطع تأثیر می گذارد. به دلیل خطا در داده های موقعیت یابی و شبکه جاده، اگر ε خیلی کوچک باشد، نقطه مسیر داخل تقاطع حذف می شود، که ممکن است منجر به عدم تطابق شود. در غیر این صورت، نقطه مسیر فراتر از تقاطع شامل خواهد شد، که منجر به راندمان تطبیق کمتر و عدم تطابق جدید می شود (یعنی زمانی که جاده ای که این نقطه مسیر مطابقت دارد یکی از جاده های مجاور تقاطع است).

4. روش تطبیق مسیر قطعه بندی شده

برای تطبیق نقشه کل مسیر از یک استراتژی تطبیق مسیر تقسیم شده استفاده می شود. ابتدا، مسیر بر اساس ε به بخش مسیر تقاطع و بخش مسیر غیرتقاطع تقسیم می شود . روش تطبیق بخش مسیر تقاطع پیشنهادی برای بخش مسیر تقاطع و روش “نگاه به جلو” برای بخش مسیر غیر تقاطع اعمال می شود. الگوریتم روش پیشنهادی در الگوریتم 2 نشان داده شده است.

الگوریتم 2 چارچوب الگوریتم تطبیق مسیر تقسیم‌بندی شده را مشخص می‌کند. ابتدا، بخش‌های جاده منطبق از نقطه اول مسیر را با روش کوتاه‌ترین فاصله از همه جاده‌ها پیدا می‌کند و آن را به دنباله بخش جاده منطبق RM اضافه می‌کند. ثانیاً، فاصله بین هر نقطه مسیر و نقطه تقاطع فعلی oc را محاسبه می کند. اگر فاصله کمتر از شعاع ε باشد ، تا زمانی که فاصله نقطه بعدی از ε بیشتر شود ، به فهرست نقاط مسیر تقاطع نامزد اضافه می شود . اگر مجموعه مجموعه خالی نباشد، الگوریتم با هر نقطه در plist مطابقت داردبه یک بخش جاده با استفاده از الگوریتم 1 و آنها را به RM اضافه می کند . در غیر این صورت، نقطه فعلی را با روش “نگاه به جلو” مطابقت می دهد و آن را به RM اضافه می کند . در نهایت، الگوریتم RM را در نتیجه برمی گرداند.

در الگوریتم، نقطه ورودی ( r _s ) و نقطه خروجی ( r _e) با استفاده از روش “نگاه به جلو” مطابقت داده می شوند، بنابراین صحت تطبیق آنها به روش “نگاه به جلو” بستگی دارد. از آنجایی که این روش برای داده‌های با فرکانس بالا مناسب‌تر است، زمانی که فرکانس نمونه‌گیری داده‌ها کم باشد، دقت تطبیق به‌طور قابل‌توجهی تحت‌تاثیر قرار می‌گیرد. بنابراین، الگوریتم برای پردازش داده های مسیر فرکانس بالا و متوسط مناسب است، به این معنی که حداقل یک نقطه مسیر در هر جاده وجود دارد. با این حال، به دلیل خطاهای داده، فرکانس داده های مسیر ثابت نیست. برخی از نقاط مسیر با فاصله زمانی زیاد در داده های فرکانس بالا وجود دارد. برای جلوگیری از این مشکل، یک آستانه بازه زمانی تنظیم شده است. اگر فاصله زمانی بین نقطه مسیر فعلی و نقطه قبلی از آستانه تجاوز نکند، نقطه فعلی با روش “نگاه به جلو” مطابقت داده می شود. اگر بیش از آن باشد،تابع MatchFirstPoint .

الگوریتم 2 الگوریتم تطبیق مسیر بخش بندی شده

ورودی: نقاط مسیر P = { p _i | i = 1, … , n }, نقاط تقاطع O = { o _i | i = 1, … , m }, بخش های جاده R = { r _i | i = 1، … ، k }، شعاع خطا ε

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

1: plist را به عنوان یک لیست خالی مقداردهی کنید. // plist لیستی از مسیر تقاطع نامزد نقطه
2 است : rrlist را به عنوان یک لیست خالی مقداردهی کنید. // rrlist لیستی از بخش
3 جاده مربوط به تقاطع نامزد است : rmlist را به عنوان یک لیست خالی راه اندازی کنید. // rmlist لیستی از بخش جاده منطبق با نامزد است.

4: rf = MatchFirstPoint( p ₁ , R ); //نقطه اول را با روش کوتاه ترین فاصله از همه جاده ها مطابقت دهید.

5: RM .add( rf );

6: r _s = rf ; //r _s به معنای بخش جاده ورودی است

7: برای i = 2 تا n انجام //Traversing

P

از جانب

p_{2}

8: oc = FindCurrentIntersectionPoint( rf , O ); // oc تقاطع نزدیک به نقطه p _{i است}

9: اگر (فاصله( p _i , oc ) ≤ ε )

10: plist .add( p _i );

11: دیگری

12: rrlist = FindRelatedRoadSections ( oc , R ); // rrlist مجموعه‌های بخش جاده‌ای مربوط به oc است

13: if ( plist .count > 0)

14: r _e = MatchbyLookAhead( p _i−₁ , rrlist ); //نقطه خروجی را با روش نگاه به جلو مطابقت دهید
[ 8 ]، r _e بخش جاده خروجی است

15: rmlist = InterectTrajMatch( plist , r _s , r _e , oc , rrlist ); //آگوریتم 1

16: RM .add( rmlist );

17: plist. clear();

18: دیگری

19: r _e = MatchbyLookAhead( p _i ، rrlist );

20: RM .add( r _e );

21: پایان اگر

22: r _s = r _e ; //بخش جاده منطبق فعلی، بخش ورودی بعدی است

23: پایان اگر

24: پایان برای

25: بازگشت RM

5. آزمایش و نتایج

5.1. داده های تجربی و طرح

داده‌های تجربی: این شامل سه داده مسیر تاکسی‌ها با فرکانس‌های نمونه‌گیری متفاوت در طول یک هفته در پکن [ 31 ، 32 ] و شبکه جاده‌ای پکن است، همانطور که در شکل 6 نشان داده شده است.

سه داده مسیر فرکانس مختلف از کل مجموعه داده مسیر تاکسی انتخاب شده اند که شامل مسیرهای GPS 10357 تاکسی در دوره 2 تا 8 فوریه 2008 در پکن است. همانطور که در جدول 1 نشان داده شده است ، مسیرها در سه بازه نمونه برداری مختلف جمع آوری می شوند: 1 ثانیه، 5 ثانیه، و 15 ثانیه. به طور دقیق، فاصله نمونه برداری از داده 1 1 ثانیه است، و 151542 نقطه مسیر در داده 1 وجود دارد. فاصله نمونه برداری از داده 2 5 ثانیه و تعداد نقاط مسیر داده 2 30،156 است. فاصله نمونه برداری از داده 3 15 ثانیه و تعداد نقاط مسیر داده 3 7141 است.

پیاده سازی آزمایش: برای دسترسی و تجسم مسیرها و داده های نقشه، توسعه پلاگین ArcGIS 10 با استفاده از C# بر روی آن انجام می شود. پلت فرم NET.

تجزیه و تحلیل: فرآیند تجزیه و تحلیل از دو بخش تشکیل شده است: ابتدا این روش با استفاده از شعاع خطاهای مختلف از نظر کارایی و دقت تجزیه و تحلیل می شود. دوم، تحلیل مقایسه ای این روش با روش LCS [ 6 ] و روش HMM حوزه تصمیم [ 7 ] از روی کارایی و دقت انجام شده است.

شعاع خطا باید قبل از تجزیه و تحلیل مشخص شود. شعاع خطا شامل خطای موقعیت یابی و خطای داده های جاده است. داده‌های مسیر در آزمایش از داده‌های موقعیت‌یابی GPS غیرنظامی استفاده می‌کنند و خطا در 20 متر است [ 7 ]. بر اساس استانداردهای طراحی جاده شهری چین [ 33 ]، عرض جاده های شهری از 10 متر تا 60 متر متغیر است. از آنجایی که داده های شبکه راه در آزمایش شامل سطوح مختلف داده های جاده است، حداکثر عرض آن 60 متر است. بنابراین، حداکثر مقدار خطای داده جاده است

60 / 2 \times \sqrt{2} \approx 42

m [ 7 ] و حداکثر شعاع خطا 62 متر است. سپس به منظور تحلیل جامع اثرات شعاع خطاهای مختلف بر کارایی و دقت روش، یازده شعاع خطا (10 متر، 20 متر، 30 متر، 40 متر، 50 متر، 60 متر، 70 متر، 80 متر، 90 متر، 100 متر و 110 متر) تعیین شده است.

5.2. مقایسه روشهای تطبیق تقاطع

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

5.3. تحلیل کارایی

کارایی این روش در یازده شعاع خطا مقایسه شده است. نتایج تحلیل کارایی داده های 1-3 در شکل 8 نشان داده شده است. شکل 8 a کل زمان اجرای هر مسیر را نشان می دهد و شکل 8 b میانگین زمان دویدن را در هر 1000 نقطه از مسیر نشان می دهد.

با توجه به نتایج تجربی در شکل 8 موارد زیر مشاهده می شود: (1) با افزایش شعاع، کارایی الگوریتم این روش روند کاهشی را نشان می دهد. با این حال، سرعت فرود پایین است، به خصوص پس از اینکه شعاع خطا از 70 متر فراتر رفت. (2) از میانگین نتیجه زمانی شکل 8 ب، می توان نشان داد که هر چه فرکانس نمونه برداری از داده های مسیر بیشتر باشد، کارایی روش بیشتر است. علاوه بر این، میانگین مدت زمان داده 3 بسیار بزرگتر از داده های 1 و 2 است، به این معنی که زمانی که فاصله نمونه برداری بیشتر از 5 ثانیه باشد، با افزایش فاصله نمونه گیری، کارایی روش به سرعت کاهش می یابد.

به منظور مقایسه روش با روش LCS و روش HMM حوزه تصمیم، شعاع خطا 60 متر و آستانه امتیاز شباهت LCS 0.95 است. نتایج تجزیه و تحلیل در جدول 2 نشان داده شده است.

با توجه به نتایج مقایسه کارایی در جدول 2، موارد زیر مشاهده می شود: (1) در مقایسه با روش LCS و روش HMM حوزه تصمیم گیری، کارایی روش پیشنهادی بالاتر است. (2) هر چه فرکانس نمونه برداری از داده های مسیر بیشتر باشد، کارایی این روش بیشتر است. به عنوان مثال، زمانی که فاصله نمونه برداری 15 ثانیه است، زمان اجرای روش LCS و روش HMM حوزه تصمیم به ترتیب حدود 3 برابر و 4.5 برابر این روش است و زمانی که فاصله نمونه برداری 5 ثانیه باشد، زمان اجرای LCS است. روش و روش HMM حوزه تصمیم به ترتیب به 9 برابر و 11 برابر روش افزایش یافته است. زمانی که فاصله نمونه برداری 1 ثانیه باشد، زمان اجرای روش LCS و روش HMM حوزه تصمیم به ترتیب به 11 برابر و 13 برابر این روش افزایش می یابد.

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

5.4. تجزیه و تحلیل دقت

تجزیه و تحلیل دقت دو استاندارد ارزیابی را اتخاذ می کند: یکی دقت تطبیق تمام نقاط مسیر و دیگری دقت تطبیق نقاط مسیر تقاطع است.

تمام نقاط مسیر منطبق با دقت با معادله (4) نشان داده شده است:

ج یک l l = n a l l _ m n یک l l

(4)

جایی که $c_{a l l}$ تمام نقاط مسیر با دقت مطابقت دارند، $n_{a l l_m}$ تعداد نقاط مسیری است که به درستی مطابقت دارند، و $n_{a l l}$ تعداد کل نقاط مسیر است.

دقت تطبیق نقاط مسیر تقاطع با رابطه (5) نشان داده می شود:

ج من = n من _ م n من

(5)

جایی که $c_{i}$ نقاط مسیر تقاطع مطابق با دقت است، $n_{i_m}$ تعداد نقاط مسیر تقاطع است که به درستی مطابقت داده شده است، و $n_{i}$ تعداد کل نقاط مسیر تقاطع است.

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

شکل 9 مقایسه دقت این روش را در یازده شعاع خطا در داده های 1-3 نشان می دهد.

شکل 9نشان می دهد که: (1) با افزایش شعاع خطا، دقت این روش روند افزایشی را نشان می دهد. با این حال، افزایش سرعت پایدار نیست. هنگامی که شعاع خطا کمتر از 40 متر است، سرعت افزایش یافته سریعتر است. هنگامی که شعاع خطا بین 40 متر و 90 متر است، سرعت افزایش یافته کندتر است. وقتی شعاع خطا بالاتر از 90 متر باشد، دقت دیگر به هیچ وجه افزایش نمی یابد و حتی اندکی کاهش می یابد. بنابراین شعاع خطای مناسب باید بین 60 متر تا 90 متر باشد. (2) روش پیشنهادی به طور قابل‌توجهی تحت‌تاثیر داده‌های مسیر با فرکانس‌های نمونه‌گیری متفاوت است. هنگامی که فرکانس نمونه برداری بالا باشد، دقت تطبیق در بین شعاع خطاهای مختلف متفاوت است. در غیر این صورت، دقت تطبیق کمتر تغییر می کند. این ویژگی به خصوص زمانی که شعاع خطا کمتر از 40 متر باشد قابل توجه است. از این رو، این روش برای داده های مسیر نمونه برداری با فرکانس بالا مناسب تر است و فاصله نمونه برداری از 15 ثانیه تجاوز نمی کند. (3) هنگامی که شعاع خطا همچنان در حال افزایش است (به عنوان مثال، بیش از 90 متر در آزمایش)، دقت تطبیق ممکن است کاهش یابد. دلیل آن این است که نقاط مسیر تقاطع به اشتباه نقاط مسیر جاده‌هایی را که در مجاورت آستانه خطای بیش از حد از حداقل طول جاده مجاور با تقاطع تجاوز نمی‌کنند، درج کرده‌اند که منجر به عدم تطابق جدید می‌شود.

نتایج مقایسه دقت این روش با روش LCS و روش HMM حوزه تصمیم در جدول 3 نشان داده شده است.

با توجه به نتایج مقایسه دقت در جدول 3، می توان دریافت که: (1) این روش در دقت تطبیق بالاتر از دو روش دیگر است. به طور خاص، این روش کمی بالاتر از دو روش دیگر در دقت تطبیق تمام نقاط مسیر است. این روش کمی بالاتر از روش HMM حوزه تصمیم است، اما در دقت تطبیق نقاط تقاطع بسیار بالاتر از روش LCS است. (2) فرکانس نمونه برداری از داده های مسیر اثرات متفاوتی بر روش های مختلف دارد. با کاهش فرکانس نمونه برداری، دقت روش پیشنهادی و روش HMM حوزه تصمیم نیز کاهش می یابد، در حالی که روش LCS اندکی افزایش می یابد. نتایج نشان می‌دهد که این روش و روش HMM حوزه تصمیم برای داده‌های فرکانس بالا مناسب‌تر هستند، در حالی که روش LCS برای داده‌های فرکانس پایین مناسب‌تر است. علاوه بر این، در مقایسه با روش HMM حوزه تصمیم، این روش تفاوت قابل توجهی در دقت تطبیق بین سه داده تجربی دارد. به عنوان مثال، اختلاف دقت بین داده های 1 و 3 روش HMM حوزه تصمیم 0.007 است، اما این روش به 0.014 می رسد. بنابراین، روش پیشنهادی نسبت به فرکانس نمونه برداری از داده های مسیر حساس تر است.

6. نتیجه گیری

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

اول از همه، این روش برای داده های مسیر نمونه برداری با فرکانس بالا مناسب تر است. از این آزمایش می توان دریافت که هر چه فراوانی نمونه گیری داده ها بیشتر باشد، دقت روش بالاتر است. هنگامی که فرکانس به تدریج کاهش می یابد، دقت روش به تدریج به روش LCS و روش HMM حوزه تصمیم نزدیک می شود. دلیل آن این است که وقتی فرکانس نمونه‌گیری داده‌های مسیر کم است، ممکن است نقاط کمتری در تقاطع وجود داشته باشد یا وجود نداشته باشد، بنابراین روش تطبیق نقطه مسیر تقاطع در این تحقیق بی‌فایده خواهد بود. دوم، از آنجایی که هسته اصلی روش تطبیق نقاط مسیر تقاطع است، سناریوی کاربردی روش باید در یک شبکه جاده ای با تقاطع های متعدد جاده باشد. از این رو، این روش برای پردازش مسیر حرکت در منطقه با جاده های متراکم مناسب تر است. سوم، در این مقاله، شعاع خطا ε به تفصیل از طریق ترکیب اشتقاق نظری و تحلیل تجربی تحلیل می‌شود. با حداکثر شعاع خطا (62 متر) به عنوان مقدار مرکزی، 11 مقدار شعاع خطا برای تجزیه و تحلیل تجربی انتخاب شده است. نتایج تجربی نشان می دهد که مقادیر شعاع خطای مناسب از 50 متر تا 90 متر متغیر است. با این حال، هنوز در شعاع خطا کمبود دارد نتایج تجربی نشان می دهد که مقادیر شعاع خطای مناسب از 50 متر تا 90 متر متغیر است. با این حال، هنوز در شعاع خطا کمبود دارد نتایج تجربی نشان می دهد که مقادیر شعاع خطای مناسب از 50 متر تا 90 متر متغیر است. با این حال، هنوز در شعاع خطا کمبود داردε ، که یک محدوده دینامیکی از مقادیر باقی می ماند زیرا ارتباط نزدیکی با دقت داده های مسیر، دقت داده های شبکه جاده ای، و چگالی داده شبکه جاده ای دارد. بنابراین، ε باید تا حد امکان بزرگ باشد، اما کمتر از حداقل طول مسیر مطابقت داده شود. علاوه بر این، برای این روش مقابله با داده های مسیر در جایی که انحراف موقعیت قابل توجهی وجود دارد دشوار است. بنابراین، قبل از استفاده از این روش برای تطبیق نقشه، داده های مسیر باید از قبل پردازش شوند تا نقاط غیرعادی حذف شوند.

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

منابع

قدوس، م. Ochieng، WY; Noland، RB الگوریتم‌های تطبیق نقشه فعلی برای کاربردهای حمل و نقل: جدیدترین و جهت‌های تحقیقاتی آینده. ترانسپ Res. قسمت C Emerg. تکنولوژی 2007 ، 15 ، 312-328. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
لو، ی. ژانگ، سی. ژنگ، ی. Xie، X. وانگ، دبلیو. Huang, Y. تطبیق نقشه برای مسیرهای GPS با نرخ نمونه برداری پایین. در مجموعه مقالات هفدهمین سمپوزیوم بین المللی ACM Sigspatial در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، سیاتل، WA، ایالات متحده آمریکا، 4 تا 6 نوامبر 2009. [ Google Scholar ]
بطائنه، س. باهیلو، ع. دیز، ال. اونیوا، ای. باطینه، اول. تطبیق نقشه آفلاین تصادفی مبتنی بر میدان برای محیط های داخلی. Sensors 2016 , 16 , 1302. [ Google Scholar ] [ CrossRef ] [ PubMed ][ نسخه سبز ]
هاشمی، م. کریمی، HA مروری انتقادی از الگوریتم های تطبیق نقشه بلادرنگ: مسائل جاری و جهت گیری های آینده. محاسبه کنید. محیط زیست سیستم شهری 2014 ، 48 ، 153-165. [ Google Scholar ] [ CrossRef ]
وانگ، اچ. لی، جی. هو، ز. نیش، آر. می، دبلیو. Huang, J. تحقیق در مورد الگوریتم تطبیق نقشه بلادرنگ موازی برای داده های عظیم GPS. خوشه. محاسبه کنید. 2017 ، 20 ، 1123-1134. [ Google Scholar ] [ CrossRef ]
زو، ال. هولدن، جی آر. Gonder، JD Trajectory Segmentation Map-Matching Approach برای داده های GPS در مقیاس بزرگ و با وضوح بالا. ترانسپ Res. ضبط 2017 ، 2645 ، 67-75. [ Google Scholar ] [ CrossRef ]
چی، اچ. دی، ایکس. Li, J. الگوریتم تطبیق نقشه بر اساس حوزه تصمیم گیری اتصال و مدل پنهان مارکوف. PLoS ONE 2019 , 14 , e0216476. [ Google Scholar ] [ CrossRef ] [ PubMed ]
برکاتسولاس، اس. Pfoser، D.; سالاس، آر. Wenk, C. در مورد داده های ردیابی وسیله نقلیه مطابق با نقشه. در مجموعه مقالات سی و یکمین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، تروندهایم، نروژ، 30 اوت تا 2 سپتامبر 2005. صص 853-864. [ Google Scholar ]
یوان، جی. ژنگ، ی. ژانگ، سی. Xie، X. Sun، GZ الگوریتم تطبیق نقشه مبتنی بر رای گیری تعاملی. در مجموعه مقالات یازدهمین کنفرانس بین المللی مدیریت داده های تلفن همراه، کاناس سیتی، MO، ایالات متحده آمریکا، 23 تا 26 مه 2010. [ Google Scholar ]
Greenfeld، JS تطبیق مشاهدات GPS با مکان‌ها در نقشه دیجیتال. در مجموعه مقالات هشتاد و یکمین نشست سالانه هیئت تحقیقات حمل و نقل، واشنگتن، دی سی، ایالات متحده آمریکا، 13 تا 17 ژانویه 2002. صص 164-173. [ Google Scholar ]
سفید، CE; برنشتاین، دی. Kornhauser، AL برخی از الگوریتم های تطبیق نقشه برای دستیاران ناوبری شخصی. ترانسپ Res. قسمت C Emerg. تکنولوژی 2000 ، 8 ، 91-108. [ Google Scholar ] [ CrossRef ]
Hsueh، YL; تطبیق نقشه Chen، HC برای مسیرهای GPS با نرخ نمونه‌برداری پایین با کاوش جهت‌های حرکت در زمان واقعی. Inf. علمی 2018 ، 433 ، 55-69. [ Google Scholar ] [ CrossRef ]
قدوس، م. Ochieng، WY; ژائو، ال. Noland, RB یک الگوریتم تطبیق نقشه کلی برای برنامه های کاربردی مخابراتی حمل و نقل. راه حل GPS. 2003 ، 7 ، 157-167. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
هاشمی، م. کریمی، HA یک الگوریتم تطبیق نقشه مبتنی بر وزن برای ناوبری وسایل نقلیه در شبکه های پیچیده شهری. جی. اینتل. ترانسپ سیستم 2016 ، 20 ، 573-590. [ Google Scholar ] [ CrossRef ]
Sharath، MN; ولاگا، NR; Quddus, MA یک الگوریتم تطبیق نقشه مبتنی بر وزن دو بعدی پویا (D2D). ترانسپ Res. قسمت C Emerg. تکنولوژی 2019 ، 98 ، 409-432. [ Google Scholar ] [ CrossRef ]
در آغوش گرفتن.؛ شائو، جی. لیو، اف. وانگ، ی. Shen, HT If-Matching: به سمت تطبیق دقیق نقشه با ترکیب اطلاعات. IEEE Trans. بدانید. مهندسی داده 2016 ، 29 ، 114-127. [ Google Scholar ] [ CrossRef ]
ژائو، ایکس. چنگ، ایکس. ژو، جی. خو، ز. دی، ن. عاشور، ع. Satapathy، SC الگوریتم تطبیق نقشه توپولوژیکی پیشرفته بر اساس نظریه D-S. عربین جی. مهندس 2018 ، 43 ، 3863-3874. [ Google Scholar ] [ CrossRef ]
Alt، H.; عفرات، ع. روت، جی. Wenk, C. تطبیق نقشه های مسطح. J. Algorithms 2003 ، 49 ، 262-283. [ Google Scholar ] [ CrossRef ]
یین، اچ. Wolfson, O. A Weight-based Map Matching Method در پایگاه داده های اشیاء متحرک. در مجموعه مقالات شانزدهمین کنفرانس بین المللی مدیریت پایگاه داده های علمی و آماری، جزیره سانتورینی، یونان، 21-23 ژوئن 2004. صص 437-438. [ Google Scholar ]
وی، اچ. وانگ، ی. فورمن، جی. Zhu, Y. تطبیق نقشه بر اساس فاصله Fréchet و بهینه سازی وزن جهانی . مقاله فنی؛ گروه علوم و مهندسی کامپیوتر، 2013; پ. 19. موجود به صورت آنلاین: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.716.7193&rep=rep1&type=pdf (در 10 دسامبر 2019 قابل دسترسی است).
میلارد بال، آ. همپشایر، آرسی Weinberger، RR نقشه تطبیق داده های GPS با کیفیت پایین در محیط های شهری: بسته pgMapMatch. ترانسپ طرح. تکنولوژی 2019 ، 42 ، 539-553. [ Google Scholar ] [ CrossRef ]
کناپن، ال. بلمنز، تی. یانسنز، دی. Wets, G. تطبیق نقشه آفلاین مبتنی بر احتمال وقوع GPS ضبط شده با استفاده از اطلاعات ردیابی جهانی. ترانسپ Res. قسمت C Emerg. تکنولوژی 2018 ، 93 ، 13-35. [ Google Scholar ] [ CrossRef ]
راپوس، ای. رابرت، اس. Cudré-Mauroux, P. یک رویکرد نیرو محور برای تطبیق نقشه مسیر GPS آفلاین. در مجموعه مقالات بیست و ششمین کنفرانس بین المللی ACM Sigspatial در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، سیاتل، WA، ایالات متحده، 6-9 نوامبر 2018؛ صص 319-328. [ Google Scholar ]
نیوزون، پی. Krumm, J. Hidden Markov نقشه مطابق با نویز و پراکندگی. در مجموعه مقالات کنفرانس بین المللی ACM Sigspatial در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، سیاتل، WA، ایالات متحده آمریکا، 4 تا 6 نوامبر 2009. [ Google Scholar ]
کولر، اچ. ویدهام، پی. دراگاشنیگ، م. Graser, A. تطبیق سریع مدل مارکوف پنهان برای مسیرهای پراکنده و پر سر و صدا. در مجموعه مقالات 2015 IEEE هجدهمین کنفرانس بین المللی سیستم های حمل و نقل هوشمند، لاس پالماس، اسپانیا، 15-18 سپتامبر 2015. صص 2557–2561. [ Google Scholar ]
یانگ، سی. Gidofalvi، G. تطبیق سریع نقشه، الگوریتمی که مدل مارکوف پنهان را با پیش محاسبه ادغام می کند. بین المللی جی. جئوگر. Inf. علمی 2018 ، 32 ، 547-570. [ Google Scholar ] [ CrossRef ]
Szwed، P. پکالا، ک. الگوریتم تطبیق نقشه افزایشی بر اساس مدل مارکوف پنهان. در مجموعه مقالات کنفرانس بین المللی هوش مصنوعی و محاسبات نرم، ICAISC 2014، Zakopane، لهستان، 1-5 ژوئن 2014. صص 579-590. [ Google Scholar ]
محمد، ر. علی، اچ. Youssef, M. تطبیق دقیق نقشه در زمان واقعی برای محیط های چالش برانگیز. IEEE Trans. هوشمند ترانسپ سیستم 2016 ، 18 ، 847-857. [ Google Scholar ] [ CrossRef ]
Jagadeesh, GR; Srikanthan، T. نقشه آنلاین تطبیق داده های مکان پر سر و صدا و پراکنده با مدل های مخفی مارکوف و انتخاب مسیر. IEEE Trans. هوشمند ترانسپ سیستم 2017 ، 18 ، 2423-2434. [ Google Scholar ] [ CrossRef ]
الگیزاوی، ای. اوگاوا، تی. المهدی، الف. تطبیق نقشه در مقیاس بزرگ در زمان واقعی با استفاده از داده های تلفن همراه. ACM Trans. بدانید. کشف کنید. داده 2017 ، 11 ، 52. [ Google Scholar ] [ CrossRef ]
یوان، جی. ژنگ، ی. Xie، X. Sun, G. رانندگی با دانش از دنیای فیزیکی. در مجموعه مقالات هفدهمین کنفرانس بین المللی ACM Sigkdd در مورد کشف دانش و داده کاوی، سن دیگو، کالیفرنیا، ایالات متحده آمریکا، 21 تا 24 اوت 2011. صص 316-324. [ Google Scholar ]
یوان، جی. ژنگ، ی. ژانگ، سی. زی، دبلیو. Xie، X. سان، جی. Huang, Y. T-drive: مسیرهای رانندگی بر اساس مسیرهای تاکسی. در مجموعه مقالات هجدهمین کنفرانس بین المللی Sigspatial در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، سان خوزه، CA، ایالات متحده آمریکا، 2-5 نوامبر 2010. صص 99-108. [ Google Scholar ]
وزارت مسکن و توسعه شهری – روستایی جمهوری خلق چین. کد طراحی مهندسی راه شهری (CJJ37-2012) ; چاپ صنعت ساختمان چین: پکن، چین، 2012.

شکل 1. تطبیق نادرست نقاط مسیر تقاطع. نقاط p _i و p _i+₁ با استفاده از روش های دیگر با r ₂ تطبیق داده می شوند . با این حال، p _i باید با r ₁ و p _i+_{1 با}r ₃ مطابقت داده شود .

شکل 2. نمونه هایی از مفاهیم مرتبط. چهار بخش جاده به نام های r _s ، r _e ، r _i ، r _j وجود دارد که در یک تقاطع o به هم متصل شده و یک شبکه راه را تشکیل می دهند. ε شعاع خطای اکتساب است. نقاط مسیر از p _s تا p _e نقاط مسیر تقاطع هستند و به عنوان بخش های مسیر تقاطع به هم متصل می شوند. p _s و p _e به ترتیب نقاط ورودی و خروجی هستند. r _s یک بخش جاده ورودی است وr _e یک بخش جاده خروجی است.

شکل 3. طبقه بندی و تطبیق نقاط مسیر تقاطع. چهار بخش جاده، r ₁ ، r ₂ ، r ₃ ، r ₄ وجود دارد که در یک تقاطع o به هم متصل می شوند . r ₁ بخش های جاده ورودی ( r _s ) و r ₄ بخش های جاده خروجی ( r _e ) است. { p ₁ , p ₂ , p ₃ , p ₄ } نقاط مسیر تقاطع هستند. p ₁ وp ₄ به ترتیب نقطه ورودی ( p _s ) و نقطه خروجی ( p _e ) هستند.

شکل 4. نقطه تطبیق مسیر تقاطع ناهنجاری. نقاط p ₁ , p ₂ , p ₃ , و p ₄ به ترتیب با r ₁ ( r _s )، o , r ₁ ( r _s ) و r ₄ ( r _e ) مطابقت دارند. بنابراین، دنباله مسیر منطبق ( _rs , o , rs _, r _e ) است که نشان می‌دهد که مسیر در بخش جاده دوباره دنبال می‌شود.r _s _ از آنجایی که این یک ردیابی مجدد نادرست است، لازم است چنین اختلالی به یک توالی منظم تبدیل شود.

شکل 5. تطبیق بخش جاده ورودی با نقطه قبلی نقطه ورودی. نقطه p _s نقطه ورودی است و نقطه p _s- 1 نقطه قبلی نقطه ورودی است. ( الف ) رابطه بین نقطه ورودی و نقطه قبلی آن در شکل، و ( ب ) رابطه بین نقطه ورودی و نقطه قبلی آن در پردازش واقعی.

شکل 6. داده های شبکه راه و مسیر. خطوط خاکستری شبکه جاده هستند. خطوط رنگی داده های مسیر هستند که خطوط آبی داده 1، خطوط نارنجی داده 2 و خطوط سبز داده 3 هستند.

شکل 7. مقایسه نتایج تطبیق: ( الف ) روش LCS، و ( ب ) روش پیشنهادی.

شکل 8. مقایسه کارایی روش پیشنهادی در یازده شعاع خطا: ( الف ) کل زمان اجرای هر داده مسیر، و ( ب ) میانگین زمان اجرا در هر 1000 نقطه از داده های مسیر.

شکل 9. مقایسه دقت این روش در یازده شعاع خطا.

مقالات داخلی و بین المللی

بدون دیدگاه

دیدگاهتان را بنویسید لغو پاسخ

برای نوشتن دیدگاه باید وارد بشوید.

مشاورین هوش پیروزی

خلاصه

کلید واژه ها:

1. معرفی