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

Authors

DOI:

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

Keywords:

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

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.

 

Author Biography

Noor Saif Muhammad Mussafi, Departement of Mathematics. UIN Sunan Kalijaga

Noor Saif Muhammad Mussafi is currently a lecturer and researcher at the Department of Mathematics, UIN Sunan Kalijaga, Indonesia. Throughout his carrier, he has received several research grants related to operations research and portfolio optimization. He obtained Ph.D. in Optimization from Department of Mathematical Sciences, Universiti Teknologi Malaysia (UTM). Earlier he did a Master in Applied Mathematics from Chemnitz University of Technology, Germany.

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.

Downloads

Published

2023-01-12

Issue

Vol. 7 No. 1 (2023): January

Section

Articles

License

Authors who publish articles in JTAM (Jurnal Teori dan Aplikasi Matematika) agree to the following terms:

  1. Authors retain copyright of the article and grant the journal right of first publication with the work simultaneously licensed under a CC-BY-SA or The Creative Commons Attribution–ShareAlike License.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).