PT Sido Rahayu is one of the big LPG (Liquefied Petroleum Gas) Agents in
Yogyakarta which distribute LPG exclussively in Yogyakarta. The weight of LPG
tubes capacity that PT Sido Rahayu distributed are 5.5 kg, 12 kg and 50 kg. For
the distribution, PT Sido Rahayu has 10 vehicles each with one driver and one staff
to deliver the LPG into 10 areas in Yogyakarta. Each area is served by 1 vehicle.
The problems in PT Sido Rahayu is the absence of a clear distribution route
standard. This resulted in the inefficiency in the delivery process and the customers
have to wait longer to receive the LPG they ordered. This research is needed to
make an improvement of the distribution management by determining the shortest
distribution routes and proposing a new approach to assign vehicles. It is to make
the distribution activities become more efficient by minimizing the travel distance.
This research will compare the nearest neighbor, cheapest insertion, two-way
exchange improvement heuristic, and branch and bound method to find the best
method to be applied using a distribution system in the company. In this research,
the appropriate method for the distribution system in PT Sido Rahayu is Branch
and Bound method. The procedure for determining the shortest distribution route
has succeeded in determining a sequence of shorter routes with a total distance
reduction of 21,7% or 52,44 km from data objects on existing systems for 2, 3, 4,
5, and 7 January 2019. Also, the distribution management in PT Sido Rahayu is
successfully compiled using Branch and Bound method with the help of WINQSB
program.