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.
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 probably 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.
Can I deploy cuOpt to my cloud environment?
The cuOpt Managed Service already provides a cuOpt server running on NVIDIA-managed hardware.
Solver-Modeling Issues/Questions
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 the user’s 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, therefore by default, 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 a bunch of orders. However, if one order demands more capacity than one vehicle can handle, then we will have to use a workaround by assigning to dummy vehicles.
How to 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) = 0 for when o is an important task and v is a dummy vehicle.
TipSetting 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”] and fleet_data[“capacities”]. For each dimension, there should be one vector capacity of length fleet_size and demand of length num_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 account for current traffic information natively. 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 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 at least a predefined number of vehicles. This is a hard constraint. One would want to do this to use all the resources (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_size” objective tries to minimize the variance between routes. It will penalize any technician or vehicle doing many more tasks than the avg tasks or for doing much fewer tasks than the avg tasks. 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_vehicles not be set when using heterogenous fleets.
Does cuOpt implement a topo sort for every route map?
This is not currently supported. Future consideration.
Floating point vs integers for specifying task locations.
The documentation says task_locations should be integers. But in the real world, latitude and longitude coordinates are floating point values. Please explain.
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 one 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 (does not include wait time, 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 Issac 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 delivey combination?
pickup_indices = [0, 2, 4]
delivery_indices = [1, 3, 5] # 2 -> 1, 3 -> 4 and 1->4
Here 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?
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_match in fleet_data.
If this is a generic question on whether a truck can pick up multiple orders, then 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_match in fleet_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 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 may be because the time limit is too short. Running the solver for a longer duration will improve 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: