אופטימיזציה בסיסית של הזמנות ביניים לאיסוף ולמשלוחים

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

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

הצגת בקשה לדוגמה

      {
        "populatePolylines": true,
        "populateTransitionPolylines": true,
        "model": {
          "globalStartTime": "2023-01-13T16:00:00-08:00",
          "globalEndTime": "2023-01-14T16:00:00-08:00",
          "shipments": [
            {
              "deliveries": [
                {
                  "arrivalLocation": {
                    "latitude": 37.789456,
                    "longitude": -122.390192
                  },
                  "duration": "250s"
                }
              ],
              "pickups": [
                {
                  "arrivalLocation": {
                    "latitude": 37.794465,
                    "longitude": -122.394839
                  },
                  "duration": "150s"
                }
              ]
            },
            {
              "deliveries": [
                {
                  "arrivalLocation": {
                    "latitude": 37.789116,
                    "longitude": -122.395080
                  },
                  "duration": "250s"
                }
              ],
              "pickups": [
                {
                  "arrivalLocation": {
                    "latitude": 37.794465,
                    "longitude": -122.394839
                  },
                  "duration": "150s"
                }
              ]
            },
            {
              "deliveries": [
                {
                  "arrivalLocation": {
                    "latitude": 37.795242,
                    "longitude": -122.399347
                  },
                  "duration": "250s"
                }
              ],
              "pickups": [
                {
                  "arrivalLocation": {
                    "latitude": 37.794465,
                    "longitude": -122.394839
                  },
                  "duration": "150s"
                }
              ]
            }
          ],
          "vehicles": [
            {
              "endLocation": {
                "latitude": 37.794465,
                "longitude": -122.394839
              },
              "startLocation": {
                "latitude": 37.794465,
                "longitude": -122.394839
              },
              "costPerKilometer": 10.0,
              "costPerHour": 40.0
            }
          ]
        }
      }
    

שדות הבקשה לאופטימיזציה של ניתוב

כפי שצוין בסקירה הכללית, הבקשה החשובה ביותר לאופטימיזציה של המסלול הנכסים הם vehicles ו-shipments.

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

קווים פוליגוניים

populatePolylines ו-populateTransitionPolylines מציינים אם נתיב האופטימיזציה צריכה להחזיר קווים פוליגוניים.

השירות מקודד קווים פוליגוניים באמצעות קודק ה-Polyline של מפות Google JS, שמייצג נתוני קו פוליגוני בינארי באמצעות תווי ASCII שניתנים להדפסה. אפשר להשתמש בכלי המקודד האינטראקטיבי של קווים פוליגונליים כדי להציג גרפית את הנתיבים שחושבו על ידי אופטימיזציית המסלולים. בדוגמה במדריך הזה, הערכים של populatePolylines ו-populateTransitionPolylines מוגדרים כ-true, אבל במדריכים אחרים הם מוגדרים כ-false כדי לצמצם את גודל התגובה.

לתיאור הקידוד, ראו פורמט אלגוריתם של קו מקודד הפורמט.

מגבלות זמן גלובליות

model.globalStartTime ו-model.globalEndTime מוגדרים ל-24 שרירותי פרק זמן של שעות. כך קל יותר לפרש את חותמות הזמן של הפלט.

ביקור במיקומים

הבקשה לדוגמה משתמשת רק ב-model.shipments[].pickups[].arrivalLocation ו- model.shipments[].deliveries[].arrivalLocation. יש גם מאפיין departureLocation למצבים שבהם הרכב יוצא במקום שהוא מגיע אליו, למשל מתחם חניה עם כניסה בצד אחד של הבניין ויציאה בצד אחר. בהודעה הזו ובהמשך נקודות ההגעה והיציאה הן זהות.

שעות ההגעה והיציאה מ-waypoint קיימות גם כחלופה ל-latLng. השדות Waypoint תומכים בשימוש במזהי מקומות ב-Google כחלופה ל-LatLng, ואפשר גם לציין כותרות של רכבים. מאמרי העזרה (REST, gRPC) לקבלת פרטים נוספים.

המגבלות בדוגמה

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

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

העלויות מפורטות בפרמטרים של מודל עלות.

מאפייני התגובה לאופטימיזציה של המסלול

