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

מפתחים באזור הכלכלי האירופי (EEA)

במאמר הזה נסביר איך לשלוח את הבקשה הראשונה ל-Route Optimization API באמצעות תרחיש לדוגמה מהעולם האמיתי.

כדי לפשט את הדוגמה, היא משתמשת ב-HTTP וב-JSON כדי להדגים את ה-API בארכיטקטורת REST. עם זאת, בסביבת הייצור מומלץ להשתמש ב-gRPC בגלל יתרונות הביצועים שלו. עם זאת, צריך להתקין את gRPC. מידע נוסף זמין במאמר ספריות הלקוח של Route Optimization API.

תרחיש

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

אתם מנהלים מעון יום לכלבים בתל אביב, שפועל בין השעות 7:00 ל-19:00. הבוקר אתם רוצים לאסוף שלושה כלבים ממיקומים שונים בעיר ולהביא אותם למעון שלכם.

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

יש לכם מסחרית אחת לעבודה, ואתם משלמים לנהג 27 $לשעה. הנהג והרכב מתחילים את היום במעון בשעה 7:00, וצריכים לחזור מהאיסופים של הבוקר עד הצהריים להפסקת צהריים.

היום הוא 13 בפברואר 2024. כל השעות בתרחיש הזה הן לפי השעון המקומי בסן פרנסיסקו, שהוא שעון החוף המערבי בארה"ב (UTC-8) בפברואר. הנהג צריך לבצע את המשימות הבאות:

  • אוספים את כלב ההרים השווייצרי ליד מגדל קויט. הבעלים ביקש חלון זמן קצר לאיסוף, בין 8:00 ל-8:20.
  • אוספים את הצ'יוואווה בפארק South Sunset Playground. הבעלים הציע חלון זמנים גמיש יותר לאיסוף, בין 7:30 ל-9:30.
  • לאסוף את הרועה הגרמני ב-Land's End. הבעלים גם ביקש חלון זמן קצר לאיסוף, בין 8:00 ל-8:20.
  • מורידים את הכלבים במעון היום בפארק מיסיון דולורס. במעון הילדים, צריך להביא את הילדים בין 9:30 ל-11:30.

כל ביקור לאיסוף או להורדה נמשך 5 דקות, שבהן הכלב עולה לרכב או יורד ממנו.

מכיוון ש-Land's End רחוק מ-Coit Tower וחלונות הזמן לאיסוף מתנגשים, הנהג לא יכול לבצע את כל שלושת האיסופים. האופטימייזר צריך לבחור על איזה כלב לדלג כדי לצמצם את העלות הכוללת (שכר הנהג וקנסות על דילוג).

לפני שמתחילים

כדי להריץ את הקוד בתרחיש לדוגמה, קודם צריך לבצע את ההוראות במאמר הגדרת Route Optimization API.

1. בחירת הגישה לאופטימיזציה של מסלולים

ב-Route Optimization API יש כמה שיטות שאפשר לבחור מביניהן, בהתאם למורכבות של בעיית האופטימיזציה.

התרחיש של מעון הכלבים הוא בקשה קטנה ופשוטה, לכן כדאי להשתמש בשיטת חסימה כמו optimizeTours, שמספקת תוצאות במהירות לבקשות קטנות. למידע נוסף על נקודות הקצה של Route Optimization API, ראו בחירת נקודת קצה.

כדי לשלוח בקשת HTTP POST ל-method‏ optimizeTours, משתמשים בכתובת ה-URL הבאה:

https://routeoptimization.googleapis.com/v1/projects/PROJECT_OR_ID:optimizeTours

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

  • מגדירים את הפרמטר timeout ל-2 שניות.
  • משאירים את הגדרות המועד האחרון כברירת מחדל, שהיא 60 שניות לבקשות REST.

2. יצירת גוף ההודעה של הבקשה

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

בתרחיש הזה, הבקשה היא הודעת OptimizeToursRequest שמקודדת כ-JSON ב-API בארכיטקטורת REST.

