UAD Template_Zalik Nuryana 10.12198/spektrum.v20i1.50 spektrum.industri@ie.uad.ac.id 31 SPEKTRUM INDUSTRI Journal homepage: http://journal3.uad.ac.id/index.php/spektrum ISSN 2442-2630 (online) | 1693-6590 (print) Integrated Saving Matrix - Branch and Bound Method to Optimize Sugar Product’s Distribution Route Ryan Rafli Devanda*, Farida Pulansari Industrial Engineering Department, Universitas Pembangunan Nasional “Veteran” Jawa Timur, Surabaya, 60294, Indonesia *Corresponding Author: ryanraflidevanda@gmail.com INTRODUCTION Product distribution is moving products from the source to the final consumer with distribution channels at the right time (Baharudin et al., 2020). The absence of proper distribution patterns affects the process of distributing products costly and lead to waste in terms of time, distance, and energy (Wei & Dong, 2022). Therefore, the company must be able to determine the right strategy in terms of product distribution to be effective and efficient. Companies can use one strategy to plan and determine the optimal distribution route so that consumers will receive the product in the right amount and low cost (Mahmud et al., 2022). The correct distribution system can achieve various supply chain needs ranging from low distribution costs to high response by consumer demand. The best distribution is the distribution with the shortest distance so that it will affect the transportation costs incurred. Shorter vehicle mileage will lower transportation costs (Sarjono, 2014). So, distribution plays a vital role in the company. Because meeting customer demand is not enough to meet the total demand but also service issues, timeliness of product delivery is the primary concern of consumers (Rizkilah et al., 2021). Determining the route of distribution of products without considering the capacity of the means of transportation results in inefficient routes; a more effective route will maximize the distance traveled, A R T I C L E I N F O A B S T R A C T Article history Received: July 2022 Revised : September 2022 Accepted: October 2022 The problem in product delivery is always being late and the company has not utilized the capacity of distribution transportation equipment to the fullest. This study aims to determine the shortest distribution route and minimize distribution costs using the Saving Matrix -Branch and Bound methods. In this study, the Saving Matrix method use to produce the shortest route distance, while the Branch and Bound method is applied to optimize a route distance. The results found that the Saving Matrix method followed by the Branch and Bound method reduced routes from the previous seven routes to five routes. Meanwhile, the proposed distribution model shortens the route of 23.6% compared to the current, and cost savings is 23%. To conclude, the model of distribution distance affects the costs savings and optimum route. This is an open access article under the CC–BY-SA license. Copyright © 2022 the Authors Keywords Distribution routes Saving Matrix Branch and Bound WINQSB https://doi.org/10.26555/ijish.v3i2.2222 mailto:spektrum.industri@ie.uad.ac.id http://journal3.uad.ac.id/index.php/spektrum mailto:ryanraflidevanda@gmail.com http://creativecommons.org/licenses/by-sa/4.0/ http://creativecommons.org/licenses/by-sa/4.0/ SPEKTRUM INDUSTRI Vol. 20 No. 2 October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 32 utilization of transportation means (fleet), distribution costs, and delivery time (Pattiasina et al., 2018). Transportation costs can be reduced by arranging the distribution system to run effectively and using existing transportation capital. Optimization of the distribution system can be done by determining the distribution route to minimize distribution costs, total distance traveled, and the length of the trip so that it can optimize the number and capacity of vehicles (Kurnia & Ernawati, 2021). The Sugar Company is a company that processes sugar cane harvests into sugar that has premium quality. Sugar Company has a target system in terms of distribution, namely, implementing and developing the right distribution channel strategy and producing optimal product sales volumes to get profits. There are several transportation strategies that may be implemented, such as shipping on time, enhancing shipment accuracy, and boosting shipping capacities (Hartati and Misnadesi, 2019). In its implementation, distribution is a marketing process that can add value to the product through various functions such as utility, place, time, and product ownership rights. In addition, the creation also runs marketing flows both physically and non-physically, such as the flow of information, promotions, negotiations, payment, and so on. But currently, Sugar Company is looking for a solution to develop an effective and efficient distribution system so that it does not cause many routes to be traversed. After the initial observations, currently Sugar Company does not yet have a specific method for determining distribution channels. This resulted in a long distribution route, and the cost of distributing sugar was not minimal. The company only relies on knowledge of the route from the driver to the location of the destination, resulting in inconsistencies in product delivery which causes frequent delays in the delivery sugar products. The next problem is that the utilization of the conveyance capacity is not maximized. Product delivery to the delivery place is routinely done without concern for the route or carrying capacity of the conveyance. This company has 7 routes in product distribution to agents. While in these 7 routes the utilization of transportation equipment capacity is not maximized, on route 1 the utilization of transportation equipment capacity is 98.15%, route 2 is 55.33%, route 3 is 69.01%, route 4 is 40%, route 5 is 96.35 %, route 6 is 53.25%, and route 7 is 53.25%. So the average utilization of transportation equipment capacity at the company is only 62.62% in 2021, which is relatively low, which is below 75%. The relative value of 75% is used to determine the feasibility of the products transported based on the vehicle's capacity (Humaira, 2021). The company does not provide a minimum limit to agents during the process of purchasing goods so that goods are often delivered with not full capacity. Therefore, the next agents often have to wait if no distribution fleet is available. Delays in the delivery of goods to agents can affect customer satisfaction with the company. As a company engaged in providing basic necessities, the company will realize that making shipping routes available for use in shipping activities is very important for the company. The saving matrix method has also been utilized by several researchers to identify distribution routes with the lowest possible transportation costs. There are many methods for optimizing distribution routes, such as the research conducted by Aprilia and Ernawati (2021) using Differential Evolution (DE), Pertiwi et al. (2019) using Clack and Wright Heuristics, Tartono (2021) using Tabu search, Harsono and Putro (2017) using Distribution Requirement Planning (DRP), and Cahyaningsih et al. (2015) using the Sweep Algorithm. However, in this research, the saving matrix and branch and bound methods are used because these methods are in accordance with the problems that occur. So as to be able to solve problems related to the Vehicle Routing Problem (VRP). For example, in research conducted by Fadlisyah et al. (2021) The company had issues with goods delivery to the project site. The distribution of items in a single delivery to the project site is carried out without first considering the carrying capability of the current fleet and research by Sugiono (2022) PT. X is a manufacturing company that produces motorcycles. PT. X now determines the distribution channel solely based on the drivers' expertise and understanding. Distribution routes must contain the proper setup of distribution networks to provide speedy and low-cost delivery. This is referred to as a vehicle routing Problem (VRP). To address this issue, research must be conducted in the hopes of reducing motorcycle unit distribution costs to dealers, namely by analyzing fuel consumption, toll fillers, unit bundles, and loading and unloading. Previous research' findings are still unsatisfactory. This might be because the method adopted is SPEKTRUM INDUSTRI Vol. 20. No 2, October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 33 not aligned with the data. As a result, this research will focus on designing a route determination model by integrating different models to achieve an optimum distribution. This research aims to determine the shortest distribution route. The difference in this study is that not only is the shortest route, but the addition of the Branch and Bound algorithm is used to minimize problems using the WINQSB software to assist in the research process. Therefore, there are three components consisting of a limiting function, a selection strategy, and branching rules that did not exist in previous studies. The proposed model is expected that sugar companies can determine the shortest distance and minimize distribution costs efficiently. RESEARCH METHOD The first step in this research is to identify problems using direct observation, namely to find out the real problems faced by Sugar company and using a review of literature to give a general summary and to bolster the data for this research (figure 1). There are two categories of data in this research: primary data and secondary data. Primary data is raw information that may be collected from the field. Interviews, observation, and documentation are the techniques used in this case. Additionally, secondary data (internal) refers to verified, reliable data that has already been collected by companies (Wirawan & Suparto, 2021). Continue to identify the variables after knowing the primary and secondary data. The dependent variables in this research are the determination of the distribution route and total distribution costs, while the independent variables are the initial route of distribution, agent location data, vehicle carrying capacity, distribution costs incurred by the company, and the amount of sugar product requests made by each consumer or agent. The steps of this research can be seen in Figure 1. Figure 1. Flowchart research Formation of a New Route Using The Saving Matrix Method A distributed scheduling method called the Saving Matrix method looks at the existing routes to find the shortest route. This method is helpful so that the distribution of products to consumers is more scheduled so companies can save costs, time, and energy (Sugiono, 2022). The vehicles needed to serve all stops can be reduced by using the Saving Matrix approach to reduce the overall distance. The savings method enables a lot of useful considerations for an implementation (Yetrina and Nainggolan, 2021). The Savings matrix is a method that determines the best route by taking into consideration the distance traveled, the number of vehicles to be used, and the number of products that can be loaded by vehicles in product delivery to consumers so that the distribution process is optimal (Wulandari, 2020). Meanwhile, data is required at this stage: the coordinates of the agent on the map, the number of agents, and the vehicle's carrying capacity. The assumption is that traffic conditions such as traffic lights and congestion do not affect vehicle speed (Damayanti et al., 2020). The saving matrix approach consists of numerous phases, which are as follows (Pujawan, 2017): 1. Identify the Distance Matrix SPEKTRUM INDUSTRI Vol. 20 No. 2 October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 34 Equation (1) is used to determine the step distance matrix: J(1,2)= √(𝑋1 − 𝑋2) 2+(𝑌1 − 𝑌2) 2 (1) 2. Identify the Savings Matrix Next, the distance saving matrix is calculated using Equation (2): 𝑆(𝑥, 𝑦) = (𝐽(𝐺, 𝑥) + 𝐽(𝐺, 𝑦) − 𝐽(𝑥, 𝑦) (2) 3. Allocate consumers to vehicles or routes In this step, the customer is allocated to the vehicle or route in the combination of customer routes, combined to the limit of the existing truck or fleet capacity, by looking at the value of the largest savings in the distance saving matrix table. The procedure used to create a customer on a route is to divide the customer based on the largest saving value. This procedure is repeated for all customers that have been allocated to the existing route (Sutoni and Apipudin, 2019). 4. Sort consumers into defined routes There are several methods for establishing the order of visits. In this research, the Nearest Insert method was applied. The Nearest Insert method is the shortest route since it is put into the current route, resulting in the minimum distance. Calculation of New Routes Using The Branch and Bound Method The Branch and Bound algorithm, namely the use of bounds for the function to be optimized combined with the best available solution value, allows this algorithm to find parts of many solutions implicitly (Monoarfa et al., 2021). In essence, this algorithm uses an enumeration approach by turning off search space which does not lead to completion. This method is made for linear programming (linear programming). This method is primarily applicable to optimization issues. This method is made up of two basic procedures: branching and bounding. Branching is the process of dividing a large problem into two or more smaller ones (sub problems). Bounding, on the other hand, is the act of finding the lower bound on the best solution to the subproblem in issue (Bangun et al., 2015). The explanation of the branch and bound algorithm on the flow chart is described as follows: a. Form a matrix (Cij) which is the distance matrix from each city that forms a matrix of size n x n, where n is the number of the initial city and all cities to be visited. Each element of the Cij matrix is the distance from the city point i to city j, while i and j are vertices.Reducing the Cij matrix by subtracting each element in the row with the smallest value. b. Reducing the Cij matrix by subtracting each element in the column that has the smallest value with the smallest value. c. Furthermore, the reduction process will produce a root node boundary value of c(R) which is obtained from the sum of all the subtraction elements. d. A matrix A is formed which is the reduced matrix for the root node R. e. Then if we assume that S is a child of R, so that the side (R, S) in the status tree, then we take several steps in the matrix A below: 1. Converts all value elements in rows and columns to values ∞ 2. Convert element A(j,1) to value ∞ 3. Reduce matrix A as in steps b) ,c) ,d) to produce another matrix such as matrix B. 4. Calculate the minimum weight value for each node according to the equation: c(S) = c(R) + A(i,j) + r, where c(S) is the minimum weight value for the S node, c(R) is the minimum weight value for the root node, A(i,j) is the minimum weight value for the root node. edge elements (i,j) at the vertices (R,S), and r is the sum of all the subtractions to obtain the reduction matrix but for the vertex S. f. The matrix reduction is continued indefinitely until a status tree with a smaller limit value is generated. g. Create a route using the nodes collected. In other words, the formation of under-cycles in the network is prohibited by these constraints. Since variables 𝑥𝑖𝑗 can only take a 0 or 1 state, this problem has a finite number of solutions. In this research, the problem solving process was assisted using the Branch and Bound method using the software. QSB (Quantity System for business) software or commonly known as WINQSB (QSB running on windows SPEKTRUM INDUSTRI Vol. 20. No 2, October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 35 operating systems), is software that contains problem-solving algorithms for operations research (operational research) and can be used to solve Traveling Salesman Problems. This is a route 1 sorting agent distance per unit kilometer example (Triyanto et al. 2015): a. Open the WinQSB software and select Network Modeling. b. Click the file and then click New Problem, then the NET Problem Specification will appear. c. Select Traveling Salesman Problem (TSP) in the Problem Type option. Then select minimization on the objective criterion. Click the spreadsheet matrix form in the data entry format. Type route 1 (adjusted to the order of the route to be calculated based on the selected method, namely the Saving Matrix method) in the problem title. Type a number (adjusted with the number of nodes on the routes to be checked based on the selected method, namely the Saving Matrix method) on the number of nodes. Finally, Click ok. d. Type edit to change the From/To description as needed. Type the distance (Km) in each column and row according to the selected nodes on the new route 1 according to the distance matrix. e. Click solve and analyze, select solve and display branch and bound step. f. Click iteration and select nonstop to finish. Selection of the Most Optimal Proposed Method Furthermore, the selection of methods from 2 methods that have been processed. The choice of the method can be seen from the distance traveled by the new route. This selection is made to determine which solution is more optimal from the two proposed methods (TJ2). Calculate the total distribution cost of the selected method Calculate the total cost of distribution of sugar products on the proposed route based on the proposed distance data. Furthermore, the initial Saving Matrix route and the Branch and Bound (TJ2) method are used to calculate the total consumer spending for the period January to December 2021. Calculation of the total cost of distribution is carried out on each route. From January 2021 to December 2021, distribution costs are estimated four times each month using a suggested approach for each new route created. at the request of the agent. As for calculating the total cost of distribution on each route (6 Km = 1 litre) using equation (3)-(5): Distribution Cost = Total Distance x 1/6 x Fuel Cost x 4x/month x 12 months (3) Retribution Cost = Retribution Cost x 4x/month x 12 months (4) Total Distribution Cost of Route X/year = Distribution Cost + Retribution Cost (5) Comparison of Company Method and Proposed Method Then will analyze the comparison between the company's distribution costs and the recommended distribusion costs using the proposed method (Flórez-Orrego et al., 2015). The formula for calculating the percentage of distance and cost savings is shown in equation (6)-(7) Percentage of Distance = Company Route – Proposed Method Route x 100% Company Route (6) Percentage of Cost = Company Cost – Proposed Method Cost x 100% Company Cost (7) RESULTS AND DISCUSSION Data collection After the collecting data procedure, the location data of consumers or agents obtained from the company is in the form of agent location data, with 13 agents spread widely in various cities in East Java Province as shown inTable 1. This research uses to determine the agent's location with a map of East Java Province with a scale of 1: 420,000. Calculate the distance between one agent and another as well as the distance between the warehouse and the agent by entering the coordinates. Coordinates are then drawn on a map of East Java, with the location of the warehouse serving as the primary coordinate point (0,0). The x-coordinate line and y-coordinate line of the map are also used to change each agent's placement. The distribution center is a storage/warehouse that is used to suit the demands of small SPEKTRUM INDUSTRI Vol. 20 No. 2 October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 36 traders in a region, allowing the market selling price of items to become more competitive. (Rao, 2017). Table 1. Average demand and warehouse-agent distance Code City Average Demand (Kg) Warehouse-Agent Distance (Km) Coordinat X Y C1 Surabaya 4,304 81.3 3.1 19.1 C2 Sidoarjo 3,548 66.8 2.5 15.7 C3 Blitar 1,813 42.4 10.1 -0.2 C4 Kediri 2,426 64.2 -14.1 5.9 C5 Jember 5,521 113 26.8 -2.3 C6 Mojokerto 348 66.3 -3.9 15.3 C7 Jombang 852 66.5 -8.6 13.3 C8 Bangkalan 3,333 110 3.2 25.9 C9 Pemekasan 4,375 132.6 21.4 23.2 C10 Madiun 2,256 117.6 -25.8 10.9 C11 Ponorogo 2,004 116.2 -27.2 5.1 C12 Gresik 430 95.4 0.6 22.7 C13 Lamongan 325 100.1 -4 23.5 Source: PT. XYZ Distribution cost data is data from companies that explain in detail the company's expenses in product distribution, ranging from fuel costs, distribution costs, to driver salaries. The distribution cost data issued by the corporation can be seen in table 2. Table 2. Cost Distribution Data No Cost Type Truck Colt Diesel (TCD) 1 Fuel Cost : Solar IDR 5,150,-/Litre 2 Retribution Cost : Parking Fees, Toll Fees and Food Fees IDR 350,000,-/Trip 3 Driver Salary IDR 3,636,250,-/Month Table 3. Company Route Data, Total Distance, and Total Demand Route Code Route Total Demand (Kg) Total Distance (Km) 1 C0-C1-C2-C0 7,852 162.8 2 C0-C3-C4-C0 4,426 211.4 3 C0-C5-C0 5,521 226 4 C0-C6-C7-C0 1,200 154.3 5 C0-C8-C9-C0 7,708 319.9 6 C0-C10-C11-C0 4,260 259 7 C0-C12-C13-C0 755 215.1 Total 31,535 1,548.4 (TJ1) Table 3 will show the initial route, total distance and total order load used by sugar company to distribute its products. Sugar company has 7 distribution routes for the initial route, and sugar distribution is carried out four times a month. Calculations revealed that total agent demand for all of the company's initial trips was 31,535 Kg, and the total distance of the initial trip for the entire company was 1,548.4 Km (TJ1). Then proceed with calculating the total cost of distribution for the months of January- December 2021 with the initial route of the company method. Table 4 shows the calculation of distribution costs using equation (3) and (4). As for employee salaries, they are calculated separately, not in one route in each route, because the driver's salary is calculated every month. Table 4. Total Distribution Costs January-December 2021 No Code Route Distribution Costs (IDR) 1 Route 1 23,507,328 2 Route 2 23,509,648 3 Route 3 26,111,184 4 Route 4 8,757,168 5 Route 5 29,979,888 6 Route 6 27,470,784 7 Route 7 11,262,144 8 Total Driver Salary 43,635,000 Total 227,933,144 SPEKTRUM INDUSTRI Vol. 20. No 2, October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 37 Formation of a new route using the Saving Matrix Method Since the distance from the warehouse to each agent has already been estimated, the first step in this procedure is to calculate the distance matrix, or the distance between one agent and another, as well as the distance between each warehouse and each agent. Since this distance between the warehouse and each agent is measured in kilometers, the following calculations are performed to estimate the distance between each agent. After getting the whole matrix, it will also be possible to determine the distances between each agent and the warehouse as well as between one agent and another measured in Kilometers. Table 5 shows the calculation of distance between the location of the agents and the sugar warehouse using equation (1). Then, the savings distance is calculated for the location distance from one agent to another. Table 6 shows the calculation of distance saving matrix between each agents using equation (2). Table 5. Distance Between Agent Location and Sugar Warehouse (Km) C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C1 2 C13 C1 81.3 0 C2 66.8 14.7 0 C3 42.4 86.2 76.9 0 C4 64.2 91.1 81 104.8 0 C5 113 134,1 127 70,7 175,1 0 C6 66,3 33,6 26.9 87.7 58.4 148.6 0 C7 66.5 54.8 47.7 96.9 38.7 162.5 21.5 0 C8 110 28.6 42.9 113.4 111 154.4 53.6 57.6 0 C9 132.6 78.9 85.4 109.6 166 109.8 111.3 132.7 77.3 0 C10 117.6 126 120.5 157.9 53.3 227.8 97.8 72.9 137.1 204.9 0 C11 116.2 140.3 132.4 158.2 55 31.1 106.8 85.4 154.7 217.8 25.2 0 C12 95.4 18.5 30.5 104.2 93.7 152.1 36.4 55.2 17.3 87.4 121.5 138.2 0 C13 100.1 35.1 42.6 115.8 85.2 168.8 34.4 47 31.9 106.7 105.8 124.4 19.6 0 Table 6. Distance Saving Matrix In Kilometers (Km) C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C1 0 C2 133.6 0 C3 37.5 32.3 0 C4 54.4 50 1.8 0 C5 60.2 52.8 84.7 2.9 0 C6 114 106.2 21 72.1 30.7 0 C7 93 85.6 12 92 17 111.3 0 C8 162.7 133.9 39 63.2 68.6 122.7 118.9 0 C9 135 114 65.4 30.8 135.8 87.6 66.4 165.3 0 C10 72.9 63.9 2.1 128.5 2.8 86.1 111.2 90.5 45.3 0 C11 57.2 50.6 0.4 125.4 198.1 75.7 97.3 71.5 31 208.6 0 C12 158.2 131.7 33.6 65.9 56.3 125.3 106.7 188.1 140.6 91.5 73.4 0 C13 146.3 124.3 26.7 79.1 44.3 132 119.6 178.2 126 111.9 91.9 160.4 0 Furthermore, after the distance saving matrix is obtained in table 6, an allocation will be made to get the shortest new route by adjusting the number of vehicle capacities owned by the company. Merger begins with the greatest savings value since it seeks to maximize savings while classifying retailers (destinations) according to a specified path (Abdurrahman et al., 2019). The allocation of agents on new vehicles and routes in the period January 2021 – December 2021 is as shown in Table 7. SPEKTRUM INDUSTRI Vol. 20 No. 2 October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 38 Table 7. Determination of Agents on The Vehicle by Using Iteration Iteration Route Saving Distance (Km) Order Size (Kg) Max Vehicle Capacity (Kg) Route To- 1 C10-C11 208.6 2,256+2,004 = 4,260 8,000 1 2 C8-C12 188.1 3,333+430 = 3,763 8,000 2 3 C8-C12-C13 178.2 3,333+430+325=4088 8,000 2 4 C8-C12-C13-C2 133.6 3,333+430+325+3,548 =7,636 8,000 2 5 C8-C12-C13-C2-C6 132 3,333+430+325+3,548 +348=7,984 8,000 2 6 C10-C11-C4 128.5 2,256+2,004+2,426 =6,686 8,000 1 7 C10-C11-C4-C7 111.2 2,256+2,004+2,426+852 =7,538 8,000 1 8 C3-C5 84.7 1,813+5,521=7,334 8,000 3 9 C1 0 4,304 8,000 4 10 C9 0 4,375 8,000 5 Total 31,535 40,000 The distribution is then sorted as the following stage. In this study, the Nearest Insert approach is applied. Sorting is accomplished by picking the agent nearest to the warehouse. Orders for sugar product distribution from the warehouse to agents should be returned to the warehouse using the closest insert technique, as detailed in Table 8. Table 8. Route Sequence After Using Saving Matrix Method (Proposed) Route Code Rute Distance (Km) 1 C0-C10-C11-C4-C7-C0 303 2 C0-C6-C8-C12-C13-C2-C0 266.2 3 C0-C3-C5-C0 226.1 4 C0-C1-C0 162.6 5 C0-C9-C0 265.2 Total Distance 1,223.1 Calculation of new routes using the Branch and Bound Method Based on the data grouping, the new route of sugar product from the warehouse to the agent formed in the table above proceeds to sort using the help of the Branch and Bound Method. WinQSB Software supports in the Branch and Bound method's application. After using the branch and bound method, the route sequence is determined using software. This is an example of sorting agent distance per unit kilometer for route 1 (Triyanto et al. 2015): a. Open the WinQSB software and select Network Modeling. b. Click the file and then click New Problem, then the NET Problem Specification will appear. c. Select Traveling Salesman Problem (TSP) in the Problem Type option. Then select minimization on the objective criterion. Click the spreadsheet matrix form in the data entry format. Type route 1 (adjusted to the order of the route to be calculated based on the selected method, namely the Saving Matrix method) in the problem title. Type a number (adjusted with the number of nodes on the routes to be checked based on the selected method, namely the Saving Matrix method) on the number of nodes. Finally, Click ok. d. Type edit to change the From/To description as needed. Type the distance (km) in each column and row according to the selected nodes on the new route 1, which contains the distance (Km) for Warehouse (C0), City of Kediri (C4), City of Jombang (C7), City of Madiun (C10), and Ponorogo City (C11) according to the distance matrix. e. Click solve and analyze, select solve and display branch and bound step. f. Click iteration and select nonstop to finish. Figure 2 shows that the order of the trip sequence on route 1 is nearly optimal is 283.8 Km, based on the data input generated in the WinQSB program. The next path will thereafter be followed. SPEKTRUM INDUSTRI Vol. 20. No 2, October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 39 Figure 2. Display of Iteration and Nonstop To Finish on Route 1 The following table 9 describes how to order the distribution of sugar from the warehouse to the agent for return to the warehouse using the Branch and Bound Method using WinQSB Software. Table 9. Route Sequence After Using the Branch and Bound Method Route Code Rute Distance (Km) 1 C0-C4-C11-C10-C7-C0 283.8 2 C0-C2-C12-C8-C13-C6-C0 247.2 3 C0-C5-C3-C0 226.1 4 C0-C1-C0 162.6 5 C0-C9-C0 265.2 Total Distance 1,184.9 Selection of the Most Optimal Proposed Method Furthermore, the selection of methods from 2 methods that have been processed is carried out. The selection of methods can be seen from the combat distance of the new route. This selection was made to determine which solution is more optimal than the two proposed methods. Table 10. Table for Selection of the Most Optimal Proposed Method Route Saving Matrix Method Distance (Km) Saving Matrix and Branch and Bound Method Distance (Km) 1 C0-C10-C11-C4-C7-C0 303 C0-C4-C11-C10-C7-C0 283.8 2 C0-C6-C8-C12-C13-C2-C0 266.2 C0-C2-C12-C8-C13-C6-C0 247.2 3 C0-C3-C5-C0 226.1 C0-C5-C3-C0 226.1 4 C0-C1-C0 162.6 C0-C1-C0 162.6 5 C0-C9-C0 265.2 C0-C9-C0 265.2 Total 1,223.1 Total 1,184.9 (TJ2) Source: Protable cessed Data Table 10 shows that there is a distance comparison between the two methods used. Based on the outcomes of the branch and bound approach and the Saving Matrix's sequence of route lengths from the warehouse to the agent. The Savings Matrix method is chosen as the most effective suggested strategy, followed by the Branch and Bound method. In comparing the values of the distance traveled, the Saving Matrix method simply results in a value of 1,223.1 Km, whereas the Branch and Bound method resulted in a value of 1,184.9 Km (TJ2). Calculate the total distribution cost of the selected method Calculate the total cost of distribution of sugar on the proposed route (TJ2) based on the proposed distance data. Furthermore, the Saving Matrix starting route and Branch and Bound (TJ2) method were used to calculate the total consumer expenses for the period of January to December 2021. From January 2021 to December 2021, distribution expenses are estimated four times each month using the suggested approach for each new route created at the agent's request. Table 11 shows the calculation of distribution costs on each route after used method proposed using equation (3) and (4). SPEKTRUM INDUSTRI Vol. 20 No. 2 October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 40 Table 11. Distribution Costs After The Proposal No Code Route Distribution Costs (IDR) 1 Route 1 28,492,560 2 Route 2 26,984,640 3 Route 3 26,115,312 4 Route 4 23,499,120 5 Route 5 27,726,240 6 Total Driver Salary 43,635,000 Total 176,452,872 Based on the results of the sequence of route distances from the warehouse to the agent using the Saving Matrix and branch and bound methods. The total distribution cost is obtained, which is Rp. 176,452,872. Comparison of Company Method and Proposed Method Then tables 12 will analyze the comparison between the company's transportation costs and the recommended transportation costs using the proposed method. Table 12. Distribution Comparison Distribution Comparison Method Saving Distance (Km) Distance Saving Percentage (%) Company Route Proposed Method (Saving Matrix and Branch and Bound) Total Distance (Km) 1,548.4 1,184.9 363.5 23% Total Cost (IDR) 228,933,144 176,452,872 52,480,272 23% The Saving Matrix method followed by the Branch and Bound method is better than the company Method. As a result, the Branch and Bound method results from the Saving Matrix method, with a total distance of 1,184.9 Km, will be chosen as the suggested route, and the total initial distance of the company is 1,548.4 Km, so the total distance savings is 363.5 Km or with a percentage of distance savings of 23%. Therefore, the Branch and Bound method followed by the Saving Matrix method may be used to find the optimal distribution path to get a less order load. The proposed method of settlement between Saving Matrix & Branch and Bound is therefore preferable to the company's initial/regular procedure. So the results obtained from the proposed method of Saving Matrix & Branch and Bound with a total cost of IDR 176,452,872,- per year with cost savings on the initial route of IDR 228,933,144,- per year, so the total cost savings of IDR 52,480,272,- per year or with a percentage of cost savings of 23%. Thus, the outputs of the combined Saving Matrix, Branch, and Bound method may be used to choose the effective distribution route in order to minimize costs. CONCLUSION This research integrates Saving Matrix and Branch and Bound to find the optimal route of sugar distribution. The proposed model results in a route of 1,184.9 Km with the company's initial route of 1,548.4 Km, then obtained savings of 363.5 Km with 23%. Therefore, the shortest route will also affect the distribution costs of the company to obtain the total cost of the company's initial distribution of IDR 228,933,144, - and the total cost of using the method of Savings Matrix and Branch and Bound of IDR 176,452,872,- then obtained savings of IDR 52,480,272,- with savings of 23%. This research has distribution of goods-related limitations. Researchers realize that in research, there are many obstacles. One factor that becomes an obstacle is the product distribution process. In this research, the products delivered are homogenous due to the fact that the product distribution procedure is occasionally sent to agents with many items. For further research, it is possible to include distribution costs for loading and unloading variables because these variables are not included in this study. Secondly, it is possible to use Google Maps to get the distance from the warehouse to the agent accurately, and lastly, it is also possible to anticipate the agent demands for the upcoming years. SPEKTRUM INDUSTRI Vol. 20. No 2, October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 41 REFERENCES Baharudin, D. S., Salsabila, S., and Anggraeni, N. F. (2020). Optimization of vehicle routing distribution of gallon bottled water products using a combination of Genetic Algorithms and Tabu search at the Banyu Belik Purwokerto refill Drinking Water Depot. Journal Of Engineering: Science Development Media And Engineering Applications, 19(01), 24-33. Bangun, P. B. J., Octarina, S., and Purba, B. V. (2015). Penyelesaian Travelling selesman problem (TSP) dengan metode Branch and Bound, Semirata 2015 bidang MIPA BKS-PTN Barat, Pontianak, 399–408. Damayanti, T. R., Kusumaningrum, A. L., Susanty, Y. D., and Islam, S. S. (2020). Route Optimization Using Saving Matrix Method – A Case Study at Public Logistics Company in Indonesia, International Conference on Industrial Engineering and Operations Management, Detroit, 1583–1591. Dell’Amico, M., Montemanni, R., & Novellani, S. (2021). Algorithms based on branch and bound for the flying sidekick traveling salesman problem. Omega, 104, 102493. Fadlisyah, H., Septiawan, D., and Mahmudin, J. (2021). Minimizing Delivery Costs With The Saving Matrix Method (Case Study At PT.Sei), Review of International Geographical, 11(5), 1053–1058. Febriyanti, D. E., Primadasa, R., & Sutono, S. B. (2022). Determination of Distribution Routes Using the Saving Matrix Method to Minimize Shipping Costs at PT. SUKUN TRANSPORT LOGISTICS. Spektrum Industri, 20(1), 79-90. Indrawati, I., Eliyati, N., and Lukowi, A. (2016). Determining the Optimal route for transporting waste in Palembang city using the Saving Matrix method. Journal Of Science Research, 18(3), 105-109. Kurnia, A., and Ernawati, D. (2021). Optimal Distribution Route Planning With Differential Evolution (De) Algorithm Method Pt. Xyz. Juminten, 2(4), 73-84. Kurniawan, V. R. B., & Puspitasari, F. H. (2020). A mathematical model for delivery zone groups based on courier assignment optimization: A case study in a logistics service provider. Spektrum Industri, 18(2), 183. Mahmud, S. L., Achmad, N., and Malango, R. (2022). Determination of 3 Kg Lpg gas distribution route using Saving Matrix method (case study : South Bolaang Mongondow Regency). Journal Of Mathematical Research And Applications, 06(01), 40-62. Mehranfar, N., Hajiaghaei-Keshteli, M., & Fathollahi-Fard, A. M. (2019). A novel hybrid whale optimization algorithm to solve a production-distribution network problem considering carbon emissions. International Journal of Engineering, 32(12), 1781-1789. Monoarfa, M. I., Lasalewo, T., and Hasanuddin. (2021). Optimization Of Subsidized Urea Fertilizer Distribution Route By Saving Matrix And Generalized Assignment Method. Journal Of Vocational Science And Tectonology, 1(1), 12-18. Poikonen, S., Golden, B., & Wasil, E. A. (2019). A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS Journal on Computing, 31(2), 335-346. Rizkilah, W. R., Rizwan, R., Faisal K. M., and Fauzi, M. (2021). Implementation of the Saving Matrix Method to Determine Vehicle Routes. Journal of Community Service, 3(1), 23-31. Sarjono, H. (2014). Determine the best route to minimize transportation costs. Applied Mathematical Sciences, 8(62), 3063-3074. Sugiono, M. C. (2022). Model vehicle routing problem for determining the distribution route of motorcycle units by saving matrix method. Journal Of Industrial Service, 7(2), 230-233. Syah, H. F., Putra, C. L., and Mulyadi, N. (2020). Meminimalkan Biaya Transportasi Pengiriman Barang Plts Seismic Area Jawa Barat Dengan Menetukan Rute Distribusi Yang Efisien Dengan Metode Saving Matrix Di Pt.Xyz. Airlangga Journal of Innovation Management, 1(2), 226–236. Triyanto, F., Adianto, H., and Susanty, S. (2015). Usulan Rancangan Rute Distribusi Gas LPG 3 Kg Menggunakan Metode Heuristik dan Metode Branch and Bound. Jurnal Online Insitut Teknologi Nasional, 03(03), 194–205. Wulandari, C. B. K. (2020). Determination of distribution routes using the Nearest Neighbors method and Branch and Bound Method to minimize distribution costs in PT. X. Journal of industrial engineering optimization (JOTI), 2(1), 7-12. SPEKTRUM INDUSTRI Vol. 20 No. 2 October 2022 pp. 31-42 Integrated Saving Matrix - Branch and Bound Method to… (Devanda & Pulansari) 42 Yetrina, M., and Nainggolan, D. S. (2021). Penentuan Rute Distribusi Untuk Meminimasi Biaya Distribusi di UKM Habil Snack. Jurnal Teknologi Dan Sistem Informasi Bisnis, 3(1), 247–253.