Distribution Route Optimization of Zakat Al-Fitr Based on the Branch-and-Bound Algorithm

Noor Saif Muhammad Mussafi

doi:10.31764/jtam.v7i1.10375

Distribution Route Optimization of Zakat Al-Fitr Based on the Branch-and-Bound Algorithm

Noor Saif Muhammad Mussafi

Abstract

The short interval between the collecting and distribution of zakat al-fitr is a recurring issue. As a result, ‘amil does not always pay attention to the ideal route, leading in inefficient transportation expenditures. This study aims to minimize the amount of vehicle mileage that affects fuel consumption. The branch-and-bound algorithm was employed to overcome the distribution route optimization problem by proposing the shortest circuit that traverses each district exactly once and returns to its original district. The procedures involve data collecting, graph analysis, branch-and-bound analysis, MATLAB code development, and the recommendation of the best route. The results indicate that the branch-and-bound algorithm can numerically solve the distribution route optimization corresponding to traveling salesman problem. Furthermore, according to a case study of zakat al-fitr distribution conducted by Eradication of Illiteracy Al Quran (PBHA), the total optimal distance of the computational-based algorithm was 152.9 km, with inter-village routes starting from Sidorejo and then via Sumberarum, Pendoworejo, Gerbosari, Banjaroyo, Banjarasri, Sendangagung, Tuksono, Argodadi, Triwidadi, Jatimulyo, Giripurwo, and ends in Sidorejo.

Keywords

Zakat al-fitr; ‘Amil; Distribution route optimization; Branch-and-bound algorithm; Traveling salesman problem.

Full Text:

DOWNLOAD [PDF]

References

Al-Albani, M. N. (2014). Shahih Al Jami’ Ash-Shaghir (4th ed.). Jakarta: Pustaka Azzam.

Al-Qaradawi, Y. (2000). Fiqh Al-Zakat: A Comparative Study of Zakat, Regulations and Philosophy in the Light of Al-Quran and Al-Sunnah. Jeddah, Kingdom of Saudi Arabia: Scientific Publishing Centre, King Abdul Aziz University, Vol. 1.

Cochran, J. J., Cox, L. A., Keskinocak, P., Kharoufeh, J. P., & Smith, J. C. (2011). Wiley Encyclopedia of Operations Research and Management Science. John Wiley & Sons.

Coutinho, W. P., Nascimento, R. Q. D., Pessoa, A. A., & Subramanian, A. (2016). A branch-and-bound algorithm for the close-enough traveling salesman problem. INFORMS Journal on Computing, 28(4), 752–765.

Dahiya, C., & Sangwan, S. (2018). Literature review on travelling salesman problem. International Journal of Research, 5(16), 1152–1155.

Dhar, P. (2013). Zakat as a measure of social justice in Islamic finance: an accountant’s overview. Journal of Emerging Economies and Islamic Research, 1(1), 1–11. Retrieved from https://core.ac.uk/download/pdf/328805993.pdf

Fathoni, M. A., Suryani, & Cahyo, E. N. (2020). Zakat Management Paradigm: Comparison of Indonesia, Malaysia and Saudi Arabia. INFERENSI: Jurnal Penelitian Sosial Keagamaan, 14(2), 267–282. Retrieved from https://inferensi.iainsalatiga.ac.id/index.php/inferensi/article/view/3417/pdf

Gmys, J., Mezmaz, M., Melab, N., & Tuyttens, D. (2016). A GPU-based Branch-and-Bound algorithm using Integer–Vector–Matrix data structure. Parallel Computing, 59, 119–139.

Grymin, R., & Jagiełło, S. (2016). Fast Branch and Bound Algorithm for the Travelling Salesman Problem. In: Saeed, K., Homenda, W. (Eds) Computer Information Systems and Industrial Management. CISIM 2016. https://doi.org/https://doi.org/10.1007/978-3-319-45378-1_19

Huang, L., Chen, X., Huo, W., Wang, J., Zhang, F., Bai, B., & Shi, L. (2021). Branch and bound in mixed integer linear programming problems: A survey of techniques and trends. ArXiv Preprint ArXiv:2111.06257.

Ibrahim, & Mussafi, N. S. M. (2013). Pengantar Kombinatorika & Teori Graf. Yogyakarta: Graha Ilmu.

Lopez, C. P. (2014). MATLAB Optimization Techniques. Apress Academic.

Lu, C., Zhou, L. S., Yue, Y. X., & Chen, R. (2016). A branch and bound algorithm for the exact solution of the problem of EMU circulation scheduling in railway network. Hindawi: Mathematical Problems in Engineering. Retrieved from https://downloads.hindawi.com/journals/mpe/2016/8537089.pdf

Mengarelli, A., Cardarelli, S., Verdini, F., Burattini, L., Fioretti, S., & Di Nardo, F. (2016). A MATLAB-based graphical user interface for the identification of muscular activations from surface electromyography signals. 38th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), 3646–3649. IEEE.

Messac, A. (2015). Optimization in Practice with MATLAB®. In Cambridge University Press. https://doi.org/10.1017/cbo9781316271391

Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C. (2016). Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19, 79–102.

Perdana, D. A., & Tunali, F. (2020). Zakat Fitrah: Management, Tradition, And Meaning Of Eidal-FitR. Fikri: Jurnal Kajian Agama, Sosial Dan Budaya, 5(2), 223–235. Retrieved from https://journal.iaimnumetrolampung.ac.id/index.php/jf/article/view/978/620

Rajarajeswari, P., & Maheswari, D. (2020). Travelling Salesman Problem Using Branch And Bound Technique. International Journal of Mathematics Trends and Technology (IJMTT), 66(5), 202–206.

Sharma, M., Sharma, S., & Sahu, G. (2017). Designing MATLAB GUI for various Analog and Digital Communication Systems. International Journal of Trend in Scientific Research and Development, 2(1), 1397–1405.

Suyanto. (2010). Algoritma Optimasi (Deterministik atau Probabilistik). Yogyakarta: Graha Ilmu.

Usmani, M. I. A., & Qazi, B. A. (2010). Guide to Zakah: Understanding and Calculation. Maktaba Ma’ariful Qur’an.

Xiong, N., Wu, W., & Wu, C. (2017). An improved routing optimization algorithm based on travelling salesman problem for social networks. Sustainability, 9(6), 985.

Yu, X., Xu, D., & Schober, R. (2020). Optimal Beamforming for MISO Communications via Intelligent Reflecting Surfaces. IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), 1–5. https://doi.org/10.1109/SPAWC48557.2020.9154337

Zegordi, S. H., & Yavari, M. (2018). A branch and bound algorithm for solving large-scale single-machine scheduling problems with non-identical release dates. European Journal of Industrial Engineering, 12(1), 24–42.

Zumaytis, S., & Karnalim, O. (2017). Introducing an educational tool for learning branch & bound strategy. Journal of Information Systems Engineering and Business Intelligence, 3(1), 8–15.

DOI: https://doi.org/10.31764/jtam.v7i1.10375