מחפש נתיב אופטימלי

סיכום

החיפוש אחר הנתיב הקצר ביותר ברשת כבישים הוא תהליך ניתוח שמטרתו לקבוע את הדרך היעילה ביותר לנסוע בין נקודות על מפה. כלי זה יכול להיות שימושי ליצירת מסלולים אופטימליים עם עצירות מרובות או למדידת המרחק וזמן הנסיעה בין מיקומים שונים. עם כל קריאה, הטכנולוגיה שלנו יכולה למצוא מסלולים אופטימליים עבור רכב אחד או מספר כלי רכב. לדוגמה, היא יכולה לעזור לנהגים למצוא את המסלולים האופטימליים להובלת סחורות או לקבוע את מרחק הנסיעה האופטימלי מהבית לעבודה עבור נוסעים שונים.

יכולות אלגוריתם

הספרייה שלנו מספקת את היכולת לבנות את הנתיב האופטימלי ביותר בין שתי נקודות על מפה. יש לה את התכונות העיקריות הבאות:

1. חיפוש הנתיב האופטימלי על המפה, תוך התחשבות בשבילים ומכשולים: אנו לוקחים בחשבון לא רק כבישים אלא גם שבילים מחוץ לכביש כמו שבילים להולכי רגל, מדרכות ומכשולים שעשויים להשפיע על הבחירה בנתיב האופטימלי.

2. חיפוש הנתיב האופטימלי רק על כבישים: אם אתה צריך למצוא מסלול אך ורק על כבישים, אנו מספקים יכולת זו. זה שימושי, לדוגמה, עבור כלי רכב המוגבלים לנסיעה רק על כבישים.

3. הגדרת מהירויות שונות לכבישים: יש לנו את היכולת להקצות מהירויות שונות לכבישים שונים. לדוגמה, ניתן לקבוע מהירויות גבוהות יותר לאוטוסטרדות עיקריות ומהירויות נמוכות יותר לנתיבים צרים.

4. הגדרת מכשולים מלבניים: אתה יכול להגדיר מכשולים מלבניים על המפה שצריך לקחת בחשבון בעת בניית הנתיב האופטימלי. זה שימושי כאשר ישנם מכשולים ידועים כמו מבנים או אגמים (הקירוב שלהם).

5. הגבלת רדיוס החיפוש לכבישים: אתה יכול להגביל את רדיוס החיפוש לכבישים כדי להפחית את זמן החיפוש ולהתמקד רק באזור ספציפי.

6. שליטה בביצועים ובדיוק: אנו מספקים את היכולת לשלוט בביצועים ובדיוק של האלגוריתם. אתה יכול לכוון אותו כדי להשיג את האיזון הרצוי בין מהירות החיפוש לבניית המסלול המדויקת.

בהמשך, נספק תיאור מפורט יותר של כל אחת מהתכונות הללו ונבחן דוגמאות ליישומים שלהן.

גישה לפתרון

אף על פי שמציאת נתיב היא משימה לא טריוויאלית, ישנם מספר אלגוריתמים טובים ואמינים המוכרים בקהילת הפיתוח.

ביישום שלנו, השתמשנו באלגוריתם לי (Lee) שונה. יש לנו רשת של תאים על המישור. מנקודת ההתחלה, גל מתפשט ל-8 כיוונים (כולל אלכסונים) לתאים שכנים, מחשב את הזמן הנדרש להגיע לכל אחד מהם. תא שכנה עשוי להכיל מכשול או כביש. לכבישים יכולים להיות מקדמי מהירות שונים. כך אנו “מסמנים” את הרשת שלנו בזמן שלוקח להגיע לכל תא מתא ההתחלה תוך רדיוס מסוים או עד להגעה לנקודת היעד. אם נגיע לנקודת היעד, נבנה נתיב הפוך באמצעות הרשת שלנו.

