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

Year 2018, Volume: 6 Issue: 2, 358 - 373, 30.06.2018

Özlem Karsu

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

Cited By: 1

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.