Chekkala Sandeep Reddy
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Chekkala Sandeep Reddy has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Lakshya Rani P
Indian Institute of Technology Madras, Chennai, India
1 shared publication - Rajesh Pandian Muniasamy
Qualcomm, Bangalore, India
1 shared publication - Rupesh Nasre
Indian Institute of Technology Madras
1 shared publication - Somesh Singh
Siemens EDA, Meylan, France
1 shared publication
Latest Publications
- Open Access
- 27 September 2026
- Published by Association for Computing Machinery (ACM)
- p. 877-887
BP-MDS: Million-Scale Approximate CVRP in Minutes via Parallel Divide-and-Conquer
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.
- 27 September 2026
- Published by Association for Computing Machinery (ACM)
- p. 877-887
Open AccessBP-MDS: Million-Scale Approximate CVRP in Minutes via Parallel Divide-and-Conquer
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.