Before getting started, a cost matrix or waypoint graph must be created. Once this prerequisite is met, the cuOpt solver takes this as input, Fleet and Task problem data files, and solver configuration. The additional constraints such as vehicle capacity, delivery time windows, and vehicle driver’s shifts and breaks during the work day can also be included within the Fleet data. The following sections detail these cuOpt features.
Additional information can be found in cuOpt Server API reference guide.
A cost matrix needs to be a square matrix of some travel metric inputted into the NVIDIA cuOpt solver. In many variations of the Traveling Salesman Problem, this includes travel time, distance, or other business costs. A cost matrix is a square matrix representing the cost of traveling between each of two pairs of locations in the problem.
A time matrix is used for checking constraints satisfiability rather than participating in cost optimization. For instance, the time matrix is used to model the time between locations with time windows referring to it while the solver could optimize for the cost set by the cost matrix.
In the case of a heterogeneous fleet, different vehicle types may have different travel times. To support this, the cost matrices and time matrices are arrays that can take multiple matrices such that each vehicle type has a corresponding matrix.
A cost matrix can be created using a third-party tool like OSRM, Esri ArcGIS, or Google Maps.
Sometimes, a unique environment is better described as a waypoint graph than a cost matrix. Such environments can be factories or warehouses, for example. This graph includes the nodes, representing the locations in the input problem, and the edges connect accessible points in the graph with a weight. Before sending this waypoint graph to cuOpt, it must be converted to Compressed Sparse Row (CSR) format.
NVIDIA cuOpt works directly with fleet source data files (for example, .csv). The schema of the fleet data contains information that cuOpt Server API can query. The following sections describe the cuOpt-supported features for Fleet data.
Vehicle start and end locations
Each vehicle in the input fleet must have a start and end location. 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, so vehicles depart their assigned depot in the morning, fulfill all their assigned tasks, and then return to the depot at the end of the work day. The start and end locations differ (e.g., a vehicle departs from Depot 1 in the morning but returns to Depot two at night).
Vehicle Time Windows
Time windows represent the operating time of the vehicles. There is a 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 a 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 between locations in minutes, the time windows must also be integer representations of minutes.
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. If 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].
Vehicle Priorities
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 not all vehicles available in the fleet may 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.
Max Wait Time
This is the slack time for vehicles in the fleet, which is the budget to let vehicles wait at locations up to a user-defined time allotment. By default, vehicles can wait an infinite amount of time. This is an upper bound for wait time per location (including depot), and the integer representation should be the same unit as the time windows. This can be used to account for vehicle driver needs, such as bathroom breaks, and still meet the given constraints.
Skip First – Drop Return 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 between task locations. In cases where drivers may start their shift from their home location instead of an assigned depot, the trip to and from the depot is unnecessary.
Heterogeneous Fleet
In a Vehicle Routing Problem, customers may have a fleet 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.
Minimum Constraints per Vehicle
By default, cuOpt tries to minimize the number of vehicles used in the solution. If a given input fleet has 20 vehicles available, but only ten are needed to fulfill all tasks, then the cuOpt solution will include only ten vehicles. However, it is possible to indicate how many vehicles we want to be used in the solution. This allows us to enforce that all vehicles available in the problem are used in the solution.
Maximum Constraints per Vehicle
Vehicles may have a constraint for the maximum distance each vehicle can travel or the maximum time a vehicle can operate, such that even if a vehicle has a time window of 9 am to 9 pm, 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.
NVIDIA cuOpt works directly with Task source data files (for example, .csv). The schema of the Task data contains information that cuOpt Server API queries. The following sections describe the cuOpt-supported features for Task data.
Pickup Deliveries
Some use cases 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.
Order Priorities
Priorities of each task are such that tasks with lower values have a higher priority. This should be used with the ‘drop infeasible tasks’ flag such that if constraints are limited and not all tasks can be completed, then at least the tasks with higher priority can be completed, increasing customer satisfaction and product retention.