Créer un service d’optimisation multi-itinéraires

​​​Ce guide explique comment utiliser Azure Maps et NVIDIA cuOpt pour créer un service d’optimisation des itinéraires. Ce service automatise le processus de création d’itinéraires pour plusieurs agents et flottes mixtes, en utilisant le moteur d’optimisation des itinéraires NVIDIA cuOpt pour optimiser les itinéraires sur plusieurs destinations.​

Il s’agit d’un processus en deux étapes qui nécessite une matrice de coûts pour le temps de trajet et un résolveur pour optimiser le problème et générer un résultat. Une matrice de coûts représente le coût du déplacement entre deux ensembles de localisations dans le problème, qui inclut le coût lié au temps de trajet et d’autres coûts de trajet.

Cet article explique comment :

• Bien démarrer avec NVIDIA cuOpt sur la Place de marché Azure.
• Utiliser l’API Matrice d’itinéraires Azure Maps pour obtenir le coût du trajet.
• Mapper le problème aux appels d’API cuOpt.
• Utiliser la réponse cuOpt.
• Appeler l’API Itinéraires Azure Maps pour obtenir les itinéraires.

Pour un démarrage rapide, consultez l’exemple de code d’optimisation multi-itinéraires.

Prérequis

• Un compte Azure Maps
• Une clé d’abonnement ou une autre forme d’authentification auprès d’Azure Maps

Prise en charge par le service

Ce service peut prendre en charge les fonctionnalités et contraintes suivantes.

Pour obtenir la liste complète des fonctionnalités prises en charge, consultez cuOpt Supported Features.

Bien démarrer avec NVIDIA cuOpt sur la Place de marché Azure

NVIDIA cuOpt utilise un solveur de logistique à accélération GPU et des optimisations pour calculer des problèmes complexes d’itinéraires de véhicules avec un large éventail de contraintes. Pour plus d’informations, consultez List of cuOpt supported features.

cuOpt est inclus avec NVIDIA AI Enterprise. Pour commencer, visitez la Place de marché Azure.

Obtenir le coût du trajet

L’optimisation de l’itinéraire nécessite une matrice carrée d’une métrique de voyage, telle que le temps ou le coût de distance, transmis au solveur cuOpt. Une matrice de coût représente le coût de déplacement entre chaque paire d’emplacements dans l’ensemble de problèmes, ce qui permet une planification et une optimisation efficaces des itinéraires.

L’API Matrice de routage Azure Maps calcule les métriques de voyage, telles que le temps et la distance, de chaque origine à chaque destination. Ces origines et destinations forment les en-têtes de colonne et de ligne d’une matrice de coût, où chaque cellule représente le coût de routage entre une paire d’origine-destination spécifique.

Par exemple, un restaurant a deux chauffeurs qui doivent livrer de la nourriture à quatre emplacements. Pour résoudre ce scénario, utilisez l’API Route Matrix pour calculer les temps de trajet entre tous les points pertinents. Cet exemple suppose que les deux chauffeurs commencent et terminent leur trajet au restaurant. Si les emplacements de début ou de fin diffèrent du dépôt, ces emplacements doivent être inclus explicitement dans la matrice des coûts.

Nombre d’origines = Nombre de destinations = 1 (restaurant, également appelé dépôt) + 4 (emplacements de livraison) = 5

Taille de matrice = 5 origines x 5 destinations = 25

Requête POST de matrice d’itinéraires :

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

La réponse de la matrice d’itinéraires est un tableau multidimensionnel 5x5 où chaque ligne représente les origines et les colonnes représentent les destinations. Utilisez le champ travelTimeInSeconds pour obtenir le coût du temps pour chaque paire de localisations. L’unité de temps doit être cohérente à l’échelle de la solution. Une fois la phase de prétraitement terminée, les informations sur la commande, le dépôt et la flotte ainsi que la matrice de coûts sont envoyées et importées vers le serveur cuOpt via des appels d’API.

L’exemple JSON suivant montre ce qui est retourné dans le corps de la réponse HTTP de l’exemple de matrice de coûts :

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], 
] 

Mapper le problème aux appels d’API cuOpt

Cette section explique comment générer des données de requête pour les appels cuOpt. Pour obtenir plus d’exemples, consultez cuOpt best practices.

1. Définir la matrice de coûts
2. Définir les données de flotte
3. Définir les données de tâche
4. Définir la configuration du solveur (facultatif)

Définir la matrice de coûts

Analysez la réponse de l’API Matrice d’itinéraires Azure Maps pour obtenir le temps de trajet entre des localisations afin de construire la matrice de coûts. Dans l’exemple suivant, « 0 » représente la clé qui représente un type de véhicule spécifique.

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

Plusieurs matrices de coûts peuvent éventuellement être fournies en fonction des types de véhicules. Certains véhicules peuvent se déplacer plus rapidement, tandis que d’autres peuvent entraîner des coûts supplémentaires lors du déplacement dans certaines régions. Cela peut être modélisé à l’aide de matrices de coûts supplémentaires, une pour chaque type de véhicule. L’exemple suivant comporte deux matrices, « 0 » représente le premier véhicule, qui peut être une voiture et « 1 » représente le deuxième véhicule, qui peut être un camion. Notez que si votre flotte comporte des véhicules avec des profils similaires, vous ne devez spécifier la matrice de coûts qu’une seule fois.

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

Définir les données de flotte

