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 (TSP), 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.
Heterogeneous Fleet¶
In a Vehicle Routing Problem (VRP), 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. 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.
Note
All time windows are expected to be => 0, and all time windows are int32 types. So the time window range supported would be
[0, 2^31-1]; this translates to[January 1, 1970, 00:00:00, January 19, 2038, 03:14:07]in UTC.
Vehicle Priorities¶
Vehicles may be prioritized such that vehicles with lower values have a higher priority. Vehicles with higher priority will get dispatched before a vehicle with lower priority. By default, the cuOpt solver 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.
Vehicle Breaks¶
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 pm, 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].
Prize Collection¶
The prizes field in task_data may be used to set a prize for each task. This supports cases where all tasks are not feasible and the user requires tasks with the highest prize to be considered before trying other tasks. If the cost of serving a customer is too high compared to the prize of serving a customer, the solver will drop that customer to improve overall cost. If the primary goal is to serve as many customers as possible, it is advisable to set very high prizes. Prize collection would be an effective way to drop infeasible tasks and prioritizing tasks with higher prizes. The main difference is in objective function, the total prize will be negated rather than getting added to overall cost.
Custom Objectives¶
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 cuOpt 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 cuOpt 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.
Pickup Deliveries¶
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 pickup 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¶
It is recommended to use the default time limit (which is 10 + number_of_nodes/6) seconds. If the time limit is set to X seconds, then solver continues to run for X seconds even when there is no improvement in the solution quality.
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. This means that even if a vehicle has a time window of 9am to 9pm, and 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.
Fixed Cost per Vehicle¶
Vehicles can have different fixed costs associated with them. This helps in scenarios where a single vehicle with a higher cost can be avoided if it can be done with two or more vehicles with lesser costs. This would be dependent on the objective function.