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

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.