An Integer Linear Programming Formulation and Branch-and-Cut Algorithm for the Capacitated m-Ring-Star Problem |
| |
| Institution: | 1. School of Management, Hefei University of Technology, Hefei, Box 270, Hefei 230009, Anhui, P.R. China;;2. Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei, Box 270, Hefei 230009, Anhui, P.R. China;;3. Ministry of Education Engineering Research Center for Intelligent Decision-Making & Information System Technologies, Hefei, 230009, Anhui, P.R. China;;4. School of Electronic Engineering, Xidian University, Xi''an, 710071, P.R. China;;5. Department of Electrical & Computer Engineering, University of Alberta, Edmonton, T6R 2V4, AB, Canada;1. Department of Industrial and Manufacturing Systems Engineering, University of Hong Kong, HK;2. Manufacturing and Industrial Engineering Cluster, School of MAE, Nanyang Technological University (NTU), Singapre;1. Department of Industrial Engineering, University of Tabriz, 29th Bahman Boulevard, Tabriz 51666-14766, Iran;2. School of Industrial Engineering & Innovation Sciences, TU Eindhoven, Eindhoven, The Netherlands;3. TUM School of Management, Technische Universität München, Munich, Germany;1. School of Materials Science and Engineering, Hefei University of Technology, Hefei 230009, China;2. Ultra-Precision Machining Center, Zhejiang University of Technology, Hangzhou 310012, China;3. National-Local Joint Engineering Research Centre of Nonferrous Metals and Processing Technology, Hefei 230009, China;4. Engineering Research Center of High Performance Copper Alloy Materials and Processing, Ministry of Education, Hefei 230009, China;5. Institute for Integrated Radiation and Nuclear Science, Kyoto University, Osaka-fu 590-0494, Japan |
| |
| Abstract: | We study the capacitated m-ring-star problem (CmRSP) that faces the design of minimum cost network structure that connects customers with m rings using a set of ring connections that share a distinguished node (depot), and optionally star connections that connect customers to ring nodes. Ring and star connections have some associated costs. Also, rings can include transit nodes, named Steiner nodes, to reduce the total network cost if possible. The number of customers in each ring-star (ring?s customers and customer connected to it through star connections) have an upper bound (capacity).These kind of networks are appropriate in optical fiber urban environments. CmRSP is know to be NP-Hard. In this paper we propose an integer linear programming formulation and a branch-and-cut algorithm. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
