Abstract
The Fixed-Charge Capacitated Multi-commodity Network Design (CMND) problem consists in finding the optimal configuration, i.e., the arcs to include in the final design, of a network on which the flows of several products (“commodities”) must be routed to satisfy given demands between origin-destination pairs. Each of the arcs that can possibly be included in the design is characterized by its capacity (the maximum amount of flow of all commodities it can support), a fixed cost to be incurred if the arc is selected, and a variable cost for each unit of flow that uses the arc. The objective of the problem is to minimize the total system cost (the sum of the fixed costs of selected arcs and routing costs), while respecting capacity limits.
In this paper, we report on an extensive investigation of different variants of a new metaheuristic, based on the Scatter Search concept originally proposed by Glover, for the CMND. Computational results on a set of small and medium size benchmark instances show that while scatter search is not yet able to match the results of the best existing metaheuristics for the problem, all variants are successful in finding better solutions on some instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Crainic, T. G. and M. Toulouse (2003), “Parallel Strategies for Meta-heuristics”, in F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, Boston, USA, 475–513.
Balakrishnan, A., T.L. Magnanti, and P. Mirchandani (1997), “Network Design”, in M. Dell’Amico, F. Maffioli, and S. Martello (eds.), Annotated Bibliographies in Combinatorial Optimization, Wiley, New York, USA, 311–334.
Crainic, T.G., A. Frangioni, and B. Gendron (2001), “Bundle-Based Relaxation Methods for Multicommodity Capacitated Network Design”, Discrete Applied Mathematics 112, 73–99.
Crainic, T.G., M. Gendreau, and J.M. Farvolden (2000), “A Simplex-Based Tabu Search Method for Capacitated Network Design”, INFORMS Journal on Computing 12, 223–236.
Gendron, B., T.G. Crainic, and A. Frangioni (1998), “Multicommodity Capacitated Network Design”, in B. Sansó and P. Soriano (eds.), Telecommunications Network Planning, Kluwer Academic Publishers, Boston, USA, 1–19.
Ghamlouche, I., T.G. Crainic, and M. Gendreau (2003), “Cycle-based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design”, Operations Research 51, 655–667.
Ghamlouche, I., T.G. Crainic, and M. Gendreau (2004), “Path Relinking, Cycle-based Neighbourhoods and Capacitated Multicommodity Network Design”, Annals of Operations Research 131, 109–133.
Glover, F. (1977), “Heuristics for Integer Programming using Surrogate Constraints”, Decision Sciences 8, 156–166.
Glover, F. (1998), “A Template for Scatter Search and Path Relinking”, in J. Hao, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers (eds.), Artificial Evolution, (Lecture Notes in Computer Science, Vol. 1363), Springer, Berlin, Germany, 13–54.
Glover, F., and M. Laguna (1997), Tabu Search, Kluwer Academic Publishers, Boston, USA.
Glover, F., M. Laguna, and R. Martí (2000), “Fundamentals of Scatter Search and Path Relinking”, Control and Cybernetics 39 (3), 653–684.
Holmberg, K. and D. Yuan (2000), “A Lagrangean Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem”, Operations Research 48 (3), 461–481.
Laguna, M. and R. Martí (2003), Scatter Search: Methodology and Implementations in C, Kluwer Academic Publishers, Boston, USA.
Magnanti, T.L. and R.T. Wong (1986), “Network Design and Transportation Planning: Models and Algorithms”, Transportation Science 18 (1), 1–55.
Minoux, M. (1986), “Network Synthesis and Optimum Network Design Problems: Models, Solution Methods and Applications”, Networks 19, 313–360.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Crainic, T.G., Gendreau, M. (2007). A Scatter Search Heuristic for the Fixed-Charge Capacitated Network Design Problem. In: Doerner, K.F., Gendreau, M., Greistorfer, P., Gutjahr, W., Hartl, R.F., Reimann, M. (eds) Metaheuristics. Operations Research/Computer Science Interfaces Series, vol 39. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-71921-4_2
Download citation
DOI: https://doi.org/10.1007/978-0-387-71921-4_2
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-71919-1
Online ISBN: 978-0-387-71921-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)