FAQ¶
cuOpt resource estimates; how large a problem can I run with xyzconstraints?¶
For the standard CVRPTW problem with real-world constraints, cuOpt can easily solve for 10K locations with NVIDIA GPU A100/H100.
Does cuOpt use multiple GPUs?¶
Currently cuOpt does not support using multiple GPUs from a single cuOpt instance.
Research is ongoing into which use cases may benefit from multiple GPUs. For the time being, if multiple GPUs are available, scale out is possible by partitioning problems into sub-problems and running multiple cuOpt instances.
How do I solve (some realistic problem)?¶
This is likely a decision tree that points to some variant of CVRP or PDP with constraints that match the use case but do not over-constrain the problem.
Do I need a GPU to use cuOpt?¶
The cuOpt Managed Service allows you to run a cuOpt client on any computer and submit problems to a cuOpt server. While the server itself does require a GPU of Pascal architecture or later, the cuOpt Managed Service takes care of provisioning the server for you on NVIDIA-managed hardware.
In case of Self-Hosted (On-Premise) scenario: yes, you would need a NVIDIA GPU (Volta/Turing or higher).
Can I deploy cuOpt to my cloud environment?¶
In case of Self-Hosted (On-Premise) scenario: the cuOpt container obtained from NVIDIA AI Enterprise can be used to host it on user’s cloud which has the GPU.
The cuOpt Managed Service already provides a cuOpt server running on NVIDIA-managed hardware.
Solver-Modeling Issues/Questions¶
Determinism and Consistency¶
cuOpt is not deterministic. So you do not get same results for the same input time. Since you might have several different solution for the same cost.
And this also depends on solver run time being set. If a problem needs 120 seconds to reach optimal solution, but it has been given only 10 seconds, the solve might not be able to search all possible solutions.
There are examples where given longer run time, the results were bad compared to smaller run time. In these cases, it depends what the other elements were. Like the earlier example, if a problem requires 120 seconds to reach the optimal solution, but the user runs the dataset for maybe 5 to 10 seconds, and the 10 second run has a comparatively worse solution. In this case, since neither allowed enough time to cover the search space, it cannot be concluded the results worsen as time passes by.
It is suggested you leave the solver run time to default, which is
10 + (num_tasks/6).
Is there any lower bound as Mixed integer gives a solution and lower bound?¶
cuOpt does not provide any lower bound. cuOpt is based on heuristics and does not use exact methods so lower bound does not matter as long as the solution is robust, and within constraints.
How do we account for dynamic changing constraints while the solver is executing?¶
Dynamic reoptimization is used when there is a change in the conditions of the operation. A vehicle getting broken, a driver calling in sick, road block, traffic, a high priority order coming in. Currently, a solver instance is started by considering which packages each vehicle has and the last location (cannot be in between nodes) of the vehicle. The solver then can be run with any configuration, except the ones that are currently in truck and waiting to be delivered.
How are order cancellations handled in cuOpt?¶
We can reduce the capacity of the vehicle accordingly, or the user can provide information wherein the canceled order can be dropped off at a location/depot. In such cases, set large time windows to derive an optimal solution.
Can cuOpt be combined with Reinforcement Learning?¶
cuOpt is an optimization solver but it could theoretically accept initial guesses from ML models. This is still in the exploratory phase as it requires extensive customization to a particular dataset.
Do we need to normalize the data when creating a time window matrix?¶
The units can be whatever the customer wants them to be minutes, seconds, milliseconds, hours, and so on. It is your responsibility to normalize the data.
How does cuOpt check for collisions in NVIDIA Isaac Sim?¶
Dynamic obstacle avoidance (humans, other robots, and so on) is handled by local planners on the robots because these events cannot be foreseen when cuOpt gets the data for a problem. For static obstacles (shelves, walls, etc.), the waypoint graph describes areas that are traversable by the robot. By default, therefore, the robots should not hit static obstacles, as cuOpt will only return locations that are present in the waypoint graph.
While setting certain customer nodes as break points using vehicle_break_locations, there is an error where the result has additional locations.¶
This is not an error. Breakpoints get appended to the existing location list. You can refer to the locations by the location ids.
How can we set the demand of a customer node higher than the capacity of the vehicle?¶
If this is for one node, then multiple vehicles can deliver many orders. However, if one order demands more capacity than one vehicle can handle, then we will need a workaround by assigning to dummy vehicles.
How do we ensure that cuOpt does not assign high priority orders to dummy vehicles or technicians (that were added to get feasible solutions)?¶
We can set
vehicle_order_match(v, o) = 0for when o is an important task and v is a dummy vehicle.Tip
Setting vehicle order match makes it a hard constraint. So if there are many high-priority orders/tasks, it may end up with infeasible solutions. But, if the high-priority orders are only a fraction of the total orders, then these solutions should work.
How can I add multiple capacity information for a specific vehicle—height, widths and length, mileage, carbon footprint, and so on?¶
It is possible to add multiple capacities. These are represented as capacity dimensions in the solver. For each capacity constraint, you can have a column in
task_data["demand"]andfleet_data["capacities"]. For each dimension, there should be one vector capacity of lengthfleet_sizeand demand of lengthnum_orders/tasks.
Is there a way to prevent vehicles from traveling along the same path in a waypoint graph, or is there a way to prevent more than one vehicle from visiting a location, or even that a location is only visited one time by a single vehicle?¶
Currently, we do not have such restrictions, and cuOpt tries to optimize for the fewest number of vehicles as the primary default objective. However, spatiotemporal restrictions continue to be a topic of research.
Can I use my own data instead of Homberger’s instance data in cuOpt?¶
Yes, you can certainly use your own data. There is a sample data file included with the cuOpt client, and the documentation includes examples of constructing a JSON object in Python to represent cuOpt data.
Travel time deviation: When using the same dataset, the travel time varies by a couple of seconds in different runs, but the distance remains the same. How can travel time deviate in multiple runs on the same data and distance remains constant?¶
This is because travel time is not part of the objective so we could have two solutions that are equivalent and when picking the best solution in this case it is not deterministic. You can include travel time, including waiting times as part of the default objective. You can also include as part of a predefined set of objectives as an extra comparator. cuOpt optimizes for fleet size and cost so these solutions are equivalent from the solver perspective. Or you can set time as your cost matrix.
Null values in the cost matrix¶
Replace null values with some high value, not max of float type.
I cannot model road conditions like traffic.¶
cuOpt accepts arbitrary distance and time matrices as input. This data typically comes from popular map engines (Google Maps, open route service, and so on) and may natively account for current traffic information. The matrix can also be updated based on current conditions and resubmitted to cuOpt. The speed of cuOpt makes such reoptimization very feasible.
Can a break happen anywhere?¶
If break locations are provided, breaks can only be taken in those points. By default, a break can be taken in any location.
What is the difference between setting min_vehicles and the variance_route_size objective?¶
Setting a minimum number of vehicles instructs the solver to use a minimum predefined number of vehicles. This is a hard constraint. You would want to do this to use all the resources (e.g., the fleet). The solver would still want to optimize for total cost while using this many vehicles. Usually, hard constraints are bad for finding optimal solutions, because you are blocking the solver from exploring a wider space.
The
variance_route_sizeobjective tries to minimize the variance between routes. It will penalize any technician or vehicle doing many more tasks than the average, or for doing much fewer tasks than the average. So if you penalize enough (using objective weight), you should get a route with all techs doing a similar number of jobs. However, this does not necessarily translate to using more vehicles.Another option for causing more vehicles to be used is to add an additional capacity dimension. For example, setting demands for all orders to 1 and setting capacity to 10 will ensure that no more than 10 orders are served by a vehicle.
As an extra note: in general, the cuOpt team recommends that
min_vehiclesnot be set when using heterogenous fleets.
Does cuOpt implement a topo sort for every route map?¶
This is not currently supported. It may be added in a future release.
Floating point vs. integers for specifying task locations.¶
The documentation says
task_locationsshould be integers. But in the real world, latitude and longitude coordinates are floating point values. To explain this, read the following section.cuOpt expects that a user provides either:
A cost matrix and corresponding location indices.
A waypoint graph and locations corresponding to waypoints as integers.
So in either case, task locations are actually integer indices into another structure.
If you have (lat, long) values, then you can generate a cost matrix using a map API. cuOpt does not directly connect to a third-party map engine, but that can be done outside of cuOpt as shown here:
How do you compute the max driving that does not include wait time or service time?¶
We have vehicle_max_times, with which you can control the max driving (this does not include wait time or service time). This uses time_matrix to compute time, so the units pertain to time and not distance.
How do I calculate and adjust the optimal route while avoiding collisions using cuOpt and Isaac Sim?¶
There is a distinction between path planning in cuOpt and local dynamic obstacle avoidance. The latter deals with any local dynamic situation that is not represented in the environment — such as a human, unexpected pallets, and so on. cuOpt handles aspects of the environment, static or dynamic, that can impact global navigation. Highly transit, localized events are handled by the local planning systems on the robot, and they follow the route provided by cuOpt.
In this case, cuOpt would consider the routes as part of the environment and factor them in global planning. If the zones become unrestricted due to any reason and the environment is updated on the cuOpt server, the subsequent optimizations will reconsider the changes. The question related to acceleration or deceleration would fall under dynamic collision avoidance. It is up to the user to reoptimize based on any user-defined triggers such as automated environment monitoring or timer.
Is it possible to define constraints such as refrigerated vehicles required for certain orders?¶
Yes, you can define constraints to match vehicles to order type. Frozen goods are a great example.
What is the role of task_locations in pickup delivery combination?¶
pickup_indices = [0, 2, 4]delivery_indices= [1, 3, 5] # 2 -> 1, 3 -> 4 and 1->4Here the pickup and delivery pairs are indices to the task locations provided, considering following example:
task_locations = [2, 1, 3, 4, 1, 4]
pickup_indices = [0, 2, 4]
delivery_indices = [1, 3, 5] # 2 -> 1, 3 -> 4 and 1->4
Each pickup and delivery are considered a task, so we have six tasks, three pickups and three deliveries.
Pickup and delivery are indices to task locations, 0 in pickup indices correspond to value in 0th index in task locations, so it depicts location - 2, similarly, index 4 represents location -1.
For something like pickup and delivery pair locations, (2 -> 1), (3->4), (1->4), pickup and delivery pair indices into task location would be (0->1), (2->3), (4->5).
How to model inputs for following scenarios?¶
The same truck picks up and delivers some orders on the way.
If we want to tie few orders to particular trucks, we can use
vehicle_order_matchinfleet_data.If this is a generic question on whether a truck can pick up multiple orders, then yes, it can.
How do we model the following scenario: Pick up from multiple different locations and deliver to a single customer?¶
Pickup from multiple different locations and delivering to a single customer will be handled by algorithm depending on how far the orders are and whether using multiple trucks would reduce the cost.
If we want to restrict it to a single truck, then use
vehicle_order_matchinfleet_data.It can also be modeled as a pickup-delivery problem. Suppose that there are four pickups from different locations and drop off to one location.
There will be four pickup-delivery pairs (eight orders in total).
The solver can then figure out an optimal way to serve these orders/requests.
If these have to be served by only a specified vehicle, use
vehicle_order_match.
I know that the problem has a feasible solution, but cuOpt returns infeasible solution. How to avoid this?¶
The optimizer first tries to find feasible solutions that may be sub-optimal and then tries to optimize these feasible solutions. If the problem is tightly constrained, it is possible that the solver may not find an initial feasible solutions. If this happens, the solver will try to make the solution feasible during the improvement phase. If the solver cannot make the solution feasible, it will return the best and closest feasible solution that could be found along with a message describing which constraints were violated. If it is known that a problem has feasible solutions but the solver is not finding them, it could be because the time limit is too short. Running the solver for a longer duration improves the chance of finding a feasible solution. Another option is to relax the constraints or provide more vehicles to get a feasible solution.
Where can I learn more about cuOpt?¶
Here are links to learn about various aspects of cuOpt: