More Web Proxy on the site http://driver.im/

article

A Hybrid Simulated Annealing and Simplex Method for Fixed-Cost Capacitated Multicommodity Network Design

Authors:

Masoud Yaghini,

Mohammad Karimi,

Mohadeseh Rahbar,

Rahim AkhavanAuthors Info & Claims

International Journal of Applied Metaheuristic Computing, Volume 2, Issue 4

Pages 13 - 28

https://doi.org/10.4018/jamc.2011100102

Published: 01 October 2011 Publication History

Abstract

The fixed-cost Capacitated Multicommodity Network Design (CMND) problem is a well known NP-hard problem. This paper presents a matheuristic algorithm combining Simulated Annealing (SA) metaheuristic and Simplex method for CMND problem. In the proposed algorithm, a binary array is considered as solution representation and the SA algorithm manages open and closed arcs. Several strategies for opening and closing arcs are proposed and evaluated. In this matheuristic approach, for a given design vector, CMND becomes a Capacitated Multicommodity minimum Cost Flow (CMCF) problem. The exact evaluation of the CMCF problem is performed using the Simplex method. The parameter tuning for the proposed algorithm is done by means of design of experiments approach. The performance of the proposed algorithm is evaluated by solving different benchmark instances. The results of the proposed algorithm show that it is able to obtain better solutions in comparison with previous methods in the literature.

References

[1]

Adenso-Díaz, B., & Laguna, M. (2006). Fine-tuning of algorithms using fractional experimental design and local search. Operations Research, 54, 99-114.

Digital Library

[2]

Ahuja, R. K., Magnanti, T. L., & Oril, J. B. (1993). Theory, algorithms, and application. Upper Saddle River, NJ: Prentice Hall.

[3]

Alvarez, A. M., Lez-Velarde, J. L. G., & De-alba, K. (2005). Scatter search for network design problem. Annals of Operations Research, 138, 159-178.

[4]

Balakrishnan, A., Magnanti, T. L., & Mirchandani, P. (1997). Annotated bibliographies in combinatorial optimization. In Dell'Amico, M., Maffioli, F., & Martello, S. (Eds.), Network design (pp. 311-334). New York, NY: John Wiley & Sons.

[5]

Beasley, J. E. (1990). OR-Library: Distributing test problems by electronic mail. The Journal of the Operational Research Society, 41, 1069-1072.

[6]

Biratteri, M. (2009). Tuning Metaheuristics: A machine learning perspective. Heidelberg, Germany: Springer-Verlag.

[7]

Blum, C., Puchinger, J., Raidl, G. R., & Roli, A. (2011). Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing, 11, 4135-4151.

Digital Library

[8]

Boschetti, M., Maniezzo, V., Roffilli, M., & Rohler, A. B. (2009). Matheuristics: Optimization, simulation and control. In Proceedings of the 6th International Workshop on Hybrid Metaheuristics (pp. 171-177).

[9]

Caserta, M., & Voββ, S. (2009). Metaheuristics: Intelligent problem solving. In Maniezzo, V., Stützle, T., & Voββ, S. (Eds.), Matheuristics: Hybridizing metaheuristics and mathematical programming (pp. 1-38). Berlin, Germany: Springer-Verlag.

[10]

Crainic, T. G. (2000). Service network design in freight transportation. European Journal of Operational Research, 122, 272-288.

[11]

Crainic, T. G., Dejax, P., & Delorme, L. (1989). Models for multimode location problem with interdepot balancing requirement. Annals of Operations Research, 18, 277-302.

[12]

Crainic, T. G., & Gendreau, M. (2002). Cooperative parallel tabu search for capacitated network design. Journal of Heuristics, 8, 601-627.

Digital Library

[13]

Crainic, T. G., & Gendreau, M. (2007). A scatter search heuristic for the fixed-charge capacitated network design problem. Metaheuristics, Operations Research/Computer Science Interfaces Series, Part I, 39, 25-40.

[14]

Crainic, T. G., Gendreau, M., & Farvolden, J. M. (2000). A Simplex-based tabu search method for capacitated network design. INFORMS Journal on Computing, 12, 223-236.

[15]

Crainic, T. G., Gendreau, M., & Hernu, G. (2004). A slope scaling/Lagrangian perturbation heuristic with long-term memory for multicommodity capacitated fixed-charge network design. Journal of Heuristics, 10, 525-545.

[16]

Crainic, T. G., Li, Y., & Toulouse, M. (2006). A first multilevel cooperative algorithm for capacitated multicommodity network design. Computers & Operations Research, 33, 2602-2622.

Digital Library

[17]

Frangioni, A., & Gendron, B. (2008). 0-1 reformulation of the multicommodity capacitated network design problem. Discrete Applied Mathematics, 157, 1229-1241.

Digital Library

