Beyond Decoupled Decisions: Jointly Learning Label Extension and Column Selection in Column Generation for Vehicle Routing Problems

Column generation (CG) is a powerful framework for large-scale routing optimization that avoids exhaustive enumeration by iteratively solving master and pricing problems. However, its efficiency is constrained by two coupled bottlenecks: the labeling-based pricing problem spends substantial computation exploring labels and uncovering many redundant candidate columns, while only a small, complementary subset materially improves the master problem. We study CG with routing pricing subproblems solved by labeling algorithms and formulate label-extension ordering and column selection as two sequential decisions within a shared Markov decision process. We consider a practical setting that learns from rich pre-collected CG trajectories without solving CG online during training, using data generated by existing CG solvers. We propose Coupled-CG, a two-stage offline Q-learning framework with stage-specific conservative regularization that combines support-aware value learning for extension ordering, relation-conditioned marginal column selection, and coupled Bellman updates that propagate value across the two stages and successive CG iterations. Experiments on public CVRPTW benchmarks demonstrate substantial reductions in labeling effort and end-to-end CG runtime. Ablation studies quantify the additional gains from jointly learning the two decisions, while instance-level analyses identify the structural characteristics of instances that benefit most from Coupled CG.