A branch-cut-and-price algorithm for the generalized vehicle routing problem
针对广义车辆路径问题（客户被分成互斥的簇，每簇只访问一个客户），开发了分支切割定价算法，用动态规划求解定价子问题，能求解八个此前未解的最优实例。
We develop a branch-cut-and-price algorithm for the generalized vehicle routing problem (GVRP)—a variant of the vehicle routing problem where customers are partitioned into mutually exclusive clusters. The decision-maker seeks to determine minimum cost routes using a limited number of vehicles such that every cluster is visited by exactly one route, and within any cluster a single customer is visited, subject to vehicle capacity constraints. The pricing subproblem is solved using a specialized dynamic programming algorithm. Computational results show that the proposed algorithm compares favorably against a state-of-the-art branch-and-cut algorithm and solves to optimality eight previously open GVRP instances in the literature.