Tabu Search for a Network Loading Problem with Multiple Facilities |
| |
| Authors: | David Berger Bernard Gendron Jean-Yves Potvin S Raghavan Patrick Soriano |
| |
| Institution: | (1) Centre Universitaire des Sciences et Techniques, Université Blaise Pascal, B.P. 206, 63174 Aubière Cedex, France;(2) Centre de recherche sur les transports, Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal, Québec, Canada, H3C 3J7;;(3) Département d'informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal, Québec, Canada, H3C 3J7;(4) Robert H. Smith School of Business, University of Maryland, College Park, MD 20742, USA;(5) Ecole des Hautes Etudes Commerciales 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7 |
| |
| 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. |
| |
| Keywords: | network design telecommunications tabu search k-shortest paths |
| 本文献已被 SpringerLink 等数据库收录！ |
|
