Design of Distribution Optimization Application Using Savings Algorithm Modification Method

Ivansius1, Siti Komsiyah2, Sudarno Wiharjo3

1Computer and Science Technology, Bina Nusantara University, West Jakarta, Jakarta;

2Computer and Science Technology, Bina Nusantara University, West Jakarta, Jakarta.

3Computer and Science Technology, Bina Nusantara University, West Jakarta, Jakarta.

Email:

ABSTRACT In daily life, the distribution process is very important in the economy. Distribution of fuel includes one of the distribution activities need process optimization for improving the efficiency of good time, cost, and effort. There are many models that describe the problem of distribution. One is the Vehicle Routing Problem (VRP). VRP is the determination of the route optimization problem with limited vehicle capacity. VRP can be completed with a variety ways, one of which is Savings Algorithm. Savings algorithm is one of the ways of classic heuristic methods. The purpose of this research is to design a program of fleet, routes, and distribution cost by using Savings Algorithm method and waterfall model. The result of this research is to determine the type and number of the fleet to be used in distributing fuel with cost as optimum as possible. It is expected that this research obtained optimum result.

Keywords: optimization, distribution, Vehicle Routing Problem (VRP), Savings Algorithm, waterfall model

  1. INTRODUCTION

In daily life, people did not escape the future use of the fuel oil. Many human activities that require fuel. In meeting the needs of fuel, it should also be noted the availability of fuel in which fuel is a natural resource which is not variety can be updated. Moreover, from time to time the increasing population growth. Automatically if the population growth is increasing, the demand for fuel will also increase.

