Route Determination for Distribution by Using a Combination of Branch and Bound Algorithm and Cheapest Insertion Heuristic

This paper discusses the determination of the LPG Gas distribution route using the concept of the Traveling Salesman Problem. The research data is secondary data obtained from a previous study, where in that study, the generated routes had different starting and ending points. However, in this research, the sought-after routes are those with the same starting and ending points. Such routes are sought with the consideration that in a travel route, the starting and ending points are usually the same. The Traveling Salesman Problem method used in determining these routes is the Branch and Bound algorithm combined with the Cheapest Insertion Heuristic. The distribution route obtained is v₁ – v₂ – v₆ – v₁₁ – v₁₀ – v₇ – v₉ – v₁₂ – v₁₃ – ^v14 – v₁₃ – v₁₂ – v₉ – v₈ – v₄ – v₅ – v₄ – v₃ – v₂ – v₁.