In this paper we propose an integer programming formulation for the capacitated m-ring-star problem (CmRSP) based on a set covering model and develop an exact branch-and-price (BP) algorithm to solve it exactly. The CmRSP is a variant of the classical one-depot capacitated vehicle routing problem in which a customer is either on a route or is connected to another customer or to some connection point present in a route. The set of potential connection points and the number m of vehicles are given a priori. Routing and connection costs are also known and the goal is to minimize the sum of routing and connection costs. To our knowledge, the only exact approach for the CmRSP is a branch-and-cut (BC) proposed in [2]. Extensive experimentation reported here shows that our BP algorithm is competitive with the BC algorithm. This performance was achieved after a profound investigation of the alternatives for column generation relaxation and a careful implementation of the pricing algorithm.
展开▼
