Key Concepts and Best Practices

The following section describes best practices for interacting with NVIDIA cuOpt, focusing on the managed service API.

Components of a Routing Optimization Problem

Environment

The environment description for a routing optimization problem outlines the cost of transitioning from one location to another. This cost could signify time, distance, monetary value, or any other user-determined metric, provided it maintains consistency within the environment’s description. cuOpt’s goal is to minimize the total accumulated costs, using this environment description as a progress measure. There are two methods of representing your environment to cuOpt. A brief explanation for each method, and the situations they’re used in, are outlined below:

• Cost Matrix: A cost matrix is a square matrix illustrating the cost incurred when moving between all pairs of locations. It is typically used when the primary focus is the cost between targeted locations, such as orders, jobs, or vehicle positions. This approach is popular in applications that use mapping services. An example of a simple cost matrix involving three locations could be as follows:

  {
  "cost_matrix_data": {
      "cost_matrix": {
          "0": [
              [0,1,1],
              [1,0,1],
              [1,1,0]
          ]
          }
      }
  }
  

  In this example, the cost of travel between any pair of (different) locations is one, and the cost from a location to itself is 0. This example is symmetric, and the cost from a location to itself is 0. While these conditions are prevalent, they are not mandatory.

• Waypoint Graph: A waypoint graph is a weighted, directed graph where the weights symbolize cost. Unlike the cost matrix, this graph often represents more than just target locations, including intermediate decision points along a route (locations merely passed through). This method is commonly used for custom environments and indoor spaces, such as warehouses and factories, where the cost between target locations is dynamic or not easily quantifiable. A basic waypoint graph with four nodes is illustrated below:

  {
  "cost_waypoint_graph_data":{
      "waypoint_graph": {
      "0": {
          "offsets": [0, 1, 2, 5, 6],
          "edges": [2, 2, 0, 1, 3, 2],
          "weights": [2, 2, 2, 2, 2, 2]
          }
      }
  
  }
  

  Graphs intended for input into cuOpt are shown in Compressed Sparse Row (CSR) format for efficiency. The translation from a more conventional (and human-readable) graph format, such as a weighted edge list, to CSR can be accomplished quickly, as depicted below:

  graph = {
          0:{
              "edges":[2],
              "weights":[2]},
          1:{
              "edges":[2],
              "weights":[2]},
          2:{
              "edges":[0, 1, 3],
              "weights":[2, 2, 2]},
          3:{
              "edges":[2],
              "weights":[2]}
      }
  
  def convert_to_csr(graph):
      num_nodes = len(graph)
  
      offsets = []
      edges = []
      weights = []
  
      cur_offset = 0
      for node in range(num_nodes):
          offsets.append(cur_offset)
          cur_offset += len(graph[node]["edges"])
  
          edges = edges + graph[node]["edges"]
          weights = weights + graph[node]["weights"]
  
      offsets.append(cur_offset)
  
      return offsets, edges, weights
  
  offsets, edges, weights = convert_to_csr(graph)
  print(f"offsets = {offsets}")
  print(f"edges   = {edges}")
  print(f"weights = {weights}")
  

Tasks

The task description for a routing optimization problem details the objectives that must be fulfilled within an environment. For instance, in the context of last-mile delivery, this could involve the delivery locations, the demand quantity at each location, and the specific times for delivery. For service technician routing, this might include the service locations, the skills required for a particular service call, and the time frame for that service. While the only mandatory element in task data is the locations, it’s often accompanied by one or more demand dimensions. A simple example is provided below:

{
"task_data": {
    "task_locations": [0,1,2],
    "demand": [[1, 1, 1]]
    }
}

The above task data represents three tasks, each with a demand quantity 1, located at positions 0, 1, and 2. When using a cost matrix to describe the environment, these locations correspond to row (or column) indices in the cost matrix. However, when you use a waypoint graph to describe the environment, these locations represent indices in the offsets array.

Important Points

• Each demand dimension’s length must align with the length of the task_locations array.

• It’s possible to assign multiple demand dimensions representing various products or service skills and their quantities. Crucially, the count of demand dimensions should correspond to the number of capacity dimensions for each vehicle (discussed further below).

Fleet

The fleet description for a routing optimization problem determines the vehicles available to carry out tasks within the environment. In the context of intra-logistics within a warehouse, this could represent the number of Autonomous Mobile Robots (AMRs), their carrying capacities, and their initial and final locations. In terms of last-mile delivery, this could represent the number of delivery vehicles and their cargo capacities. The only required data for the fleet is each vehicle’s start and end locations, although this is often paired with one or more capacity dimensions. Here’s a simple example:

    {
     "fleet_data": {
        "vehicle_locations": [
            [0,1], [0,1]
        ],
        "capacities": [[2,2]]
        }
    }

The above fleet data indicates two vehicles, both starting their route at location 0 and ending at location 1. Each vehicle has a capacity of 2. In the context of a cost matrix description of the environment, these vehicle locations correspond to row (or column) indices in the cost matrix. Conversely, when using a waypoint graph for describing the environment, these locations represent indices in the offsets array.

Important Points

• Each capacity dimension’s length must align with the length of the vehicle_locations array.

• It’s possible to assign multiple capacity dimensions to represent various products or service skills and their amounts transported by each vehicle. Crucially, the count of capacity dimensions should correspond to the number of demand dimensions for each location (discussed previously).

Introducing Additional Constraints

While the construction of simple routing problems often suffices for academic and benchmark purposes, real-world scenarios frequently necessitate the inclusion of additional constraints for generating business-relevant solutions. This section explains how some of the most common constraints are incorporated using the NVIDIA cuOpt managed service.

Task Time Windows

Time windows introduce time constraints on when a task should be completed. To implement this, the cuOpt solver must know the time required to travel from one location to another within the environment and the time needed to execute each task (if applicable).

Requirements

• travel_time_matrix_data or travel_time_waypoint_graph_data : This is an auxiliary environment description similar to the ones discussed earlier, but instead of depicting abstract cost, it represents the time between locations:

  {
  "travel_time_matrix_data": {
      "cost_matrix": {
          "0": [
              [0,2,2],
              [1,0,2],
              [1,1,0]
          ]
          }
      }
  }
  

• task_time_windows and service_times represent the times a specific task must be initiated and the duration required to complete, respectively.

  {
  "task_data": {
      "<other-relevant-task":"data>",
  
      "task_time_windows": [
          [0,10],
          [0,4]
          ],
      "service_times": [1,1],
  
      "<other-relevant-task":"data>"
      }
  }
  

  Each task is assigned an earliest and latest time window. In this example, the first task must be completed between time 0 and 10, and once initiated, it requires 1 unit of time to complete.

Mixed Fleet

In some cases, not all vehicles within a fleet are identical. Some might travel faster, while others might incur unaffordable costs when traveling through certain areas. This scenario can be modeled in cuOpt by incorporating additional cost matrices and allocating particular cost matrices to specific vehicles.

Requirements

• Multiple Cost Matrices: More than one cost matrix can be introduced, each assigned an individual integer key.

  {
  "cost_matrix_data": {
      "cost_matrix": {
          "0": [
              [0,1,1],
              [1,0,1],
              [1,1,0]
          ],
          "1":[
              [0,2,2],
              [2,0,2],
              [2,2,0]
          ]
          }
      }
  }
  

• vehicle_types: Using this field informs cuOpt about the relationship between each vehicle and its assigned cost matrix. This optional field is only necessary when vehicles are not all employing the same cost matrix.

  {
  "fleet_data": {
      "<other-relevant-fleet":"data>",
  
      "vehicle_types": [0,1]
  
      "<other-relevant-fleet":"data>"
      }
  }
  

  In this case, the length of vehicle_types must align with the length of vehicle_locations. In the given example, the first vehicle will use cost matrix 0, and the second vehicle will employ cost matrix 1.

Minimum Vehicles

By default, cuOpt first strives to optimize for the smallest number of vehicles capable of performing a given set of tasks, then minimizing cost by utilizing a minimal number of vehicles. However, you should establish a lower limit on the number of vehicles used in some cases. This can be achieved using min_vehicles.

Requirements

• min_vehicles: This is an integer value indicating the minimum number of vehicles employed in a solution. This value must be larger than the number of tasks.

  {
  "fleet_data": {
      "<other-relevant-fleet":"data>",
  
      "min_vehicles": 2
  
      "<other-relevant-fleet":"data>"
      }
  }
  

  In this scenario, if there are two or more tasks, at least two vehicles will be used in the solution, even if all tasks could be completed with a single vehicle.

Max Cost Per Vehicle

Sometimes, it may be necessary to set an upper limit on a single vehicle’s cost. This might represent the maximum mileage per day for a specific vehicle or some other limiting constraint.

Requirements:

• vehicle_max_costs : This is a value that can be assigned within the fleet data as an array with a length equal to vehicle_locations.

  {
  "fleet_data": {
      "<other-relevant-fleet":"data>",
  
      "vehicle_max_costs": [100,150]
  
      "<other-relevant-fleet":"data>"
      }
  }
  

  In this example, two vehicles are depicted: the first has a maximum cost of 100, and the second has a maximum cost of 150. This situation could influence the number of vehicles needed to complete all tasks.

Vehicle Fixed Costs

This is used to assign fixed costs to each vehicle, in-turn this also acts as vehicle priority.

Prizes

While using prizes won’t set the drop infeasible tasks option, the solver will try to optimize to complete jobs with higher prizes and dropping the ones which would be infeasible in such scenarios.

Other Constraints

The constraints mentioned above are just a subset of the most commonly used within cuOpt, but there are others. Many of the other constraints follow a similar pattern to those demonstrated above. Please refer to the service documentation for a complete list of available constraints.

Avoiding Common Mistakes

This section enumerates some common errors encountered when setting up an optimization problem.

Over Constrained Problems

NVIDIA cuOpt can efficiently navigate a colossal search space in a limited time. Only truly NECESSARY constraints should be applied to any given optimization problem. It’s rarely necessary to assist cuOpt with an effective solution. Often, cuOpt can identify solutions that were not previously considered. It’s advised that users allow cuOpt to find the best solutions and only implement additional constraints if the returned solutions violate essential business objectives.

Dimension Match

Throughout the setup of a cuOpt problem, it is vital to ensure consistency in relevant dimensions across the problem description, as mentioned above. If a constraint is being specified for vehicles on a per-vehicle basis (such as priority or max cost), a value must be provided for all vehicles. The same principle applies to tasks.

Time Value Consistency

If you provide a time description of the environment, the values presented must represent your desired time units. The same units must be used when employing time values in constraints for time windows, processing times, or break durations.