A hybrid quantum-inspired and deep learning approach for the capacitated vehicle routing problem with time windows

This paper introduces a hybrid approach to address the Capacitated Vehicle Routing Problem with Time Windows by integrating quadratic unconstrained binary optimization (QUBO) hardware with deep learning-assisted heuristics. The proposed three-phase heuristic leverages the strengths of QUBO-solving hardware while mitigating its limitations, aiming at offering better scalability to larger problem instances. In the first phase, a deep learning-enhanced QUBO formulation is employed to partition the vertices into clusters. The second phase uses deep learning-assisted tree searches to generate candidate routes within each cluster. These candidate routes are combined in the third phase into a feasible global solution by solving a quadratic unconstrained binary set partition problem. This framework ensures compliance with capacity and time window constraints while maintaining computational efficiency. Computational results indicate that the hybrid approach is promising to potentially scale well for larger problem cases while respecting hardware limitations, offering a viable approach for leveraging quantum-inspired hardware in combination with advanced heuristics for solving complex combinatorial optimization problems.

Subjects

Deep Learning

Quantum-inspired Computing

Vehicle Routing

DDC Class

600: Technology

519: Applied Mathematics, Probabilities

Options

A hybrid quantum-inspired and deep learning approach for the capacitated vehicle routing problem with time windows