Crie um serviço de otimização de vários itinerários

Este guia explica como usar o Azure Maps e o NVIDIA cuOpt para criar um serviço de otimização de itinerário. Este serviço automatiza o processo de construção de itinerários para vários agentes e frotas mistas, utilizando o motor de otimização de rotas NVIDIA cuOpt para otimizar rotas em vários destinos.

Este é um processo de duas etapas que requer uma matriz de custos para o tempo de viagem e um solucionador para otimizar o problema e gerar um resultado. Uma matriz de custos representa o custo de viajar entre cada dois conjuntos de locais no problema, o que inclui o custo do tempo de viagem e outros custos de viagem.

Este artigo descreve como:

• Introdução ao NVIDIA cuOpt no Azure Marketplace.
• Use a API da Matriz de Rotas do Azure Maps para obter o custo da viagem.
• Como mapear o problema para chamadas de API cuOpt.
• Como usar a resposta cuOpt.
• Chame a API de Rotas do Azure Maps para roteamento.

Consulte o exemplo de código de otimização de itinerário múltiplo para um início rápido.

Pré-requisitos

• Uma conta do Azure Maps
• Uma chave de subscrição ou outra forma de Autenticação com o Azure Maps

Suporte de serviço

Este serviço pode suportar os seguintes recursos e restrições.

Para obter a lista completa de recursos suportados, consulte Recursos suportados pelo cuOpt.

Introdução ao NVIDIA cuOpt no Azure Marketplace

O NVIDIA cuOpt usa o solucionador de logística acelerado por GPU e otimizações para calcular problemas complexos de roteamento de veículos com uma ampla gama de restrições. Para obter mais informações, consulte a Lista de recursos suportados pelo cuOpt.

O cuOpt está incluído no NVIDIA AI Enterprise. Visite o Azure Marketplace para começar.

Obtenha o custo da viagem

A otimização do itinerário requer uma matriz quadrada de uma métrica de viagem, como o custo de tempo ou distância, que é passada para o solucionador cuOpt. Uma matriz de custos representa o custo de viagem entre cada par de locais no conjunto de problemas, permitindo um planejamento e otimização de rotas eficientes.

A API da Matriz de Rotas do Azure Maps calcula métricas de viagem, como tempo e distância, de cada origem a cada destino. Essas origens e destinos formam os cabeçalhos de coluna e linha de uma matriz de custo, onde cada célula representa o custo de roteamento entre um par origem-destino específico.

Por exemplo, um restaurante tem dois motoristas que precisam entregar comida em quatro locais. Para resolver esse cenário, use a API da matriz de rotas para calcular os tempos de viagem entre todos os pontos relevantes. Este exemplo pressupõe que ambos os motoristas começam e terminam no restaurante. Se os locais de início ou fim forem diferentes do depósito, esses locais devem ser explicitamente incluídos na matriz de custos.

Número de origens = Número de destinos = 1 (restaurante, também referido como depósito) + 4 (locais de entrega) = 5

Tamanho da matriz = 5 origens x 5 destinos = 25

A solicitação POST da matriz de rotas:

https://atlas.microsoft.com/route/matrix?api-version=2025-01-01&routeType=shortest&subscription-key={Your-Azure-Maps-Subscription-key}

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "geometry": {
        "type": "MultiPoint",
        "coordinates": [
            [4.85106, 52.36006], //restaurant or depot 
            [4.85056, 52.36187], //delivery location 1 
            [4.85003, 52.36241], //delivery location 2 
            [4.42937, 52.50931], //delivery location 3 
            [4.42940, 52.50843]  //delivery location 4 
        ]
      },
      "properties": {
        "pointType": "origins"
      }
    },
    {
      "type": "Feature",
      "geometry": {
        "type": "MultiPoint",
        "coordinates": [
            [4.85106, 52.36006], //restaurant or depot 
            [4.85056, 52.36187], //delivery location 1 
            [4.85003, 52.36241], //delivery location 2 
            [4.42937, 52.50931], //delivery location 3 
            [4.42940, 52.50843]  //delivery location 4 
        ]
      },
      "properties": {
        "pointType": "destinations"
      }
    }
  ]
}

A resposta Route Matrix retorna uma matriz multidimensional 5x5 onde cada linha representa as origens e as colunas representam os destinos. Use o campo travelTimeInSeconds para obter o custo de tempo para cada par de locais. A unidade de tempo deve ser consistente em toda a solução. Uma vez concluída a etapa de pré-processamento, o pedido, o depósito, as informações da frota e a matriz de custos são enviados e importados para o cuOpt Server por meio de chamadas API.

O exemplo JSON a seguir mostra o que é retornado no corpo da resposta HTTP do exemplo de matriz de custo:

cost_matrix_data = [
    [ 0, 10,  8,  6, 10], 
    [10,  0, 12,  8,  6], 
    [ 8, 16,  0,  8,  4], 
    [ 2,  8,  6,  0,  8], 
    [ 6,  6, 10, 12,  0], 
] 

Mapeie o problema com chamadas da API cuOpt

