מידע על OR-Tools

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

• ניתוב כלי רכב: איתור מסלולים אופטימליים לצי הרכבים שאוספים ומוסרים חבילות בהתאם למגבלות (למשל "במשאית הזו לא יכולים לעמוד במשקל יותר מ-10,000 ק"ג" או "יש לספק את כל המשלוחים בתוך שעתיים").
• תזמון: מוצאים את לוח הזמנים האופטימלי לקבוצה מורכבת של משימות, שאת חלק מהן צריך לבצע לפני אחרים, על גבי קבוצה קבועה של מחשבים או משאבים אחרים.
• סידור בקונטיינרים (bin packing): אריזות של כמה שיותר אובייקטים בגדלים שונים בקונטיינרים עם קיבולת מקסימלית.

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

OR-Tools כולל פתרונות עבור:

אילוצים

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

הטמעה לינארית ושילוב של מספר שלם

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

ניתוב רכב

ספרייה מיוחדת לזיהוי המסלולים הכי טובים של כלי רכב בגלל מגבלות.

אלגוריתמים של תרשים

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

בקטע הבא תוכלו להתחיל לעבוד במהירות עם OR-Tools.