Clear Sky Science
הסברים מבוססי ראיות, עם מעט ז'רגון

Clear Sky Science · he

פתרון בעיית הסוכן הנוסע הרב-מחסנית עם מסלולים סגורים באמצעות אשכולות היררכיים k-means++ ורשתות נאורליות קומבינטוריות

· חזרה לאינדקס

מסלולים חכמים לנהגים רבים

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

Figure 1. כיצד אשכולות בשילוב רשתות ניורליות ממירים מפת מסירה מרובת כלי רכב ומורכבת למסלולים מהירים ויעילים.
Figure 1. כיצד אשכולות בשילוב רשתות ניורליות ממירים מפת מסירה מרובת כלי רכב ומורכבת למסלולים מהירים ויעילים.

האתגר של מחסנים רבים ונהגים רבים

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

מגבלות חיפוש קלאסי וחלוקה פשוטה

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

להכשיר רשת לניתוב, ואז לעזור לה להתקדם בקנה מידה

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

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

כיצד עובד השיטה בעלת שתי השלבים

השיטה המוצעת, שנקראת KHC-NCN, מתחילה בשימוש בגרסה משופרת של אשכולות k-means להקצות ערים למחסנים ולנהגים שונים. אם אזור שנוצר מכיל יותר מדי ערים עד כדי כך שהפותר הניורלי לא יכול לטפל בו באמינות, השיטה מפצלת את האזור הזה אוטומטית לחתיכות קטנות יותר, כל אחת בגודל הקרוב למה שהרשת ראתה במהלך האימון. הקואורדינטות בכל חתיכה מומרות מחדש לריבוע סטנדרטי כדי שידמו את נתוני האימון באופן קרוב יותר. הרשת הניורלית מייצרת אז מסלול לכל חתיכה קטנה. לבסוף, שלב המיזוג תופר את תתי־המסלולים הללו ללולאה אחת לכל נהג, באמצעות כללים גאומטריים פשוטים שמחברים חתיכות כך שהוספת המרחק המיותר תהיה המינימלית.

מהירות ואיכות במפות מבחן אמיתיות

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

מה משמעות הדבר לניתובים בעולם האמיתי

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

ציטוט: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

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