Solver Configuration

CuOpt has innovatively adapted meta-heuristics (tabu search, guided local search, ant colony) to exploit the power of GPU architecture using parallel climbers. Climbers enable parallel exploration of the solution space, and each climber is essentially a separate thread of execution working on a distinct subset of the solution space. Each climber is only a weak solver, executing hill climber heuristics that cannot escape local optima, but combining local climbers with the meta-heuristics allows a methodical exploration of the solution space and, in practice, rapid convergence to a neighborhood of the global optima.

There is no guarantee that the global optima will be reached, only that we find a ‘good’ solution in a reasonable amount of time.

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.

Soft Time Windows

With the soft time window option, we can relax a hard time window constraints and a penalty to come up with a solution but at an additional cost. For soft windows, in the solver config, set solution_scope = 1. This will set the scope to SOFT_TW and expand the search to infeasible regions. Additionally, this can be implemented by introducing penalties. If the constraints are relaxed, certain tasks can be prioritized by adding a penalty. cuOpt will try to complete these tasks first and then relax the constraints for the rest of the tasks if necessary. If the initial solution is infeasible, soft time windows can relax time constraints to get a feasible solution.

Custom Cost Functions

The main objective of the solver is to optimize the cost. If other criteria should be considered when solving for an optimal solution, this function selects the best solution across all climbers based on other criteria. The objective function can be defined as a linear combination of the different objectives. By default, the solver optimizes for vehicle count first and cost second. Customers can set multiple cost matrices using set_cost_matrix in addition to set_travel_time_matrix.

© Copyright 2021-2023, NVIDIA. Last updated on Jul 14, 2023.