We consider a variant of the vehicle routing problems with time windows, where the objective includes the inconvenience cost modeled by a convex function on each node. We formulate this mixed integer convex program using a novel set partitioning formulation, by considering all combinations of routes and block structures over the routes. We apply a branch-and-price framework to solve this formulation. To solve the pricing problem, we leverage a recursive algorithm that solves the optimal service time scheduling problem given a fixed route, and develop a labeling algorithm with a dominance rule that is easy to check. In our computational study, we show the effectiveness of the labeling algorithm compared to state-of-the-art mixed integer convex programming solvers on an extensive set of vehicle routing problems with time windows and quadratic inconvenience costs.
Article
View Vehicle Routing Problems with Time Windows and Convex Node Costs