Column Generation Algorithms for the Capacitated m-Ring-Star Problem
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 onedepot 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
Edna A. Hoshino Cid C. de Souza
University of Mato Grosso do Sul, Department of Computing and Statistic,Campo Grande MS, Brazil University of Campinas,Institute of Computing, Campinas SP, Brazil
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
631-641
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）