הצגת תשובה לבקשה לדוגמה

    {
      "routes": [
        {
          "vehicleStartTime": "2023-01-14T00:00:00Z",
          "vehicleEndTime": "2023-01-14T00:36:41Z",
          "visits": [
            {
              "shipmentIndex": 2,
              "isPickup": true,
              "startTime": "2023-01-14T00:00:00Z",
              "detour": "0s"
            },
            {
              "shipmentIndex": 1,
              "isPickup": true,
              "startTime": "2023-01-14T00:02:30Z",
              "detour": "150s"
            },
            {
              "isPickup": true,
              "startTime": "2023-01-14T00:05:00Z",
              "detour": "300s"
            },
            {
              "startTime": "2023-01-14T00:11:25Z",
              "detour": "0s"
            },
            {
              "shipmentIndex": 1,
              "startTime": "2023-01-14T00:19:29Z",
              "detour": "503s"
            },
            {
              "shipmentIndex": 2,
              "startTime": "2023-01-14T00:29:02Z",
              "detour": "1324s"
            }
          ],
          "transitions": [
            {
              "travelDuration": "0s",
              "waitDuration": "0s",
              "totalDuration": "0s",
              "startTime": "2023-01-14T00:00:00Z",
              "routePolyline": {}
            },
            {
              "travelDuration": "0s",
              "waitDuration": "0s",
              "totalDuration": "0s",
              "startTime": "2023-01-14T00:02:30Z",
              "routePolyline": {}
            },
            {
              "travelDuration": "0s",
              "waitDuration": "0s",
              "totalDuration": "0s",
              "startTime": "2023-01-14T00:05:00Z",
              "routePolyline": {}
            },
            {
              "travelDuration": "235s",
              "travelDistanceMeters": 795,
              "waitDuration": "0s",
              "totalDuration": "235s",
              "startTime": "2023-01-14T00:07:30Z",
              "routePolyline": {
                "points": "kvteFtfjVAA?C?C@C?A?C@AFMj@s@JKb@k@Zc@LSjA}ARWDGdAxAdAvAXa@@k@AsA\\c@FKp@_A\\c@Ze@fA{ALSFGd@o@rAgBB{BZc@"
              }
            },
            {
              "travelDuration": "234s",
              "travelDistanceMeters": 793,
              "waitDuration": "0s",
              "totalDuration": "234s",
              "startTime": "2023-01-14T00:15:35Z",
              "routePolyline": {
                "points": "cwseFti_jVRWj@w@x@eAHLNRHJbApAHLX\\V^?@hA~AT\\PVFFDHDFJNp@~@NRLNNTFFUZIJY^Y^g@p@[`@KP{@fAEFSXe@l@c@h@WZY\\?BELk@v@MNa@l@"
              }
            },
            {
              "travelDuration": "323s",
              "travelDistanceMeters": 1204,
              "waitDuration": "0s",
              "totalDuration": "323s",
              "startTime": "2023-01-14T00:23:39Z",
              "routePolyline": {
                "points": "cuseFhjVSTY`@Yb@GHEDIJEF]f@IJi@r@oAbBeCfDKLaApAKNQVIPKPCDQJIBIBM@iAJeALqBVC@C?A?QBYDI@C?_@Dc@FO@a@FDp@HfAHvABVDl@Dj@PpCQDiALsALAQASKwAOgBEe@COCYEa@Es@Eg@"
              }
            },
            {
              "travelDuration": "209s",
              "travelDistanceMeters": 665,
              "waitDuration": "0s",
              "totalDuration": "209s",
              "startTime": "2023-01-14T00:33:12Z",
              "routePolyline": {
                "points": "{zteFxbajV?CAYEc@AMC_@AOAK?E?CCWAOAKCe@CY?WScDEm@d@EFA\\ENCB?XEVC^E`@EhBUVCNEB?@?\\Er@IMUe@k@k@w@AAMQa@i@SWQWMQi@u@AC?A"
              }
            }
          ],
          "routePolyline": {
            "points": "kvteFtfjVAA?C?C@C?A?C@AFMj@s@JKb@k@Zc@LSjA}ARWDGdAxAdAvAXa@@k@AsA\\c@FKp@_A\\c@Ze@fA{ALSFGd@o@rAgBB{BZc@RWj@w@x@eAHLNRHJbApAHLX\\V^?@hA~AT\\PVFFDHDFJNp@~@NRLNNTFFUZIJY^Y^g@p@[@KP{@fAEFSXe@l@c@h@WZY\\?BELk@v@MNa@l@STY@Yb@GHEDIJEF]f@IJi@r@oAbBeCfDKLaApAKNQVIPKPCDQJIBIBM@iAJeALqBVC@C?A?QBYDI@C?_@Dc@FO@a@FDp@HfAHvABVDl@Dj@PpCQDiALsALAQASKwAOgBEe@COCYEa@Es@Eg@?CAYEc@AMC_@AOAK?E?CCWAOAKCe@CY?WScDEm@d@EFA\\ENCB?XEVC^E`@EhBUVCNEB?@?\\Er@IMUe@k@k@w@AAMQa@i@SWQWMQi@u@AC?A"
          },
          "metrics": {
            "performedShipmentCount": 3,
            "travelDuration": "1001s",
            "waitDuration": "0s",
            "delayDuration": "0s",
            "breakDuration": "0s",
            "visitDuration": "1200s",
            "totalDuration": "2201s",
            "travelDistanceMeters": 3457
          },
          "travelSteps": [
            {
              "duration": "0s",
              "routePolyline": {}
            },
            {
              "duration": "0s",
              "routePolyline": {}
            },
            {
              "duration": "0s",
              "routePolyline": {}
            },
            {
              "duration": "227s",
              "distanceMeters": 794,
              "routePolyline": {
                "points": "kvteFtfjVAA?C?C@C?A?C@AFMj@s@JKb@k@Zc@LSjA}ARWDGdAxAdAvAXa@@k@AsA\\c@FKp@_A\\c@Ze@fA{ALSFGd@o@rAgBB{BZc@"
              }
            },
            {
              "duration": "233s",
              "distanceMeters": 791,
              "routePolyline": {
                "points": "cwseFti_jVRWj@w@x@eAHLNRHJbApAHLX\\V^?@hA~AT\\PVFFDHDFJNp@~@NRLNNTFFUZIJY^Y^g@p@[`@KP{@fAEFSXe@l@c@h@WZY\\?BELk@v@MNa@l@"
              }
            },
            {
              "duration": "322s",
              "distanceMeters": 1205,
              "routePolyline": {
                "points": "cuseFhjVSTY`@Yb@GHEDIJEF]f@IJi@r@oAbBeCfDKLaApAKNQVIPKPCDQJIBIBM@iAJeALqBVC@C?A?QBYDI@C?_@Dc@FO@a@FDp@HfAHvABVDl@Dj@PpCQDiALsALAQASKwAOgBEe@COCYEa@Es@Eg@"
              }
            },
            {
              "duration": "208s",
              "distanceMeters": 666,
              "routePolyline": {
                "points": "{zteFxbajV?CAYEc@AMC_@AOAK?E?CCWAOAKCe@CY?WScDEm@d@EFA\\ENCB?XEVC^E`@EhBUVCNEB?@?\\Er@IMUe@k@k@w@AAMQa@i@SWQWMQi@u@AC?A"
              }
            }
          ],
          "vehicleDetour": "2201s",
          "routeCosts": {
            "model.vehicles.cost_per_hour": 24.455555555555556,
            "model.vehicles.cost_per_kilometer": 34.57
          },
          "routeTotalCost": 59.025555555555556
        }
      ],
      "totalCost": 59.025555555555556,
      "metrics": {
        "aggregatedRouteMetrics": {
          "performedShipmentCount": 3,
          "travelDuration": "1001s",
          "waitDuration": "0s",
          "delayDuration": "0s",
          "breakDuration": "0s",
          "visitDuration": "1200s",
          "totalDuration": "2201s",
          "travelDistanceMeters": 3457
        },
        "usedVehicleCount": 1,
        "earliestVehicleStartTime": "2023-01-14T00:00:00Z",
        "latestVehicleEndTime": "2023-01-14T00:36:41Z",
        "totalCost": 59.025555555555556,
        "costs": {
          "model.vehicles.cost_per_kilometer": 34.57,
          "model.vehicles.cost_per_hour": 24.455555555555556
        }
      }
    }
    

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

