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.

Keywords: Integer programming, multicommodity network design, routing, shortest path.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1125753

References:

[1] 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.
[2] 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.
[3] B. Gendron, Crainic, T. G., and Frangioni, A. (1999). Multicommodity capacitated network design. Springer US.
[4] E. Gourdin, Labb, M., and Yaman, H. (2001). Telecommunication and location.
[5] 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.
[6] D. S. Johnson, Lenstra, J. K., and Kan, A. H. G. (1978). The complexity of the network design problem. Networks, 8(4), 279-285.
[7] B.Y. Kara and V. Verter, Designing a road network for hazardous materials transportation, Transportation Science, 38(2):188, 2004.
[8] 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
[9] T. Lee, S. Park and K. Park, (2000) A Genetic Algorithm for Packet Data Network Design, Proceedings of INFORMS-KORMS Seoul 2000.
[10] S. Pierre and Legault, G. (1996) An Evolutionary Approach for Configuring Economical Packet Switched Computer Networks. Artificial Intelligence in Engineering, 10, 127-134