PT Petrogas Prima Services is a company engaged in the repair of 3 KG LPG Gas Cylinders which meet ISO 9001, 14001 and 45001 standards. The company is located at 12, Jl. Magelang - Yogyakarta No.Km, Meduro, Bojong, Kec. Mungkid, Magelang Regency, Central Java 56512. Transportation problems are problems that are often encountered in the distribution of goods. Another problem that is often faced with distribution is making decisions regarding routes that can optimize distance and travel time. The main problem in this study is how to optimize the distance and time of PT Petrogas Prima Services 3kg gas cylinder transportation delivery routes by solving the Vehicles Routing Problem. In this way, the main problem of transportation is how to determine the distribution of goods from sources so that all destination needs are met but with a shorter route time. to a minimum. With the product distribution activities of PT Petrogas Prima Services, the calculation and optimization of transportation time can be done using the Vehicles route Problem method, namely Nearest Insert and Nearest Neighbor for proof. Where the results of this method obtained 3 significant routes as follows route G-C6-C1-C7-G for first group is 32.70km, route G-C8-C5-C4-G for second group is 26.50km, and the last route G-C2-C3-G is 54,50km.