Optimización básica de pedidos de paradas para retiros y entregas

En esta situación, se optimiza el orden de las paradas asignadas a un vehículo con parámetros de costo simples. Este es el modo más simple de la operación de optimización de rutas y garantiza que se visiten todas las paradas dentro del período especificado.

En el siguiente ejemplo, se muestra una situación básica con un vehículo y tres envíos, todos desde una única ubicación denominada depósito.

Consulta una solicitud de ejemplo

      {
        "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
            }
          ]
        }
      }
    

Campos de la solicitud de optimización de rutas

Como se mencionó en la Descripción general, las propiedades más importantes de la solicitud de optimización de rutas son vehicles y shipments.

Además de un vehículo y los envíos, la solicitud incluye los siguientes campos:

Polilíneas

populatePolylines y populateTransitionPolylines especifican si la optimización de rutas debe mostrar polilíneas.

El servicio codifica polilíneas con el códec de polilínea de Maps JS, que representa datos binarios de polilíneas con caracteres ASCII imprimibles. Puedes utilizar la utilidad codificadora de polilínea interactiva para visualizar las rutas calculadas por la optimización de rutas. En el ejemplo de esta guía, se establecen populatePolylines y populateTransitionPolylines como verdaderos, pero otras guías los establecen en falso para reducir el tamaño de la respuesta.

Consulta Formato del algoritmo de polilínea codificada para obtener una descripción del formato de codificación.

Importante: La optimización de rutas convierte los caracteres de barra inversa (\) en las polilíneas en doble barra inversa (\\), según las indicaciones del Formato del algoritmo de polilínea codificada. Sin embargo, la utilidad codificadora de polilínea interactiva espera barras diagonales inversas únicas sin escape (\) en su entrada de polilínea codificada. Antes de decodificar una polilínea que muestra la optimización de rutas, reemplaza las barras inversas dobles por barras inversas individuales.

Las limitaciones de tiempo globales

model.globalStartTime y model.globalEndTime se configuran en un período arbitrario de 24 horas. Esto hace que las marcas de tiempo de salida sean más fáciles de interpretar.

Visitar ubicaciones

La solicitud de ejemplo solo usa model.shipments[].pickups[].arrivalLocation y model.shipments[].deliveries[].arrivalLocation. También hay una propiedad departureLocation para situaciones en las que el vehículo sale de un punto diferente al que llega, como un complejo de estacionamiento con una entrada en un lado del edificio y una salida en otro. En esta guía y en las subsiguientes, se supone que los puntos de llegada y de salida son los mismos.

Los valores de llegada y salida de waypoint también existen como alternativa a latLng. Los campos Waypoint admiten el uso de los IDs de lugar de Google como alternativa a LatLng y también pueden especificar orientaciones de vehículos. Consulta la documentación de referencia (REST, gRPC) para obtener más detalles.

Restricciones del ejemplo

En esta situación, se restringe el optimizador de varias maneras:

1. Toda la actividad debe completarse entre las horas de inicio y finalización globales. En esta situación, las horas de inicio y finalización son una restricción muy laxa dada la proximidad a los envíos y el amplio margen temporal global.
2. Se deben completar todos los envíos. Este es el comportamiento predeterminado cuando no se especifican los costos de penalización en shipments.
3. Se configuraron costPerKilometer y costPerHour en el vehículo.

Los costos se abordan en los parámetros del modelo de costos.

Advertencia: Asegúrate de especificar al menos un parámetro de costo. Si los parámetros de costo que limitan el ShipmentModel, la optimización de rutas muestra cualquier ruta que se puede completar en el período permitido, sin importar la duración o la duración.

Propiedades de respuesta de la optimización de rutas

Cómo ver una respuesta a la solicitud de ejemplo

    {
      "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
        }
      }
    }
    

La respuesta de optimización de rutas incluye un campo routes de nivel superior que representa las rutas propuestas, con una ruta por vehículo. Como la solicitud de ejemplo de esta guía especifica solo un vehículo, routes incluye un mensaje ShipmentRoute.

ShipmentRoute propiedades

Las dos propiedades más importantes del tipo de mensaje ShipmentRoute son visits y transitions.

Cada Visit representa la finalización de un retiro o una entrega desde uno de los VisitRequest del mensaje de solicitud. Una visita es un trabajo asignado efectivamente a un vehículo en algún lugar y horario.

Cada Transition representa el vehículo que viaja de una ubicación a la siguiente. Las transiciones pueden ocurrir entre un par del punto de partida del vehículo, una ubicación de visita y el extremo del vehículo.

Para reconstruir la ruta completa del vehículo, se deben combinar el visits y el transitions de ShipmentRoute. La combinación de campos en una progresión de la actividad del vehículo se ve de la siguiente manera:

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

Un ShipmentRoute siempre tiene un transitions más que visits, ya que el vehículo debe viajar desde su ubicación de inicio hasta su primera visita al comienzo de la ruta y desde su última visita hasta su ubicación final al final de la ruta. Si el vehículo no tiene una ubicación de partida o de destino, habrá una transitions más que visits porque la ubicación de la primera o la última visita se usa como ubicación de partida o de finalización del vehículo, respectivamente.

En este ejemplo, las tres primeras visitas de retiro tienen transiciones entre ellas sin distancia y duración de cero porque los tres puntos de partida comparten la misma ubicación en la solicitud.

Consulta la documentación de referencia de ShipmentRoute (REST, gRPC) para obtener más detalles.

Nota: Los campos que terminan con Index reflejan la posición de un mensaje correspondiente tal como apareció en la solicitud. Cuando el valor de un campo Index es cero, la API lo omite de la respuesta. En la respuesta de ejemplo, la primera entrada visits es una partida que corresponde a shipments[0] en el mensaje de solicitud.

Nota: Si los envíos omiten las visitas de retiro, el optimizador supone que los vehículos comienzan con los envíos ya cargados. En este caso, es posible que no se apliquen funciones como UnloadingPolicy (FIFO o LIFO) porque no hay una secuencia de retiro.

Optimización sencilla del orden de puntos de referencia

Como se demuestra en este ejemplo, la optimización de rutas modela las visitas como propiedades de envíos y no tiene una noción de puntos de referencia ni paradas como una entidad independiente. Sin embargo, es posible representar paradas o puntos de referencia como envíos con exactamente un VisitRequest como retiro o entrega. Al vehículo se le debe asignar un costPerHour o un costPerKilometer para que el optimizador encuentre una ruta óptima (en lugar de cualquier ruta posible).