Commenced in January 2007
Paper Count: 30855
Integer Programming Model for the Network Design Problem with Facility Dependent Shortest Path Routing
Authors: Taehan Lee
Abstract:We consider a network design problem which has shortest routing restriction based on the values determined by the installed facilities on each arc. In conventional multicommodity network design problem, a commodity can be routed through any possible path when the capacity is available. But, we consider a problem in which the commodity between two nodes must be routed on a path which has shortest metric value and the link metric value is determined by the installed facilities on the link. By this routing restriction, the problem has a distinct characteristic. We present an integer programming formulation containing the primal-dual optimality conditions to the shortest path routing. We give some computational results for the model.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1125753Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 792
 R. K. Ahuja, Thomas L. Magnanti, and James B. Orlin. (1993) Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.
 M. Fischetti, Polo, C., and Scantamburlo, M. (2004). A local branching heuristic for mixed-integer programs with 2-level variables, with an application to a telecommunication network design problem. Networks, 44(2), 61-72.
 B. Gendron, Crainic, T. G., and Frangioni, A. (1999). Multicommodity capacitated network design. Springer US.
 E. Gourdin, Labb, M., and Yaman, H. (2001). Telecommunication and location.
 K. Holmberg and Yuan, D. (2000). A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Operations Research, 48(3), 461-481.
 D. S. Johnson, Lenstra, J. K., and Kan, A. H. G. (1978). The complexity of the network design problem. Networks, 8(4), 279-285.
 B.Y. Kara and V. Verter, Designing a road network for hazardous materials transportation, Transportation Science, 38(2):188, 2004.
 K.T. Ko, Tang, K.S.,Chan, C.Y. and Man, K.F. (1997). Packet Switched Communication Network Design using GA. Proceeings of GARESIA97, 398 - 403
 T. Lee, S. Park and K. Park, (2000) A Genetic Algorithm for Packet Data Network Design, Proceedings of INFORMS-KORMS Seoul 2000.
 S. Pierre and Legault, G. (1996) An Evolutionary Approach for Configuring Economical Packet Switched Computer Networks. Artificial Intelligence in Engineering, 10, 127-134