Can you provide cuOpt resource estimates (how large a problem can I run with a given set of constraints)?
For the standard capacitated vehicle routing problem with time-windows (CVRPTW) problem with real-world constraints, cuOpt can easily solve for ten thousand locations.
What is cuOpt GPU Memory Usage?
Before diving into this, it is key to understand the two types of memories—global memory and shared memory. cudaMalloc always allocates global memory that resides on the GPU. The contents of global memory are visible to all the threads running in each kernel, that is any thread can read and write to any location of the global memory. In contrast, shared memory is memory shared between the threads within a block and is not visible to all threads. For instance, the shared memory of the A100 GPUs capacity per streaming multiprocessor (SM) is 164 KB, with 108 SMs on the chip. Each SM has an isolated shared memory and can only communicate by copying to global memory. Global memory is limited by the total memory available to the GPU, for instance, an A100 GPU (40 GB) offers 40 GB of device memory. Shared memory is like a local cache shared among the threads of a block, magnitudes faster to access than global memory and limited in capacity.
While in general cuOpt memory usage is problem size dependent, it is equally important to note that cuOpt memory usage is very sensitive to the constraints specified. The global memory usage is determined by the size of the input distance and cost matrices while the longest route in terms of number of nodes on the route determines the peak shared memory usage. As an approximate estimate, a 10,000 locations CVRPTW test case with challenging constraints can execute on a single A100 GPU (40 GB) without any out-of-memory issue. However, for even larger problem sizes, cuOpt in the latter half of 2023 will offer multi-GPU support by partitioning the inputs seamlessly across GPUs.
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.
How many climbers do I need?
The total time depends on the user. The user has the flexibility of setting a higher time‑limit for better results. If the user wants the first solution, then around 2-3 seconds for 2000-4000 climbers are enough. cuOpt solver does not interrupt the initial solution. So if the user specifies a shorter time than it takes for the initial solution, the initial solution is returned when it is computed. Increasing the number of climbers will increase the time it takes to compute the initial solution.
If the time limit is set to X seconds and the solver completes earlier, will it still run for X seconds?
Yes, the solver will continue to run for X seconds looking for more solutions.
In the set_pickup_delivery_pairs(), see an error - ValueError: Pickup/delivery indices size is not equal to number of pairs from this function.
In cuOpt, the depot is always node 0 and it should be included in most APIs. The pickup delivery pairs must have a size of (orders+1)/2 (+1 comes from the depot).
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.
While setting certain customer nodes as break points, using add_break_dimensions(), 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 does one 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.
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.
While calling API /cuopt/get_optimized_routes, we get an error {“detail”:”Failed to find solution with given constraints”}. Is it possible to know which constraint caused this to fail?
It is not possible to prioritize constraints with R22.12. So even if one constraint cannot be satisfied, the solver returns failure and an empty route. With drop infeasible tasks enabled, the solver does not fulfill all the customer orders and returns a partial route and a list of unfulfilled orders. You can also provide more vehicles in the fleet data to get a feasible solution if it makes sense for your problem.
How can I add multiple capacity information for a specific vehicle—height, widths and length, mileage, carbon footprint, and soon.
It is possible to add multiple capacities. These are represented as capacity dimensions in the solver. For each capacity constraint, you can call data_model.*add_capacity_dimension* if you are using python API or have multiple columns in task_data[“demand”] and fleet_data[“capacities”] if you are using server API. 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. One way to do it would be to structure your data in the same format as the Homberger data files and use the cuOpt utilities to read it.
Another way is to construct your cost matrices, and so on, directly in Python. If you look at the example notebooks in the ea-cuopt image, you can see how to do this. For example, the cost_matrix_creation.ipynb notebook shows a simple example of constructing a cost matrix from literal values.
**RuntimeError: cuOpt failure at
file=/cuopt-build-utilities/cuopt/cpp/src/solution/get_solution.cu
line=196: Truck capacity is smaller than
volume.
This is not accuracy as there is one vehicle with a capacity of 750 can carry a demand of 713 and another can carry a demand of 434 (considering that we have 70 vehicles available with no time restrictions or anything extra, only capacity restriction).
The problem was in the order in which we passed the data frame with the locations to go through, for display purposes we were ordering from highest to lowest according to demand, leaving the largest values in the first position (wrongly representing the deposit), the solution was to always insert the deposit in the first position with zero demand.
The property num_of_climbers: int. What number is a typical value? What is the default value?
By default, the number of climbers is chosen by considering occupancy of a small GPU and experimented runtime versus number of climbers trade-off (that is, the best result in shortest time). Normally 1024 or multiple is a good start.
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 get updated based on current conditions and cuOpt can reoptimize the new problem quickly.
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.
Time windows issues
Time window and any other time-related data are accepted in the form of float, so the time in date/time format or string format must be converted to floating value. (Example: 9:00 am - 6:00 pm, converting this to minutes in a 24-hour period starting at 12:00 am, 540 - 1080).
All time/cost unit provided to cuOpt should be in the same units.
What is the difference between set_min_vehicles and the horizontal loading feature?
set_min_vehicles indicates the solver to use 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 these many vehicles. Usually, hard constraints are bad for finding optimal solutions, because you are blocking the solver from exploring wider space.
Horizontal loading 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 average tasks. So if you penalize enough, you should get a route with all techs doing a similar number of jobs.
Does cuOpt implement a topo sort for every route map?
This is not currently supported, however it is afuture consideration.
How to choose various solution strategies?
Available strategies are HILL_CLIMBING, TABU_SEARCH, TABU_GLS, default is TABU_GLS.
Floating point versus integers when using the Set Task data server API call.
It says task_locations should be integers. But in the real world, latitude and longitude coordinates are floating point values.
cuOpt expects that a user provides either:
A cost matrix and corresponding location indices.
A waypoint graph and locations corresponding to waypoints as integers.
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 easily done outside cuOpt as shown in this example.
How do you compute the max driving that does not include wait time or service time?
We have set_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 notdistance.
When do I use set_vehicle_max_costs vs set_vehicle_max_times?
set_vehicle_max_costs uses cost matrix; cost can be distance.
set_vehicle_max_times uses a time matrix.
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.
Are there any plans to allow each vehicle to have its own maximum route distance so that mixed fleets with electric and traditional vehicles can be optimized?
Today, we can set a max distance per vehicle per route—look at the following API to see if this works for your use case.
set_max_distance_per_route(*max_distance_per_route)*
What is the role of set_order_location()in pickup delivery 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 order locations provided, considering following example from the doc:
order_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 an order, so we have six orders, three pickups, and three deliveries.
Pickup and Delivery are indices to order locations, 0 in pickup indices correspond to value in 0th index in order 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 order 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 a few orders to particular trucks, we can use vehicle order add_vehicle_order_match.
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 add_vehicle_order_match.
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 add_vehicle_order_match API.
We enabled the following “error_logging”: “verbose_mode”: true but still did not get any reason why it failed?
The solver does not report the details of the error at the moment when using the server API.
I know that the problem has a feasible solution, but cuOpt fails with infeasible. How do I 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 immediately returns infeasible. 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: