Introduction

NVIDIA cuOpt is a GPU-accelerated combinatorial optimization engine for solving complex routing problems with multiple constraints, while delivering new capabilities like dynamic rerouting and robotic simulation. Typical problem spaces such as the Traveling Salesperson Problem (TSP), Vehicle Routing Problem (VRP), and Pickup and Delivery Problem (PDP) that are common to the logistics and operations research industry have historically frustrated many in the ecosystem, due to the inaccuracy and long wait times that are associated with CPU solvers. NVIDIA cuOpt accelerates these problem spaces through advanced use of parallel heuristics, and supports many variations of these base problems, such as adding constraints on vehicle capacities, delivery time windows, and vehicle drivers’ shifts and breaks during the work day.

These operational research and logistics problems are incredibly compute-intensive with massive operational costs. Most problems common to this space are NP-hard, or in layman’s terms there exists no apparent or efficient algorithm to directly calculate a solution. NVIDIA GPUs bring the throughput capabilities needed to fuel the most ambitious heuristics (evolutionary algorithms, guided ejection search, local search, etc.) while also supporting the most challenging constraints with accelerated runtime and better accuracy.

The cuOpt production-ready solver is offered as a RESTful API Service that is simple and easy to use with any browser. Using the NVIDIA cuOpt service, users do not need to worry about resource provisioning or environment setup; simply pip install the cuOpt Python thin client, enter your credentials, and solve your routing problems.

TSP, VRP, and PDP

The Vehicle Routing Problm (VRP) and Pickup and Delivery Problems (PDP) are derived from the Traveling Salesperson Problem (TSP), which is one of the most studied problems in operations research and, more generally, in computer science. TSP asks the following question: “Given a list of destinations and a matrix of distances between each pair of destinations, what is the shortest possible route that visits each destination exactly one time and returns to the original location?” For example, the TSP has several applications in planning and logistics, where a good solution can save significant travel time and fuel costs in the transportation and delivery of goods. VRP and PDP are essentially extensions of TSP with additional complexity.

The VRP generalizes the TSP to solve for the optimal set of routes for a fleet of vehicles in order to deliver to a given set of customers. The PDP adds the possibility of two different types of services, namely pickup or delivery, whereas in VRP all customers require the same service be performed at a customer location.

What is NP-Hard?

In mathematical terms, the TSP, VRP, and PDP belong to the class of problems called “NP-hard,” meaning that the required time to find an optimal solution increases at least exponentially with the size of the problem (for example, the number of deliveries to make). The number of possible states in the search space for VRP is of the order of n!, where n is the number of nodes (locations the vehicle must reach) in the network. Given the large search space, brute force approaches are practically intractable for large problem sizes (more than a few dozen locations), even on a modern supercomputer.

For instance, a ten-node problem has about 3628800 (3.6*10^6) possible states, but if we double the problem size, the solution space becomes 2432902008176640000 (2.4 \* 10^18), which means that the solution space grew by a factor of 670442572800; it is about 6.7 trillion times larger. In other words, there is a massive need for more compute.

The Necessity for Heuristics

Given the time and computational resources required for brute-force enumeration, obtaining the exact optimal solution is not realistic at all. However, there are well-studied heuristics that yield near-optimal solutions for very large networks within a reasonable time, and NVIDIA cuOpt focuses on using these heuristics.

How cuOpt Solves the Problem

cuOpt first generates an initial population of solutions, then iteratively improves the population until the time limit is reached, and picks the best solution from the population.

GPUs Unleash Massive Parallel Computing Capabilities

With their ability to harness thousands of parallel cores, GPUs are an ideal computing platform for accelerating massive parallelizable problems where thousands or millions of separate tasks are to be computed in parallel. This enables orders-of-magnitude speedups when running heuristics for this class of problems, thereby reducing operational costs and improving solution accuracy.

Using cuOpt

1. cuOpt provides a managed service API that is intuitive and easy to adopt. It exposes a composable solver for all the implemented variants of the VRP problem and available heuristics.

2. A Python reference client and CLI is provided for cuOpt that enables users to easily submit cuOpt problems represented as JSON objects. Users are free to build their own clients using the reference client and documentation as guides.