ShipmentRoute מלונות

שני המאפיינים החשובים ביותר לסוג ההודעה ShipmentRoute הם visits ו-transitions.

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

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

כדי לשחזר את המסלול המלא של הרכב, צריך לשלב את visits ו-transitions של ShipmentRoute. שילוב השדות להתקדמות של פעילות הרכב נראית כך:

request.vehicles[0].startLocation -> transitions[0] -> visits[0] ->
transitions[1] -> visits[1] -> transitions[2] -> ... -> visits[3] ->
transitions[4] -> request.vehicles[0].endLocation

ל-ShipmentRoute יש תמיד אחד יותר transitions מ-visits, מכיוון הרכב חייב לנסוע מנקודת ההתחלה שלו עד הביקור הראשון שלו בהתחלה של המסלול ומהביקור האחרון שלו ועד למיקום הסיום שלו בסוף מסלול. אם לא נקבע מיקום התחלה או נקודת סיום לרכב, עדיין יהיה מיקום כזה יותר transitions מ-visits, כי המיקום של הביקור הראשון או האחרון הוא משמש כנקודת ההתחלה או הסיום של הרכב, בהתאמה.

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

מידע נוסף זמין במסמכי העזרה של ShipmentRoute (REST, gRPC) פרטים.

אופטימיזציה פשוטה של סדר ציון הדרך

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