Esta seção descreve como criar dados de solicitação para chamadas cuOpt. Para obter mais exemplos, consulte as práticas recomendadas do cuOpt.

1. Definir matriz de custos
2. Definir dados da frota
3. Definir dados da tarefa
4. Definir configuração do Solver (opcional)

Definir matriz de custos

Analise a resposta da API da Matriz de Rotas do Azure Maps para obter o tempo de viagem entre locais para construir a matriz de custos. No exemplo a seguir, "0" representa a chave que representa um tipo de veículo específico.

"data": {" cost_matrix_data ": {
    "data": {
    "0": [
        [0, 5, 4, 3, 5],
        [5, 0, 6, 4, 3],
        [4, 8, 0, 4, 2],
        [1, 4, 3, 0, 4],
        [3, 3, 5, 6, 0]
    ]
    }}}

Opcionalmente, podem ser fornecidas várias matrizes de custos, dependendo dos tipos de veículos. Alguns veículos podem viajar mais rápido, enquanto outros podem incorrer em mais custos ao viajar por determinadas áreas. Isso pode ser modelado usando mais matrizes de custo, uma para cada tipo de veículo. O próximo exemplo tem duas matrizes, "0" representa o primeiro veículo, que pode ser um carro e "1" representa o segundo veículo, que pode ser um caminhão. Note-se que, se a sua frota tiver veículos com perfis semelhantes, terá de especificar a matriz de custos apenas uma vez.

"data": {" cost_matrix_data ": {
    "data": {
    "0": [
        [0, 5, 4, 3, 5],
        [5, 0, 6, 4, 3],
        [4, 8, 0, 4, 2],
        [1, 4, 3, 0, 4],
        [3, 3, 5, 6, 0]
    ],
    "1": [
        [0, 4, 2, 3, 3],
        [2, 0, 6, 5, 3],
        [3, 8, 0, 3, 2],
        [1, 5, 3, 0, 4],
        [3, 4, 5, 7, 0]
    ],
    }}}

Definir dados da frota

Os dados da frota podem descrever a descrição da frota, como o número de veículos, a sua localização inicial/final e a capacidade do veículo que são utilizados pelo solucionador para determinar quais os veículos disponíveis para realizar a tarefa dentro das restrições.

{
     "fleet_data": {
        "vehicle_locations": [
            [0,1], [0,1]
        ],
        "capacities": [[2,3]],
"vehicle_time_windows": [
        [0, 80],
        [1, 40]
    ],
"vehicle_break_time_windows":[
        [
            [20, 25],
            [20, 25]
        ]
    ],
"vehicle_break_durations": [[1, 1, 1, 1, 1]]
        }
    }

• Localização dos veículos: No exemplo acima, os dados da frota indicam dois veículos, uma matriz para cada veículo. Ambos os veículos começam no local 0 e terminam a viagem no local 1. No contexto de uma descrição do ambiente pela matriz de custos, estas localizações de veículos correspondem a índices de linha (ou coluna) na matriz de custos.
• Capacidades: O conjunto de capacidades indica a capacidade do veículo; o primeiro veículo tem uma capacidade de dois e o segundo veículo tem uma capacidade de três. A capacidade pode representar várias coisas, por exemplo, peso do pacote, habilidades de serviço e suas quantidades transportadas por cada veículo. Na próxima seção, você criará um JSON de tarefa que exigirá uma dimensão de necessidade para cada local de tarefa e o número de dimensões de necessidade corresponderá ao número de dimensões de capacidade nos dados da frota. Por exemplo, se um caminhão está entregando mercadorias, a capacidade seria quanto peso no total cada veículo pode transportar, e a demanda seria o peso de cada pedido. Certifique-se de que a mesma unidade é usada para ambos (como libras ou quilogramas).
• Janelas de tempo do veículo: As janelas de tempo especificam o tempo de funcionamento do veículo para concluir as tarefas. Esta pode ser a hora de início e fim do turno do agente. Os dados brutos podem incluir o formato de data/hora Universal Time Stamp (UTC) ou o formato de cadeia de caracteres que deve ser convertido em valor flutuante. (Exemplo: 9:00 am - 6:00 pm convertido em minutos num período de 24 horas a partir das 0:00, seria [540, 1080]). Todas as unidades de tempo/custo fornecidas ao solucionador cuOpt devem estar na mesma unidade.
• Pausas do veículo: Os períodos de paragem do veículo e a respetiva duração também podem ser especificados. Isso pode representar a pausa para o almoço do agente, ou outras pausas, conforme necessário. O formato da janela de pausa seria o mesmo que o formato da janela de tempo do veículo. Todas as unidades de tempo/custo fornecidas ao solucionador cuOpt devem estar na mesma unidade.

Definir dados da tarefa

As tarefas definem o objetivo que deve ser cumprido dentro das restrições. No contexto da entrega na última milha, isso pode incluir os locais de entrega, a quantidade de demanda em cada local, a janela de entrega e o tempo de permanência para cada local.

