Solving the Capacitated Vehicle Routing Problem with Time Windows with Deep Learning and Quantum-Inspired Computing

Working Groups: Lehrstuhl Diskrete Mathematik

Collaborators (MAT): Jorin Dornemann, M. Sc.

Description

Only very few methods exist that use deep learning to solve routing problems with hard constraints. We develop a supervised deep learning-based non-autoregressive approach to approximately solve the CVRPTW. The constructive nature of the proposed approach allows to cope with the hard constraints and the non-autoregressive nature balances the costly search for correct solutions with respect to the computation time. Furthermore, the deep learning approach is combined with quantum-inspired computing by formulating the optimization problem as a quadratic unconstrained binary optimization problem and applying the trained deep network as a form of learned problem reduction to reduce the search space to a size that allows a quantum(-inspired) computer to efficiently handle it. This approach combining deep learning and quantum computing aims at highlighting the possibilities of combining recent results from both fields of research for future research.

References

[1] Kallehauge B, Larsen J, Madsen OB, Solomon MM. Vehicle routing problem with time windows. Desaulniers G, Desrosiers J, Solomon MM, editors, Column Generation (Boston, MA: Springer US) (2005), 67–98.

[2] Joshi CK, Laurent T, Bresson X. An efficient graph convolutional network technique for the travelling salesman problem. arXiv (2019) arXiv:1906.01227.

[3] Suen WY, Parizy M, Lau HC. Enhancing a QUBO solver via data driven multi-start and its application to vehicle routing problem. Proceedings of the Genetic and Evolutionary Computation Conference Companion (ACM) (2022), 2251–2257.