Eşitlikçi Çok Amaçlı Sırt Çantası Problemi

Özlem Karsu

doi:10.29109/http-gujsc-gazi-edu-tr.362369

Eşitlikçi Çok Amaçlı Sırt Çantası Problemi

Abstract

Bu çalışmada, eşitlikçi kaygıların olduğu kaynak dağıtımı problemi için kullanılabilecek, çok amaçlı matematiksel modelleme yaklaşımı geliştirilmiştir. Karar vericinin eşitlikçi tercih ilişkisine sahip olduğu varsayılmış ve eşitlikçi Pareto çözümler bulunması amaçlanmıştır. Eşitlikçi Pareto çözüm kümesinin bulunması için, problemdeki eşitlikçi kaygıları gözönüne alarak tasarlanmış, eşitlikçi Pareto çözümler vermeyecek durum vektörlerini alt ve üst sınırlar kullanarak eleyen, bir dinamik programlama algoritması önerilmiştir. Bu algoritmada, yazında önerilen alt sınırlara ek olarak yeni bir alt sınır mekanizması kullanılmış ve etkililiği gösterilmiştir. Dinamik programlama algoritması, epsilon kısıt yöntemi ile iki amaçlı problemler için karşılaştırılmıştır. Ayrıca, üç amaçlı problemler için epsilon kısıt yöntemi sonuçları verilmiştir.

Keywords

çok amaçlı sırt çantası problemi,eşitlikçi tercihler,eşitlikçi Pareto çözümler,dinamik programlama

References

[1] D. Baatar, M.M. Wiecek, Advancing equitability in multiobjective programming, Computers & Mathematics with Applications, Volume 52, Issues 1–2, 2006, 225-234.
[2] C. Bazgan, H. Hugot, D. Vanderpooten, Solving efficiently the 01 multi-objective knapsack problem, Computers & Operations Research 36 (1) (2009) 260-279, part Special Issue: Operations Research Approaches for Disaster Recovery Planning.
[3] M. E. Captivo, J. Clı́maco, J. Figueira, E. Martins, J. L. Santos, Solving bicriteria 0–1 knapsack problems using a labeling algorithm, Computers & Operations Research, 30 (12), 2003, 1865-1886.
[4] P. Czyzak, A. Jaszkiewicz, Pareto simulated annealing metaheuristic technique for multiple-objective combinatorial optimization, Journal of Multi-Criteria Decision Analysis 7 (1998) 34-47.
[5] M. Ehrgott ve Gandibleux, A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spectrum 22 (4), (2000) 425-460.
[6] J. R. Figueira, L. Paquete, M. Sim~oes, D. Vanderpooten, Algorithmic improvements on dynamic programming for the bi-objective f0,1g knapsack problem, Computational Optimization and Applications 56 (1) (2013) 97-111.
[7] Ö. Karsu, A. Morton, Inequity averse optimisation in operational research, 245 (2), 2015, 343-359.
[8] Ö. Karsu, A. Morton Incorporating balance concerns in resource allocation decisions: A bi-criteria modelling approach, Omega 44 (2014) 70 - 82.

