מידות

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

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

דוגמאות למאפיינים

הנה כמה דוגמאות למאפיינים מהקטעים הקודמים.

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

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

בדוגמאות הבאות מוגדר מאפיין של VRPTW באמצעות AddDimension .

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++‎

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#‎

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

ה-method AddDimension כוללת את פרטי הקלט הבאים:

• callback_index: האינדקס של הקריאה החוזרת שמחזירה את הכמות. אינדקס, שהוא ההפניה הפנימית של הפותר לקריאה חוזרת (callback), נוצר על ידי כמו RegisterTransitCallback או RegisterUnitaryTransitCallback.
• slack_max: הערך המקסימלי ל-slack, משתנה שמשמש לייצוג ההמתנה פעמים במיקומים. מידע נוסף מופיע בקטע משתני Slack בהמשך פרטים. אם הבעיה לא כוללת זמן המתנה, בדרך כלל אפשר להגדיר slack_max ל-0.
• capacity: הכמות המקסימלית שנצברה לאורך כל מסלול. צריך להשתמש ב-capacity כדי ליצור אילוצים כמו אלה שיעור המרה (CVRP). אם לבעיה שלכם אין אילוץ, אפשר להגדיר את capacity לערך גדול מספיק כדי לא מגבילים את המסלולים – לדוגמה, את הסכום של כל של המטריצה או המערך ששימשו להגדרת הקריאה החוזרת.
• fix_start_cumulative_to_zero: ערך בוליאני. אם True, הערך המצטבר מהכמות מתחילה ב-0. ברוב המקרים, הערך צריך להיות True. עם זאת, במסגרת ה-VRPTW או בעיות עם מגבלות משאבים, כלי רכב מסוימים יכול להיות שתצטרכו להתחיל אחרי השעה 0 בגלל מגבלות של חלון זמן, לכן להגדיר את fix_start_cumulative_to_zero כ-False לבעיות האלה.
• dimension_name: מחרוזת של השם של המאפיין, למשל 'Distance', שאפשר להשתמש בהם כדי לגשת למשתנים בכל מקום אחר בתוכנית.

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

פרטים נוספים זמינים בRoutingModel על שיטות אחרות ליצירת מאפיינים.

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

משתני Slack

הנה דוגמה שממחישה משתני Slot לבעיה שכוללת זמן הגעה. נניח רכב עובר ממיקום i למיקום j בשלב אחד במסלול, ואז:

• זמן הנסיעה המצטבר של הרכב ב-i הוא 100 דקות.
• זמן הנסיעה המצטבר של הרכב ב-j הוא 200 דקות.
• זמן ההגעה מ-i ל-j הוא 75 דקות.

הרכב לא יכול לצאת מהמיקום i מיד עם ההגעה, או אם הוא השעה במיקום j תהיה 175. במקום זאת, הרכב צריך להמתין 25 דקות ב- מיקום i לפני היציאה; במילים אחרות, החוסר במיקום i הוא 25.

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

לעומת זאת, ביחס ל-CVRP, השינוי בעומס שנצבר מ-i ל- j תמיד שווה לביקוש ב-i, כך שאין מרווח. לבעיות כמו במקרה הזה אפשר להגדיר את slack_max ל-0.

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

• משתני תחבורה ציבורית: העלייה או הירידה בכמות בכל שלב של מסלול. אם i -> j הוא שלב אחד במסלול, משתנה התחבורה הציבורית הוא i, ערך j של מטריצת התחבורה הציבורית (לקריאה חוזרת (callback) של תחבורה ציבורית), או פשוט ערך הקריאה החוזרת במיקום i (אם הקריאה החוזרת תלויה במיקום אחד בלבד).
• משתנים מצטברים: הכמות הכוללת שנצברה בכל מיקום. שלך יכולים לגשת למשתנה המצטבר במיקום i, dimension_name.CumulVar(i) לדוגמה, אפשר להיכנס אל מגבלות של חלון זמן בדוגמה של VRPTW.

בהנחה שכלי רכב עובר ממיקום i למיקום j בצעד אחד, הערך של הפרמטר slack קשור למשתנים האלה באופן הבא:

slack(i) = cumul(j) - cumul(i) - transit(i, j)

מידע נוסף על מאפיינים זמין במאמר RoutingDimension בקטע ההפניה.