כדי לקבוע את הנתיב האופטימלי ברשת הכבישים, יש לבצע מספר שלבים. ראשית, עליך להגדיר את הכבישים ולציין את מהירות התנועה על כל אחד מהם. עליך גם לשקול את קיומם של מכשולים טבעיים ומלאכותיים שעשויים להשפיע על מעבר הנתיב. לאחר מכן, עליך לציין את נקודות ההתחלה והיעד של החיפוש. ברגע ששלבים מקדימים אלה הושלמו, תוכל לעבור לחיפוש הנתיב בפועל. התוצאה תהיה נתיב המיוצג, למשל, כרשימה של קואורדינטות נקודה.

חשוב לציין שהנתיב האופטימלי עשוי להיות תלוי במצב התחבורה שנבחר, מכיוון שמהירות התנועה וקבוצת המכשולים עשויה להשתנות. לכן, יש להשתמש בקבוצות כבישים ומכשולים שונות עבור כל סוג של תחבורה בעת חיפוש הנתיב האופטימלי.

פרויקט הדגמה ב-GitHub

כדי להבין טוב יותר את הפונקציונליות של הספרייה שלנו, נשקול דוגמה לשימוש בה. קוד זה ממחיש כיצד להגדיר כבישים ומכשולים באלגוריתם מציאת הנתיב ולמצוא את המסלול האופטימלי.

הדוגמה כוללת את השלבים הבאים:

1. יצירת רשימת מידע על הכביש (RoadInfo), הכוללת מידע על קטע הכביש (Segment) ומהירות התנועה (Velocity).
2. הוספת כבישים מהירים לרשימה.
3. הוספת כבישים טבעתיים איטיים לרשימה.
4. יצירת מחולל שכבת דרך (WayLayerGenerator) והוספת כבישים לגנרטור.
5. חיפוש מספר נתיבים מנקודת ההתחלה (startPoint) לנקודות היעד (goalPoint01, goalPoint02, goalPoint03) באמצעות הרדיוס שצוין (radius).
6. הכנת שכבת כבישים (roadsLayer) לתצוגה על המפה והוספת אובייקטי כביש.
7. הכנת שכבת דרך (wayLayer) לתצוגה על המפה ויצירת עצמים גיאומטריים עבור כל נתיב שנמצא.
8. תצוגת המפה באמצעות הפונקציה ShowMap, שמירת המפה בנתיב שצוין.

קוד זה בונה ומציג נתיבי כביש על המפה עבור נקודות שצוינו, תוך שימוש במידע על הכביש ובמחולל שכבת הדרך.

אפשרויות חיפוש

מציאת נתיב מתבצעת באמצעות המחלקה 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

שיטות אלה מאפשרות לנו להגדיר את מפת הכבישים והמכשולים לפני תחילת תהליך מציאת הנתיב.

דוגמאות קוד

הנה כמה דוגמאות קוד שממחישות כיצד להגדיר כבישים ומכשולים באלגוריתם מציאת הנתיב ולמצוא את המסלול האופטימלי.

דוגמה 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);

דוגמאות הקוד הללו בונות ומציגות נתיבי כביש על המפה עבור נקודות שצוינו, תוך שימוש במידע על הכביש ובמחולל שכבת הדרך.

לסיכום, מחפש הנתיב האופטימלי הוא כלי רב עוצמה לניתוח רשתות כבישים וקביעת המסלולים היעילים ביותר בין נקודות על מפה. הוא לוקח בחשבון גורמים שונים כמו סוגי כבישים, מכשולים ומהירויות שונות כדי לחשב את הנתיב האופטימלי. עם היכולת לחפש נתיבים הן על כבישים והן בשבילים מחוץ לכביש, כמו גם לשלוט ברדיוס החיפוש ולהתאים ביצועים ודיוק, אלגוריתם זה מספק פתרון רב תכליתי לאופטימיזציה של נתיבים. על ידי התחשבות במצבי תחבורה שונים והתאמת קבוצות כבישים ומכשולים בהתאם, ניתן להשתמש בו בתרחישים שונים כמו תכנון משלוחים או אופטימיזציה של נסיעות לעבודה. דוגמאות הקוד וההסברים המסופקים מדגימים את יכולות האלגוריתם ואת השלבים המעורבים בשימוש בו. בסופו של דבר, מחפש הנתיב האופטימלי מציע דרך חזקה למצוא את המסלולים היעילים ביותר ולשפר ניווט ברשת כבישים.