Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
High-Precision Method for Space-Time-Fractional Klein-Gordon Equation Read chapter Read first chapter

2024 | OriginalPaper | Chapter

Dynamic and Static Simulated Annealing for Solving the Multi-objective k-Minimum Spanning Tree Problem

Authors : El Houcine Addou, Abdelhafid Serghini, El Bekkaye Mermri

Published in: Applied Mathematics and Modelling in Finance, Marketing and Economics

Publisher: Springer Nature Switzerland

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper deals with the optimisation of the Multi-Objectif k-Minimum Spanning Tree (MO k-MST) problem. A wide varieties of decision making problems in the real world can be formulated as a MO k-MST, which is known to be NP-complete. In order to solve a such problem, we propose two approximate approaches based on simulated annealing method: the first one will integrates the static weighted sum method while the second one uses the dynamic weighted sum method. Computational experiments were carried out in order to compare the performance of each method.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Solving Fuzzy Linear Programming Using the Parametric Form
next chapter Kantorovich Methods for Urysohn Integral Equations
Literature
1.
Arroyo, J.E., Vieira, P., Vianna, D.: A GRASP algorithm for the multi-criteria minimum spanning tree problem. Ann. OR 159, 125–133 (2008)
2.
Baños, R., Ortega, J., Gil, C., Fernández, A., de Toro, F.: A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows. Exp. Syst. Appl. 40(5), 1696–1707 (2013)CrossRef
3.
Blum, C., Blesa, M.J.: New metaheuristic approaches for the edge-weighted k-cardinality tree problem. Comput. Oper. Res. 32(6), 1355–1377 (2005)CrossRef
4.
Chankong, V., Haimes, Y.: Multiobjective Decision Making: Theory and Methodology (1983)
5.
Davis-Moradkhan, M., Browne, W.: Evolutionary algorithms for the multi criterion minimum spanning tree problem. In: Tenne, Y., Goh, C.-K. (eds.) Computational Intelligence in Expensive Optimization Problems. Adaptation Learning and Optimization, pp. 423–452. Springer, Berlin, Heidelberg (2010)CrossRef
6.
Gabli, M., Jaara, E., El Bekkaye, M.: A genetic algorithm approach for an equitable treatment of objective functions in multi-objective optimization problems. IAENG Int. J. Comput. Sci. 41, 102–111 (2014)
7.
Goldbarg, E., Souza, G., Goldbarg, M.: Particle Swarm Optimization for the Bi-objective Degree Constrained Minimum Spanning Tree, pp. 420–427, Jan. 2006
8.
Guo, W., Chen, G., Feng, X., Yu, L.: Solving Multi-criteria Minimum Spanning Tree Problem with Discrete Particle Swarm Optimization, pp. 471–478, Sept. 2007
9.
Han, L., Wang, Y.: A novel genetic algorithm for multi-criteria minimum spanning tree problem. In: Hao, Y., Liu, J., Wang, Y., Cheung, Y.-M., Yin, H., Jiao, L., Ma, J., Jiao, Y.-C. (eds.), Computational Intelligence and Security, Lecture Notes in Computer Science, pp. 297–302. Springer, Berlin, Heidelberg (2005)
10.
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science (New York, N.Y.), vol. 220(4598), pp. 671–680, May 1983
11.
Knowles, J., Corne, D.: A comparison of encodings and algorithms for multiobjective minimum spanning tree problems. In: Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, 1 Apr. 2001
12.
Liu, L., Haibo, M., Yang, J., Li, X., Fang, W.: A simulated annealing for multi-criteria optimization problem: DBMOSA. Swarm Evol. Comput. 14, 48–65 (2014)CrossRef
13.
Liu, Q., Li, X., Liu, H., Guo, Z.X.: Multi-objective metaheuristics for discrete optimization problems: a review of the state-of-the-art. Appl. Soft Comput. 93, 106382, May 2020
14.
Narzisi, G.L.: Classic Methods for Multi-objective Optimization (2008)
15.
Neumann, F.: Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. European J. Oper. Res. 181(3), 1620–1629 (2007)CrossRef
16.
Robini, M.C., Reissman, P.-J.: From simulated annealing to stochastic continuation: a new trend in combinatorial optimization. J. Glob. Optim. 56(1), 185–215 (2013)MathSciNetCrossRef
17.
Yu, V.F., Redi, A.A.N.P., Hidayat, Y.A., Wibowo, O.J.: A simulated annealing heuristic for the hybrid vehicle routing problem. Appl. Soft Comput. 53, 119–132, Apr. 2017
18.
Zhou, G., Gen, M.: Genetic algorithm approach on multi-criteria minimum spanning tree problem. European J. Oper. Res. 114(1), 141–152 (1999)CrossRef
Metadata
Title
Dynamic and Static Simulated Annealing for Solving the Multi-objective k-Minimum Spanning Tree Problem
Authors
El Houcine Addou
Abdelhafid Serghini
El Bekkaye Mermri
Copyright Year
2024
Book
Applied Mathematics and Modelling in Finance, Marketing and Economics

Print ISBN: 978-3-031-42846-3

Electronic ISBN: 978-3-031-42847-0

Copyright Year: 2024

DOI
https://doi.org/10.1007/978-3-031-42847-0_4

Premium Partners

    Image Credits