Optimizing the Distribution of Cow Skin Crackers at UMKM Putra-Putri Agli Using the Min-Plus Algebra Method for Shortest Route Determination

Abstract

This study applies Min–Plus Algebra to model and analyze the distribution network of UMKM Putra-Putri Agli, a small enterprise in West Lombok engaged in the production and distribution of cowhide crackers. The objective of this research is to analyze the distribution network and identify shortest-path relationships between distribution locations based on actual distance data. The distribution system is represented as an undirected weighted graph, where nodes correspond to distribution locations and edge weights represent the distances between locations obtained from Google Maps. The analysis is conducted by constructing a distance matrix and applying Min–Plus Algebra operations to compute successive matrix powers, leading to the formation of the closure matrix . The results show that the closure matrix successfully identifies the minimum distances between all pairs of distribution locations and provides the basis for deriving a distribution route with a total distance of 88.1 km. The findings also indicate that the network's structure and connectivity significantly influence route formation, as some locations can only be reached via intermediate nodes. The novelty of this study lies in the application of Min–Plus Algebra to an UMKM distribution network using actual field data and a network structure characterized by limited connectivity. The results demonstrate that Min–Plus Algebra provides a systematic algebraic framework for analyzing shortest-path relationships in small-scale distribution networks. However, the model is limited to static distance-based analysis and does not consider dynamic factors such as traffic conditions, travel time variations, or vehicle capacity constraints.