JKIE (Journal Knowledge Industrial Engineerin.
Vol.
No.
August 2022, pp.
http://jurnal.
id/v2/index.
php/jkie Journal Knowledge Industrial Engineering E-ISSN: 2541-4461
P-ISSN: 2460-0113
Determining the Optimal Rice Distribution Route in Medan City Using Dijkstra's Algorithm a,b,c Anita Christine Sembiringa.
Jasonb.
Vivianac Department of Industrial Engineering.
Universitas Prima Indonesia.
Indonesia Corresponding Autor: Jasonwang200004@gmail.
Article Info Article history Received : June 17, 2022 Revised : July 22, 2022 Accepted : August 12, 2022 Published : August 30, 2022 Keywords:
Algoritma Dijkstra.
Distribution.
Shortest route.
Node.
Open Accsess license CC-BY-SA
ABSTRACT
Distribution is an activity carried out to spread the product throughout the market so that consumers can buy it.
Distribution can also affect the price of goods.
Therefore, the distribution must be effective.
The purpose of this study is to determine the shortest route that is effective in distribution so that product prices are not high and the company does not suffer losses.
The data analysis method used is Dijkstra's Algorithm obtained with data on the distance between the starting point and the destination point through predetermined points.
The calculation results show that the shortest and fastest routes to be taken based on the dijkstra algorithm are: A-20-19-F-26-C-D-11-12-B-E with a distance 71 km.
There are several road routes that can be chosen to be used but the shortest route that can be taken is 40.
71 km.
Medan Rice Distributors are expected to choose the shortest transportation route so that rice distribution can be carried out quickly and optimally.
DOI: https://doi.
org/10.
35891/v9i2.
Introduction Distribution is a familiar term in the world of economics.
Because distribution is an important part of the world economy.
Therefore, the problem of distribution of goods is one of the important aspects that need to be considered by every freight forwarding company.
The occurrence of distribution constraints can even cause losses to the company or producer.
With distribution, the production will reach consumers who are located quite far away.
Therefore, the distribution must use the optimal route, but not all companies use the method in dealing with the problem of the optimal distribution route.
be able to choose the optimal route, it is necessary to know the distance between the destinations.
Then the optimal path is chosen from the starting point to the destination point.
But this is often not helpful because of the large number of roads that exist, resulting in many choices of routes that can be taken.
Because it must be selective in choosing a short and efficient path, not tortuous, can save time and costs.
And not only that, a good distribution must also determine the utility/vehicle to be used.
For that, we need an algorithm that is able to handle the problem of finding a route that is able to handle the problem of finding the shortest route.
Such as the distribution of rice carried out at the Medan City Rice Distributor.
The company has several distribution points in the city of Medan.
Distribution is carried out from the Medan City Rice Distributor to several supermarkets as distribution points.
Distribution is carried out at different locations so that a travel route is needed from one delivery location to another.
The route used by the - 82 - P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Medan City Rice Distributor is still done manually without regard to distance or other routes that might be the shortest route.
This is a deficiency in the distribution route determination system.
To determine the shortest route optimally, the method can be used.
There are many algorithms that can solve this problem, including the Dijkstra algorithm, the Floyd-Warshall algorithm, and the Bellman-Ford From the explanation above regarding the importance of implementing distribution in a company and seeing the many methods that can solve these problems, the researchers consider it necessary to review the distribution problem at the Medan City Rice Distributor.
For this reason, in writing this final project, the researcher is interested in taking the title of "determination of the shortest route for transporting field rice using the dijkstra algorithm method.
Literature Review Distribution Distribution is a marketing activity that seeks to facilitate and facilitate the delivery of products and services from producers to consumers so that their use is appropriate .
ype, quantity, price, and plac.
as needed.
The most effective distribution will facilitate the flow or access of goods by consumers so that they can be obtained easily.
In addition, consumers will also get goods in accordance with what is needed.
Basically the distribution function is segmenting, determining the mode of transportation used, scheduling and determining routes, adding value services, storing inventory, and handling In general, distribution systems can be divided into two types, namely: direct distribution systems and indirect distribution systems.
Direct distribution systems distribute goods directly from producers to consumers.
The distribution system does not directly use an intermediary .
so that it does not directly meet consumers.
Shortest Path The shortest path is the minimum path required to reach a place from a certain place.
The minimum path in question can be found by using a graph.
A graph is a set of points in a two-dimensional plane connected by a set of edges.
A graph is formed from a set of vertices connected by edges.
There are several terms related to graphs, including:
C These points are called vertices.
C The lines connecting the vertices are called edges.
C Adjacent means neighbor.
That is, if there are two vertices called adjacent, if they have the same C Paths are paths that pass through edges and vertices in a graph.
C A cycle is a path that starts and ends at the same vertex.
C Direct on a directed graph where the edges have a direction.
The graphs used are weighted graphs, namely graphs in which each edge is assigned a value.
There are several kinds of shortest path problems (Mukti et a.
, 2.
, including:
C The shortest path between two specific vertices .
pair shortest pat.
C The shortest path between all pairs of vertices .
ll pairs shortest pat.
C The shortest path from a certain vertex to all other vertices .
ingle source shortest pat.
C The shortest path between two vertices that pass through certain vertices .
ntermediate shortest pat.
In determining the shortest route, these locations form a graph.
The steps are as follows (Nawagusti, 2.
C Combine each vertex of each route into a connected graph.
C Give the direction of travel on the route as a flow so that a directed graph is formed from the existing connected graph.
C Data from the mileage obtained is converted into the weight of the distance.
Apply the distance weights as a directed graph load flow so as to form a weighted graph.
- 83 -
P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Application of Dijkstra's Algorithm Dijkstra's algorithm is an algorithm used to solve the shortest path problem for a directed graph.
Look at the graph below.
A person wants to travel from city s .
to city t .
There are several alternative routes that can be traversed, namely through city 1 or city 2 or city 3 and then city t Gambar 2.
1 Graf Rute Figure 1: Route Graph If the numbers on the arc of the graph indicate the distance between two cities connected by the respective road segment, find the shortest path that can be taken from city s to city t.
The shortest path problem can be solved by Dijkstra's algorithm.
According to this algorithm, each node is marked, for example, marked with an X and not marked with an X.
If a node is found to be part of the shortest path, then the node and arc leading to that node are marked with an X.
This algorithm consists of a three-step procedure that done repeatedly to find the shortest distance starting from the initial node s gradually to the node t.
Suppose that from node s there are m nearby nodes that can be selected when departing from s.
Since there are m nodes in front of node s, there are m routes to choose from when departing from s.
Choose the shortest route m of these routes.
Suppose that for the moment this selected route is the shortest route from s to y.
Put an X on the node s and arc .
Now determine which node is the .
th node closest to node s? The closest .
node to node s is a node that has not been marked with an X, that is, a node that is temporarily considered to have the shortest route from node s to node .
must use or traverse the node that has been marked X as a among node.
If the m nodes closest to node s are known, the node to .
can be searched in the manner described above, starting from m=0.
The process is repeated until the shortest route from s to t has been For further explanation.
Dijkstra's algorithm can be described in the following steps:
Step 1: First of all, all nodes and arcs are not marked with X.
Number d.
for each node to indicate the length of the shortest route from node s to node x.
Step 2: For each node x that has not been marked with an X, determine d.
as follows:
= Min .
, d.
} If d.
= O for all x that is not marked X then the iteration is stopped because there is no route from s to any node that has not been marked with the X.
If d.
O O then put an X on the node x which has the smallest d.
Also color the arc that goes directly to the x node from the colored node where the d.
minimum was found, for example y=x.
Step 3: If node t has been marked with X, the iteration process is stopped because all the shortest routes from s to t have been found.
If node t has not been marked with an X, go back to step 2 Methodology The type of research used in this research is descriptive research.
This is because this study describes a problem that exists and then provides a proposal as the final result and conclusion.
The location where the research was conducted is in the city of Medan with the starting point being at the Rice Distributor in Medan City, which is located at Jl.
Sei Snake Baru.
Babura Sunggal.
Kec.
Medan Sunggal.
Medan City.
North Sumatra.
The object observed in this study is the route data and the system used in determining the fastest route - 84 - P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Start Initial identification C Identification of problems C Previous research C Literature review Data collection C Request received C Mileage used C Available vehicles Enough data Yes Calculation with dijkstra algorithm C precise and efficient route and vehicle Finish Figure 1.
research flow chart Results and Discussion Based on research using the dijkstra algorithm, the following data is needed:
The company studied was only 1 rice distributor.
The locations studied were only those in the city of Medan.
The data provided is the location points and the distance between the points based on Google Maps.
Figure 2.
Medan Rice Distributors The nodes are the location of crossroads, small shops, places to eat and also shops that sell services.
The entered nodes are then numbered along with letters to make it easier to identify the location on the graph.
- 85 -
P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Figure 3.
Graph of Rice Transport Node Distribution Node Node Location Tabel 1.
Node Location Names Node Node Location Merdeka Walk Medan Rice Distributor Lotte Mart Center Point Hydraulic Dorsmer Warunkkitta J&T Express Darussalam JR11 Barbershop Richeese Factory Domino's Pizza Brastagi Supermarket Gatot Subroto Babar Teak Chicken Noodles Baby Milano Photography Carrefour Transmart Fountain Monument WS Jaya Service HM Yamin Crossroads ATM Mandiri Graha Brastagi Tiara Supermarket RA Kartini T-junction Sudirman T-junction Private Broadcasting Radio Association Indonesian Islamic Bank Maruso Boutique T-junction Dr.
Manyur Medan University Area Benz Mobile Muslim Captain's Crossroads Medan Petisah District Office Lottemart Sun Plaza Alphamart Convenience Store Philips Electronics Merdeka Walk The route modeling that is the subject of the study is to make an algorithmic calculation from node A which is the Medan Rice Distributor as the initial location for reading to several nodes as the destination for rice distribution, namely node B, node C, node D, node E and node F.
From the results of the calculation With these results, one shortest route will be generated that will pass through node B, node C, node D, node E and node F so that rice can be distributed faster and does not take longer.
Due to the nature of Dijkstra, which is greedy, where the calculation process is imposed on all existing nodes, for ease of calculation of this rice transportation route, a Bounding Box is used, namely by selecting only certain nodes in the same direction where the node is most likely to be traversed or passed in one direction.
reading route.
This makes Dijkstra's calculations faster and more For example, for the transportation route from node A to node F, the nodes included in the bounding box are node 2, node 3, node 4, node 5, node 19, node 20, node 26 and node F.
For transport routes from node A to node C, the nodes included in the bounding box are node 2, node 3, node 4, node 5, node 6, node 20, node 26 and node C.
In this calculation, it is necessary to determine the shortest route from node A to node closest.
There are two closest nodes from A, namely node C and node, it is necessary to calculate the route from node A to node C and node A to node respectively.
The calculation of Dijkstra's algorithm from point A to point F is as follows:
- 86 -
P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Figure 4.
Graph of Rice Transport Node Distribution Put an X on node A, and d(A)=0, d.
=O for the whole x O A d.
= Min .
, d(A) a(A,.
} = Min {O, .
} = 4.
= Min .
, d(A) a(A,.
} = Min {O, .
} = 3.
= Min .
, d(A) a(A,.
} = Min {O, .
} = 4.
Since d.
= 3.
55 is the smallest of all nodes 20 and arc(A,.
are marked with arrows.
The shortest route is from node A to node 20.
Node F has not been marked with an X so go back to step 2.
Figure 5.
Graph of Rice Transport Node Distribution step 1 y=20 d.
= Min .
, d.
} = Min {O, .
} = 7.
= Min .
, d.
} = Min {O, .
} = 8.
= Min .
, d.
} = Min {O, .
} = 6.
= Min .
, d.
} = Min .
38, .
55 O)} = 4.
Since d.
= 4.
38 is the smallest of all, node 1 is marked with an X and arc(A,.
is marked with an arrow.
Node F has not been marked with an X so go back to step 2.
- 87 -
P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Figure 6.
Graph of Rice Transport Node Distribution step 2 d.
= Min .
, d.
} = Min {O, .
} = 8.
= Min .
, d.
} = Min {O, .
} = 8.
Since d.
= 8.
26 is the smallest of all, node 4 is marked with an X and arc.
is marked with an arrow.
Node F has not been marked with an X so go back to step 2.
Figure 7.
Graph of Rice Transport Node Distribution step 3 d.
= Min .
, d.
} = Min {O, .
} = 11.
= Min .
, d.
} = Min {O, .
} = 10.
Since d.
= 10.
60 is the smallest of all, node 5 is marked with an X and arc.
is marked with an arrow.
Node F has not been marked with an X so go back to step 2.
- 88 -
P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Figure 8.
Graph of Rice Transport Node Distribution step 4 d.
= Min .
, d.
} = Min {O, .
} = 14.
= Min .
, d.
} = Min .
60, .
} = 8.
Since d.
= 8.
60 is the smallest of all, node 2 is marked with an X and arc.
is marked with an arrow.
However, node 2 is only connected to node 5.
So put an X on node 5 and an arrow on arc.
And y=5 is calculated again, so d.
=12.
34 is the smallest, then it is marked X at node 26 and arc.
is marked X.
Node F has not been marked with an X so go back to step 2.
Figure 9.
Graph of Rice Transport Node Distribution step 5 y=26 d(F) = Min .
(F), d.
,F)} = Min {O, .
} = 16.
= Min .
, d.
} = Min .
55, .
} = 3.
= 3.
55 is the smallest of all.
Node F has not been marked X so go back to step 2.
y=20 d.
= Min .
, d.
} = Min .
34, .
} = 8.
= Min .
, d.
} = Min {O, .
} = 6.
Since d.
= 6.
56 is the smallest of all, node 5 is marked with an X and arc.
is marked with an arrow.
Node F has not been marked with an X so go back to step 2.
- 89 -
P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Figure 10.
Graph of Rice Transport Node Distribution step 6 y=19 d(F) = Min .
(F), d.
,F)} = Min {O, .
} = 10.
It has been obtained that d(F) = 10.
65 is the shortest route, then it is marked with an X at node F and an arrow is given to arc.
,F).
The final result is that the shortest route from node A to node F is A-20-19-F.
Figure 11.
Graph of Rice Transport Node Distribution step 7 The calculation of Dijkstra's algorithm from point A to point C is as follows:
Figure 12.
Graph of Rice Transport Node Distribution - 90 - P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Put an X on node A, and d(A)=0, d.
=O for the whole x O A d.
= Min .
, d(A) a(A,.
} = Min {O, .
} = 4.
= Min .
, d(A) a(A,.
} = Min {O, .
} = 3.
= Min .
, d(A) a(A,.
} = Min {O, .
} = 4.
Since d.
= 3.
55 is the smallest of all nodes 20 and arc(A,.
are marked with arrows.
The shortest route temporarily is from node A to node 20.
Node F has not been marked with an X so go back to step 2.
Figure 13.
Graph of Rice Transport Node Distribution y=20 d.
= Min .
, d.
} = Min {O, .
} = 7.
= Min .
, d.
} = Min {O, .
} = 8.
= Min .
, d.
} = Min {O, .
} = 6.
= Min .
, d.
} = Min .
38, .
55 O)} = 4.
Since d.
= 4.
38 is the smallest of all, node 1 is marked with an X and arc(A,.
is marked with an arrow.
Node F has not been marked with an X so go back to step 2.
Figure 14.
Graph of Rice Transport Node Distribution d.
= Min .
, d.
} = Min {O, .
} = 8.
= Min .
, d.
} = Min {O, .
} = 8.
Since d.
= 8.
26 is the smallest of all, node 4 is marked with an X and arc.
is marked with an arrow.
Node F has not been marked X so go back to step 2.
- 91 -
P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 diberi tanda X maka kembali ke langkah 2.
DOI:
https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Figure 15.
Graph of Rice Transport Node Distribution d.
= Min .
, d.
} = Min {O, .
} = 11.
= Min .
, d.
} = Min {O, .
} = 10.
Since d.
= 10.
60 is the smallest of all, node 5 is marked with an X and arc.
is marked with an arrow.
Node F has not been marked X so go back to step 2.
Figure 16.
Graph of Rice Transport Node Distribution d.
= Min .
, d.
} = Min {O, .
} = 14.
= Min .
, d.
} = Min .
,60, .
} = 8.
So now value d.
= 8.
= Min .
, d.
} = Min {O,.
} = 12.
Since d.
= 8.
60 is the smallest of all, node 2 is marked with an X and arc.
is marked with an arrow.
However, node 2 is only connected to node 5.
So put an arrow on arc.
And y=5 is calculated again d.
= Min .
, d.
} = Min .
} = 10.
then now d.
= Min .
, d.
} = Min .
} = 12.
then marked X at node 6 and arc.
marked X.
- 92 -
P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
Figure 17.
Graph of Rice Transport Node Distribution d(C) = Min .
(C), d.
,C)} = Min {O, .
} = 16.
It has been obtained that d(C) = 16.
43 is the shortest route, so it is marked with an X at node F and an arrow is given to arc .
,C).
The final result is that the shortest route from node A to node F is A-1-4-5-6-C.
Figure 18.
Graph of Rice Transport Node Distribution Obtained d(F) = 10.
65 and d(C) = 16.
43, then the shortest route to be used is from node A to node F, namely A-20-19-F with a distance of 10.
The shortest route from node F to node C = F-26-C is 3.
58 = 6.
Shortest route from node C to node D = 4.
Shortest route from node D to node B = D-11-12-B = 1.
77 = 11.
Shortest route from node B to node E = 4.
33 = 8.
Then the shortest route that can be passed is A-20-19-F-26-C-D-11-12-B-E with a distance of 65 6.
10 = 40.
Conclusion Based on the analysis and calculation results, conclusions are obtained.
This study uses the Dijkstra algorithm to determine the shortest route from the Medan City Distributor to several supermarket locations.
The calculation results show that the shortest and fastest routes to be taken based on the dijkstra algorithm are: A-20-19-F-26-C-D-11-12-B-E with a distance of 40.
71 km.
Medan Rice Distributors are expected to choose the shortest transportation route so that rice distribution can be carried out quickly and optimally.
The Medan Rice Distributor is expected to coordinate with drivers who drive rice transportation vehicles regarding the shortest route to be taken so that the rice distribution process can be carried out optimally and on time.
- 93 -
P-ISSN: 2460-0113 I JKIE (Journal Knowledge Industrial Engineerin.
I E-ISSN: 2541-4461 DOI: https://doi.
org/10.
35891/jkie.
3288 I Vol.
No.
August 2022, pp.
References