Vehicle Routing Problem (VRP) and Pickup and Delivery Problem (PDP) are derived from TSP, one of the most studied problems in operations research and, more generally, in computer science. TSP asks: “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 once 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 transporting and delivering goods. VRP and PDP are extensions of TSP with additional complexity. VRP generalizes the TSP to solve for the optimal set of routes for a fleet of vehicles to deliver to a given set of customers. PDP adds the possibility of two different types of services, namely pickup or delivery, whereas, in VRP, all customers require the same service to be performed at a customer location.
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, i.e., there is a massive need for more compute.
Given the time and computational resources required for brute-force enumeration, obtaining the optimal solution is unrealistic. However, well-studied heuristics yield near-optimal solutions for very large networks within a reasonable time, and NVIDIA cuOpt focuses on using these heuristics.
cuOpt generates a feasible initial solution (initial phase) and then iteratively improves the solution quality (improvement phase). The termination criteria are reached when the solution quality improves slower than a threshold tolerance (adaptively set internally by cuOpt heuristics) or if an execution time limit has elapsed.
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.
cuOpt provides developer APIs in Python that are intuitive and easy to adopt. It exposes a composable solver for all the implemented variants of the VRP problem and available heuristics. Developer APIs are available by consuming an NVIDIA-managed service offering or deploying a containerized microservice on-premise.
The ready-to-use cuOpt cloud service, delivered as a RESTful API Service, minimizes the development effort and simplifies the implementation, enabling organizations to leverage cuOpt – even without deep expertise.
The microserver leverages HTTP POST requests running on port 5000 to accept input data.
This user guide focuses primarily on the cuOpt cloud service.