Özlem KARSU

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

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.

Anahtar Kelimeler:

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

PDF

___

[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.