Contribution to the Improvement of the Petroleum Products Delivery Policy by the Implementation of a Computer System Based on the Dijkstra Method ()
1. Introduction
The Democratic Republic of Congo is a member of the Organization of Petroleum Exporting Countries (OPEC), among the 4 segments of the petroleum chain namely: petroleum exploration, production, refining and distribution [1] but it is the latter which is active in the society since it is called to produce energy for production purposes at all levels of the society. To this end, it must distribute petroleum products such as gasoline, Kerzone, fuel oil, asphalt and many others [2]. As far as the VP of Kinshasa is concerned, the demographic growth, the hazards of the electric current supply have increased the demand, the state of the roads and other hassles related to the road traffic make difficult the task of distribution of these petroleum products in the 24 communes.
In the Democratic Republic of Congo, the distribution segment is managed by the dispatching service of the SEP-Congo company. From our visits, we realized that this dispatching service is experiencing difficulties in this area, including the manual elaboration of the delivery routes of the orders by tanker trucks. The control of the different routes to optimize the trajectories of the tanker trucks to save time and fuel [3].
The state of the roads and the different radii of curvature of these roads do not facilitate access to the different service stations. As SEP-Congo, has a computer unit it can bring improvements in the distribution sectors if it is provided with the means assigned in the oil logistics. In this study, we propose to implement a computer system of the policy of delivery of petroleum products in the town of Lemba based on the method of Dijkstra [4].
2. Presentation of the Study Environment
The Commune of Lemba is one of the 24 Communes of the City Province of Kinshasa in the district of Mont-Amba. It originates from a village called LEMBA MAWA. It is towards the years 1959, before the independence, that the Commune of Lemba was born. It was called LEMBA MAWA and its boundaries corresponded to those of the current Lemba foire district [5]. The municipality of Lemba is limited to the east by the municipalities of Matete and Kisenso; by the MATETE river, from the axis of the LUMUMBA boulevard until downstream of its source, a straight line of the valley and the extension of the ravine on the KISANTU avenue until the KWAMBILA river in the north by the commune of LIMETE, from LUMUMBA boulevard and the axis of the inner circle of the interchange, KIKWIT avenue, passing in front of the international fair of KINSHASA (FIKIN) up to the MUNGULU DIAKA bridge over the YOLO riverIn the west by the commune of MONT-NGAFULA, which goes from the bifurcation of the avenue by pass and the road KIMWENZA to the triangle until the height of the source of the river MANIONSI in the south by the commune of MONT-NGAFULA, at the height of the plateau of the residents of the professors of UNIKIN in its whole, the commune of LEMBA is bathed by only one watercourse to know; the river KALAMU, which separates the commune of LEMBA and that of matete [6]. The commune of Lemba has 14 districts, including the district of the teachers’ plateau, located within the precincts of the University of Kinshasa and two camps. The districts are the following: ECHANGEUR, ECOLE, FOIRE, COMMERCIALE, MANDRANDELE, MASANO, KIMWENZA, GOMBELE, MOLO, SALONGO, KEMI (RHIGINI), LIVULU, MBANZA-LEMBA and the PLATEAU DES PROFESSEURS (Table 1).
3. Literature Review
In the distribution segment in the distribution segment, petroleum logic covers all the means used to distribute petroleum products from the refinery to the end consumer [7]. The aim of petroleum logic is to serve operations while preserving the interests of the companies, by optimizing time, quantities and costs in compliance with internal and international rules [8]. It is therefore reduced to a problem of industrial engineering which results in the development of a software with a mapping system that allows the dispatching service to direct the tanker trucks to the shortest routes to reach the service stations [9]. The same logic also aims at reaching the customer in a timely manner and having in stock the operational products and those in stock [10] such a distribution process represented in Figure 1.
The graph theory allows to solve this problem of finding the shortest transport path [11]. The improvement of the delivery policy will result from the constriction of the computer system to be operated by the dispatching service [12]. The Dijkstra algorithm is used to calculate the shortest path between a particular vertex and all others. The computations are performed using a gluttonous technique and lead to the least observed execution time [13]. Divert solve all one-to-all problems. NS. Between a set of origin and destination nodes (if the latter can be reached) [14]. Moreover, this algorithm can be easily adapted to one-to-one problems (problem limited to the calculation of the origin and destination routes). To do so,
![]()
Figure 1. Logical segment from production to consumption of petroleum products [11].
![]()
Table 1. Distribution of service stations by neighborhood.
simply add a stop test when reaching the target node. The complexity of the algorithm is defined when the data structure used is an adjacency list [15]. The complexity of the algorithm is as follows: Initialization is done at O (N), and vertex x is searched every N major iterations. The smallest label (lines 6 - 10) occurs at O (N) and the following paths occur at O (d + (x)) [10].
4. Materials and Methods
4.1. Materials
The equipment used in this study includes: GPS brand G Mouse Mini R5232 SIRF: 1, YEDGraph Editor online platform: 1 computer brand LENOVO, processor DUAL CORE, hard drive 500 Giga Octect, RAM memory 4 Giga Octet, Windows 10 operating system with Netbeans software version 8.1.
4.2. Methods
The survey method consists in identifying the delivery points of the products (gas stations), then using the graph theory applied to the distribution of petroleum products to implement our algorithm [14].
Collecting the geographical coordinates of the service stations with the help of GPS.
We realized the network of the service stations of the commune of Lemba by using the platform on line YEDGraph Editor [15].
Realize the computer system of the commune of Lemba by exploiting the algorithm of Dijisktra to find the shortest path between any two of these stations.
In this context we used the UML language for the design and the JAVA language for the implementation with the Netbeans software.
With the help of the obtained system we can realize any kind of work (Figure 2).
Gives us the main window of our project, to use the application is first launch the application from the icon, then when a starting point (which can be the SEP CONGO, a station or another place where the tanker is parked) is entered in the software, then enter in the software a point of arrival (arrival station or delivery of product), then applied the algorithm by clicking on the point of the map, the system will provide even the distance to travel as well as the shortest path [16].
5. Results
We used the Dijkstra algorithm to find the tree of the shortest path of the graph that constitutes the mapping of gas station through the commune of Lemba here represent by the letter in capital letter, following, the management of roads that corresponds to a graph G = (X, E, v) corresponding to the road network, where the vertices are the hot spots of the commune [10]. The graph corresponds to the road network of the commune of Lemba, the problem consists in calculating the most economic routes from a point of the commune, it is thus a problem of shortest ways of a top towards all the other tops [11], the criterion to be minimized is the monetary cost of the ways in consumption of time and oil products (Figure 3).
![]()
Figure 3. Planar graph of service stations [12].
The computer presentation of a graph is done by an adjacency matrix or list. an adjacency matrix Table 2 of the weighted and oriented graph G(V, E) in Figure 2, is the matrix M(G) Є M n(R) whose coefficients m i, j (Table 2) [13].
Construction of a shortest path from the adjacency matrix, the procedure to follow is first at each step the graph is partitioned into three subsets of vertices [14]:
The visited vertices, VV, vertex x for which we know definitively the shortest distance from A to x, the reached vertices AA, unvisited vertices, the neighbours of the previous ones, for which we have an estimation of the distance, and the others, i.e. those of X-(VV U AA), for which the distance is infinite [15].
Initially VV contains A, AA contains its neighbors, B, C, D, G and H, their estimated distances correspond to the evaluations of the corresponding edges, i.e. 8, 6, 5, 6 and 15 and the other vertices have infinite distance [16].
Step take AA one of the vertices x whose estimated distance is the smallest.
Initial step: VV = {A}, d(A) = 0, AA = = {B, C, D, G, H}(these are the neighbors of A) with d(B) = 8, d(C) = 6, d(D) = 5, d(G) = 6, d(H) = 15 and p(B) = d(C) = p(D) = p(G) = p(H) = A, all the other vertices have an infinite distance and their predecessors are at 0.
Step 1: D is chosen so VV = {A, D} and its (final) distance is d(D) = 5, AA = = {B, C, E, G, H}, d(B) = 8, d(C) = 6, d(D) = 5, d(G) = 6, d(H) = 15 and p(B) = d(C) = p(D) = p(G) = p(H) = A and p(E) = D, the other vertices have an infinite distance and are without any predecessor. In the following, we will not mention these vertices anymore, only the vertices of VV and AA will be mentioned.
Step 2: C is chosen, G could have been chosen instead, so VV = {A, C, D} and its distance d(C) = 6, AA = = {B, E, G, H}, d(B) = 8, d(E) = 11, d(G) = 6, and d(H) = 14, and p(B) = p(G) = A, p(E) = D, and p(H) = C.
Step 3: G is chosen, so VV = {A, C, D, G} and its distance d(C) = 6, AA = = {B, E, F, H}, d(B) = 8, d(E) = 11, d(F) = 18, and d(H) = 14 and p(B) = A, p(E) = D and p(F) = G and p(H) = C.
Step 4: B is chosen, we could have chosen C, so VV = {A, B, C, D, G} and its distance d(B) = 8, AA = = {E, F, H}, d(E) = 11, d(F) = 16, and d(H) = 14 and p(E) = D, p(F) = B and p(H) = C.
Step 5: E is chosen so VV = {A, B, C, D, E, G} and its distance d(E) = 11, AA = = {E, H}, d(F) = 16, d(H) = 14, p(F) = B and p(H) = C.
Step 6: H is chosen so VV = {A, B, C, D, E, G, H} and its distance d(H) = 14, AA = = {F}, d(F) = 16, p(F) = B.
Step 7: (because at the end of this step all vertices are visited): F is chosen so VV = {A, B, C, D, E, G, H} and its distance d(F) = 16, p(F) = B.
The partial graph corresponding to the shortest paths is obtained using the table of predecessors, this gives the following graph (Figure 4).
![]()
Table 2. Adjacency matrix on distance distribution between two gas stations.
![]()
Figure 4. Planar graph of the shortest path obtained after applying Dijkstra’s algorithm starting from the station represented by A [16].
6. Discussion
The algorithm of search of path in a graph which is faster and often gives good paths and exactly the shortest path in any situation as an example by using our software if for example a vehicle of SEP Congo is in the COBIL of the General Management towards the University of Kinshasa, having received two orders at the same time from the General Management the first is to deliver the service station of Super LEMBA and that of the Interchange whose distance between the IG of the ESU to Super LEMBA is equivalent to nearly 5 km and that of the IG to the station of the Interchange is equivalent to nearly 6 km, by using our platform based on the algorithm of Dijkstra it can easily choose the service station to be served in first. In case, the tanker of SEP Congo is located at the roundabout super Lemba to serve two stations that of LEMBA FIKIN and Echangeur the tool is also essential for this case.
7. Conclusion
The main contribution of our contribution was to set up a computer system based on an operational research algorithm in order to solve a transport problem that arises in the city of Kinshasa because the state of our roads is generally impassable, the construction of this computer system is to find an optimal path for the SEP Congo in the distribution of tanker trucks to supply the service stations which should necessarily improve the policy of delivery of petroleum products to service stations. But there was also the problem related to the petroleum logistics and the effective motivation of the agents to wait for the objectives desired by our contribution. The results are interesting because this project is going to help most of the services working in the distribution of petroleum products as well as to the researchers for the advancement of the sciences in this field.