=Paper=
{{Paper
|id=Vol-2274/paper-04
|storemode=property
|title=Comparative Analysis of Multi-agent Approaches for Planning Fuel Delivery of Petrol Stations
|pdfUrl=https://ceur-ws.org/Vol-2274/paper-04.pdf
|volume=Vol-2274
|authors=Hambardzum L. Ayvazyan,Olga P. Aksyonova
}}
==Comparative Analysis of Multi-agent Approaches for Planning Fuel Delivery of Petrol Stations==
https://ceur-ws.org/Vol-2274/paper-04.pdf
Comparative Analysis of Multi-agent
Approaches for Planning Fuel Delivery of Petrol
Stations
Hambardzum L. Ayvazyan1,2 and Olga P. Aksyonova1
1
Ural Federal University by the first President of Russia B.N. Yeltsin, 620002
Ekaterinburg, Russia,
bpsim.dss@gmail.com
2
Yerevan State University, 0025 Yerevan, Armenia,
hambardzum.ayvazyan@gmail.com
Abstract. This work describes results of development of a intelligent
petrol supplies planning system. Analysis of transportation problem was
implemented. For solving the transportation problem of petrol station
the network was suggested to integrate some methods and approaches
(transportation algorithm, multi-agent approach, and simulation mod-
eling). Comparative analysis of the multi-agent approaches for planning
the fuel delivery of petrol stations was done. Supposed method of deci-
sion making for supplies scheduling problem and intelligent system are
currently using on petrol stations network in the city of Ekaterinburg
and Sverdlovsk Region.
Keywords: modeling, simulation modeling, multi-agent modeling, trans-
portation problem
1 Introduction
Adequate mathematical models of most problems of the effective and optimal
transportation planning can be presented as the corresponding problems of linear
programming of the transport type, for the solution of which nowadays there
are universal methods, first of all, the simplex method [23-24] and its variants
taking into account the specific nature of this type of tasks(various complicated
and modified formulations of the transport task).But the linear methods do not
allow one to take into account a number of requirements of the domain and,
also, to solve the following tasks in dynamics.
1. Planning the vehicle loading with orders;
2. Reschedule the vehicle loading (in case of arrival of a new order);
3. Planning the vehicle route taking into account the delivery times of individ-
ual orders, accommodation of hotels, and gas stations;
4. Reschedule the vehicle route in the event of a new order;
34
These tasks require different methods of solution. The only way to solve the
tasks of scheduling is the use of decision support systems (DSS) [27-28] based on
the effective simulation and multi-agent models [25-26]. Such models allow one
to ”lose” various schemes of vehicle fleet management taking into account the
current situation (urgency and volumes of cargo transportation, condition and
dislocation of vehicles, fuel residues in vehicles, location of filling stations), ana-
lyze various variants of the development of events, and choose the most effective
solution for a given instant.
2 Development of hybrid method of planning fuel
delivery
The closest classical technique for planning the fuel transportation is the trans-
port problem [1-2]. In the course of analysis of the applicability of the transport
task, the following limitations of the subject area were revealed: 1)multiplicity
of the cargo transportation volume should be multiple to the volume of the sec-
tion; 2) the cargoes are not homogeneous, and each cargo (depending on the
type of fuel) can be transported in one section of the tank truck; 3)sequence of
the fuel draining is not taken into account (depending on the design features of
the drainage devices, the order of discharge of the sections may differ); 4) there
is no time component in the form of start and end times of flights, loading /
unloading times; 5) there is no division into types of goods or their marking fuel
types. (for example, 92, 95, 98, Diesel, 80); 6)presence of several sections in the
fuel tank truck is not taken into account; 7)the physical limitations of gasoline
tankers for filling stations are not taken into account; 8)there is no possibility to
take into account preferences of the petrol tankers for filling stations; 9)the pos-
sibility of servicing close gas stations by a gasoline tanker per flight is not taken
into account. These restrictions are proposed to be taken into account using the
multi-agent approach. The following approaches and models of the multi-agent
planning [3-4, 7, 15-17] were investigated: 1) multi-agent model of the process of
resource transformation (MAPP) [5-6, 12, 18]; 2) network of needs-opportunities
(PV network) [13-14], V.. Wittich, P.O. Skobelev, G.A. Rzhevsky; 3) model of
active and passive transducers (AMS) by Klebanov and I.M. Moskalev [19-20],
as well as its change in the system of modeling of the socio-economic devel-
opment; 4) the approach Borshcheva AV, Karpova Yu.G. implemented in the
AnyLogic modeling system . There are various approaches used in construc-
tion of the multi-agent models. The most promising are the following: networks
of needs-opportunities (PV network) and the multi-agent resource transforma-
tion processes. The purpose of this subsection is to determine their merits and
drawbacks on the example of the problem of supplying fuel to network of filling
stations. The technique PV-networks was developed by VA. Wittich and P.O.
Skobelev. The software was implemented in the product MAGENTA. Currently,
the MAGENTA system is not on the market and is not available for research. To
build a PV network, any software product that uses the multi-agent interaction
models based on the notion of an intelligent agent is sufficient. Therefore, the
35
model on the PV network, as well as, the model of the MPPP, is implemented in
the BPsim.MAS. To solve the problem of the delivery planning, a hybrid method
was developed based on the integration of the transport problem, the theory of
scheduling, the apparatus of simulation, expert modeling and the multi-agent
systems (MAPP). The method consists of the following steps.
1. Calculation (determination) of the fuel needs at the filling stations of the
multiple capacity of the minimum gasoline tank truck. The forecast of re-
quirements for the remaining capacities of the filling stations, in which for
the second half of the shift the demand, which is a multiple of the capacity
of the minimum gasoline tank truck, can enter in ;
2. The solution of the transport task with regard to planning the deliveries
from oil depots to the gas stations (without linkage of the gasoline tankers);
3. Processing the supporting solution from the transport task 1: All the needs
are ranked (the most urgent needs are identified what we carry earlier, and
what is later) according to the priority. The definition for each order (supply
requirements) of the supplier (warehouse / logistics center to the tank depot)
and the route of delivery;
4. Processing the supporting solution from the transport task 2: Creation of
flights (transportation plan). Assigning for each order a vehicle and deter-
mining the time of execution (the times of the beginning and end of the
voyage). At this stage, an intelligent scheduling agent is used with a frame
knowledge base that takes into account the statistics of the fuel sales from
the gas station, the physical limitations of gas stations, the gasoline tankers
(by their compatibility and service capabilities), and, also, the preferences
for use;
5. Verification of the logistics plan by the logistics specialist / dispatcher;
6. Verification and adjustment of the export plan on the multi-agent simulation
model of the resource conversion process;
7. Implementation of the plan;
8. In the conditions of external influences leading to dispatching situations, the
expert’s plan for the dispatch is being adjusted by the expert (dispatcher).
The main criterion for the success of solving this task is to ensure the unin-
terrupted operation of the network of filling stations;
3 Network of Gas Stations
Consider the operation of the gas stations network. In this software, there are
five filling stations, a parking lot with three gasoline tankers, and an oil depot.
Each gas station contains a set of columns with a certain type of fuel:
1. at the gas station 1, AZS2 and AZS4 there are columns with the fuel AI-92,
AI-95 and diesel fuel (DT);
2. at the filling stations and A5S there are columns with the fuel AI-92 and
AI-95;
36
Fig. 1. The diagram of the gasoline tankers motion and the location of the filling
station in relation to the parking lot, tank farms, and each other.
3.1 Comparative analysis of multi-agent approaches: MAPP and
PV networks
The main difference between these models is the following: in the MAPP model,
the dispatch agent solves the planning task (which application to which gasoline
truck to fix), the principle of centralized control is implemented. In the PV
network, the decision-making process is implemented in the process of matching,
which occurs between the gasoline tank carriers and agent-applications. In the
process of communication (negotiation) of the agents needs and opportunities,
the following task is solved: who and what application will consolidate itself, that
is, there is decentralized management (taking into account the implementation in
SIM, the number of communications in the current clock cycle does not overlap,
and they end in solving all situations initiated by the match procedure). In
the case of the PV network, communication and the matchings procedure give
a negative effect of the ”nervousness” of the system. As the practice of using
MAGENTA technology (PV network) for taxi services and freight companies has
shown, the procedure for the real-time matching does not have the best effect on
the drivers of the gasoline tankers (it has the effect of nervousness). But, on the
other hand, communications and the procedure of matching can bring a rational
solution closer. This is due to the possibility of a permanent review of the plan
in order to find more advantageous combinations. For the network model, the
gas station is a refusal of already fixed orders by the gasoline tanker and the
taking of other applications. In the case of the MAPP approach, the time spent
on a particular model run is significantly less than in the case of the model
37
built on the PV network. The model of the MPRP with the function of the best
distribution of requests for gasoline tank trucks copes as follows: it analyzes after
what amount of time the application will appear and with which this or that
fuel carrier will have the least penalty. If this time is not so great, the dispatcher
sets the waiting status of this application with a gasoline tanker, if not, then
he gives the most appropriate application to the gas tank truck. When creating
a PV network, it is necessary to implement in a large number similar (but not
identical) rules of the agent-opportunities and agents-needs (first of all) that
are necessary for making contracts between the latter. Note that this affects the
performance of the analyst who develops the model. Another drawback of the PV
network models is that the system resources are expensive to determine in the
order the agent-opportunity will communicate with the agent-need; in the case
of communication it does not happen with everyone. If the communication takes
place each with each, then in this case significant system resources of computer
facilities will be involved. In the MDPP model, the costs of computing resources
during the run are much less. Thus, the application of the MAPP approach in
production and logistics models has a number of advantages, as listed above, in
comparison with applying the demand-opportunity network approach.
4 Program realization of hybrid method of planning of
delivery of fuel
Based on the hybrid decision-making method for the fuel distribution planning
through the filling station network, the decision support system (DSS) was devel-
oped as a result of integration of the ”Planner”, BPsim.MAS (multi-agent mod-
eling system), and the, BPsim.DSS (frame intelligent system) systems [21-22].
This DSS is problem-oriented and supports manual, automated and automatic
updating of the plan for export by the expert (dispatcher). The architecture of
the MAPP agent is based on the hybrid architecture of the InteRRaP [8] and is
shown in Fig. 2.
4.1 Application of frame approach in the program agent
”SCHEDULER
An example of a solution search chart for the sub-task manager for distribution
of the requests-needs from the gas stations in the gasoline tank trucks in the
visual designer of the logical output engine BPsim.DSS for the Scheduler agent
(Fig. 3).
The visual interface of the manager of the agent Scheduler is shown in Fig.4
The use of the frame output engine and the visual interface of the dispatcher
allows one to flexibly resolve the situations associated with dispatching. The
dispatching situations that require minimal plan adjustments are handled by the
decision maker using the visual interface. In the cases of significant adjustment
38
Fig. 2. Architecture of the MAPP agent.
Fig. 3. Chart of the search tree of decisions Planning of a delivery of fuel. Distribution
of requests on fuel trucks
39
Fig. 4. Visual interface of the manager
of the plan or complete rebuilding, the script of the inference engine is used.
The results of computational experiments of the simulation model are compared
with the actual data of the transfer. The results showed the convergence in part
of the flights and the volume of fuel transportation. The results of the analysis
prove that the method implemented in the DSS shows a greedy strategy for the
number of flights and the volume of traffic (on 13 percent higher in average).
5 Conclusion
In this paper, we propose the hybrid method for solving the problem of plan-
ning the transportation of fuel through a network of the gasoline stations. The
method was developed as a result of integration of the transport task and the
multi-agent simulation model of the process of resource conversion. The method
is implemented in software as the decision support system as a result of inte-
gration of the Scheduler and BPsim systems. If communication takes place each
with each, then in case f model on the PV networks, significant system resources
of computer facilities will be involved. In the MDPP model, the costs of comput-
ing resources during the run are much less. Thus, the application of the MAPP
approach in production and logistics models has a number of advantages, as
listed above, in comparison with applying the demand-opportunity network ap-
proach. Approbation of the method and DSS took place in the current network
of the gas stations in the Sverdlovsk Region. When solving the task of planning
the delivery, the task of integrating the DSS with the corporate system of the
enterprise was solved. This now makes it possible to classify the BPsim as an
40
open modeling system and makes it possible to apply it to real-time control tasks.
Acknowledgments. The work was supported by the Act 211 Government of
the Russian Federation, contract 02.A03.21.0006.
References
1. Galyutdinov R.R: Transportation problem -decision of potential method
http://galyautdinov.ru/post/transportnaya-zadacha, (2016)
2. Prosvetov G.I.: Mathematical method in logistic: problem and decision: Alfa Press,
304 p, (2014)
3. Wooldridge M. : Agent-based software engineering.In: IEEE Proc. Software Engi-
neering, 144 (1) 2637, (1997)
4. Kowalski M., Zelewski S., Bergenrodt D., Klupfel H.: Application of new tech-
niques of artificial intelligence in logistics: an ontology-driven case-based reasoning
approach. In: Proceedings of ESM’2012 (ESM - European Simulation and Mod-
elling Conference) October 22-24, FOM University of Applied Sciences, Essen,
Germany, 323-328(2012)
5. Aksyonov K., Bykov E., Aksyonova O., Goncharova N., Nevolina A. :Decision Sup-
port for Gasoline Tanker Logistics with BPsim.DSS. In: International Conference
on Computer Information Systems and Industrial Applications (CISIA 2015). June
28-29, Bangkok, Thailand. P.604-606. WOS:000359866200164 (2015)
6. Aksyonov K., Antonova A. :Application of a metallurgical enterprise information
system for collection and analysis of big data and optimization of multi-agent
resource conversion processes. In: 2018 International Research Workshop on In-
formation Technologies and Mathematical Modeling for Efficient Development of
Arctic Zone, IT and MathAZ 2018; Graduate School of Business and Managemen-
tYekaterinburg; Russian Federation; CEUR Workshop Proceedings. Volume 2109,
1-6, (2018)
7. Jennings N. R.: On agent-based software engineering. In: Artificial Intelligence, vol.
117, 277-296. URL:http://www.agentfactory.com/ rem/day4/Papers/AOSEJenni
ngs.pdf (2000)
8. Muller J.P., Pischel M.: The Agent Architecture InteRRaP. In: Concept and Ap-
plication, German Research Center for Artificial Intelligence (DFKI) (1993)
9. Sowa J. F.: Conceptual graphs for a database interface. In: IBM Journal of Research
and Development. 20:4, 336-357(1976)
10. Sowa J. F. Conceptual Structures : Information Processing in Mind and Machine
/ J. F. Sowa. Reading, MA : Addison - Wesley, 481 (1984)
11. Sowa J. F. : Knowledge Representation : Logical, Philosophical, and Computational
Foundations / J. F. Sowa. - Pacific Grove, CA : Brooks/ Cole Publishing Co., 594
p (2000)
12. K. Aksyonov, E. Bykov, E. Smoliy, E. Sufrygina, O. Aksyonova and Wang Kai :
Development and Application of Decision Support System BPsim.DSS . In: Pro-
ceedings of the IEEE 2010 Chinese Control and Decision Conference (CCDC 2010),
Xuzhou, China, Pages 1207-1212 (2010)
13. V. A. Wittich, P. O. Skobelev : Multi-agent interaction models for the design of
the nets of requirements and capabilities in open systems, Automatics and teleme-
chanics, vol. 1, 177-185 (2003)
41
14. Skobelev P. O.: Multi-agent technologies for the control of resources in
real-time. In :Proceedings of the seminarMechanics, control and informatics,
track Perspective computer systems: devices, methods and concepts, Tarusa,
http://www.iki.rssi.ru/seminar/2011030204/presentation/20110303 03.pdf (2011)
15. Devyatkov V.V., Vlasov S.A., Devyatkov T.V. : Cloud Technology in Simulation
Studies: GPSS Cloud Project. In: Proceedings of the 7th IFAC Conference on
Manufacturing Modeling, Management, and Control. Saint Petersburg (Russia):
IFAC, Volume 7, Part 1, 637-641 (2013)
16. Sokolov B.V., Pavlov A.N., Yusupov R.M., Ohtilev M.U., Potryasaev S.A.: The-
oretical and technological foundations of complex objects proactive monitoring
management and control. In: Proceedings of the Symposium Automated Systems
and Technologies Peter the Great St. Petersburg Polytechnic University, Leibniz
Universitt Hannover, 103-110 (2015)
17. Solovyeva I., Sokolov B., Ivanov D.: Analysis of position optimization method ap-
plicability in supply chain management problem. In; 2015 International Conference
”Stability and Control Processes” in Memory of V.I. Zubov (SCP), 498-500 (2015)
18. Aksyonov K., Bykov E., Aksyonova O., Goncharova N. and Nevolina A.: Extension
of the multi-agent resource conversion processes model: Implementation of agent
coalitions. In: 5th International Conference on Advances in Computing, Commu-
nications and Informatics, ICACCI 2016; LNM Institute of Information Technol-
ogy (LNMIIT)Jaipur; India. 593-597. DOI: 10.1109/ICACCI.2016.7732110 URL:
http://www.scopus.com WOS:000392503100094 (2016)
19. Klebanov B., Antropov T., Riabkina, E.: Bases of imitation model of arti-
ficial society construction accounting of the agents needs recursion. In: 16th
International Multidisciplinary Scientific GeoConference SGEM 2016. Book2
Vol. 1, 101-108. URL:https://sgemworld.at/sgemlib/spip.php?article8493. DOI:
10.5593/SGEM2016/B21/S07.014, WOS:000395499400014 (2016)
20. Klebanov B., Antropov, T., Riabkina, E.: The principles of multi-agent mod-
els of development based on the needs of the agents. In: 35th Chinese Control
Conference, CCC 2016 . 7551-7555 DOI: 10.1109/ChiCC.2016.7554553. URL :
http://ieeexplore.ieee.org/document/7554553/ , WOS:000400282203147 (2016)
21. Aksyonov K., Antonova A.: Application of the process parameter analysis tree for
technological process analysis. In: 2018 Ural Symposium on Biomedical Engineer-
ing, Radioelectronics and Information Technology (USBEREIT). Yekaterinburg,
Russia. 212-215. DOI: 10.1109/USBEREIT.2018.838458 (2018)
22. Aksyonov K., Antonova A.: Analysis of Subcontracting Scheduling Methods Based
on Modeling. In: UKSim-AMSS 11th European Modelling Symposium on Mathe-
matical Modelling and Computer Simulation. Manchester, England,138-141. DOI
10.1109/EMS.2017.33 (2017)
23. Shorikov A.F.: Solution of the Two-Level Hierarchical Minimax Program Control
Problem in a Nonlinear Discrete-Time Dynamical. In: 2th IFAC Conference on
Modelling, Identification and Control of Nonlinear Systems. Book of Abstracts.
University of Guadalajara, Mexico, p 33 (2018)
24. Shorikov, A. F.: Minimax Program Terminal Control in Two-Level Hierarchic Non-
linear Discrete Dynamical System. In: Journal of Mathematical Sciences (United
States). 230, 5, 808-812 (2015)