Formulation of Set Covering Problem Using Myopic Algorithm and Greedy Reduction Algorithm in Determining the Location of Temporary Landfills in Semambu Island Village, Ogan Ilir Regency, South Sumatra
Article Sidebar
Keywords:
-
Set Covering Problem, Greedy Reduction Algorithm, Myopic Algorithm, Semambu Island Village, Optimal TPS Location
Abstract
This study discusses Set Covering Problem (SCP) in designing the optimal temporary waste disposal site (TWDS) in Semambu Island Village using the Myopic Algorithm (MA) and Greedy Reduction Algorithm (GRA). The analysis was carried out and compared using a maximum distance of 500m and 1000m to get the best solution from two methods. The results of the p Median Problem by LINGO 13.0 software and MA with a maximum distance of 500m show the same TWDS location, namely Working Area (WA) 1, 2, 3, 4, 5, and 6 with the location of the candidate TWDS being at TWDS 2 WA 1, TWDS 1 WA 2, TWDS 2 WA 3, and TWDS 2 WA 5. For 1000m, it will be the location of the candidate’s TWDS being at TWDS 2 WA 1, TWDS WA 2, and TWDS 2 WA 3. Using GRA, results were obtained will be 4 TWDS, namely TWDS 2 Hamlet 1, TWDS 1 Hamlet 2, TWDS 2 Hamlet 3, TWDS 2, Hamlet 5. Then using GRA, 2 solutions are obtained, namely columns 2 and 5 which dominate. Column 2 nomination are Hamlets 1, 2, 3, and 6. Column 5 which dominates will be Hamlets 1, 3, 5, and 6.
References
Akhter, F. (2015). A Heuristic Approach for Minimum Set Cover Problem. International Journal of Advanced Research in Artificial Intelligence, 4(6); 40–45
Alizadeh, R. and T. Nishi (2019). Hybrid Covering Location Problem: Set Covering and Modular Maximal Covering Location Problem. IEEE International Conference on Industrial Engineering and Engineering Management, 3; 865–869
Arba, M. F. D. (2021). Strategi Inovasi Agro Wisata Di Desa Pulau Semambu Ogan Ilir. Jurnal Pendidikan dan Pemberdayaan Masyarakat, 8(1); 53–60
Bangun, P. B. J., S. Octarina, R. Aniza, L. Hanum, F. M. Puspita, and S. S. Supadi (2022). Set Covering Model Using Greedy Heuristic Algorithm to Determine the Temporary Waste Disposal Sites in Palembang. Science and Technology Indonesia, 7(1); 98–105
Basciftci, B., S. Ahmed, and S. Shen (2021). Distributionally Robust Facility Location Problem Under Decision-dependent Stochastic Demand. European Journal of Operational Research, 292(2); 548–561
Bendík, J. (2015). Selection of Minimal Set of Locations In the Public Service System Design. International Scientific Conference on Informatics, 2015; 47–51
Binev, P., A. Cohen, O. Mula, and J. Nichols (2018). Greedy Algorithms for Optimal Measurements Selection In State Estimation Using Reduced Models. SIAM/ASA Journal on Uncertainty Quantification, 6(3); 1101–1126
Chen, A. Y. and T. Y. Yu (2016). Network Based Temporary Facility Location for The Emergency Medical Services Considering the Disaster Induced Demand and the Transportation Infrastructure in Disaster Response. Transportation Research Part B: Methodological, 91; 408-423
Chen, X. M., H. Zheng, J. Ke, and H. Yang (2020). Dynamic Optimization Strategies For On demand Ride Services Platform: Surge Pricing, Commission Rate, and Incentives. Transportation Research Part B: Methodological, 138; 23–45
Doungpan, S. (2020). Application the Facility Location Model for Setting Ready-Mix Concrete Plant: Case Study at Rayong Province, Thailand. International Conference on Industrial Engineering and Applications, ICIEA; 615–619
Dzator, M. and J. Dzator (2015). An Efficient Modified Greedy Algorithm for the P-median Problem. International Congress on Modelling and Simulation, 4(5); 61–64
Gajda, M., A. Trivella, R. Mansini, and D. Pisinger (2022). An Optimization Approach for a Complex Real-life Container Loading Problem. Omega, 107; 102559
Kawi, E. A. and A. Rusdiansyah (2009). Analisis Penentuan Lokasi Pembangunan Stasiun Pengisian Bulk Elpiji (spbe) untuk Program Konversi Minyak Tanah Ke Lpg 3 Kg Di Propinsi Jawa Timur Menggunakan Metode P-median. 4(6); 1–3 (In Indonesia)
Kocaoglu, B., A. Z. Acar, and B. Yilmaz (2014). Demand Forecast, Up-to-date Models, and Suggestions For Improvement an Example Of A Business. Journal of Global Strategic Management, 8(1); 26–37
Kordalewski, D. (2013). New Greedy Heuristics for Set Cover and Set Packing. Graduate Department of Computer Science: Vol. Master
Machado, A. M., G. R. Mauri, M. C. S. Boeres, and R. de Alvarenga Rosa (2021). A New Hybrid Matheuristic of GRASP and VNS Based on Constructive Heuristics, Set-covering and Set partitioning Formulations Applied to the Capacitated Vehicle Routing Problem. Expert Systems with Applications, 184; 115556
Medrano-Gómez, X. D., D. Ferreira, E. A. Toso, and O. J. Ibarra Rojas (2020). Using the Maximal Covering Location Problem to Design A Sustainable Recycling Network. Journal of Cleaner Production, 275; 124020
Mohri, S. S. and H. Haghshenas (2021). An Ambulance Location Problem for Covering Inherently Rare and Random Road Crashes. Computers & Industrial Engineering, 151; 106937
Octarina, P. F. M. S. S. S. . E. N. A., S. (2022). Greedy Reduction Algorithm as the Heuristic Approach in Determining the Temporary Waste Disposal Sites in Sukarami Sub-District, Palembang, Indonesia. Science and Technology Indonesia, 7(4); 469–480
Özceylan, E., S. Mete, and Z. A. Çil (2017). Optimizing the Location-allocation Problem of Bike Sharing Stations: A Case Study In Gaziantep University Campus. International Symposium on Operational Research; 141–146
Puspita, F. M., S. Octarina, and H. Pane (2019). Pengoptimalan Lokasi Tempat Pembuangan Sementara (TPS) Menggunakan Greedy Reduction Algorithm (GRA) di Kecamatan Kemuning. Annual Reseach Seminar, 4(1); 267–274
Segall, M., R. Lumb, V. Lall, and A. Moreno (2017). Healthcare Facility Location: A DEA Approach. American Journal of Management, 17(6); 54–65
Sitepu, R., F. M. Puspita, I. Lestari, E. Yuliza, and S. Octarina (2022). Facility Location Problem of Dynamic Optimal Location of Hospital Emergency Department in Palembang. Science and Technology Indonesia, 7(2); 251–256
Sitepu, R., F. M. Puspita, S. Romelda, A. Fikri, B. Susanto, and H. Kaban (2019a). Set covering models in optimizing the emergency unit location of health facility in Palembang. Journal of Physics: Conference Series, 1282(1); 012008
Sitepu, R., F. M. Puspita, S. Romelda, A. Fikri, B. Susanto, and H. Kaban (2019b). Set Covering Models In Optimizing the Emergency Unit Location of Health Facility In Palembang. Journal of Physics: Conference Series, 1282(1); 012008
Yang, P., Y. Xiao, Y. Zhang, S. Zhou, J. Yang, and Y. Xu (2020). The Continuous Maximal Covering Location Problem in Large-scale Natural Disaster Rescue Scenes. Computers & Industrial Engineering, 146; 106608
Zhang, K. and S. Zhang (2015). Maximizing the Service Area: A Criterion To Choose Optimal Solution in The Location of Set Covering Problem. International Conference on Geoinformatics, 20; 1–3
Alizadeh, R. and T. Nishi (2019). Hybrid Covering Location Problem: Set Covering and Modular Maximal Covering Location Problem. IEEE International Conference on Industrial Engineering and Engineering Management, 3; 865–869
Arba, M. F. D. (2021). Strategi Inovasi Agro Wisata Di Desa Pulau Semambu Ogan Ilir. Jurnal Pendidikan dan Pemberdayaan Masyarakat, 8(1); 53–60
Bangun, P. B. J., S. Octarina, R. Aniza, L. Hanum, F. M. Puspita, and S. S. Supadi (2022). Set Covering Model Using Greedy Heuristic Algorithm to Determine the Temporary Waste Disposal Sites in Palembang. Science and Technology Indonesia, 7(1); 98–105
Basciftci, B., S. Ahmed, and S. Shen (2021). Distributionally Robust Facility Location Problem Under Decision-dependent Stochastic Demand. European Journal of Operational Research, 292(2); 548–561
Bendík, J. (2015). Selection of Minimal Set of Locations In the Public Service System Design. International Scientific Conference on Informatics, 2015; 47–51
Binev, P., A. Cohen, O. Mula, and J. Nichols (2018). Greedy Algorithms for Optimal Measurements Selection In State Estimation Using Reduced Models. SIAM/ASA Journal on Uncertainty Quantification, 6(3); 1101–1126
Chen, A. Y. and T. Y. Yu (2016). Network Based Temporary Facility Location for The Emergency Medical Services Considering the Disaster Induced Demand and the Transportation Infrastructure in Disaster Response. Transportation Research Part B: Methodological, 91; 408-423
Chen, X. M., H. Zheng, J. Ke, and H. Yang (2020). Dynamic Optimization Strategies For On demand Ride Services Platform: Surge Pricing, Commission Rate, and Incentives. Transportation Research Part B: Methodological, 138; 23–45
Doungpan, S. (2020). Application the Facility Location Model for Setting Ready-Mix Concrete Plant: Case Study at Rayong Province, Thailand. International Conference on Industrial Engineering and Applications, ICIEA; 615–619
Dzator, M. and J. Dzator (2015). An Efficient Modified Greedy Algorithm for the P-median Problem. International Congress on Modelling and Simulation, 4(5); 61–64
Gajda, M., A. Trivella, R. Mansini, and D. Pisinger (2022). An Optimization Approach for a Complex Real-life Container Loading Problem. Omega, 107; 102559
Kawi, E. A. and A. Rusdiansyah (2009). Analisis Penentuan Lokasi Pembangunan Stasiun Pengisian Bulk Elpiji (spbe) untuk Program Konversi Minyak Tanah Ke Lpg 3 Kg Di Propinsi Jawa Timur Menggunakan Metode P-median. 4(6); 1–3 (In Indonesia)
Kocaoglu, B., A. Z. Acar, and B. Yilmaz (2014). Demand Forecast, Up-to-date Models, and Suggestions For Improvement an Example Of A Business. Journal of Global Strategic Management, 8(1); 26–37
Kordalewski, D. (2013). New Greedy Heuristics for Set Cover and Set Packing. Graduate Department of Computer Science: Vol. Master
Machado, A. M., G. R. Mauri, M. C. S. Boeres, and R. de Alvarenga Rosa (2021). A New Hybrid Matheuristic of GRASP and VNS Based on Constructive Heuristics, Set-covering and Set partitioning Formulations Applied to the Capacitated Vehicle Routing Problem. Expert Systems with Applications, 184; 115556
Medrano-Gómez, X. D., D. Ferreira, E. A. Toso, and O. J. Ibarra Rojas (2020). Using the Maximal Covering Location Problem to Design A Sustainable Recycling Network. Journal of Cleaner Production, 275; 124020
Mohri, S. S. and H. Haghshenas (2021). An Ambulance Location Problem for Covering Inherently Rare and Random Road Crashes. Computers & Industrial Engineering, 151; 106937
Octarina, P. F. M. S. S. S. . E. N. A., S. (2022). Greedy Reduction Algorithm as the Heuristic Approach in Determining the Temporary Waste Disposal Sites in Sukarami Sub-District, Palembang, Indonesia. Science and Technology Indonesia, 7(4); 469–480
Özceylan, E., S. Mete, and Z. A. Çil (2017). Optimizing the Location-allocation Problem of Bike Sharing Stations: A Case Study In Gaziantep University Campus. International Symposium on Operational Research; 141–146
Puspita, F. M., S. Octarina, and H. Pane (2019). Pengoptimalan Lokasi Tempat Pembuangan Sementara (TPS) Menggunakan Greedy Reduction Algorithm (GRA) di Kecamatan Kemuning. Annual Reseach Seminar, 4(1); 267–274
Segall, M., R. Lumb, V. Lall, and A. Moreno (2017). Healthcare Facility Location: A DEA Approach. American Journal of Management, 17(6); 54–65
Sitepu, R., F. M. Puspita, I. Lestari, E. Yuliza, and S. Octarina (2022). Facility Location Problem of Dynamic Optimal Location of Hospital Emergency Department in Palembang. Science and Technology Indonesia, 7(2); 251–256
Sitepu, R., F. M. Puspita, S. Romelda, A. Fikri, B. Susanto, and H. Kaban (2019a). Set covering models in optimizing the emergency unit location of health facility in Palembang. Journal of Physics: Conference Series, 1282(1); 012008
Sitepu, R., F. M. Puspita, S. Romelda, A. Fikri, B. Susanto, and H. Kaban (2019b). Set Covering Models In Optimizing the Emergency Unit Location of Health Facility In Palembang. Journal of Physics: Conference Series, 1282(1); 012008
Yang, P., Y. Xiao, Y. Zhang, S. Zhou, J. Yang, and Y. Xu (2020). The Continuous Maximal Covering Location Problem in Large-scale Natural Disaster Rescue Scenes. Computers & Industrial Engineering, 146; 106608
Zhang, K. and S. Zhang (2015). Maximizing the Service Area: A Criterion To Choose Optimal Solution in The Location of Set Covering Problem. International Conference on Geoinformatics, 20; 1–3
Authors
Puspita, F. M., Octarina, S. ., Hanum, L. ., Simamora, C. Y. ., Kemit, H. V. B. ., & Yuliza, E. . (2023). Formulation of Set Covering Problem Using Myopic Algorithm and Greedy Reduction Algorithm in Determining the Location of Temporary Landfills in Semambu Island Village, Ogan Ilir Regency, South Sumatra. Science and Technology Indonesia, 8(2), 184–194. https://doi.org/10.26554/sti.2023.8.2.184-194
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.