The Problem of Backpacks with Fuzzy Values of Hesitant Value Ranges

Document Type : Original Article

Authors

20.1001.1.27174409.1399.3.1.12.7/DOR

Abstract

In this study, we intend to investigate the zero-one backpack problem in which the value of each item is expressed as a hesitant fuzzy set of interval values. This means that more than one decision-maker has participated in evaluating the value of each item in the backpack, and in addition, the decision-makers have recorded their opinions in a range between zero and one. Of course, the weight of each item, as well as the total weight, is definitely considered for the backpack. For this purpose, we designed an appropriate framework to achieve the appropriate answer to the problem. By properly analyzing the structure of the problem and identifying the factors influencing its solution, the appropriate ranking method and cumulative operator were selected to find the answer to the problem. Finally, a numerical example was presented to examine the proposed model and solution method. The results are obtained from the perspective of an optimistic, pessimistic and balanced decision maker. Therefore, there is a good variety in choosing the answer for the decision maker.

Keywords

References

[1] Wascher, G., Schumann, H., An improved typology of cutting and packing problems, Eur. J. Oper. Res. 183 (3) (2007) 1109–1130.
 
[2] Nawrocki, J., Complak, W., Błazewicz, J., Kopczyn-' ska, S., Mac' kowiaki, M., The knapsack-lightening problem and its application to scheduling HRT tasks,Bull. Polish Acad. Sci.: Tech. Sci. 57 (1) (2009) 71–77.
 
[3] Kong, M., Tian, P., Kao, Y., A new ant colony optimization algorithm for the multidimensional knapsack problem, Comput. Oper. Res. 35 (8) (2008) 2672–2683.
 
[4] Granmo, O., Oommen, B,. Myrer, S., Olsen, M., Learning automata-based solutions to the nonlinear fractional knapsack problem with applications to optimal resource allocation, IEEE Trans Syst. Man Cybern. Part B Cybern. 37 (1) (2007) 166–175.
 
[5] Vanderster, D., Dimopoulos, N., Parra-Hernandez, R., Sobie, R., Resource allocation on computational grids using a utility model and the knapsack problem, Future Gener. Comput. Syst. 25 (1) (2009) 35–50.
 
[6] Deng, Y., Chen, Y., Zhang, Y., Mahadevan, S., Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment, Appl. Soft Comput. 12 (2011) 1231-1237.
 
[7] Mavrotas, G., Diakoulaki, D., Kourentzis, A., Selection among ranked projects under segmentation, policy and logical constraints, Eur. J. Oper. Res. 187 (1) (2008) 177-192.
 
[8] Bas, E., A capital budgeting problem for preventing workplace mobbing by using analytic hierarchy process and fuzzy 0-1 bidimensional knapsack model, Expert Syst. Appl. 38 (10) (2011) 12415-12422.
 
[9] Wilbaut, C., Hanafi, S., Salhi, S., A survey of effective heuristics and their application to a variety of knapsack problems, IMA J. Manage. Math. 19 (3)(2008) 227.
 
[10] Dudzinski, K., "A Dynamic Programming Approach to Solving the Multiple Choice Knapsack Problem”, Bull. Polish Acad. Sci., Tech. Sci., No. 32, 1984, PP. 325-332.
 
[11] Dyer, M.E., Kayal, N., Walker, J., "A Branch and Bound Algorithm for Solving the Multiple Choice Knapsack Problem”, Journal of Computational and Applied Mathematics, No. 11, 1984, PP. 231-249.
 
[12] Dyer, M.E., Riha, W.O., Walker, J., "A Hybrid Dynamic Programming/Branch and Bound Algorithm For The Multiple-Choice Knapsack Problem", Journal of Computational and Applied Mathematics, No. 58, 1995, PP. 43-54.
 
[13] Abdel-Basset, M., El-Shahat, D., and El-Henawy, I., "Solving 0-1 knapsack problem by binary flower pollination algorithm,” Neural Computing and Applications, vol. 31, no. 9, pp. 5477–5495, 2019.
 
[14] Olivas, F., Amaya, I., Ortiz-Bayliss, J.C., Conant-Pablos, S.E., and Terashima-Marin, H., "A Fuzzy Hyper-Heuristic Approach for the 0-1 Knapsack Problem," 2020 IEEE Congress on Evolutionary Computation (CEC), Glasgow, United Kingdom, 2020, pp. 1-8, doi: 10.1109/CEC48606.2020.9185710.
 
[15] L. A. Zadeh et al., "Fuzzy sets," Information and control, vol. 8, no. 3,pp. 338–353, 1965.
 
[16] Okada, S., Gen, M., "Fuzzy Multiple Choice Knapsack Problem", Fuzzy Sets and Systems, No. 67, 1994, PP. 71-80.
 
[17] Okada, S., Gen, M., "A Method for Solving Fuzzy Multi-Dimensional 0-1 Knapsack Problems", Japanese Journal Fuzzy Theory Systems, No. 6, 1995, PP. 687-702.
 
[18] Torra, V., Narukawa, Y., On hesitant fuzzy sets and decision. The 18-thIEEE International Conference on Fuzzy Systems, Jeju Island, Korea(2009) 1378-1382.
 
[19] Torra, V., Hesitant Fuzzy Sets, Int. J. Intell. Syst. 25 (2010) 529–539.
 
[20] Xia MM, Xu ZS, Chen N (2013) Some hesitant fuzzy aggregation operators with their application in group decision making. Group DecisNegot 22:259–279.
 
[21] Sengupta A, Pal TK (2000) On comparing interval numbers. Eur J Oper Res 127:28-43.
 
[22] Wei GW, Zhao XF, Li R (2013) Some hesitant interval-valued fuzzy aggregation operators and their applications to multiple attribute decision making. Knowl Based Syst 46:43–53.
 
[23] Zeng, W., Li, D. Gu, Y. Note on the aggregation operators and ranking of hesitant interval-valued fuzzy elements. Soft Comput23, 8075-8083 (2019). https://doi.org/10.1007/s00500-018-3445-x.

Files

History

  • Receive Date: 28 October 2020
  • Revise Date: 03 January 2021
  • Accept Date: 01 February 2021

Share

How to cite

Statistics