Design of Capacitated Multicommodity Networks with Multiple Facilities

Yogesh K. Agarwal ()
Additional contact information
Yogesh K. Agarwal: Indian Institute of Management, Prabandh Nagar, Off Sitapur Road, Lucknow, India 226013

Operations Research, 2002, vol. 50, issue 2, 333-344

Abstract: 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.

Keywords: Networks; multicommodity: telecommunications network design (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.2.333.423 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:50:y:2002:i:2:p:333-344

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().