BP-MDS: Million-Scale Approximate CVRP in Minutes via Parallel Divide-and-Conquer

Authors:
Open Access
Publisher website
Google Scholar
Abstract
The Capacitated Vehicle Routing Problem (CVRP) is a well-known NP-hard problem with wide applications in logistics and transportation. Given the combinatorial nature of the problem, a diverse set of heuristics has been proposed in the literature to obtain approximate solutions to CVRP. Prior research has largely focused on small- and medium-sized instances, having up to a few thousand customers. With growing instance sizes and problem complexity in logistics and transportation, there is a pressing need to design scalable techniques for CVRP. The current state-of-the-art CVRP heuristics struggle to scale to large problem instances, taking prohibitively long to arrive at a reasonable solution and also having a massive memory footprint. We introduce BP-MDS, a parallel divide-and-conquer framework for approximate CVRP that targets large-scale (million-customer) instances while achieving low optimality gaps. BP-MDS decomposes the problem into smaller subproblems that are processed concurrently, exhibiting empirically near-linear scalability with respect to input size and strong scaling across threads. Experimental results show that BP-MDS achieves 20 × –60 × speedups over ParMDS and up to 100 × (single-threaded) and 2370 × (multi-threaded) speedups over HGS-CVRP. BP-MDS solves CVRP instances with up to 5 million customers in 8 minutes.

This publication has 18 references indexed in Scilit: