מידות

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

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

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

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

• בדוגמה ל-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)

השיטה AddDimension כוללת את סוגי הקלט הבאים:

• callback_index: האינדקס של הקריאה החוזרת שמחזירה את הכמות. האינדקס, שהוא ההפניה הפנימית של פותר הבעיות לקריאה לאחור, נוצר על ידי שיטות כמו 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

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

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

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

לפרטים נוספים על מאפיינים, תוכלו לעיין בקטע RoutingDimension בקטע ההפניה.