כדי ליצור את הודעת הבקשה, פועלים לפי השלבים הבאים:

  1. מתחילים עם המבנה הבסיסי של הבקשה:

    {
  "timeout": ...,
  "model": {
    "shipments": [...],
    "vehicles": [...],
    "globalStartTime": "...",
    "globalEndTime": "..."
  }
}

    למידע נוסף על המבנה, עיינו במדריך למושגי מפתח בנושא מבנה בסיסי (ShipmentModel,‏ Shipment ו-Vehicle).

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

    1. לכל כלב, יוצרים VisitRequest לאיסוף ו- נוסף למשלוח, שבמקרה הזה הוא הורדה במעון.

      • באיסופים, מגדירים את arrivalWaypoint למיקום האיסוף של הכלב (Coit Tower לכלב ההרים הברנזי, South Sunset Playground Park לצ'יוואווה או Land's End לרועה הגרמני). מגדירים את timeWindows לשעת האיסוף שביקש הבעלים (8:00 עד 8:20 לכלב ההרים השוויצרי ולרועה הגרמני, ו-7:30 עד 9:30 לצ'יוואווה).

      • במשלוחים, מגדירים את arrivalWaypoint למעון היום ואת timeWindows לשעת ההורדה הנדרשת (9:30 עד 11:30).

      • בכל האיסופים והמשלוחים, מגדירים את duration ל-5 דקות (300s) כדי להביא בחשבון את העמסת הכלבים ופריקתם.

      מידע נוסף על חלונות זמן זמין במאמר חלונות זמן.

    2. כדי לתת עדיפות ללקוחות קבועים, אתם מגדירים את penaltyCost ל-1000 לכלב הרים שוויצרי ולצ'יוואווה, ול-100 לרועה גרמני. אחרי שמגדירים את עלויות הקנס, כלי האופטימיזציה יכול לדלג על כל אחד מהכלבים, אבל הוא ישקול לדלג קודם על הרועה הגרמני (שהקנס שלו נמוך יותר) אם האילוצים לא מאפשרים לבצע את כל האיסופים.

    3. אתם יכולים להשתמש בשדה label כדי להוסיף מזהה לכל משלוח, כמו "כלב הרים שוויצרי", "צ'יוואווה" ו"רועה גרמני". כך תוכלו לזהות את המשלוחים בתגובה.

    מידע נוסף על הגדרת משלוחים זמין במאמר משלוח.

  3. הגדרת כלי רכב. בשדה vehicles, מוסיפים הודעה ב-Vehicle לגבי המסחרית האחת עם מעון היום כנקודת ההתחלה והסיום, עלות השכר של הנהג ושעות הפעילות של המסחרית.

    1. מגדירים את startWaypoint ואת endWaypoint של הרכב למיקומי ההתחלה והסיום של היום, שהם מעון היום ליד פארק מיסיון דולורס.

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

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

      • אם מגדירים את startTime ב-startTimeWindows לשעה 07:00, הנהג יכול להתחיל את המשמרת שלו כבר בשעה 07:00. הוא יכול גם להתחיל מאוחר יותר אם אין איסופים מוקדם בבוקר.

      • אם מגדירים את endTime ב-endTimeWindows לשעת הצהריים, הנהג חייב לסיים את המשמרת עד הצהריים. הם יכולים גם לסיים את המשמרת ברגע שהם מסיימים את המשלוח האחרון.

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

    מידע נוסף על הגדרת כלי רכב זמין במאמר כלי רכב.

  4. הגדרת חלון זמן גלובלי. חלון הזמן הגלובלי מייצג את מסגרת הזמן שבה הרכב יכול לבצע איסופים והורדות של ילדים במעון במהלך היום. בתרחיש הזה, מגדירים את globalStartTime לשעה 7:00 ואת globalEndTime לשעה 19:00 ב-13 בפברואר 2024, שמייצגות את שעות הפעילות של מעון היום לכלבים.

3. שליחת הבקשה

הדוגמה הבאה היא בקשת curl פשוטה שמבוססת על התרחיש של מעון הכלבים, ומשתמשת בשיטת החסימה optimizeTours.

לפני ששולחים את הבקשה, מחליפים את PROJECT_NUMBER_OR_ID בקוד לדוגמה במזהה הפרויקט ב-Google Cloud.

curl -X POST 'https://routeoptimization.googleapis.com/v1/projects/PROJECT_NUMBER_OR_ID:optimizeTours' \
-H "Content-Type: application/json" \
-H "Authorization: Bearer $(gcloud auth application-default print-access-token)" \
--data @- << EOM
{
  "timeout": "2s",
  "model": {
    "shipments": [
      {
        "pickups": [
          {
            "arrivalWaypoint": {
              "location": {
                "latLng": {
                  "latitude": 37.802395,
                  "longitude": -122.405822
                }
              }
            },
            "timeWindows": [
              {
                "startTime": "2024-02-13T08:00:00-08:00",
                "endTime": "2024-02-13T08:20:00-08:00"
              }
            ],
            "duration": "300s"
          }
        ],
        "deliveries": [
          {
            "arrivalWaypoint": {
              "location": {
                "latLng": {
                  "latitude": 37.759719,
                  "longitude": -122.42798
                }
              }
            },
            "timeWindows": [
              {
                "startTime": "2024-02-13T09:30:00-08:00",
                "endTime": "2024-02-13T11:30:00-08:00"
              }
            ],
            "duration": "300s"
          }
        ],
        "label": "Bernese mountain dog",
        "penaltyCost": 1000
      },
      {
        "pickups": [
          {
            "arrivalWaypoint": {
              "location": {
                "latLng": {
                  "latitude": 37.738067,
                  "longitude": -122.498593
                }
              }
            },
            "timeWindows": [
              {
                "startTime": "2024-02-13T07:30:00-08:00",
                "endTime": "2024-02-13T09:30:00-08:00"
              }
            ],
            "duration": "300s"
          }
        ],
        "deliveries": [
          {
            "arrivalWaypoint": {
              "location": {
                "latLng": {
                  "latitude": 37.759719,
                  "longitude": -122.42798
                }
              }
            },
            "timeWindows": [
              {
                "startTime": "2024-02-13T09:30:00-08:00",
                "endTime": "2024-02-13T11:30:00-08:00"
              }
            ],
            "duration": "300s"
          }
        ],
        "label": "Chihuahua",
        "penaltyCost": 1000
      },
      {
        "pickups": [
          {
            "arrivalWaypoint": {
              "location": {
                "latLng": {
                  "latitude": 37.78018,
                  "longitude": -122.51194
                }
              }
            },
            "timeWindows": [
              {
                "startTime": "2024-02-13T08:00:00-08:00",
                "endTime": "2024-02-13T08:20:00-08:00"
              }
            ],
            "duration": "300s"
          }
        ],
        "deliveries": [
          {
            "arrivalWaypoint": {
              "location": {
                "latLng": {
                  "latitude": 37.759719,
                  "longitude": -122.42798
                }
              }
            },
            "timeWindows": [
              {
                "startTime": "2024-02-13T09:30:00-08:00",
                "endTime": "2024-02-13T11:30:00-08:00"
              }
            ],
            "duration": "300s"
          }
        ],
        "label": "German shepherd",
        "penaltyCost": 100
      }
    ],
    "vehicles": [
      {
        "startWaypoint": {
          "location": {
            "latLng": {
              "latitude": 37.759719,
              "longitude": -122.42798
            }
          }
        },
        "endWaypoint": {
          "location": {
            "latLng": {
              "latitude": 37.759719,
              "longitude": -122.42798
            }
          }
        },
        "costPerHour": 27,
        "startTimeWindows": [
          {
            "startTime": "2024-02-13T07:00:00-08:00"
          }
        ],
        "endTimeWindows": [
          {
            "endTime": "2024-02-13T12:00:00-08:00"
          }
        ]
      }
    ],
    "globalStartTime": "2024-02-13T07:00:00-08:00",
    "globalEndTime": "2024-02-13T19:00:00-08:00"
  }
}
EOM

הפרמטרים של הבקשה שנעשה בהם שימוש בבקשה

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

הורה פרמטר סוג הנכס תיאור
OptimizeToursRequest model אובייקט (ShipmentModel) זהו החלק העיקרי של הבקשה. זהו אובייקט יחיד שבו מגדירים את כל הבעיה, כולל כל הכלבים שצריך לאסוף ולהוריד (shipments) והרכב בצי (vehicles). אפשר לחשוב על זה כעל התוכנית המלאה לבעיה שצריך לפתור.
timeout משך הפרמטר הזה מציין את משך הזמן המקסימלי שהשרת עובד על בקשה לפני שהוא מחזיר תשובה. השתמשו בפרמטר הזה כדי לקצר את זמן ההמתנה. לבקשות קטנות ומהירות, כמו התרחיש הזה של מעון לכלבים, מגדירים את הערך הזה ל-2 שניות.
ShipmentModel shipments[] מערך של אובייקטים (Shipment) זהו מערך של אובייקטים שבו כל אובייקט מייצג כלב שצריך לאסוף או להוריד.
vehicles[] מערך של אובייקטים (Vehicle) זהו מערך של אובייקטים שבו כל אובייקט מגדיר רכב בצי שלכם. כאן מתארים את המשאבים, כמו הרכב שאוסף ומוריד את הנוסעים. כדי לקבל מסלול אופטימלי, צריך להגדיר לפחות רכב אחד.
globalStartTime חותמת זמן זה הזמן המוקדם ביותר שבו אירוע כלשהו יכול להתרחש במודל כולו. הפרמטר הזה מצמצם את בעיית האופטימיזציה בזמן, וזה חיוני לחישובים מדויקים של תנועה ומסלולים. בתרחיש הזה של מעון הכלבים, מגדירים את השעה המוקדמת ביותר שבה הנהג יכול להפעיל את הרכב באותו יום, שהיא 7:00 ב-13 בפברואר 2024.
globalEndTime חותמת זמן זהו הזמן האחרון האפשרי להתרחשות של אירוע כלשהו במודל כולו. בתרחיש של מעון היום לכלבים, מגדירים את השדה הזה לשעה שבה המסחרית אמורה לסיים את הפעילות שלה, כלומר 19:00 ב-13 בפברואר 2024.
Shipment pickups[] מערך של אובייקטים (VisitRequest) זו רשימה של כל אפשרויות האיסוף של המשלוח. הכלי לאופטימיזציה בוחר את המודל הכי מתאים לפתרון הבעיה. בתרחיש הזה של מעון הכלבים, צריך לציין את מיקומי האיסוף ואת חלונות הזמן שכל בעלים סיפק לכל כלב.
deliveries[] מערך של אובייקטים (VisitRequest) זו רשימה של כל אפשרויות המסירה של המשלוח. הכלי לאופטימיזציה בוחר את המודל הכי מתאים לפתרון הבעיה. בתרחיש הזה של מעון יום לכלבים, צריך לציין את המיקום של המעון ואת חלון הזמנים שבו הנהג צריך להחזיר כל כלב לארוחת צהריים.
label מחרוזת זהו מזהה של משלוח ספציפי בבקשה שלכם. אפשר לציין תוויות בבקשה כדי שיהיה קל יותר לקרוא את התשובה. בתרחיש הזה של מעון לכלבים, משתמשים במחרוזת תיאורית כמו "צ'יוואווה", "כלב הרים ברנזי" או שם הכלב כדי להתאים את הפתרון לקלט כשמקבלים את התגובה מה-API.
penaltyCost double זו עלות הקנס שנגבית אם האופטימיזציה מדלגת על המשלוח הזה. כברירת מחדל, המשלוחים הם חובה – הכלי לאופטימיזציה נותן עדיפות למזעור הדילוג על משלוחי חובה, ומדלג עליהם רק כשאין אפשרות אחרת. הגדרת עלות קנס מאפשרת לכלי האופטימיזציה לדלג על משלוח אם הוא לא אפשרי או יקר מדי לביצוע, ומאפשרת לכם לשקול את סדרי העדיפויות בין המשלוחים. בתרחיש הזה, אתם מגדירים עלות קנס גבוהה יותר (1000) ללקוחות הקבועים (כלב הרים שוויצרי וצ'יוואווה) ועלות קנס נמוכה יותר (100) לבקשה של הרגע האחרון לרועה גרמני. כך כלי האופטימיזציה יודע לתת עדיפות ללקוחות הקבועים, ולדלג קודם על הרועה הגרמני אם אי אפשר לבצע את כל האיסופים.
VisitRequest arrivalWaypoint אובייקט (Waypoint) זה המיקום של ביקור ספציפי במסלול. אפשר להגדיר את זה באמצעות קואורדינטות של קו רוחב וקו אורך, מזהה מקום או כיוון. בתרחיש הזה של מעון יום לכלבים, צריך להגדיר את המיקום שסופק על ידי הבעלים בשביל pickups ואת הכתובת של מעון היום בשביל deliveries.
timeWindows[] מערך של אובייקטים (TimeWindow) זהו מערך של אובייקטים שמגדירים את מגבלות הזמן לאיסוף או למשלוח. בתרחיש הזה, נשתמש בזה כדי להגדיר את חלון האיסוף של כל אחד מהכלבים ואת החלון המקובל להורדת הכלבים במעון.
duration משך הפרמטר הזה מציין את משך הביקור (למשל, זמן הטעינה או הפריקה). בתרחיש הזה, אתם מגדירים זמן המתנה של 5 דקות (300s) לכל האיסופים והמשלוחים כדי להביא בחשבון את הזמן שלוקח לנהג להעלות את הכלבים לרכב ולהוריד אותם ממנו.
Vehicle startWaypoint אובייקט (Waypoint) זהו מיקום ההתחלה של מסלול הרכב, שמוגדר באמצעות קואורדינטות של קו רוחב וקו אורך או מזהה מקום. הפרמטר הזה מציין לכלי האופטימיזציה איפה הרכב צריך להתחיל את המסלול. אם לא מגדירים את נקודת הדרך הזו, הכלי לאופטימיזציה בוחר באחת מנקודות האיסוף או המסירה כמיקום ההתחלה. בתרחיש הזה של מעון הכלבים, הנהג מתחיל את היום במעון, אז צריך להשתמש בקואורדינטות של Mission Dolores Park.
endWaypoint אובייקט (Waypoint) זהו היעד הסופי של מסלול הרכב, שמוגדר באמצעות קואורדינטות של קו רוחב וקו אורך או מזהה מקום. הפרמטר הזה מציין לכלי האופטימיזציה איפה הרכב צריך לסיים את המסלול. אם לא מגדירים את נקודת הדרך הזו, כלי האופטימיזציה בוחר באחד מהאיסופים או המשלוחים כסוף המסלול. בתרחיש הזה של מעון הכלבים, הנהג צריך לסיים את היום במעון, ולכן צריך להשתמש בקואורדינטות של Mission Dolores Park.
costPerHour number זו העלות שנגבית על כל שעה שבה משתמשים ברכב, לא משנה אם הוא בנסיעה או בעצירה. בתרחיש הזה של מעון יום לכלבים, משתמשים בזה כדי ליצור מודל של שכר שעתי לנהג.
startTimeWindows[] מערך של אובייקטים (TimeWindow) זהו חלון הזמן המקובל שבו הנהג יכול להתחיל את המשמרת שלו. בתרחיש הזה של מעון יום לכלבים, מגדירים את startTime בתור 7:00, אבל משמיטים את endTime. כך כלי האופטימיזציה יכול לדחות את תחילת המשמרת אם האיסוף הראשון מתבצע בשעה מאוחרת יותר בבוקר. שימו לב שגם אם לא תציינו endTime ל-startTimeWindows, שעת ההתחלה תוגבל באופן משתמע על ידי endTimeWindows. הרכב חייב להתחיל את המסלול לפני שהמסלול מסתיים.
endTimeWindows[] מערך של אובייקטים (TimeWindow) זהו חלון הזמן המקובל שבו הנהג צריך לסיים את המסלול. בתרחיש הזה של מעון יום לכלבים, מגדירים את endTime כצהריים אבל משמיטים את startTime. כך הנהג יכול לחזור למעון מיד אחרי ההורדה האחרונה.

הבא

פירוש התשובה