Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows

H(x) includes large-weight penalty terms for each constraint (visiting each customer once, capacity limit, time windows, depot start/return, etc.). The result is a quadratic binary optimization problem whose ground-state solution corresponds to an optimal or near-optimal set of routes for the CVRPTW [14]. Prior works have demonstrated how to construct such QUBO models for vehicle routing problems. For instance, Papal-itsas et al. [14] developed a QUBO model for the Traveling Salesman Problem with Time Windows, encoding time window constraints with binary variables and penalties. Likewise, recent studies have formulated capacitated VRPs as QUBO by embedding route feasibility conditions into the objective function [8]. Although formulating the CVRPTW as a QUBO is complex - especially due to the time window inequalities - it enables the use of quantum annealers and digital annealing hardware to search for high-quality solutions by minimizing the combined objective [10].