cuOpt Supported Features¶
Multiple input matrices¶
A cost matrix needs to be a square matrix of some travel metric that is passed to the NVIDIA cuOpt solver. In many variations of the Traveling Salesman Problem, this includes travel time, distance, or another business cost. A cost matrix is a square matrix that represents the cost of traveling between each two pairs of locations in the problem. cost_matrix_data can hold any cost matrix; the cost can be travel time, travel distance, dollar cost, or any weighted function of cost. If the cost matrix doesn’t use travel time, travel_time_matrix_data should be used so that the cost matrix is used for optimization while the travel time matrix is used for meeting time constraints. In the case of a heterogeneous fleet, different vehicle types may have different travel times. To support this, cost_matrix_data and travel_time_matrix_data can each hold multiple matrices such that each vehicle type has a corresponding matrix.
In a Vehicle Routing Problem, enterprise customers may have a fleet that is composed of different vehicles, such as trucks and motorbikes. Each vehicle type will likely have different constraints, such as travel time, time windows, start and end locations, and carrying capacity. Therefore, users can provide cuOpt multiple input matrices (one travel time matrix per vehicle type). Capacity values are indicated in the capacity input array, where the index of the array corresponds to each vehicle in the fleet.
Vehicle time windows¶
Time windows represent the operating time of the vehicles. There is one time window per vehicle. This data is represented as an integer or float. Raw data may include Universal Time Stamp (UTC) date/time format or string format which must be converted to floating value. (Example: 9:00 am - 6:00 pm converted to minutes in a 24-hour period starting at 12:00 am, would be [540, 1080]). All time/cost units provided to the cuOpt solver should be in the same unit. If the travel time cost matrix includes the travel time in between locations in minutes, the time windows must be integer representation of minutes as well.
Priorities of each vehicle such that vehicles with lower values have a higher priority. Vehicles with higher priority will get dispatched before a vehicle with lower priority. The cuOpt solver, by default, tries to minimize the number of vehicles used in a solution, so it is possible that not all vehicles available in the fleet will be used in the solution. With vehicle priority, it is possible to indicate which vehicles should be prioritized when selecting vehicles to be included in the solution. For example, a vehicle with assigned priority number 1 is more likely to be dispatched than a vehicle with assigned priority number 2.
In addition to vehicle time windows, vehicles may also have break time windows. If the time windows represent a driver’s working hours in a day, the break time window may represent their lunch break in the middle of the day. The integer representation is consistent with the time windows. In case raw input data is in UTC timestamp, if a vehicle is working a shift of 9:00 am - 6:00, then in a 24-hour period this is equivalent to 540 - 1080. If the vehicle has a break from 1 pm - 1:30 pm, then the break time window would be [780, 810].
The prizes field in task_data may be used to set a prize for each task. When the prizes are set, the solver optimizes for total cost - total prize. If the prize for a given task is smaller compared to the cost of serving that task, the solver will drop that task. If the primary goal is to increase the number of served customers for given resources, the prize of each task should be set to a large enough value.
The default objective of the solver is to optimize the cost computed using cost matrices. However, a few other objectives can be set using the objectives field. The final objective is the linear combination of all the objectives specified. The specified objective weights are used as coefficients. By default the solver optimizes for vehicle count first and final objective next. Customers can set multiple cost matrices using cost_matrix_data in addition to travel_time_matrix_data.
Drop first/last trips¶
By dropping the first or last trip, the solver does not take into account the vehicles’ trip from their depots to their first stop, or the trip from their last stop back to the depots. With these parameters, the route includes only travel costs and times between task locations. In cases where drivers may start their shift from wherever their home location instead of an assigned depot, the trip to and from the depot is unnecessary.
Some use cases may include picking up an order from one location and delivering it to another. Each order has two corresponding locations- one for pick up and one for delivery. The same vehicle must handle both the pickup and delivery of the same order, and the pickup of the order must occur prior to the delivery.
Precise time limits¶
If the time limit is set to X seconds and the solver completes earlier, the solver will continue to run for X seconds looking for more solutions.
Vehicle start and end locations¶
Each vehicle in the fleet must have a start and end location for the given set of locations in a waypoint graph or cost matrix. These locations must be included in the cost matrices or WayPoint graphs. In many use cases, these start and end locations are depots or distribution centers, such that vehicles depart their assigned depot in the morning, fulfill all of their assigned tasks, and then return to the assigned depot at the end of the work day. The start and end locations are not necessarily the same location (e.g. a vehicle departs from depot 1 in the morning but returns to depot 2 at night).
Minimum constraint on number of vehicles¶
By default, cuOpt tries to minimize the number of vehicles used in the solution and considers the fleet size an upper bound. The fleet size is inferred from vehicle_locations. If a given input fleet has 20 vehicles available but only 10 are needed to fulfill all of the tasks, then the cuOpt solution will include only 10 vehicles. To set a lower bound on the number of vehicles used, set min_vehicles in fleet_data. If the exact number of vehicles to be used is known, specifying a fleet of the desired size and setting min_vehicles equal to the fleet size will guarantee that all vehicles are used.
Maximum constraints per vehicle¶
Vehicles may have a constraint for maximum distance each vehicle can travel or maximum time a vehicle can operate, such that even if a vehicle has a time window of 9am to 9pm, a driver may be available to work for those 12 hours, we can add a constraint that a work day must not exceed 8 of those 12 hours.