Abstract
A GRASP embedded Scatter Search is developed for the multicommodity capacitated network design problem. Difficulty for this problem arises from the fact that selection of the optimal network design is an NP-complete combinatorial problem. There exist no polynomial exact algorithms which can solve this problem in a reasonable period of time for realistically sized instances. In such cases, heuristic procedures are commonly used. Two strategies were designed for GRASP: a traditional approach and a memory based technique. As for Scatter Search, 5 different strategies were used to update the reference set. Computational results on a large set of randomly generated instances show the convenience of the proposed procedures.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alvarez, A., J.L. González-Velarde, and K. De Alba. (2001). “Scatter Search for the Multicommodity Capacited Network Design Problem.” In Proceeding of 6th Annual International Conference on Industrial Engineering–Theory, Aplications and Practice, San Francisco, CA, USA.
Argüello, M.F., J.F. Bard, and G. Yu. (1997). “A Grasp for Aircraft Routing in Response to Groundings and Delays.” Journal of Combinatorial Optimization 1(3), 211–228.
Arráiz, E., A. Martínez, O. Meza, and M. Ortega. (2001). “GRASP and Tabu Search Algorithms for Computing the Forwarding Index in a Graph.” In Proceedings of MIC 2001, Porto, Portugal, July, pp. 367–370.
Balakrishnan, A. and T.L. Magnanti. (1989). “A Dual Ascent Procedure for Large-Scale Uncapacitated Network Design.” Operations Research 37(5), 716–740.
Binato, S., W.J. Hery, D. Loewenstern, and M.G.C. Resende. (2002). “A Greedy Randomized Adaptive Search Procedure for Job Shop Scheduling.” In Ribeiro, C. and Hansen, P. (eds.), Essays and Surveys on Metaheuristics, Kluwer, Boston, USA, pp. 58–79.
Campos, V., M. Laguna, and R. Martí. (1999). “Scatter Search for the Linear Ordering Problem.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization, McGraw-Hill: New York, USA, pp. 331–339.
Chardaire, P., G.P. McKeown, and J.A. Maki. (2001). “Application of GRASP to the Multiconstraint Knapsack Problem.” In E.J.W. Boers, J. Gottlieb, P.L. Lanzi, R.E. Smith, S. Cagnoni, E. Hart, G.R. Raidl, and H. Tijink, (eds.), Applications of Evolutionary Computing, Lecture Notes in Computer Science, Vol. 2037, Springer, Heidelberg: Germany, pp. 30–39.
CPLEX Optimization, Inc. (1999). ILOG CPLEX 7.1 Reference Manual. Incline Village, NV: USA.
Crainic, T.G., A. Frangioni, and B. Gendron. (2001). “Bundle-Based Relaxation Methods for Multicommodity Capacitated Fixed Charge Network Design.” Discrete Applied Mathematics 112(1–3), 73–79.
Crainic, T.G., M. Gendreau, and J. Farvolden. (2000). “A Simplex-Based Tabu Search Method for Capacitated Network Design.” INFORMS Journal on Computing 12(3), 223–236.
Delgado, C., M. Laguna, and J. Pacheco. (2004). “Minimizing Labor Requirements in a Periodic Vehicle Loading Problem.” To appear in Computational Optimization and Applications.
Feo, T.A. and M.G.C. Resende. (1989). “A Probabilistic Heuristic for a Computationally Difficult Set Covering Problem.” Operations Research Letters 8(2), 67–71.
Feo, T.A. and M.G.C. Resende. (1995). “Greedy Randomized Aaptive Search Procedures.” Journal of Global Optimization 6(2), 109–133.
Fernández, E. and R. Martí. (1999). “GRASP for Seam Drawing in Mosaicking of Aerial Photographic Maps.” Journal of Heuristics 5(1), 81–197.
Fleurent, C. and F. Glover. (1999) “Improved Constructive Multistart Strategies for the Quadratic Assignment Problem using Adaptive Memory.” INFORMS Journal on Computing 11(2), 198–204.
Gendron, B. and T.G. Crainic. (1996). “Bounding Procedures for Multicommodity Capacitated Fixed Charge Network Design Problems.” Publication CRT-96-06. Centre de Recherche sur le Transport, Université de Montréal, Montreal, Canada, January.
Gendron, B. and T.G. Crainic. (1994a). “Parallel Implementations of Bounding Procedures for Multicommodity Capacitated Network Design Problems.” Publication CRT-94-45. Centre de Recherche sur le Transport, Université de Montréal, Montreal, Canada, September.
Gendron, B. and T.G. Crainic. (1994b). “Relaxations for Multicommodity Capacitated Network Design Problems.” Publication CRT-965. Centre de Recherche sur le Transport, Université de Montréal, Montreal, Canada, February.
Glover, F. (1998). “A Template for Scatter search and path relinking.” In J.K. Hao, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers, (eds.), Artificial Evolution: Third European Conference, Lecture Notes in Computer Science, Vol. 1363, Springer, Heidelberg, Germany, pp. 13–54.
Herrmann, J.W., G. Ioannou, I. Minis, J.M. y Proth. (1996). “A Dual Ascent Approach to the Fixed-Charge Capacitated Network Design Problem.” European Journal of Operational Research 95(4), 476–490.
Hochbaum, D.S. and y Segev A. (1989). “Analysis of a Flow Problem with Fixed Charges.” Networks, 19(3), 291–312.
Holmberg, K. and J. Hellstrand. (1998). “Solving the Uncapacitated Network Design Problem by a Lagrangean Heuristic and Branch-and-Bound.” Operations Research 46(2), 247–258.
Holmberg, K. and D. Yuan. (2000). “A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem.” Operations Research 48(3), 461–481.
Johnson, D.S, J.K. Lenstra, H.G. y Rinnooy. (1978). “The Complexity of the Network Design Problem.” Networks 8(4), 279–285.
Laguna M. (2002). “Scatter Search.” In P.M. Pardalos, and M.G.C. Resende, (eds.), Handbook of Applied Optimization. pp. 183–193.
Laguna, M. and V.A. Armentano. (2004). “Lessons from Applying and Experimenting with Scatter Search.” In C. Rego and A. Bahram, (eds.), Adaptive Memory and Evolution: Tabu Search and Scatter Search. Kluwer, (in press).
Laguna, M. and R. Martí. (2003). Scatter Search Methodology and Implementations in C. Kluwer, Boston, USA.
Lawler, E.L. (1972). “A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and its Application to the Shortest Path Problem.” Management Science 18, 401–405.
Magnanti, T., P. Mireault, and R. Wong. (1986). “Tailoring Benders Decomposition for Uncapacitated Network Design.” Mathematical Programming Study, 26 112–154.
Magnanti, T. and R. Wong. (1984). “Network Design and Transportation Planning: Models and Algorithms.” Transportation Science 18(1) 1–55.
Martí, R., H. Lourenço, and M. Laguna. (2000). “Assigning Proctors to Exams with Scatter Search.” In M. Laguna and J.L. González-Velarde, (eds.), Computing Tools for Modeling Optimization and Simulation: Interphases in Computer Science and Operations Research. Kluwer: Boston, USA. pp. 215-227.
Moscato, P. (2000). Memetic Algorithms. In P.M. Pardalos and M.G.C. Resende, (eds.), Handbook of Applied Optimization. Oxford University Press, USA.
Pacheco, J.A. and S. Casado. (2004). “Solving Two Location Models with Few Facilities by Using a Hybrid Heuristic.” A real health resource case. (In Press) Computers and Operation Research No 113.
Sridhar, V. and J.S. Park. (2000). “Benders-and-Cut Algorithm for Fixed-Charge Capacitated Network Design Problem.” European Journal of Operational Research 125(3), 622–632.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Alvarez, A.M., González-Velarde, J.L. & De-Alba, K. Grasp Embedded Scatter Search for the Multicommodity Capacitated Network Design Problem. J Heuristics 11, 233–257 (2005). https://doi.org/10.1007/s10732-005-1509-4
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10732-005-1509-4