User-oriented cumulative vehicle routing: a column generation approach with enhanced labeling

This work studies a user-oriented formulation of the cumulative vehicle routing problem where the objective is to minimize total passenger ride time. Optimizing this objective within a column generation framework is challenging because the reduced cost structure may violate the nondecreasing property required by conventional dominance rules in labeling algorithms for resource-constrained shortest path problems. To address this issue, we introduce additional resources that restore this property and enable efficient labeling strategies for solving the pricing problem on benchmark instances.