Les données de flotte peuvent comporter une description de la flotte, comme le nombre de véhicules, leur localisation de départ / d’arrivée, et la capacité du véhicule, qui sont utilisées par le solveur pour déterminer quels véhicules sont disponibles pour effectuer la tâche dans les contraintes spécifié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]]
        }
    }

• Localisation des véhicules : dans l’exemple ci-dessus, les données de flotte indiquent deux véhicules, avec un tableau pour chaque véhicule. Les deux véhicules partent de la localisation 0 et arrivent à la localisation 1. Dans le contexte d’une description de matrice de coûts de l’environnement, ces localisations de véhicules correspondent aux index de ligne (ou de colonne) dans la matrice de coûts.
• Capacités : le tableau de capacités indique la capacité du véhicule ; le premier véhicule a une capacité de deux, tandis que le deuxième véhicule a une capacité de trois. La capacité peut représenter diverses choses, par exemple le poids du colis, les compétences de service et leurs quantités transportées par chaque véhicule. Dans la section suivante, vous allez créer une tâche JSON qui nécessite une dimension de demande pour chaque emplacement de tâche et le nombre de dimensions de demande correspond au nombre de dimensions de capacité dans les données de la flotte. ​​​Par exemple, si un camion livre des marchandises, la capacité est le poids total que chaque véhicule peut transporter, et la demande est le poids de chaque commande. Assurez-vous que la même unité est utilisée pour les deux (par exemple, livres ou kilogrammes).
• Fenêtres de temps du véhicule : les fenêtres de temps spécifient le temps d’exploitation du véhicule pour effectuer les tâches. L'heure de début et de fin du quart de travail de l'agent peut être indiquée. Les données brutes peuvent inclure des données au format date/heure UTC (Universal Time Stamp) ou au format de chaîne qui doivent être converties en valeur flottante. (Exemple : 9h00 – 18h00 converti en minutes dans une période de 24 heures à partir de 12h00 donnerait [540, 1080]). Toutes les valeurs de temps/coût fournies au solveur cuOpt doivent être dans la même unité.
• Pauses de véhicule : vous pouvez également spécifier des fenêtres et durées de pauses du véhicule. Cela peut représenter la pause déjeuner de l’agent ou d’autres pauses si nécessaire. Le format de la fenêtre de pause est identique au format de la fenêtre de temps du véhicule. Toutes les valeurs de temps/coût fournies au solveur cuOpt doivent être dans la même unité.

Définir les données de tâche

Les tâches définissent l’objectif qui doit être rempli dans les contraintes spécifiées. Dans le contexte de la dernière livraison, cela peut inclure les localisations de livraison, la quantité de demande à chaque localisation, la fenêtre de livraison et la durée d’immobilisation pour chaque localisation.

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

• Localisation de la tâche : dans l’exemple ci-dessus, task_locations indique la localisation de livraison située aux positions 1, 2, 3 et 4. Ces localisations correspondent à des index de ligne (ou de colonne) dans la matrice de coûts.
• Demande : le tableau de demandes indique la quantité de demande à chaque localisation ; la première localisation a une demande de 3, les deuxième et troisième localisations une demande de 4, et la dernière localisation une demande de 3. Le nombre de dimensions de demande doit correspondre au nombre de dimensions de capacité pour chaque véhicule.
• Fenêtre de temps de tâche : les contraintes de fenêtre de temps spécifient quand une tâche doit être terminée. Une fenêtre de début et de fin est affectée à chaque tâche, et celle-ci doit être terminée dans les limites de cette fenêtre. Les données brutes peuvent inclure des données au format date/heure UTC (Universal Time Stamp) ou au format de chaîne qui doivent être converties en valeur flottante. (Exemple : 9h00 – 18h00 converti en minutes dans une période de 24 heures à partir de 12h00 donnerait [540, 1080]). Toutes les valeurs de temps/coût fournies au solveur cuOpt doivent être dans la même unité.
• Temps de service : cela représente la durée requise pour effectuer les tâches. Le tableau service_times spécifie la durée pour chaque localisation de tâche. Toutes les valeurs de temps/coût fournies au solveur cuOpt doivent être dans la même unité.

Définir la configuration du solveur (facultatif)

Vous pouvez éventuellement spécifier la configuration du solveur afin d’allouer un délai maximal pour trouver une solution. Cela dépend du cas d’usage, et la définition d’une limite de temps plus élevée retourne de meilleurs résultats.

        "solver_config": {
         "time_limit": 1
        }

Comment utiliser la réponse cuOpt

Le solveur cuOpt retourne l’arrêt optimisé pour chaque véhicule ainsi que l’itinéraire. Analysez la réponse et convertissez chaque localisation en point de coordonnées avant d’appeler l’API Itinéraires Azure Maps pour obtenir les itinéraires. Ces itinéraires optimisés incluent le parcours et les instructions de navigation pour chaque agent.

Exemples de données de requête

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

Exemple de réponse

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

Appeler l’API Itinéraires Azure Maps pour obtenir les itinéraires

Une fois que les emplacements de la réponse cuOpt sont mappés aux coordonnées correspondantes, le service cuOpt peut être utilisé avec l’API Route Directions d’Azure Maps et le Kit de développement logiciel (SDK) web pour créer une application web qui affiche les itinéraires attribués et les itinéraires optimisés sur la carte. Vous pouvez coder par couleur le parcours de chaque véhicule en fonction des arrêts attribués, et l’afficher sur les données de base Azure Maps.

Étapes suivantes