Abstract
This paper examines a network design problem that arises in the telecommunications industry. In this problem, communication between a gateway vertex and a number of demand vertices is achieved through a network of fiber optic cables. Since each cable has an associated capacity (bandwidth), enough capacity must be installed on the links of the network to satisfy the demand, using possibly different types of cables. Starting with a network with no capacity or some capacity already installed, a tabu search heuristic is designed to find a solution that minimizes the cost of installing any additional capacity on the network. This tabu search applies a k-shortest path algorithm to find alternative paths from the gateway to the demand vertices. Numerical results are presented on different types of networks with up to 200 vertices and 100 demand vertices.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R.K., T.L. Magnanti, and J.B. Orlin. (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice-Hall.
Baker, J. (1985). “Adaptive Selection Methods for Genetic Algorithms.” In J.J. Grefenstette (ed.), Proceedings of the First Int. Conf. on Genetic Algorithms and their Applications. Hillsdale, NJ: Lawrence Erlbaum Associates, pp. 101-111.
Balakrishnan, A., T.L. Magnanti, and P. Mirchandani. (1998). “Network Design.” In M. Dell'Amico, F. Maffioli, and S. Martello (eds.), Annotated Bibliographies in Combinatorial Optimization. Wiley, pp. 311-334.
Balakrishnan, A., T.L. Magnanti, and R.T. Wong. (1989). “A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design.” Operations Research 37, 716-740.
Barahona, F. (1996). “Network Design Using Cut Inequalities.” SIAM J. on Optimization 6, 823-837.
Bienstock, D. and O. Günlük. (1996). “Capacitated Network Design-Polyhedral Structure and Computation.” INFORMS J. on Computing 8, 243-259.
Crainic, T.G., A. Frangioni, and B. Gendron. (1998). “Bundle-Based Relaxation Methods for Multicommodity Capacitated Fixed Charge Network Design Problems.” Technical Report CRT-98-45, Centre de recherche sur les transports, Université de Montréal.
Crainic, T.G., M. Gendreau, and J.M. Farvolden. (1996). “Simplex-Based Tabu Search for the Multicommodity Capacitated Fixed Charge Network Design Problem.” Technical Report CRT-96-07, Centre de recherche sur les transports, Université de Montréal.
Dijkstra, E.W. (1959). “ANote on Two Problems in Connection with Graphs.” Numerische Mathematik 1, 269-271.
Gavish, B. and I. Neuman. (1989). “A System for Routing and Capacity Assignment in Computer Communication Networks.” IEEE Trans. Commun., 360-366.
Gavish, B. and A. Altinkemer. (1990). “Backbone Network Design Tools with Economic Tradeoffs.” ORSA J. on Computing 2, 236-252.
Gendron, B., T.G. Crainic, and A. Frangioni. (1998). “Multicommodity Capacitated Network Design.” In B. Sansó and P. Soriano (eds.), Telecommunications Network Planning. Kluwer, pp. 1-19.
Gendron, B. and T.G. Crainic. (1996). “Bounding Procedures for Multicommodity Capacitated Network Design Problems.” Technical Report CRT-96-06, Centre de recherche sur les transports, Université de Montréal.
Glover, F. (1989). “Tabu Search-Part I.” ORSA J. on Computing 1, 190-206.
Glover, F. (1990). “Tabu Search-Part II.” ORSA J. on Computing 2, 4-32.
Glover, F. (1997). “Tabu Search and Adaptive Memory Programming-Advances, Applications and Challenges.” In R.S. Barr, R.V. Helgason, and J.L.Kennington (eds.), Advances in Metaheuristics, Optimization and Stochastic Modeling Technologies. Boston: Kluwer, pp. 1-75.
Glover, F. and M. Laguna. (1997). Tabu Search. Boston: Kluwer.
Holmberg, K. and D. Yuan. (1996). “A Lagrangean Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem.” Research Report LiTH-MAT-R-1996-23, Dept. of Mathematics, Linkoping Institute of Technology.
Magnanti, T.L. and P. Mirchandani. (1993). “Shortest Paths, Single Origin-Destination Network Design and Associated Polyhedra.” Networks 23, 103-121.
Magnanti, T.L., P. Mirchandani, and R. Vachani. (1993). “The Convex Hull of Two Core Capacitated Network Design Problems.” Mathematical Programming 60, 233-250.
Magnanti, T.L., P. Mirchandani, and R. Vachani. (1995). “Modeling and Solving the Two-Facility Capacitated Network Loading Problem.” Operations Research 43, 142-157.
Magnanti, T.L. and R.T. Wong. (1984). “Network Design and Transportation Planning: Models and Algorithms.” Transportation Science 18, 1-55.
Miaou, S.P. and S.M. Chin. (1991). “Computing k-Shortest Path for Nuclear Spent Fuel Highway Transportation.” European J. of Operational Research 53, 64-80.
Minoux, M. (1989). “Network Synthesis and Optimum Network Design Problems: Models, Solution Methods and Applications.” Networks 19, 313-360.
Ng, T. and D. Hoang. (1987). “Joint Optimization of Capacity and Flow Assignment in a Packet-Switched Communication Network.” IEEE Trans. Comput. 35, 202-209.
Raghavan, S. (1995). “A Heuristic for the IOF Routing Problem.”Working Paper, US West Advanced Technologies, Boulder, CO.
Rochat, Y. and É.D. Taillard. (1995). “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing.” Journal of Heuristics 1, 147-167.
Shier, D.R. (1979). “On Algorithms for Finding the k-Shortest Paths in a Network.” Networks 9, 195-214.
Taillard, É.D. (1993). “Parallel Iterative Search Methods for Vehicle Routing Problems.” Networks 23, 661-673.
Whitley, D. (1989). “The GENITOR Algorithm: Why Rank-Based Allocation of Reproductive Trials is Best.” In J.D. Schaffer (ed.), Proceedings of the Third Int. Conf. on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann, pp. 116-121.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Berger, D., Gendron, B., Potvin, JY. et al. Tabu Search for a Network Loading Problem with Multiple Facilities. Journal of Heuristics 6, 253–267 (2000). https://doi.org/10.1023/A:1009679511137
Issue Date:
DOI: https://doi.org/10.1023/A:1009679511137