בעיית ניתוב רכבים

בעיית ניתוב הרכבים (או: סידור מסלולים לנהגים; באנגלית: Vehicle Routing Problem ובראשי תיבות: VRP) היא בעיית אופטימיזציה NP קשה בתכנות בשלמים, שמטרתה למצוא את הפתרון האופטימלי של מסלולים לצי של רכבים, כך שיעברו בין כל הנקודות (לקוחות), תוך כדי עמידה באילוצים שונים ותוך הבאה למינימום את מרחק הנסיעה (או זמן הנסיעה) הכולל של צי הרכבים.

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

ציי רכבים מקצועיים, המשתמשים ב-TMS‏ (Transportation Management System), הפותרת את הבעיה, מצליחים להגיע לחיסכון של כ 30% בעלויות השינוע בעזרת חיסכון בדלק, זמן נסיעה ומספר רכבים נדרש.

סוגי בעיות[עריכת קוד מקור | עריכה]

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

VRPTW - בעיית ניתוב נהגים עם אילוצי חלונות זמן.
VRPP - בעיית ניתוב נהגים עם רווחים; בעיית אופטימיזציה שבה יש מחיר (רווח) לכל ביקור, ונדרש להשיא (להביא למקסימום) את הביקורים בנקודות, תוך כדי עמידה באילוצים.
CVRP - בעיית ניתוב נהגים עם אילוצי קיבולת; בעיית אופטימיזציה שבה לכל רכב יש קיבולת מוגבלת של מספר הפריטים שהוא יכול להוביל.
DVRP - בעיית ניתוב נהגים דינאמית, שבה קיימים עדכונים של הבעיה בזמן אמת תוך כדי ביצוע העבודה, כמו למשל עומסי תנועה, שינויים בהזמנות וכולי.

הגדרה פורמלית של בעיה התכנות בשלמים[עריכת קוד מקור | עריכה]

פונקציית המטרה:

{\text{min}}\sum _{i\in V}\sum _{j\in V}c_{ij}x_{ij}

בהינתן האילוצים הבאים:

$\sum _{i\in V}x_{ij}=1\quad \forall j\in V\backslash \left\{0\right\}$

$\sum _{j\in V}x_{ij}=1\quad \forall i\in V\backslash \left\{0\right\}$

$\sum _{i\in {V\backslash \left\{0\right\}}}x_{i0}=K$

$\sum _{j\in {V\backslash \left\{0\right\}}}x_{0j}=K$

$\sum _{i\notin S}\sum _{j\in S}x_{ij}\geq r(S),~~\forall S\subseteq V\setminus \{0\},S\neq \emptyset$

$x_{ij}\in \{0,1\}\quad \forall i,j\in V$

שיטות פתרון היוריסטיות[עריכת קוד מקור | עריכה]

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

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

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