Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
1 April 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 87-101 Penyelesaian Vehicle Routing Problem Dengan Algoritma Clarke And Wright Savings Di Perumahan Umum Bulog Medan Amplas Solution of The Vehicle Routing Problem with The Algorithm Clarke and Wright Savings in Bulog General Company Medan Amplas Nurul Aina Universitas Sumatera Utara Email : nurulaina807@gmail.
James Piter Marbun Universitas Sumatera Utara Email : jamespitermarbun@gmail.
Abstract.
Distribution routes are generally a problem for every company, including in the public company BULOG Medan Amplas.
Distribution to the Medan Amplas BULOG public company, namely having to serve every stall that is far from the warehouse with scattered locations, and limited vehicle capacity.
So far, driver considerations in distributing products have only been based on random intuitions of driver and does not consider the efficiency of the route taken.
Therefore, this research uses Clarke and Wright Savings algorithm to obtain optimal mileage by taking into account every consumer demand and vehicle capacity.
Calculation results using the Clarke and Wright Savings Algorithm obtained the vehicle mileage of 695.
08 km with a savings of 11 km or 1.
Keyword: Clarke and Wright Savings Algorithm.
Capacitated Vehicle Routing Problem.
Distribution.
Abstrak.
Rute distribusi umumnya menjadi masalah bagi setiap perusahaan, termasuk di perusahaan umum BULOG Medan Amplas.
pendistribusian pada perum BULOG Medan Amplas yaitu harus melayani setiap warung yang jauh dari gudang dengan lokasi yang tersebar, dan kapasitas kendaraan yang terbatas.
Selama ini pertimbangan pengemudi dalam mendistribusikan produk hanya berdasarkan intuisi acak pengemudi dan dan tidak mempertimbangkan keefisienan rute yang ditempuh.
Oleh karena itu, penelitian ini menggunakan algoritma Clarke and Wright Savings untuk memperoleh jarak tempuh yang optimal dengan memperhatikan setiap permintaan konsumen dan kapasitas Hasil dari perhitungan dengan menggunakan Algoritma Clarke and Wright Savings diperoleh jarak tempuh kendaraan 695,08 km dengan penghematan 11 km atau 1,56%.
Received Febuari 01, 2023.
Revised Maret 02, 2023.
April 01, 2023 * Nurul Aina, nurulaina807@gmail.
Penyelesaian Vehicle Routing Problem Dengan Algoritma Clarke And Wright Savings Di Perumahan Umum Bulog Medan Amplas Kata Kunci: Algoritma Clarke and Wright Savings.
Capacitated Vehicle Routing Problem.
Distribusi.
INTRODUCTION
Distribution is an activity to distribute goods or services from producers to Distribution activities can help producers and companies to spread their products to each region.
So, the more distributors spread across various regions, the more consumers will get their products.
Therefore, the distribution and transportation system must be designed optimally so asto obtain minimum costs and distances.
Perum BULOG is one of the institutions assigned by thegovernment to distribute rice in every e-warong that has been provided by the government.
The problem of distribution at Perum BULOG Medan Amplas is that it has to serve every stall far from the warehouse with scattered locations, and limited vehicle Therefore, it is necessary to determine an efficient distribution route for distributing rice at each e-warong so that the company can obtain optimal mileage by taking into account every consumer demand and vehicle capacity.
This vehicle route problem is included in the VRP (Vehicle Routing Proble.
The Clarke and Wright Savings Algorithm is a method invented by Clarke and Wright in 1964.
This method is published as an algorithm that is used as a solution to the vehicle route problem where a set of routes at each step is exchanged to get a better set of routes, and this method is used to overcome problems that are quite large and the number of routes is large.
LITERATURE REVIEW
Graph The use of graphs in everyday life to describe various kinds of existing The goal is tovisualize objects to make them easier to understand.
A graph is a pair of sets (V.
E) and is written with the notation G = (V.
E).
V is a nonempty set of vertices .
ertices or node.
{ 1, 2.
A , } and E is a set of edges ( edge or arc.
{ 1, 2.
A , pair of vertices (Munir & Rinaldi,2.
JURRIMIPA - VOLUME 2.
NO.
APRIL 2023
} connecting a Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
1 April 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 87-101 Vehicle Routing Problem The Vehicle Routing Problem (VRP) is one of the complex problems of combinatorial optimization, which can be seen as a combination of two problems, namely the Traveling Salesperson Problem (TSP) and the Bin Packing Problem (BPP).
If given a fleet of vehicleswith uniform capacity, general depots, and several customer requests, it will obtain a set of routes with a minimum overall route cost that satisfies all requests (Machado et all, 2.
Capacitated Vehicle Routing Problem The Capacitated Vehicle Routing Problem (CVRP) is the most basic form of VRP.
CPRV is an optimization problem to determine a route with a minimum cost for a number of vehicles with a certain homogeneous capacity .
omogeneous flee.
, which serves a number of customer requests whose demand quantity is known before the delivery process takes place.
CVRP as a directed graph G = (V.
E) where 1, 2.
A , .
is a set of nodes .
, 0 represents the depot and is the pseudo depot of Meanwhile, ={ , ={ 1.
OO .
O } is a set of directed edges which isa set of edges 2.
A , } is a vehicle with a limited capacity, namely Q, so the length of each route is limited by the capacity of the vehicle.
Each node ( , has a distance of 0which is where the vehicle starts and ends the route.
that connect between nodes.
Each node V has a demand of The set
= { 0,
, which is the distance from node i to node j.
The travel distance is assumed to be symmetric, namely = 0 (Caric & Gold,2.
Clarke and Wright Savings Algorithm Clarke and Wright Savings Algorithm is one of the algorithms developed for CVRP problems and is often used.
The purpose of the savings method is to minimize the total distance traveled by all vehicles and indirectly to reduce the number of vehicles needed to serve all stops (Clarke & Wright, 1.
The basis of this saving concept is to combine two routes into one route as shown in Figure 1.
Penyelesaian Vehicle Routing Problem Dengan Algoritma Clarke And Wright Savings Di Perumahan Umum Bulog Medan Amplas Figure 1.
Illustration Of The Concept Of Saving Based on Figure 1.
Customers i and j are visited by separate routes.
To get savings, customers i and j will be visited by the same route, an example is shown in Figure 1.
The route of the vehicle is shown between nodes i and j by the route of the vehicle by in Figure 1.
= 0
The equivalent of the vehicle route 0 0 in Figure 1.
is = 0 By combining the two routes we get the = 0 0 Oe( 0 0 0 Oe Where:
0 = distance from node i to depot 0 = distance from depot to node j = distance from node i to node j = distance saving value from node i to node j The value of savings ( ) is the distance that can be saved if route 0 Oe Oe 0 is combined 0 Oe Oe 0 to become route 0 Oe Oe Oe 0 served by the same vehicle (Octora,2.
The steps for establishing a distribution route using the Clarke and Wright Savings Algorithmare as follows:
JURRIMIPA - VOLUME 2.
NO.
APRIL 2023
Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
1 April 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 87-101 Step 1 Create a distance matrix between depots to customers or between customers to Step 2 Calculate the savings value using the equation 0 0 Oe for each customer and then create a savings matrix.
Step 3 Sort customer pairs based on the value of the largest savings to the smallest.
This step is an iteration of the savings matrix, where if the largest saving value is at points i and j then row i and column j are crossed out, then i and j are combined in one route, and so on until the last iteration.
The iteration will stop when all entries in the rows and columns are selected.
Step 4 Establishment of the first route .
= .
Step 5 Determine the first customer assigned to the route by selecting the customer combination with the largest savings value.
Step 6 Count the number of requests from consumers who have been selected.
If the number of requests still meets the vehicle capacity, then proceed to step 7.
If the number of requests exceeds the vehicle capacity, then proceed to step 8.
Step 7 Select the next customer to be assigned based on the last selected customer combination withthe largest savings value, go back to step 8.
Step 8 Delete the last selected customer, go to step 9.
Step 9 Insert the pre-selected customer to be assigned to the route t formed.
If there are still customers who have not been selected, then proceed to step 10.
If all customers have been assigned, the Clarke and Wright Savings algorithm work process has been Step 10 Formation of a new route .
=t .
Penyelesaian Vehicle Routing Problem Dengan Algoritma Clarke And Wright Savings Di Perumahan Umum Bulog Medan Amplas
RESEARCH METHODS
This research uses data collection techniques with field research and library research to obtain information.
This research was conducted at Perum BULOG Medan Amplas which is located at Jalan Sisingamangaraja km 10.
This research was conducted from March to December 2020.
The research methodology was carried out with the following steps:
Data Collection The data obtained from the company are as follows: a.
The location of depots and customers as well as the amount of rice demanded by each customer.
The number and capacity of the transportation equipment used by the company.
The distribution routes carried out by the company.
Data Processing Finding the optimal route using the Clarke and Wright Savings algorithm: a.
Modeling the Capacitated Vehicle Routing Problem on rice distribution.
Solving the Capacitated Vehicle Routing Problem Using the Clarke and Wright Savings Algorithm.
Create a distance matrix from the depot to the customer and between Create a saving matrix.
Sort the saving value from largest to smallest.
Clustering routes.
Sorting routes using the Nearest Neighbor algorithm.
Analysis and interpretation of results Comparison of Clarke and Wright Savings algorithm routes with company routes.
Conclusions and Suggestions Draw conclusions and suggestions based on the route results obtained using the Clarke and Wright Savings algorithm.
JURRIMIPA - VOLUME 2.
NO.
APRIL 2023
Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
1 April 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 87-101
RESULT AND DISCUSSION
1 Data collection The data obtained are the location of each e-warong, the demand for each e-warong, thecapacity of the vehicle and the number of vehicles.
There are 38 e-warongs in the Medan city area with different requests for each e-warong, where each vehicle is capable of carrying 9.
000 kg of rice.
Table 1.
E-Warong Location Data and Number of Rice Requests (Kilogram.
Name E-Warong E-Warong Doa Bersama E-Warong Serba Setia E-Warong Pelita Harapan E-Warong Bagelen Jaya Abadi E-Warong Tambangan Jaya Bersama E-Warong Platina Raya E-Warong Manggis Bersama E-Warong Asoka Bersama E-Warong Marelan Rengganis E-Warong Marelan Sukses E-Warong Pringgan Bersinar E-Warong Berkah Bersama E-Warong Deli Sejahtera E-Warong Handayani E-Warong Hidup Baru E-Warong Menteng Indah E-Warong Berkah Abadi E-Warong Jaya Bersama E-Warong Labuhan Satu E-Warong Labuhan Dua E-Warong Labuhan Tiga E-Warong Labuhan Empat E-Warong Labuhan Lima E-Warong Mawar Labuhan E-Warong Berkah Labuhan E-Warong Harapan Bersama E-Warong Sumber Rezeki Address Jl.
Merpati No.
Jl.
Sunggal No.
Jl.
Flamboyan Gg.
Inpres Lk II No.
Jl.
Abdul Hamid Lk IV Jl.
Aluminium Lk.
Jl.
Platina Raya Gg.
Masjid Lk.
Jl.
Marelan Raya Gg.
Manggis D Jl.
Marelan IX.
Gg.
Hasan Jl.
Marelan V Gg.
Abadi Lk.
Jl.
Baru Gg.
Klinik Evi Lk.
Jl.
Marelan Gg Pringgan Lk.
Vi Jl.
Titi Pahlawan Gg.
Abu Bakar Lk 5 Jl.
Young Panah Gg.
Kenanga II Pekan Labuhan Jl.
Pasar IV Timur Marelan Jl.
Raya Menteng Gg.
Rahayu No.
Jl.
Menteng VII Gg.
Buntu Jl.
Tangguk Bongkar X Jl.
Denai Gg.
Krio Jl.
Pasar Lama Gg.
Pesantren Lk.
Jl.
Tangguk Damai II No.
125 Lk.
Griya Martubung Jl.
Sei Mati Lk.
Jl.
Chaidir Lk.
Jl.
Syahbuddin Yatim Lk.
Jl.
Lorong I Masjid AsAoSaadah Jl.
Rawe V No.
151 Lk.
Jl.
Perwira II No.
Jl.
Bilal Ujung No.
Penyelesaian Vehicle Routing Problem Dengan Algoritma Clarke And Wright Savings Di Perumahan Umum Bulog Medan Amplas Name E-Warong E-Warong Maju Bersama E-Warong Sehati Belawan I E-Warong Samudra E-Warong Rukun Selalu E-Warong Bahagia Selalu E-Warong Sicanang E-Warong Sapriyan E-Warong Indra Kasih E-Warong Sidorejo E-Warong Tembung E-Warong Bantan Address Jl.
Jawa Belawan Jl.
TM Pahlawan No.
18 Lk.
Xi Jl.
Pulau Seram Lk.
Jl.
Selar Lk.
XIV
Jl.
Sembilang Lk.
XIV
Blok XXI Lk.
VII
Jl.
Hiu No.
1 P1 Lk II.
Belawan Jl.
Karya Bakti No.
Jl.
Sring Gg.
Medung No.
Jl.
Benteng Hulu No.
Jl.
Pertiwi Gg.
Kesuma No.
Data processing Capacitated Vehicle Routing Problem Model on Rice Distribution The CVRP problem on rice distribution is modeled as a graph G = (V.
E).
The set V is a node set consisting of a combination of customer sets C and depots.
V= .
0, v1, v2, v3.
A , v.
where depot is 0 and C = .
1, v2, v3.
A , v.
is e-warong 1 to 38.
The road traversed by the vehicle is expressed as a set of directed edges E, namely the link = {( , )| .
OO ,
between customers.
O }.
K is the set of vehicles used which are homogeneous with a capacity of q.
Unit every i OO C has a request starts from depot 0.
Every customer i for , so that the length of the route is limited by the capacity of the vehicle.
Every .
, .
E has a distance of A route is defined as the cycle cost of the graph G passing through depot 0 so that the total demand from the visited vertices does not exceed the vehicle capacity, where i is the initial customer, j is the destination customer and k is the vehicle.
The decision variables for each k vehicle are defined as follows:
Ea Ea Ea Ea The purpose function of CVRP for rice distribution in BULOG Medan Amplas is as follows:
Min Z= i=0 j=1 k=1 JURRIMIPA - VOLUME 2.
NO.
APRIL 2023
Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
1 April 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 87-101 Obstacles, among others:
Each customer can only be visited exactly once by one vehicle.
= 1.
OA OO
OA OO
OA OO
Each route starts from the depot.
Route continuity means that every vehicle that has finished serving one node will leave Oe Each vehicle carrying goods does not exceed the capacity of the vehicle.
O 900.
OA OO
= 1.
OA OO
Each route ends at the depot.
The decision variable is a binary variable.
Where:
: Customer set : Initial node index : Destination node index : Vehicle index Ckij Xkij OA.
OO ,OA OO
: The distance from the starting node i to the destination node j which is done by vehicle k.
: The decision variable .
ecision variable is a binary variable which identifies node i, node j is performed by vehicle .
: Vehicle capacity at the starting node Xkij OO .
, .
: Binary constraints for the decision variables Penyelesaian Vehicle Routing Problem Dengan Algoritma Clarke And Wright Savings Di Perumahan Umum Bulog Medan Amplas Distance Matrix In this stage the identification process of the distance matrix is carried out, the distance matrix isthe distance between the depot and the customer and between the customer and the customer using kilometers .
with the help of Google Maps.
Table 2.
Distance Matrix
Cij
18 1,6
17 7,9
16 7,5
21 4,1
8,6 11
11 12 13
14 15 .
1,4 0
2,2 2
3,5 3,8
6,2 6,5
5,8 7,2
4 4,3
5,8 8,6
3 3,3
2,4 0
4,9 3,5
6,6 6,3
5 4,7
6,6 8
4,1 2,3
20 5,9 .
3,6 0
2,5 5,9
3 Saving Matrix Saving matrix is obtained by combining two customers in one route.
The following is an example of calculating the saving value for e-warong 1 and 2.
1,2 =
,0 0.
0,2 Oe 1,2 = 20 18 Oe 1,6 1,2 = 36,4 4 Saving Value Ordering The saving values that have been obtained are sorted from the largest to the smallest based on the saving matrix.
The largest saving value is selected then the next iteration crosses out the rows and columns where there is the largest saving value.
The iteration stops when all row and column entries have been selected so that a table of saving values is obtained.
JURRIMIPA - VOLUME 2.
NO.
APRIL 2023
Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
1 April 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 87-101 Table 3.
Order of Saving Values Iteration Saving Value .
66,87 .
Penyelesaian Vehicle Routing Problem Dengan Algoritma Clarke And Wright Savings Di Perumahan Umum Bulog Medan Amplas 3 Route Grouping Based on the order of saving values, customers with the largest to the smallest saving values are grouped into routes by paying attention to demand and vehicle capacity so that a route groupingtable is obtained based on the saving matrix.
Table 4.
Route Grouping Vehicle Route E-warong Request .
JURRIMIPA - VOLUME 2.
NO.
APRIL 2023
Number Of Requests .
Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
1 April 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 87-101 7 Route Sequencing Using Nearest Neighbor Algorithm The routes that have been grouped based on the saving matrix are then sorted using the Nearest Neighbor algorithm.
Thus, the calculation table for the Clarke and Wright Savings algorithm is obtained.
Table 5.
Clarke and Wright Savings Algorithm Route Route to- Travel Order Number of Requests .
Mileage .
0 Ae 30 Ae 13 Ae 22 Ae 33 Ae 0
0 Ae 29 Ae 31 Ae 32 Ae 34 Ae 0
67,93
0 Ae 11 Ae 19 Ae 28 Ae 0
0 Ae 23 Ae 12 Ae 21 Ae 10 Ae 0
0 Ae 9 Ae 14 Ae 0
0Ae6Ae7Ae8Ae0
0 Ae 26 Ae 25 Ae 20 Ae 24 Ae 0
0Ae5Ae0
0 Ae 36 Ae 27 Ae 1 Ae 0
0Ae4Ae0
0 Ae 18 Ae 37 Ae 38 Ae 2 Ae 0
47,95
0 Ae 16 Ae 15 Ae 17 Ae 35 Ae 3 Ae 0
695,08
Total
Penyelesaian Vehicle Routing Problem Dengan Algoritma Clarke And Wright Savings Di Perumahan Umum Bulog Medan Amplas
CONSLUSION
Based on the previous description and discussion, several conclusions were obtained, namely:
The results in this study obtained a comparison of rice delivery routes at Perum BULOG Medan Amplas, which was 706.
08 km with a total demand of 9,800 kg and 12 routes,while using the Clarke and Wright Savings algorithm the distance was 695.
08 km with a total demand of 9,800 kg and 12 routes.
This algorithm is able to provide mileage savings of 11 km or 1.
This shows that the Clarke and Wright savings algorithm can reduce the distance traveled and at the same time the cost of distributing rice.
REFFERENCES
Braysy OB.
Gendreau M, 2005.
Vehicle Routing Problem with Time Windows.
Part I: Route Construction and Local Search Algorithms.
Transportation Science, 39: 104-118.
Chopra S dan Peter M, 2010.
Supply Chain Management: Strategy.
Planning and Operation.
Pearson Education.
New Jersey: Prentice Hall.
Clarke G.
Wright JW, 1964.
Scheduling of Vehicles from a Central Depot to a Number ofDelivery Points.
Operations Research, 12.
: 568-581.
Dreo.
Petrowsky.
Siarry.
Taillard.
Meta Ae Heuriustic for Hard Optimization: Methods and case studies.
Berlin: Springer Ernawati D.
Raharjo H.
Aryani E, 2015.
Minimalisasi Biaya Distribusi Kayu dengan Metode Clarke and Wright Savings Heuristic (Studi Kasus: CV Sumber Jaya Gresi.
Jurnal Tekmapro, 10.
: 46-56.
Foulds.
LR 1984.
Combinatorial Optimization for Undergraduates.
New York:
Springer-Verlag.
Inc.
Gunawan P, 2012.
Enhanced Nearest Neighbors Algorithm for Design of Water Network.
Chemical Engineering Science, 84: 197-206.
Iskandar.
Model Optimasi Vehicle Routing Problem dan Implementasinya.
TesisInstitut Pertanian Bogor.
Jong Jek Siang.
Matematika Diskrit dan Aplikasinya pada Ilmu Komputer.
Yogyakarta: ANDI.
Li F.
Golden B.
Wasil E, 2005.
Very large-scala vehicle routing: new test problem, algorithm, and results.
Computer and Operation Research 32.
: hal.
JURRIMIPA - VOLUME 2.
NO.
APRIL 2023
Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
1 April 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 87-101 Machado P.
Tavares J.
Pereira FB, dan Costa E, 2002.
Vehichel routing problem:Doing itevolutionry way.
Proceeding of GECCO.
Mittal.
Garg.
Ambashta.
H dan Mehndiratta.
Chanranjeev.
Solving VRP in an Indian Transportation Firm through Clarke and Wright Algorithm: A Case Study.
International Journal of Emerging Technologies in Engineering Research (IJETER) Vol.
Issue 10: 163 -168.
Munir.
Rinaldi.
Matematika Diskrit.
Bandung: Informatika Bandung.
Octora.
Pembentukan Rute Distribusi Menggunakan Algoritma Clarke and Wright Savings dan Algoritma Sequential Insertion.
Jurnal Institut Teknologi Nasional.
Bandung, 2.
Pertiwi PP.
Iriani.
Ariyni E.
Penentuan Distribusi Produk dengan Metode Algoritma Clarke and Wright Saving Heuristic untuk Meminimumkan Biaya Distribusi di PT.
Jurnal Manajemen Industri dan Teknologi.
: 2433.
Pop PC, et al.
Heuristic algorithms for solving the generalized vehicle routing problem.
International Journal of Computers Communicationsand Control 6.
: 158-165.
Roberto Cantu-Funes, et al.
Multi Depot Periodic Vehicle Routing Problem with Due Dates and Time Windows.
Journal of the Opertional Research Society, 62.
: 296- 306.
Taha.
HA.
Operations Research: An Introduction.
Ed Ke-8.
Pearson EducationInternational.
Singapore Tonci Caric.
Hrvoje Gold.
Vehicle Routing Problem.
University of Zagreb :
In-tehCroatia.
Toth dan Vigo.
2002 Vehicle Routing Problem.
Bologna: Universitas Degli Studi.