"task_data": {
        "task_locations": [1, 2, 3, 4], 
        "demand": [[3, 4, 4, 3]], 
        "task_time_windows": [[8, 17], [8, 17], [8, 17], [17, 20]], 
        "service_times": [0, 0, 0, 0]
}

• Local da tarefa: No exemplo acima, task_locations indicar o local de entrega localizado nas posições 1, 2, 3 e 4. Esses locais correspondem a índices de linha (ou coluna) na matriz de custos.
• Demanda: A matriz de demanda indica a quantidade de demanda em cada local; A primeira localização tem uma procura de 3, a segunda e terceira localização tem 4 e a última localização tem 3. A contagem das dimensões da procura deve corresponder ao número de dimensões de capacidade de cada veículo.
• Janela de tempo da tarefa: as restrições da janela de tempo especificam quando uma tarefa deve ser concluída. A cada tarefa é atribuída uma janela de tempo de início e fim, e a tarefa deve ser concluída dentro dela. Os dados brutos podem incluir o formato de data/hora Universal Time Stamp (UTC) ou o formato de cadeia de caracteres que deve ser convertido em valor flutuante. (Exemplo: 9:00 am - 6:00 pm convertido em minutos num período de 24 horas a partir das 0:00, seria [540, 1080]). Todas as unidades de tempo/custo fornecidas ao solucionador cuOpt devem estar na mesma unidade.
• Tempos de serviço: representa a duração necessária para concluir as tarefas. A matriz service_times especifica a duração do tempo para cada local de tarefa. Todas as unidades de tempo/custo fornecidas ao solucionador cuOpt devem estar na mesma unidade.

Definir configuração do Solver (opcional)

Opcionalmente, você pode especificar a configuração do solucionador para alocar um tempo máximo para encontrar uma solução. Isso depende do caso de uso, e definir um limite de tempo mais alto retorna melhores resultados.

        "solver_config": {
         "time_limit": 1
        }

Como usar a resposta cuOpt

O solucionador cuOpt devolve a paragem otimizada para cada veículo e o itinerário de viagem. Analise a resposta e converta cada local em um ponto de coordenadas antes de chamar a API de Direções de Rota do Azure Maps para obter as rotas. Essas rotas otimizadas incluem o caminho da rota e as direções de condução para cada agente.

Dados de solicitação de amostra

{
"requestBody": {
"data": {"cost_matrix_data": {"data": {"1": [[0, 5, 4, 3, 5], [5, 0, 6, 4, 3], [4, 8, 0, 4, 2], [1, 4, 3, 0, 4], [3, 3, 5, 6, 0]]}},
"fleet_data": {
        "vehicle_locations": [[0, 0], [0, 0]], 
        "vehicle_ids": ["Car-A", "Car-B"], 
        "vehicle_types": [1, 1], 
        "capacities": [[75, 75]], 
        "vehicle_time_windows": [[8, 18], [8, 17]], 
        "vehicle_break_time_windows": [[[12, 14], [12, 14]]], 
        "vehicle_break_durations": [[0, 0]]
}, 
"task_data": {
        "task_locations": [1, 2, 3, 4], 
        "demand": [[30, 40, 40, 30]], 
        "task_time_windows": [[8, 17], [8, 17], [8, 17], [17, 15]], 
        "service_times": [0, 0, 0, 0]
},
"solver_config": {
         "time_limit": 1
        }},
    "client_version": ""
    }
}

Resposta da amostra

  "reqId": "4bdc2610-d821-48dc-b53f-57698015bb2e",
  "status": "fulfilled",
  "percentComplete": 100,
  "response": {
    "response": {
      "solver_response": {
        "status": 0,
        "num_vehicles": 2,
        "solution_cost": 19.0,
        "vehicle_data": {
          "Car-A": {
            "task_id": [
              "Depot",
              "Break",
              "0",
              "2",
              "Depot"
            ],
            "arrival_stamp": [
              8.0,
              13.0,
              13.0,
              17.0,
              18.0
            ],
            "route": [
              0,
              1,
              1,
              3,
              0
            ],
            "type": [
              "Depot",
              "Break",
              "Delivery",
              "Delivery",
              "Depot"
            ]
          },
          "Car-B": {
            "task_id": [
              "Depot",
              "Break",
              "1",
              "3",
              "Depot"
            ],
            "arrival_stamp": [
              8.0,
              12.0,
              12.0,
              14.0,
              17.0
            ],
            "route": [
              0,
              2,
              2,
              4,
              0
            ],
            "type": [
              "Depot",
              "Break",
              "Delivery",
              "Delivery",
              "Depot"
            ]
          }
        },
        "msg": ""
      }
    }
  }
}

Chame a Azure Maps Route Directions API para obter direções de rotas

Depois que os locais na resposta cuOpt são mapeados para as coordenadas correspondentes, o serviço cuOpt pode ser usado com a API de Rotas do Azure Maps e o SDK da Web para criar um aplicativo Web que exiba os itinerários atribuídos e as rotas otimizadas no mapa. Você pode codificar por cores o caminho da rota para veículos individuais com base nas paradas atribuídas e exibi-lo nos dados de base do Azure Maps.

Próximos passos