DOI: -

Keywords: Cheapest insertion heuristic, ATSP, Distribution route, Travel salesman problem, UD UTY Crystal Ice Tube, Rute distribusi

ABSTRACT

UD UTY Crystal Ice Tube is a company in the food processing industry, specializing in ice tube commodities. The company distributes ice tubes to 29 points using a box car. The main problem of this company is that the distribution routes are selected based on driver assumptions, necessitating calculations to optimize efficiency. This problem is included in the Travel Salesman Problem (TSP) So the purpose of this research is to determine the optimal route and schedule for ice tube distribution. The method used in this research is the Cheapest Insertion Heuristic. Data was gathered using Google Maps to calculate distances between distribution points, then processed using the Asymmetric Traveling Salesman Problem (ATSP) software. The calculated route resulted in a total distribution distance of 43.66 km. There is no significant difference to the initial route, which is only a difference of 400 meters. Delivery begins at 07:15 WIB and finishes at 10:20 WIB.