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

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

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

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

סוגי בעיות

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

• VRPTW - בעיית ניתוב נהגים עם אילוצי חלונות זמן.
• VRPP - בעיית ניתוב נהגים עם רווחים; בעיית אופטימיזציה שבה יש מחיר (רווח) לכל ביקור, ונדרש להשיא (להביא למקסימום) את הביקורים בנקודות, תוך כדי עמידה באילוצים.הבעיה כוללת בתוכה שלוש וריאציות עיקריות:
  • Orienteering Problem (OP), בה המטרה היא לאסוף סכום גדול ככל הניתן של רווח בתוך מגבלת זמן נתונה (מגבלת הזמן נתונה, והמטרה היא למקסם את הרווח).
  • Prize Collecting Traveling Salesman Problem (PCTSP), בה המטרה היא לאסוף רווח בכמות שעולה על ערך נתון, תוך מזעור זמן המסלול (הסכום הדרוש נתון, והמטרה היא למזער את הזמן).
  • Profitable Tour Problem (PTP), בה המטרה היא למקסם את הפרשת בין הרווח לבין מחיר החיפוש, כשהמחיר יכול להיות מבוטא במונחים של זמן מסלול (לא נתונים מראש רווח דרוש וזמן מסלול, המטרה היא למקסם את הראשון ולמזער את השני).

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

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

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

$\text{min}\sum _{i\in V}\sum _{j\in V}{c}_{ij}{x}_{ij}$

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

$\sum _{i\in V}{x}_{ij}=1\mathrm{\forall }j\in V\mathrm{\setminus }\left\{0\right\}$

$\sum _{j\in V}{x}_{ij}=1\mathrm{\forall }i\in V\mathrm{\setminus }\left\{0\right\}$

$\sum _{i\in V\mathrm{\setminus }\left\{0\right\}}{x}_{i0}=K$

$\sum _{j\in V\mathrm{\setminus }\left\{0\right\}}{x}_{0j}=K$

$\sum _{i\notin S}\sum _{j\in S}{x}_{ij}\ge r(S),\mathrm{\forall }S\subseteq V\setminus \{0\},S\ne \mathrm{\varnothing }$

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

שיטות פתרון היוריסטיות

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

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

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

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

ראו גם

• בעיית הסוכן הנוסע

לקריאה נוספת

• ד״ר אורן נחום, יסודות תובלה ושינוע
• בועז שניידר, איזון עבודה בבעיית ניתוב רכבים
• Sustainable Transportation Management System for a Fleet of Electric Vehicles

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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