Liquid Petroleum Gas (LPG) distribution has become very important because LPG is a com modity used by the community every day. Late deliveries and high distribution costs due to non-optimal routes will have an impact on customer satisfaction. One of the companies that conduct LPG 3 kg for the East Jakarta region is PT Kurnia Cipinang Jaya. The Company has a problem determining distribution routes that are not optimal and impact the high total distance travelled and an increased distribution cost. This problem can be solved using the VRPSPD model, where the vehicle delivers and picks up LPG 3 kg simultaneously at the destination. One of the methods used to get the optimal route is using the Simulated Annealing (SA) algorithm. The result of this research indicated that SA algorithm can produce a feasible solution on all instances with fast computation time. At the same time, the exact method requires a long computational time with several instances that do not produce a solution. The optimization method results show that it can save total distance travelled 380 km with a fuel cost savings is Rp 451.250,00 for one week, compared to the results in the nearest neighbor scenario used by the Company.