[18]

Gendron, B., & Crainic, T. G. (1994). Relaxations for multicommodity capacitated network design problems (Publication No. CRT-945). Montreal, QC, Canada: Centre de recherche sur les transports, Université de Montréal.

[19]

Gendron, B., Crainic, T. G., & Frangioni, A. (1998). Multicommodity capacitated network design. In Sanso, B., & Soriono, P. (Eds.), Telecommunication network planning (pp. 1-19). Boston, MA: Kluwer Academic.

[20]

Ghamlouche, I., Crainic, T. G., & Gendreau, M. (2003). Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design. Operations Research, 51, 655-667.

Digital Library

[21]

Ghamlouche, I., Crainic, T. G., & Gendreau, M. (2004). Path relinking, cycle-based neighborhoods and capacitated multicommodity network design. Annals of Operations Research, 131, 109-133.

[22]

Glover, F., & Kochenberger, G. A. (2003). Handbook of metaheuristics. Boston, MA: Kluwer Academic.

[23]

Jayaraman, V., & Ross, A. (2002). A simulated annealing methodology to distribution network design and management. European Journal of Operational Research, 144, 629-645.

[24]

Katayama, N., Chen, M., & Kubo, M. (2009). Capacity scaling heuristic for the multicommodity capacitated network design problem. Journal of Computational and Applied Mathematics, 232, 90-101.

Digital Library

[25]

Kirkpatrick, S., Gelatt, C., & Vecchi, M. (1983). Optimization by simulated annealing. Science, 220, 671-680. 17813860.

[26]

Magnanti, T. L., & Wong, R. T. (1984). Network design and transportation planning: models and algorithms. Transportation Science, 18, 1-55.

Digital Library

[27]

Minoux, M. (1989). Network synthesis and optimum network design problems: Models, solution methods and applications. Networks, 19, 313-360.

[28]

Minoux, M. (2001). Discrete cost multicommodity network optimization problems and exact solution methods. Annals of Operations Research, 106, 19-46.

[29]

Minoux, M. (2004). Polynomial approximation schemes and exact algorithms for optimum curve segmentation problems. Discrete Applied Mathematics, 144, 158-172.

Digital Library

[30]

Montgomery, D. (2005). Design and analysis of experiments. New York, NY: John Wiley & Sons.

[31]

Ridge, E. (2007). Design of experiments for the tuning of optimization algorithms (Unpublished doctoral dissertation). University of York, York, UK.

Cited By

(2018)A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design ProblemINFORMS Journal on Computing10.5555/2736028.273603227:1(48-58)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.5555/2736028.2736032
(2018)A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design ProblemINFORMS Journal on Computing10.5555/2735998.273600227:1(48-58)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.5555/2735998.2736002
(2018)A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design ProblemINFORMS Journal on Computing10.5555/2725966.272597027:1(48-58)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.5555/2725966.2725970
Show More Cited By

A Hybrid Simulated Annealing and Simplex Method for Fixed-Cost Capacitated Multicommodity Network Design

Recommendations

A three-phase matheuristic for capacitated multi-commodity fixed-cost network design with design-balance constraints

This paper proposes a three-phase matheuristic solution strategy for the capacitated multi-commodity fixed-cost network design problem with design-balance constraints. The proposed matheuristic combines exact and neighbourhood-based methods. Tabu search ...
Randomized heuristics for the Capacitated Clustering Problem

In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between ...
A simulated annealing heuristic for the capacitated location routing problem

The location routing problem (LRP) is a relatively new research direction within location analysis that takes into account vehicle routing aspects. The goal of LRP is to solve a facility location problem and a vehicle routing problem simultaneously. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Applied Metaheuristic Computing

International Journal of Applied Metaheuristic Computing Volume 2, Issue 4

October 2011

57 pages

ISSN:1947-8283

EISSN:1947-8291

Issue’s Table of Contents

Publisher

IGI Global

United States

Publication History

Published: 01 October 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

(2018)A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design ProblemINFORMS Journal on Computing10.5555/2736028.273603227:1(48-58)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.5555/2736028.2736032
(2018)A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design ProblemINFORMS Journal on Computing10.5555/2735998.273600227:1(48-58)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.5555/2735998.2736002
(2018)A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design ProblemINFORMS Journal on Computing10.5555/2725966.272597027:1(48-58)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.5555/2725966.2725970
(2018)A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design ProblemINFORMS Journal on Computing10.5555/2725954.272595827:1(48-58)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.5555/2725954.2725958
(2018)A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design ProblemINFORMS Journal on Computing10.5555/2700896.270090027:1(48-58)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.5555/2700896.2700900
(2018)A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design ProblemINFORMS Journal on Computing10.1287/ijoc.2014.0609(1-11)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1287/ijoc.2014.0609

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents