Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems
针对车辆容量、成本、车场分配或可服务客户子集不同的异构车队VRP变体，提出一种增强型分支切割定价算法，融合扩展容量割和秩1割等高级特性，在多达200个客户的算例上显著优于现有精确算法。
This paper considers a family of Vehicle Routing Problem (VRP) variants that generalize the classical Capacitated VRP by taking into account the possibility that vehicles differ by capacity, costs, depot allocation, or even by the subset of customers that they can visit. This work proposes a Branch-Cut-and-Price algorithm that adapts advanced features found in the best performing exact algorithms for homogeneous fleet VRPs. The original contributions include: (i) the use of Extended Capacity Cuts, defined over a pseudo-polynomially large extended formulation, together with Rank-1 Cuts, defined over the Set Partitioning Formulation; (ii) the concept of vehicle-type dependent memory for Rank-1 Cuts; and (iii) a new family of lifted Extended Capacity Cuts that takes advantage of the vehicle-type dependent route enumeration. The algorithm was extensively tested in instances of the literature and was shown to be significantly better than previous exact algorithms, finding optimal solutions for many instances with up to 200 customers and also for some larger instances. A new set of benchmark instances is also proposed.