Optimal Path Finder

Summary

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

Algorithm Capabilities

کتابخانه ما امکان ساخت بهینه‌ترین مسیر بین دو نقطه روی نقشه را فراهم می‌کند. این کتابخانه دارای ویژگی‌های اصلی زیر است:

1. جستجوی مسیر بهینه روی نقشه، با در نظر گرفتن مسیرها و موانع: ما نه تنها جاده‌ها بلکه مسیرهای خارج از جاده مانند مسیرهای پیاده‌روی، گذرگاه‌های عابرین پیاده و موانعی که ممکن است بر انتخاب مسیر بهینه تأثیر بگذارند را نیز در نظر می‌گیریم.

2. جستجوی مسیر بهینه فقط روی جاده‌ها: اگر نیاز به یافتن مسیری منحصراً روی جاده‌ها دارید، ما این قابلیت را ارائه می‌دهیم. این برای وسایلی که محدود به سفر فقط روی جاده‌ها هستند مفید است، به عنوان مثال.

3. تنظیم سرعت‌های مختلف برای جاده‌ها: ما می‌توانیم سرعت‌های مختلفی را به جاده‌های مختلف اختصاص دهیم. به عنوان مثال، می‌توان سرعت‌های بالاتری را برای بزرگراه‌های اصلی و سرعت‌های پایین‌تری را برای کوچه‌ها تعیین کرد.

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

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

6. کنترل عملکرد و دقت: ما امکان کنترل عملکرد و دقت الگوریتم را فراهم می‌کنیم. شما می‌توانید آن را تنظیم کنید تا به تعادل مطلوب بین سرعت جستجو و دقت ساخت مسیر برسید.

در ادامه، توضیحات مفصل‌تری از هر یک از این ویژگی‌ها ارائه خواهیم داد و نمونه‌هایی از کاربردهای آنها را بررسی خواهیم کرد.

Approach to Solution

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

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

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

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

Demo Project on GitHub

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

این مثال شامل مراحل زیر است:

1. ایجاد لیستی از اطلاعات جاده (RoadInfo)، که شامل اطلاعات مربوط به قطعه جاده (Segment) و سرعت حرکت (Velocity) است.
2. افزودن جاده‌های سریع به لیست.
3. افزودن حلقه‌های کندرو به لیست.
4. ایجاد یک تولیدکننده لایه راه (WayLayerGenerator) و افزودن جاده‌ها به تولیدکننده.
5. جستجوی چندین مسیر از نقطه شروع (startPoint) به نقاط هدف (goalPoint01، goalPoint02، goalPoint03) با استفاده از شعاع مشخص شده (radius).
6. آماده‌سازی یک لایه جاده (roadsLayer) برای نمایش روی نقشه و افزودن اشیاء جاده.
7. آماده‌سازی یک لایه راه (wayLayer) برای نمایش روی نقشه و ایجاد اشیاء هندسی برای هر مسیر یافت شده.
8. نمایش نقشه با استفاده از تابع ShowMap، ذخیره نقشه در مسیر مشخص شده.

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

Search Options

یافتن مسیر با استفاده از کلاس WayLayerGenerator که در فضای نام Aspose.Gis.GeoTools.WayAnalyzer قرار دارد انجام می‌شود.

کلاس WayLayerGenerator دارای روش FindTheWay برای یافتن مسیر از نقطه شروع به هدف است. برای ایجاد یک نمونه از کلاس WayLayerGenerator، پارامترهای WayOptions را منتقل می‌کنیم (همه پارامترها اختیاری هستند):

• StartPoint: نقطه شروع
• GoalPoint: نقطه هدف
• Radius: شعاع جستجو
• Scale: مقیاس شبکه
• IsMoveOnlyRoad: اینکه آیا فقط باید مسیر را روی جاده‌ها جستجو کرد یا خیر

ویژگی قابل توجه در اینجا پارامتر Scale است. اگر در سازنده مشخص شده باشد، ما یک مقیاس ثابت برای جستجوهای بعدی تنظیم می‌کنیم. اگر پارامتر Scale تنظیم نشده باشد اما StartPoint و GoalPoint تنظیم شده باشند، مقیاس را به عنوان فاصله بین نقطه شروع و هدف تقسیم بر 100 محاسبه می‌کنیم. در همه موارد دیگر، مقدار پیش‌فرض Scale برابر با 1 است. برای کاربران باتجربه، بهتر است Scale را تنظیم کنید یا مستقیماً StartPoint و GoalPoint را تنظیم کنید تا جاده‌ها و موانع را به طور مؤثرتری روی شبکه نشان دهید (به خصوص اگر تعداد زیادی از آنها وجود داشته باشد).

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

قبل از شروع جستجو، باید نقشه جاده و مانع را با استفاده از روش‌های AddRoad و AddBlock مربوطه کلاس WayLayerGenerator تعریف کنید.

برای روش AddRoad، باید مشخص کنید:

• startPoint: نقطه شروع جاده
• endPoint: نقطه پایان جاده
• velocity: سرعت حرکت روی جاده

برای روش AddBlock، باید مشخص کنید:

• x: مختصات x گوشه بالا سمت چپ بلوک
• y: مختصات y گوشه بالا سمت چپ بلوک
• sizeX: اندازه در محور x
• sizeY: اندازه در محور y

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

Code examples

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

مثال 1: یافتن مسیری بین نقاط شروع و پایان.

WayOptions mapGeneratorOptions = new WayOptions();
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(5, 7);
Point goalPoint = new Point(15, 13);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

مثال 2: تنظیم پارامتر مقیاس و داشتن مختصات منفی برای نقطه.

WayOptions mapGeneratorOptions = new WayOptions(1);
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(-50, -70);
Point goalPoint = new Point(150, 130);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

مثال 3: تنظیم پارامتر IsMoveOnlyRoad و شعاع جستجو.

WayOptions mapGeneratorOptions = new WayOptions();
mapGeneratorOptions.IsMoveOnlyRoad = true;
var generator = new WayLayerGenerator(mapGeneratorOptions);
generator.AddRoad(new Point(100, 100), new Point(140, 150), 10);
generator.AddRoad(new Point(140, 150), new Point(190, 100), 10);
Point startPoint = new Point(100, 100);
Point goalPoint = new Point(190, 100);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 100);

مثال 4: تنظیم پارامتر مقیاس برای جستجوی سریع‌تر.

WayOptions mapGeneratorOptions = new WayOptions(10);
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(50, 70);
Point goalPoint = new Point(1650, 1300);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 2500);

مثال 5: مثال جستجوی چندگانه.

WayOptions mapGeneratorOptions = new WayOptions();
var generator = new WayLayerGenerator(mapGeneratorOptions);
generator.AddBlock(200, 1700, 1500, 100, 0);
generator.AddBlock(1700, 200, 100, 1600, 0);
generator.AddBlock(200, 200, 1500, 100, 0);
generator.AddRoad(new Point(1000, 1150), new Point(200, 600), 10);
generator.AddRoad(new Point(50, 450), new Point(150, 1850), 10);

Point startPoint = new Point(1000, 1000);
Point goalPoint = new Point(1900, 1000);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 3500);

Point startPoint = new Point(50, 50);
Point goalPoint = new Point(70, 70);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

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

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