[9] H. Kellerer, U. Pferschy, D. Pisinger, Knapsack Problems, Springer, Berlin, 2004.
[10] K. Klamroth, M. M. Wiecek, Dynamic programming approaches to the multiple criteria knapsack problem, Naval Research Logistics 47 (1) (2000) 57-76.
[11] M. M. Kostreva, W. Ogryczak, Linear optimization with multiple equitable criteria, RAIRO Operations Research 33 (1999) 275-297.
[12] M. M. Kostreva, W. Ogryczak, A. Wierzbicki, Equitable aggregations and multiple criteria analysis, European Journal of Operational Research, 158, (2), 2004, 362-377.
[13] M. Laumanns, L. Thiele, E. Ziztler, An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method, European Journal of Operational Research 169 (2006) 932-942.
[14] M. Laumanns, L. Thiele, E. Zitzler, An adaptive scheme to generate the pareto front based on the epsilon-constraint method, in: J. Branke, K. Deb, K. Miettinen, R. E. bSteuer (Eds.), Practical Approaches to Multi-Objective Optimization, no. 04461 in Dagstuhl Seminar Proceedings, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, Dagstuhl, Germany, 2005.
[15] S. Martello, P. Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., 1990.
[16] W. Ogryczak, A. Wierzbicki, M. Milewski, A multi-criteria approach to fair and efficient bandwidth allocation, Omega, 36 (3), 2008, 451-463.
[17] A. Rong, J.R. Figueira, M. PatoA two state reduction based dynamic programming algorithm for the bi-objective 0-1 knapsack problem Computers & Mathematics with Applications, 62 (2011), pp. 2913-2930.
[18] M. Visee, J. Teghem, M. Pirlot, E. Ulungu, Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem, Journal of Global Optimization 12 (2) (1998) 139-155.

Details

Primary Language

Turkish

Subjects

Engineering

Journal Section

Research Article

Authors

Özlem Karsu ^*
İHSAN DOĞRAMACI BİLKENT ÜNİVERSİTESİ
0000-0002-9926-2021
Türkiye

Publication Date

June 30, 2018

Submission Date

December 5, 2017

Acceptance Date

January 18, 2018

Published in Issue

Year 2018 Volume: 6 Number: 2

DOI

https://doi.org/10.29109/http-gujsc-gazi-edu-tr.362369

IZ

https://izlik.org/JA45BA63FA

Cite

RIS / Bibtex

APA

Karsu, Ö. (2018). Eşitlikçi Çok Amaçlı Sırt Çantası Problemi. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım Ve Teknoloji, 6(2), 358-373. https://doi.org/10.29109/http-gujsc-gazi-edu-tr.362369

AMA

1.Karsu Ö. Eşitlikçi Çok Amaçlı Sırt Çantası Problemi. GUJS Part C. 2018;6(2):358-373. doi:10.29109/http-gujsc-gazi-edu-tr.362369

Chicago

Karsu, Özlem. 2018. “Eşitlikçi Çok Amaçlı Sırt Çantası Problemi”. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım Ve Teknoloji 6 (2): 358-73. https://doi.org/10.29109/http-gujsc-gazi-edu-tr.362369.

EndNote

Karsu Ö (June 1, 2018) Eşitlikçi Çok Amaçlı Sırt Çantası Problemi. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji 6 2 358–373.

IEEE

[1]Ö. Karsu, “Eşitlikçi Çok Amaçlı Sırt Çantası Problemi”, GUJS Part C, vol. 6, no. 2, pp. 358–373, June 2018, doi: 10.29109/http-gujsc-gazi-edu-tr.362369.

ISNAD

Karsu, Özlem. “Eşitlikçi Çok Amaçlı Sırt Çantası Problemi”. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji 6/2 (June 1, 2018): 358-373. https://doi.org/10.29109/http-gujsc-gazi-edu-tr.362369.

JAMA

1.Karsu Ö. Eşitlikçi Çok Amaçlı Sırt Çantası Problemi. GUJS Part C. 2018;6:358–373.

MLA

Karsu, Özlem. “Eşitlikçi Çok Amaçlı Sırt Çantası Problemi”. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım Ve Teknoloji, vol. 6, no. 2, June 2018, pp. 358-73, doi:10.29109/http-gujsc-gazi-edu-tr.362369.

Vancouver

1.Özlem Karsu. Eşitlikçi Çok Amaçlı Sırt Çantası Problemi. GUJS Part C. 2018 Jun. 1;6(2):358-73. doi:10.29109/http-gujsc-gazi-edu-tr.362369

Cited By

0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü

Academic Platform Journal of Engineering and Science

https://doi.org/10.21541/apjes.640252