Optimizing Vehicle Routing Problem with Nearest Neighbour Method and Saving Matrix on PT XYZ

Abstract

Transportation is part of supply chains that could contribute up to 40% of total logistics costs. Therefore, the company should have a proper transportation system. PT XYZ is one of the pharmaceutical industries that offer/serve distribution and logistics services in health and other sectors in Indonesia. The recent problem at PT XYZ lingers on the Vehicle Routing Problem (VRP) along with its limitation. PT XYZ often finds some difficulties when dealing with distribution process, specifically the frequent delay in delivering products to their customers due to the inaccuracy of route configuration, and this exact case causes an increased transportation cost. In November 2020, PT XYZ could spend an average transportation cost for Rp. 1.902.022 daily with eight distribution routes. This happened since the company’s ineffectiveness in maximizing the route and the vehicle capacity. The aim of this study is to determine distribution route and proper vehicle capacity at PT XYZ and to calculate the total cost of transportation by using nearest neighbor method and saving matrix. The nearest neighbor matrix is a simple method using the nearest neighborhood concept, while the saving matrix method is one of the methods that uses matrix table economical distance and restriction regarding cargo capacity. Based on the result processed by using nearest neighbor method and saving matrix, the most appropriate method that resulted optimal route with the distance covered and maximum capacity was saving matrix method. The calculation that used nearest neighbor method resulted in six routes with total distance at 168 km, whilst the saving matrix yielded five routes with the total distance at 186 km. The calculation result of the total cost regarding distribution activities for the nearest neighbor was Rp. 1.396.145, whilst the saving matrix method was Rp. 1.181.601. The cost comprised of the sum of fixed costs with variable costs and the total distance that had been calculated by both methods. By using the nearest neighbor method and saving matrix, the company could save up to 27% and 38% respectively for each method.