בתרחיש הזה מתבצעת אופטימיזציה של סדר התחנות שהוקצו לרכב באמצעות פרמטרים פשוטים של עלות. זהו המצב הפשוט ביותר של אופן הפעולה של אופטימיזציית המסלולים, והוא מבטיח שכל התחנות ייכללו במסלול במסגרת מסגרת הזמן שצוינה.
הדוגמה הבאה ממחישה תרחיש בסיסי עם רכב אחד ושלוש משלוחים, כולם מגיעים ממיקום אחד שנקרא מחסן.
דוגמה לבקשה
{
"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
}
]
}
}
שדות הבקשה של Route Optimization
כפי שצוין בסקירה הכללית, מאפייני הבקשה החשובים ביותר של אופטימיזציית מסלולים הם vehicles ו-shipments.
בנוסף לרכב ולמשלוחים, הבקשה כוללת את השדות הבאים:
קווים פוליגונים
populatePolylines ו-populateTransitionPolylines מציינים אם האופטימיזציה של המסלולים תחזיר קווים פוליגונליים.
השירות מצפין קווים פוליגונליים באמצעות הקודק של קווים פוליגונליים ב-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).
האילוצים בדוגמה
התרחיש הזה מגביל את האופטימיזטור בכמה דרכים:
- כל הפעילות צריכה להתבצע בין שעת ההתחלה לשעת הסיום הגלובלית. בתרחיש הזה, שעות ההתחלה והסיום הן אילוצים גמישים מאוד, בהתחשב בקרבת המשלוחים ובחלון הזמן הגלובלי הרחב.
- כל המשלוחים חייבים להסתיים. זוהי התנהגות ברירת המחדל כשעלויות העונש לא מצוינות ב-
shipments. 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
}
}
}
התשובה של Route Optimization כוללת את השדה 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 כדי שהאופטימיזטור יוכל למצוא מסלול אופטימלי (לעומת חיפוש של כל מסלול אפשרי).