Column generation algorithms for the capacitated m-ring-star problem

Autor(es)

Hoshino, Edna A. ; de Souza, Cid C. ; Hu, XD ; Wang, J

• Tipo de documento: Artigo Científico
• Fonte: Lecture Notes in Computer Science; v. 5092, p. 2-pg., 2008-01-01.

Resumo

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. (AU)

• Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático