Design of capacitated multicommodity networks with multiple facilities
成果类型：
Article
署名作者：
Agarwal, YK
署名单位：
Indian Institute of Management (IIM System); Indian Institute of Management Lucknow
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.50.2.333.423
发表日期：
2002
页码：
333-344
关键词：
摘要：
This paper addresses the problem of designing a multicommodity network using several facilities with different costs and capacities. The problem is addressed in a special context of designing private telecommunications networks using Fractional-T1 services. The algorithm starts from any given solution of the problem and gradually improves it by solving a series of subproblems, arriving at a local minimum. The subproblem is defined over a subset of links, called the subnetwork, by using one of the links as the base link. It is shown that the subproblem can be formulated as a multiple choice knapsack problem that is solved by dynamic programming. Computational results and lower bounds are reported on problems of up to 20 nodes and up to 3 facilities. On most problems, the algorithm produces solutions within about 5% of lower bound on the average. Although it was not possible to compute lower bounds for larger problems, heuristic solutions and running times are reported for problems of up to 99 nodes and four facilities.