Otimização básica de pedidos de parada para retiradas e entregas

Esse cenário otimiza a ordem das paradas atribuídas a um veículo com parâmetros de custo simples. Esse é o modo mais simples de operação da otimização de trajeto e garante que todas as paradas sejam visitadas no período especificado.

O exemplo a seguir ilustra um cenário básico com um veículo e três envios, todos originados de um único local chamado depósito.

Confira um exemplo de solicitação

      {
        "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 da solicitação de otimização de trajetos

Conforme mencionado na Visão geral, as propriedades de solicitação mais importantes da otimização de rotas são vehicles e shipments.

Além de um veículo e remessas, a solicitação inclui os seguintes campos:

Polilinhas

populatePolylines e populateTransitionPolylines especificam se a otimização de rotas precisa retornar polilinhas.

O serviço codifica polilinhas usando o codec de polilinha do Maps JS, que representa dados de polilinha binária usando caracteres ASCII imprimíveis. Você pode usar o Utilitário interativo de codificação de polilinhas para visualizar os caminhos calculados pela otimização de rotas. O exemplo neste guia define populatePolylines e populateTransitionPolylines como verdadeiros, mas outros guias os definem como falsos para reduzir o tamanho da resposta.

Consulte Formato do algoritmo de polilinha codificada para conferir uma descrição do formato de codificação.

Importante: o Route Optimization converte os caracteres de barra invertida (\) em polilinhas para barra invertida dupla (\\), de acordo com as orientações do Formato do algoritmo de polilinha codificada. No entanto, o Utilitário interativo de codificação de polilinhas espera barras invertidas (\) sem escape na entrada de polilinha codificada. Antes de decodificar uma poligonal retornada pela Otimização de rotas, substitua as barras invertidas duplas por barras invertidas simples.

Restrições de tempo globais

model.globalStartTime e model.globalEndTime são definidos como um período arbitrário de 24 horas. Isso facilita a interpretação dos carimbos de data/hora de saída.

Visitar locais

A solicitação de exemplo usa apenas model.shipments[].pickups[].arrivalLocation e model.shipments[].deliveries[].arrivalLocation. Há também uma propriedade departureLocation para situações em que o veículo sai de um ponto diferente de onde chega, como um complexo de estacionamento com uma entrada em um lado do edifício e uma saída em outro. Neste e nos próximos guias, os pontos de chegada e partida são considerados iguais.

Os campos waypoint de chegada e partida também são uma alternativa a latLng. Os campos Waypoint oferecem suporte ao uso de IDs de lugar do Google como uma alternativa a LatLng e também podem especificar direções do veículo. Consulte a documentação de referência (REST, gRPC) para mais detalhes.

Restrições no exemplo

Esse cenário restringe o otimizador de várias maneiras:

1. Toda a atividade precisa ser concluída entre os horários de início e término globais. Nesse cenário, os horários de início e término são uma restrição muito flexível, devido à proximidade dos envios e à ampla janela de tempo global.
2. Todos os envios precisam ser concluídos. Esse é o comportamento padrão quando os custos de penalidade não são especificados em shipments.
3. costPerKilometer e costPerHour estão definidos no veículo.

Os custos são abordados em Parâmetros do modelo de custo.

Aviso: especifique pelo menos um parâmetro de custo. Sem parâmetros de custo restringindo o ShipmentModel, a Otimização de rotas retorna qualquer rota que possa ser concluída no período de tempo permitido, independentemente do comprimento ou da duração.

Propriedades de resposta da Otimização de trajetos

Confira uma resposta para o exemplo de solicitação

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

A resposta da otimização de rotas inclui um campo routes de nível superior que representa as rotas propostas, com uma rota por veículo. Como a solicitação de exemplo neste guia especifica apenas um veículo, o routes inclui uma mensagem ShipmentRoute.

ShipmentRoute propriedades

As duas propriedades mais importantes para o tipo de mensagem ShipmentRoute são visits e transitions.

Cada Visit representa a conclusão de uma coleta ou entrega de uma das VisitRequests da mensagem de solicitação. Uma visita é um trabalho atribuído para ser realizado por um veículo em um determinado lugar e horário.

Cada Transition representa o veículo que viaja de um local para o seguinte. As transições podem ocorrer entre um par de pontos de partida do veículo, um local de visita e o ponto final do veículo.

Para reconstruir o trajeto completo do veículo, o visits e o transitions do ShipmentRoute precisam ser combinados. A combinação de campos em uma progressão da atividade do veículo é semelhante a esta:

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

Um ShipmentRoute sempre tem um transitions a mais do que visits, porque o veículo precisa viajar do local de partida até a primeira visita no início da rota e da última visita até o local de chegada no fim da rota. Se o veículo não tiver um local de início ou de término, ainda haverá um transitions a mais do que visits, porque o local da primeira ou da última visita é usado como o local de início ou de término do veículo, respectivamente.

Neste exemplo, as três primeiras visitas de retirada têm transições entre elas com distância e duração zero, porque as três retiradas compartilham o mesmo local na solicitação.

Consulte a documentação de referência ShipmentRoute (REST, gRPC) para mais detalhes.

Observação: os campos que terminam com Index refletem a posição de uma mensagem correspondente conforme ela apareceu na solicitação. Quando o valor de um campo Index é zero, a API o omite da resposta. Na resposta de exemplo, a primeira entrada visits é uma coleta que corresponde a shipments[0] na mensagem de solicitação.

Observação: se os envios omitirem visitas de coleta, o otimizador vai assumir que os veículos começam com os envios já carregados. Nesse caso, recursos como UnloadingPolicy (FIFO ou LIFO) não se aplicam porque não há uma sequência de coleta.

Otimização simples da ordem dos pontos de passagem

Como demonstrado neste exemplo, os modelos de Otimização de rotas consideram as visitas como propriedades de envios e não têm noção de pontos de passagem ou paradas como uma entidade independente. No entanto, é possível representar paradas ou pontos de passagem como remessas com exatamente um VisitRequest como retirada ou entrega. O veículo ainda precisa ser atribuído a um costPerHour ou costPerKilometer para que o otimizador encontre uma rota ideal, em vez de encontrar qualquer rota viável.