P T. Rizkina Sadaya Sejahtera is a company which provides distribution service of Liquified Petroleum Gas (LPG) tube, particularly the 3-kilogram LPG tube. At present, the company has not had any distinct methods to quantity the number of customer demand and to determine the delivery route traveled by the company vehicles in distributing the LPG tube to the customer places. The delivery route is recently arranged according to the systematic sequence order of customer requests. It results in ineffective travel route arrangement causing longer distances to travel and higher transportation costs during delivery services. In order to overcome those problems, the company needs effective method to quantity the number of customer demand and to determine the optimal delivery route so that distribution of LPG tube can be more effective and efficient. The aims of this research is to conduct a demand forecast and the optimal distribution model. This research started by forecasting the demand during a period of four weeks by using Artificial Neural Network method . After the forecasting process is finished, supporting data collection, which is important for planning of distribution model, is conducted which includes the distance between the company office and costomer places; the distance between one customer's place to another customer's place; the type of transportation vehicle available including the vehicle load capacity and fuel consumption capacity; loading and unloading time. The model created is demand forecasting model using ANN method by using Matlab software and a distribution model with Vehicle Routing Problem approach using Simulated Annealing during a period of 4 weeks. The result of model implementation showed that there is a decrease of delivery route distances by 102,003 km and a reduction of fuel cost by Rp 374100,00.