Realization of distribution of subsidized fuel by the end of June totaled 22.6 million tonnes, or 47.4 percent of the total quota for PT Pertamina (Persero) which is allocated based on APBN-P 2013 set of 47.6 million KL. Realization of data based on subsidized fuel distribution to 30 June 2013, Premium has tersalurkan as much as 14.4 million KL, or 46,7 percent against a quota of subsidized fuel Pertamina amounted to 30,7 million KL. (

Distribution of fuel will also have good performance if supported with the use of technology and information. Advances in technology and information rapidly, hence the need for computer use is increasingly needed. As for the benefits of the technology and information for a company, among others, can provide added value to the company. In addition to information technology can also increase the effectiveness of the internal controls, improve, create a competitive advantage, creating an image or the "image" of business, upgrade the work process, accelerate decision-making, reduce operational errors, etc.

Currently, many companies that his system is still done manually started to switch to computerized era. With the computerization is expected the company's performance more effectively and efficiently. It also needed a system that is accurate and easy to run. Therefore, every company is required to implement a reliable and information technology are also accurate. Accurate information is required to process the data storage in order to produce a report that the company's output.

In this thesis, the author would apply Savings to problem solving Algorithm VRP (Vehicle Routing Problem) in the form of a desktop application. This algorithm with application in the field of distribution of fuel then the problem costs for operations and delivery time can be obtained seoptimal results possible.

Based on the background that exists, then the outline of the issues that will be discussed are:

  1. The needs of the community will fuel which is ever increasing.
  2. Request the delivery of fuel oil that vary in every public fueling station.
  3. The distance between the gas station and depot which is much concerned with the availability of fuel-carrying tank truck fleet, travel time, as well as expenditure in the distribution of FUEL from the depot to the fas station.

The core of the scope to be covered in this research are:

  1. Create an application distribution design using the C # programming language
  2. The methods used in the design optimization of the distribution it is Savings Algorithm
  3. Distribution is only done on a gas station COCO (Company's Own Company Operated) of PT. Pertamina Retail in Jakarta except fas station COCO Pondok Indah and gas stationCOCO Fatmawati.
  4. The Program is designed based on to the needs and requests of the gas station with the population and the expansion areas
  5. Schedule the distribution used in one year running
  6. The Program is not designed to be used by the public, only certain divisions within the company
  7. The Data used for the design of the program obtained internally from PT. Pertamina and PT Pertamina Retail Patra Niaga.
  8. The Program does not change the existing database, just use such data as input.

Goals to be achieved from this research are as follows:

  1. To solve the problem of distribution process with a simple program so that the process can be well-ordered so that it will get the optimal decision.
  2. Design and then test the desktop application for pendistibusian fuel oil Savings method Algorithm using a programming language based on C#.

The benefits to be achieved from this research are as follows:

  1. For gas station: can estimate quantity of fuel.
  2. For PT. Pertamina Retail: can estimate the cost to be incurred and the profit obtained.
  3. For Depot: can estimate how much fuel is distributed to gas stations in accordance with the availability of fuel at the depot as well as determine the fleet that will be used to distribute the fuel from the depot to the gas station so that it will be determined the distribution of the minimum total cost.
  4. For the community: can play well without any obstacles lack of FUEL for their activities using BBM.
  1. MATERIALS AND METHODS
  2. Vehicle Routing Problem (VRP)

Vehicle Routing Problem (VRP) is a combinatorial optimization problem is one of the most popular, where the issue involves the determination of the route of the vehicle with a limited load capacity originating from depots (distribution center) to serve all customers with requests for a number of goods. Depot as a distribution center of goods has a limited capacity with a vehicle to transmit a number of the goods to the customer.

VRP in simple terms can be expressed as a problem to determine optimal routes through a set of locations and defined in a graph G = (V, A) where V = {v0, v1, ..., vn} is the set of nodes and A = {(vi, vj): vi, vj∈ V, vi ≠ vj } is the set of arcs. The Node represents a v0 depot where fleet vehicles Nv which has the same capacity is located. The value of Nv can be determined or non, which is bounded by a constant, N ≤ n-1. All remaining nodes represent the customer, a non-negative matrix (distance or time or cost) C = (cij) defined in A. Because cij = cji for all (vi, vj), then the problem is said to be symmetrical, and an arc is represented by indirect node. A non-negative weights in connected with all nodes that represent request customer vi, and naturally the weighting that is connected with every route must not exceed the capacity of the vehicle Qv.

The basic Model of a single depot VRP is as follows:

Minimize

Constraints

where:

: decision variables (variables a variable is binary decision indicating that the bow()served by v vehicles.

(1): the objective function of minimizing the distance or time or cost.

(2) and (3): each node will be served by a single vehicle.

(4): every vehicle will have nodes they visit meniggalkan.

(5): limitation of the capacity of the vehicle.

(6) and (7): States that the availability of the vehicle will not be exceeded.

(8): binary decision variables for limits.

A graf — G = (V, A) where V = {0, 1, ..., n} is the set of n + 1 nodes and A = {(i, j): i, j∈ V, i ≠ j} is the set of arcs. Node 0 represents a depot, and a set of V* = V – 0 related to n customer. Every customer i∈V* require a supply depot units of qi (assumed q0 = 0). A fleet of vehicles that are heterogeneous in depot and was used to supply the needs of the customer. The fleet of vehicles consists of m-type vehicles are available at the depot, each having a capacity equal to Qk. Each vehicle is also connected with a fixed fee, equal to Fk, which is the cost to rent the vehicle. In addition, for each ARC (i, j) A and for each type of vehicle for kM, given the cost of routing . A route is defined as a pair (R, k) where R = (i1, i2, ..., i|R|) V*, is the simple circuit in G that contains the depot, and k is a type of a vehicle with regard to the route.

A route (R, k) is said to be worth in total demand from the customer does not exceed the capacity of the vehicle Cost of a Qk. route associated with the total cost of an arc which forms the route, plus a fixed cost of vehicle related issues. The most common form of formation of Heterogeneous VRP contains the set of routes that are worth a total minimum cost such that:

•Each customer visit right by one route

•The number of routes that do not outweigh the mk

Two versions of the above problems naturally formed: symmetrical, when , then every pair (i, j) ∈ V and for any type of vehicle for k ∈ M, and symmetrical if otherwise. (Baldacci et al, 2008)

2.2Savings Algorithm

Clarke & Wright Savings Algorithm is a method invented by Clarke and Wright in 1964. Algorithm Clarke & Wright Savings measured savings doing the calculations of how much mileage reduction can be done and time spent with hooking existing nodes and routes based on the value of savings is the largest that the mileage between the source node and a destination node. The process of calculation, the method is not only use distance as a parameter, but it is also the time to acquire the biggest savings for later compiled into a best route.

The purpose of the method of savings is to manage the total distance traveled of all vehicles and to manage the indirect number of vehicles required to serve all customer (gas stations). The logic of this method originated from the depot and then serve all customer and ends at the depot. This gives the maximum distance in the matter of the determination of the route. Then place two or more merged into one route so mileage can be minimized which is shown in the image below.

Savings approach allows many considerations are very important in a realistic application. Before the customer put in a route, the route with the next stop should be seen. A number of questions about the design of the route can be asked questions, such as whether the route exceeds the maximum distribution of the time drivers are permitted, what time to break for the driver have been met, whether a vehicle large enough to carry the volume of available routes. Breach of these conditions can be refused to the rest of the entire route. The next stop is visible according to the value of the biggest savings and the process is repeated consideration. This approach does not guarantee an optimal solution, but taking into account the complex problems that exist, a good solution can be sought.

Figure 1 reduction of Mileage through consolidation of Stops en route

(Ballou, Ronald h., 1999)

Troubleshooting by using Savings Algorithm or commonly called by Clarke and Wright Algorithm as follows:

  1. Calculate the savings (savings) by using the equation

s (i, j) = d (D, i) + d (D, j) – d (i, j) for each node

  1. Create a ranking of the calculation of savings and create a list of savings is the largest to smallest.
  2. To yield savings s (i, j) which are being considered include the relationship node (i, j) on a single route. When there is no limiting routes, it will interfere with the pencatuman route (i, j) and when:
  3. Well i or j are determined on a route where in some cases the new proposed route included in j.
  4. Or, only one of the two points (i or j) is already included in existing routes and nodes that are not included on that route (including one node on the route when it is not bordering the depot D so that it does not exceed the node), where the relationship (i, j) is added on the same route).
  5. Or, both i and j are included into two different routes and the other node is included in the route, where the two routes can be combined.

From decryption before, done modeling for minimising the costs of distribution by PT Pertamina Patra Niaga simultaneously:

N: the set of nodes, where N = {0, ..., the i, the ..., n}. Node 0 declare depot

K: the set of types of vehicles, where K = {1, ..., the t}

dij: the distance between nodes i and node j

i: retailer demand rate i N

qi: retailer quantity delivery i∈N

Ck: the maximum capacity of each vehicle type k

Qi: tank capacity maximum of pendam retailer i∈N

fk: fixed cost of each vehicle type k

mk: the number of vehicles type k used

P: the price of fuel used liter per vehicle

rk: the ratio of the fuel needs of vehicle type k

then the model is formulated as follows:

Minimize

The purpose of the model function i.e. for minimising total cost of daily distribution which describes the total amount of the rental fee of the vehicle is the multiplication of the number of vehicles types of k that are used with the cost of rent of vehicles types k and total variable costs which is the multiplication between the needs of vehicle fuel type k with distance traveled from node i to node j in node j to node i once visited.

With the limiting function:

  1. To define that each node customer visited only once by one vehicle
  1. If the vehicle visiting customer, then the vehicle must also be out of there
  1. Convincing each route starts and ends in the Central depot
  1. Vehicle capacity limits
  1. Quantity shipped for each shipment must be less than the tank capacity pendam retailer i ∈ V
  1. Load the vehicle type k can not exceed the capacity of the vehicle type

Because the vehicles can only send with multiples of the capacity of each compartment, then to ease the demand rate in the calculation will be rounded up a number of multiples of 8 with the following limits:

Table 1 tank car fleet size Table

No / Interval Demand Rate (D) / Capacity that is sent(KL)
1 / D 8 / 8
2 / 8 D 16 / 16
3 / 16 D 24 / 24
4 / 24 D 32 / 32
5 / D 32 / 40

Travel expenses are the cost of vehicle fuel use in doing several visits. This fee depends on the distance of nearby vehicles reach the gas station tertntu. This cost can be described as variable cost because the amount is different for each vehicle. The magnitude of the cost of travel on vehicles is calculated in the following way:

where:

= travel costs

ratio= comparison of the fuel consumption of vehicle

The ratio of the fuel needs for each type of vehicle are shown in the table below:

Table 2 ratio of needs of each tank car

Vehicle Capacity / The Ratio Of Fuel Needs
16 KL / 3.2
24 KL / 2.7
32 KL / 2.2
40 KL / 1.8
  1. DISCUSSION

Discussion is performed using an application program that has been created.

Figure 3 screen display Input

Figure 4 Savings Algorithm Calculationdisplay screen

Figure 5 Display Results Using a fleet of 40 KL

Figure 6 Display the results Using a fleet of 24 KL and 16 KL

  1. CONCLUTION

After doing the analysis and creation of application programs above, then it can be summed up as follows:

  1. By using this program, the company will be more wise in use-use fleet-related costs that are required in the process of distribution of fuel to gas stations.
  2. The application of this Program has been tailored to the approach that occur in the field, especially in the field of distribution of fuel type premium.
  3. This application Program can help the process of editing data (specifically for Fleet and User) that is contained in the database so that users no longer need to update data manually in the database. The Program has also been equipped with error message intended to aid the user in performing the action errors.

REFERENCES

Baldacci, R., Battara, M. dan Vigo, D. (2008), “Routing A Heterogeneous Fleet of Vehicle”, dalam The Vehicle Routing Problem: Latest Advances and New Challeges, Operation Research / Computer Sciences Interfaces, eds. Golden, B., Raghavan, S., Wasil, E., Springer Science and Business Media, LLC, New York, hal. 327.

Caccetta, L., Alameen, M. dan Abdul-Niby, M. (2013), “An Improved Clarke and Wright Algorithm to Solve the Capacitated Vehicle Routing Problem”, dalam ETASR - Engineering, Technology & Applied Science Research, Vol. 3, No. 2: 413-415.

Cáceres-Cruz, J., Riera, D., Buil, R. Dan Juan, A. A. (2013), “Applying a savings algorithm for solving a rich vehicle routing problem in a real urban context”, dalam Lecture Notes in Management Science, Vol. 5: 84-92.

Cordeau, J.F., Laporte, G., Savelsbergh, M. W. P. dan Daniele, V. (2007), “Vehicle Routing”, dalam Handbook in Operation Research MS, Vol. 14, eds. Barnhart C, Laporte G., Elsevier.

Deitel, P., & Deitel, H. (2012). C++ How to Program (9th Edition). USA: Pearson Prentice Hall.

Dutta, J. (2004). “Optimization Theory - A Modern face of Applied Mathematics”, dalam International Journal. New Delhi.

El-Sherbeny, N. A. (2010), “Vehicle Routing With Time Windows: On Overview Of Exact, Heuristic, and Metaheuristic Methods”, Journal of King Saud University (Science), Vol. 22, hal. 123-131.

Golden, B.L., Assad, A. A., Levy, L. dan Gheysens, F.G. (1984), “The Fleet Size and Mix Vehicle Routing Problem” dalam Computers and Operation Research, Vol. 11, No. 1, hal. 49-66.

Guo, T., Luo, Q. Data Definition and Data Manipulation With Teradata SQL.

Hansen, D. (2005). Flowcharting Help Page (Tutorial). diakses pada tanggal 22 April 2014

Jorge, N., Wright, S. J. (2006). Numerical Optimization. New York: Springer.

Kiran, M., Cijo, M. dan Jacob, K. (2013). “A Modified Savings Algorithm Based Approach for Vehicle Routing Problem with Simultaneous Pick-up and Delivery” dalam International Journal of Emerging Technology and Advanced Engineering.