אחת ממשימות האופטימיזציה הנפוצות ביותר היא ניתוב כלי רכב, שבה המטרה היא למצוא את המסלולים הטובים ביותר של צי כלי רכב שמבקרים במספר מיקומים. בדרך כלל, המשמעות של 'הטוב ביותר' היא מסלולים עם העלות הכוללת או המרחק הכולל הנמוך ביותר. כמה דוגמאות לבעיות שקשורות לתכנון מסלול:
- חברה לשילוח חבילות רוצה להקצות מסלולים לנהגים לביצוע משלוחים.
- חברת טלוויזיה בכבלים רוצה להקצות מסלולים שבהם טכנאים יוכלו לבצע שיחות שירות באזור המגורים.
- חברה לשיתוף נסיעות מעוניינת להקצות לנהגים מסלולים לאיסוף ולהורדה של נוסעים.
בעיית המסלול המפורסמת ביותר היא בעיה של איש המכירות בנסיעות (TSP): צריך למצוא את המסלול הקצר ביותר לאנשי מכירות שצריכים לבקר לקוחות במיקומים שונים ולחזור לנקודת ההתחלה. TSP יכול להיות מיוצג על ידי גרף שבו הצמתים תואמים למיקומים, והקצוות (או הקשתות) מציינים מעבר ישיר בין מיקומים. לדוגמה, התרשים הבא מציג TSP עם ארבעה מיקומים בלבד, שנקראים A, B, C ו-D. המרחק בין שני מיקומים נקבע על ידי המספר שליד הקצה שמחבר ביניהם.
בחישוב המרחקים של כל המסלולים האפשריים אפשר לראות שהמסלול הקצר ביותר הוא ACDBA, והמרחק הכולל שלו הוא 35 + 30 + 15 + 10 = 90.
הבעיה חמורה יותר כשיש יותר מיקומים. בדוגמה שלמעלה, יש רק שישה מסלולים. אבל אם יש עשרה מיקומים (לא כולל את נקודת ההתחלה), מספר המסלולים הוא 362880. אם מדובר ב-20 מיקומים, המספר מזנק ל-2432902008176640000. בעזרת חיפוש מקיף של כל המסלולים האפשריים, מובטחת שתמצאו את המסלול הקצר ביותר. עם זאת, אפשר לחשב את החישוב הזה רק לקבוצות קטנות של מיקומים. כדי לטפל בבעיות גדולות יותר, צריך להשתמש בשיטות אופטימיזציה כדי לבצע חיפוש חכם במרחב הפתרונות ולמצוא פתרון אופטימלי (או כמעט אופטימלי).
גרסה כללית יותר של ה-TSP היא בעיית הניווט ברכב (VRP), שבה יש כמה כלי רכב. ברוב המקרים, למכונות VR יש מגבלות: לדוגמה, כלי רכב יכולים להכיל את המשקל המרבי או הנפח המקסימלי של פריטים שהם יכולים לשאת, או שהנהגים יידרשו לבקר במיקומים בתוך חלונות זמן מסוימים שהלקוחות יבקשו.
OR-Tools יכולים לפתור סוגים רבים של VRP, כולל:
- בעיה של איש מכירות בנסיעה, בעיית המסלול הקלאסית שבה יש רק רכב אחד.
- בעיה בניתוב רכב, שהיא הכללות של ה-TSP עם כמה כלי רכב.
- VRP עם מגבלות קיבולת – בכלי רכב יש קיבולת מקסימלית לפריטים שהם יכולים לשאת.
- VRP עם חלונות זמן – כלי הרכב צריכים להגיע למיקומים במרווחי זמן ספציפיים.
- VRP עם מגבלות משאבים, כמו מקום או צוות לטעינה ולהורדה של כלי רכב בתחנה (נקודת ההתחלה של המסלולים).
- VRP עם ירידה במספר הביקורים – לא צריך לנסוע לכל המיקומים, אבל צריך לשלם קנס על כל ביקור שבוטל.
מגבלות בפתרון בעיות שקשורות לתכנון מסלול ברכב
בעיות בתכנון מסלול רכב הן מטבען אינסופיות: משך הזמן שנדרש לפתרון הבעיות האלה גדל בשיעור גבוה מאוד. במקרה של בעיות גדולות מספיק, ייתכן שיחלפו שנים עד למציאת הפתרון האופטימלי OR-Tools (או כל תוכנת ניתוב אחרת) שנים. כתוצאה מכך, לפעמים לחיצה על OR-Tools מחזירה פתרונות טובים, אבל לא אופטימליים. כדי למצוא פתרון טוב יותר, כדאי לשנות את אפשרויות החיפוש של הפותר. לדוגמה, ראו שינוי אסטרטגיית החיפוש.