Comparative Analysis of Multi-agent Approaches for Planning Fuel Delivery of Petrol Stations

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 modeling). Comparative analysis of the multi-agent approaches for planning the fuel delivery of petrol stations was done. Supposed method of decision 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
• transportation problem

-

Adequate mathematical models of most problems of the e ective 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, rst of all, the simplex method [ 23-24 ] and its variants taking into account the speci c nature of this type of tasks(various complicated and modi ed 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 individual orders, accommodation of hotels, and gas stations; 4. Reschedule the vehicle route in the event of a new order; These tasks require di erent 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 e ective simulation and multi-agent models [25-26]. Such models allow one to "lose" various schemes of vehicle eet management taking into account the current situation (urgency and volumes of cargo transportation, condition and dislocation of vehicles, fuel residues in vehicles, location of lling stations), analyze various variants of the development of events, and choose the most e ective 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 transport 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 section; 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 di er); 4) there is no time component in the form of start and end times of ights, 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 lling stations are not taken into account; 8)there is no possibility to take into account preferences of the petrol tankers for lling stations; 9)the possibility of servicing close gas stations by a gasoline tanker per ight 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 development; 4) the approach Borshcheva AV, Karpova Yu.G. implemented in the AnyLogic modeling system . There are various approaches used in construction of the multi-agent models. The most promising are the following: networks of needs-opportunities (PV network) and the multi-agent resource transformation 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 lling 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 su cient. Therefore, the 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 lling stations of the multiple capacity of the minimum gasoline tank truck. The forecast of requirements for the remaining capacities of the lling 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 identi ed what we carry earlier, and what is later) according to the priority. The de nition 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 ights (transportation plan). Assigning for each order a vehicle and determining 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. Veri cation of the logistics plan by the logistics specialist / dispatcher; 6. Veri cation 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 in uences 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 uninterrupted operation of the network of lling stations; 3

Network of Gas Stations

Consider the operation of the gas stations network. In this software, there are ve lling 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 lling stations and A5S there are columns with the fuel AI-92 and

AI-95;

Comparative analysis of multi-agent approaches: MAPP and PV networks The main di erence between these models is the following: in the MAPP model, the dispatch agent solves the planning task (which application to which gasoline truck to x), 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 e ect 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 e ect on the drivers of the gasoline tankers (it has the e ect 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 nd more advantageous combinations. For the network model, the gas station is a refusal of already xed 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 signi cantly less than in the case of the model 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 ( rst of all) that are necessary for making contracts between the latter. Note that this a ects 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 signi cant 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 lling station network, the decision support system (DSS) was developed as a result of integration of the "Planner", BPsim.MAS (multi-agent modeling 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 exibly 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 signi cant adjustment 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 ights 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 ights and the volume of tra c (on 13 percent higher in average). 5

Conclusion

In this paper, we propose the hybrid method for solving the problem of planning 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 integration of the Scheduler and BPsim systems. If communication takes place each with each, then in case f model on the PV networks, signi cant 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. 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 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 Engineering , 144 ( 1 ) 2637 , ( 1997 )

4. Kowalski M. , Zelewski S. , Bergenrodt D. , Klupfel H. : Application of new techniques of arti cial intelligence in logistics: an ontology-driven case-based reasoning approach . In: Proceedings of ESM'2012 (ESM - European Simulation and Modelling 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 Support 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 Information Technologies and Mathematical Modeling for E cient Development of Arctic Zone, IT and MathAZ 2018; Graduate School of Business and ManagementYekaterinburg; Russian Federation; CEUR Workshop Proceedings . Volume 2109 , 1 - 6 , ( 2018 )

7. Jennings N. R. : On agent-based software engineering . In: Arti cial 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 Application, German Research Center for Arti cial 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 . - Paci c 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: Proceedings 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 telemechanics , vol. 1 , 177 - 185 ( 2003 )

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. : Theoretical 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 applicability 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, Communications and Informatics , ICACCI 2016 ; LNM Institute of Information Technology (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 articial society construction accounting of the agents needs recursion . In: 16th International Multidisciplinary Scienti c 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 models 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 Engineering, 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 Mathematical 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, Identi cation 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 Nonlinear Discrete Dynamical System . In: Journal of Mathematical Sciences (United States) . 230 , 5 , 808 - 812 ( 2015 )