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

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

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

דוגמה לבקשה

      {
        "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 מציינים אם הפונקציה RouteOptimization צריכה להחזיר קווים פוליגוניים.

השירות מקודד קווים פוליגוניים באמצעות קודק הקווים הפוליגוניים של Maps 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 מוגדרות ברכב.

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

מאפייני התגובה של Route Optimization

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

    {
      "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 מייצג את כלי הרכב שנוסע ממיקום אחד למיקום הבא. מעברים יכולים להתרחש בין זוגות של נקודת ההתחלה של הרכב, מיקום ביקור ונקודת הסיום של הרכב.

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

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 כדי שהכלי לאופטימיזציה ימצא מסלול אופטימלי (ולא סתם מסלול אפשרי).