Currently, the interaction between its participants plays an important role in the supply chain management process. The article proposes a multi-agent method for selecting product suppliers, which automates supplier selection and speeds up the decision-making process of the seller. The developed method includes determining the characteristics of product suppliers, creating a protocol for interaction between the seller and suppliers, developing methods for forming requirements for suppliers, analyzing the characteristics of suppliers and evaluating suppliers based on the results of their work. The proposed metaheuristic method for assigning orders to product suppliers is based on a genetic algorithm and, through the use of dynamic parameters, improves the accuracy and speed of the method and ensures its convergence. Prospects for further research include studying the proposed methods for a wide class of artificial intelligence problems. supply chain management, multi-agent system, protocol for interaction between seller and suppliers, metaheuristics, genetic algorithm IntelITSIS'2024: 5th International Workshop on Intelligent Information Technologies and Systems of Information Security, March 28, 2024, Khmelnytskyi, Ukraine
Currently, one of the areas of logistics is supply chain management. Within this direction, artificial intelligence methods are actively used for forecasting, classification, and clustering [1]. Also for the supply chain management process, the interaction between its participants plays an important role [2-3], which can be modeled using a multi-agent system [4-6].
The goal of the work is to increase the efficiency of selecting product suppliers and assigning orders to them based on multi-agent systems and metaheuristics.
∗ Corresponding author. † These authors contributed equally.
3. Create a multi-agent metaheuristic method based on a genetic algorithm to solve the assignment problem.
Interactive sites of sellers (for example, online stores) are usually not intended for interactions with suppliers, and, in particular, for holding a competition among them. Therefore, multiagent technologies are currently becoming widespread, allowing for the selection of suppliers.
The introduction of a multi-agent environment into the sales force structure is promising due to the following aspects: 1. Security of transactions on the Internet, which is achieved due to the fact that any information about the consumer and supplier is transmitted using a special agent message language, Agent Communication Language (ACL). This eliminates the possibility of using intercepted information flows. 2. The ability to provide up-to-date information about supplier agents in your directory, thanks to the use of a directory service (DF). 3. The possibility of creating new types of agents to work with consumers and suppliers.
Currently, the most preferred protocol for interaction between the seller agent and supplier agents is the Contract net protocol, which is implemented in multi-agent environments. However, the standard Contract Net is abstract in nature, is not focused on a specific subject area, and does not cover all stages of interaction. Thus, there is a need to modify this protocol.
To improve efficiency, the seller's assignment of orders to selected suppliers should rely on optimization techniques. Optimization methods that find an exact solution have high computational complexity. Optimization methods that find an approximate solution through a directed search have a high probability of hitting a local extremum. Random search methods do not guarantee convergence. In this regard, the problem of insufficient efficiency of optimization methods arises, which needs to be solved.
To quickly find a quasi-optimal solution to optimization problems and reduce the probability of hitting a local extremum, metaheuristics (or modern heuristics) are used [7-8]. Metaheuristics extend the capabilities of heuristics by combining heuristic methods based on a high-level strategy [8-10]. Metaheuristics are used for discrete and continuous optimization [11-12].
Existing metaheuristics have one or more of the following disadvantages: • • • • there is only an abstract description of the method or the description of the method is focused on solving only a specific problem [13]; the influence of the iteration number on the process of finding a solution is not taken into account [14]; the convergence of the method is not guaranteed [15]; there is no possibility to use non-binary potential solutions [16]; the procedure for determining parameter values is not automated [17]; there is no possibility to solve conditional optimization problems [18-19]; insufficient accuracy of the method [20-21].
Thereby, the problem arises of constructing effective metaheuristic optimization methods [22-23].
One of the popular metaheuristics is evolutionary metaheuristics [24-25]. Among them, we can highlight a genetic algorithm that allows solving combinatorial optimization problems (for example, the assignment problem) [26-27]. 3. Multi-agent method for selecting product suppliers To intellectualize the interactive selection of product suppliers to a seller (for example, an online store), it is necessary to: • • • • • • determine the characteristics of product suppliers; propose a protocol for interaction between the seller and suppliers; develop methods to formulate requirements for suppliers, analyse supplier characteristics and evaluate suppliers based on the results of their work. 3.1
Product supplier characteristics This paper highlights the following characteristics of product suppliers: x 1 – cost of purchased products, x 2 – products’ grade (varies from high-quality to low-quality products, it is possible to indicate a list of manufacturing companies), x 3 – the distance between the seller and the supplier’s products warehouse, x 4 – conditions for the delivery of products (pickup by the seller, delivery to the seller’s warehouse, direct delivery to consumers) and its guarantee (if the delivery is carried out by the supplier), x 5 – lead times for orders, x 6 – the minimum batch size of products purchased from the supplier and the period for which this batch should be purchased,
x 7 – terms of payment (no advance payment, work on credit, provision of installments, or lack thereof) and the need to make a security deposit, x 8 – the availability and organization of the supplier’s quality management system, x 9 – the ability of the supplier to service the supplied equipment with spare parts throughout its entire service life, x 10 – the supplier’s connections with respectable organizations, x 11 – the number of years of the supplier’s existence in the market of products and services, x 12 – the availability of product certificates, x 13 – the availability of discounts and conditions for their granting, x 14 – the frequency of products’ delivery to the supplier, x 15 – providing notifications about product updates, x 16 – providing notifications about changes in products’ prices, x 17 – providing notice of termination of supply of certain products, x 18 – terms of return and exchange of defective products, x 19 – terms for the return or exchange of illiquid products, x 20 – the range of products (wide or narrow).
These characteristics are learned from product suppliers in the process of interactive interaction with them. 3.2
Interaction protocol between the seller and suppliers Today, the interaction of the seller with suppliers is intellectualized through a multi-agent system (MAS). In MAS, the online store and suppliers are represented by their respective agents. The most effective protocol for interaction between them is the Contract Net. However, the standard Contract Net is abstract in nature, is not focused on a specific subject area, and does not provide for all stages of interaction.
Therefore, in order to select product suppliers based on an interactive competition, a modified Contract Net protocol is proposed, which includes the following stages: • • • • • • problem identification (the need for the supply of products); problem announcement; proposal; contract conclusion; problem solving; declaring further cooperation.
At the problem identification stage, the sales agent determines, based on the product sales forecast and inventory control, that he needs products to sell. The selling agent understands that he needs products of a certain quality, in certain terms, etc.
At the problem announcement stage, the selling agent informs the supplying agents about his problem and also makes demands on them. Three situations are possible: 1. If the selling agent does not know about certain characteristics of the supplying agents, then he is forced to send a message to all the supplying agents. 2. If the selling agent knows which supplying agents are possible candidates, then he can send a limited message to only those candidates. 3. If the selling agent knows exactly which supplying agent is the appropriate one, then he can send a message to the specific supplying agent.
At the proposal stage, the supplying agents, aware of the problem, evaluate it relative to their own characteristics, i.e. whether they can solve it quickly and whether they can satisfy the requirements of the selling agent. If the problem can be solved by the supplying agent, А2 А3 А2 А3 I have a problem А1 then the supplying agent makes a proposal to the selling agent. The proposal specifies the characteristics of the provider agent that are associated with solving this problem. A selling agent may receive many such proposals in response to a single problem announcement.
At the contract conclusion stage, based on the characteristics of the supplying agents contained in their proposals, the selling agent selects the most suitable supplying agents to solve the problem. The selling agent announces his choice to the selected supplying agents through a message about the conclusion of the contract. These selected supplier agents take responsibility for solving the problem.
At the problem solving stage, supplier agents implement the solution to the problem. Once the problem is resolved, the supplier agents send messages to the selling agent.
At the stage of declaring further cooperation, the selling agent informs about the prospects for further cooperation with the supplying agents based on the results of their solution to the problem.
This negotiation process can be simplified to make the protocol more efficient. If the selling agent knows exactly which supplying agent is suitable for solving the problem, then he can enter into a direct contract with that supplying agent.
This contract differs from the announced contract in that there is no announcement and no proposals, but the conclusion of the contract is made directly. In such cases, supplier agents with whom contracts have been entered into must acknowledge receipt of the contract notification and have the opportunity to refuse.
For tasks that make simple requests for information, the contract may not be used. In such cases, the request-response sequence can be used without further improvements. Such messages are implemented as request and inform messages. The request message is used to encode direct requests for information when entering into a contract is unnecessary. The inform message is used to respond to a request message and to transmit data.
For the Contract Net interaction protocol, there is its FIPA specification SC00029, which in this work was modified by adding a stage for declaring further cooperation and adding methods for the stages of offer, contract conclusion and declaring further cooperation. The modified FIPA-ContractNet interaction protocol (represented as a UML diagram in Figure 2) allows the selling agent (Initiator) to declare its problem to the supplying agents (Participant).
Supplier agents process the statement of problem (cfp) of the selling agent and decide whether to send their proposals (propose) or refuse to solve the problem (refuse) based on logical-formal rules.
The selling agent processes proposals and makes a decision to accept (accept-proposal) or reject (reject-proposal) proposals based on logical-formal rules. If the proposals are accepted, the relevant supplying agents notify the selling agent of the outcome of the problem resolution. Such a notification can be failure (if the solution to the problem is unsuccessful), inform-done (if the problem is successfully resolved and the sales agent is notified only about this) or inform-result (if the problem is successfully resolved and the sales agent is notified about this and the result).
The selling agent processes the result of solving the problem and makes a decision to accept or reject further cooperation based on logical-formal rules. In addition, during the execution of this protocol, the recipient can inform the sender that he did not understand the information sent to him. This is done through a non-understood message.
Appropriate methods must be developed for the stages of proposal, contract conclusion and declaring further cooperation.
Method of forming requirements for suppliers In this work, for the proposal stage, a method has been created for generating requirements for suppliers based on the following logical-formal rules x 1 ∈A 1 ∧x 2 ∈A 2 ∧x 3 ∈A 3 ∧x 4 ∈A 4 ∧x 5 ∈A 5 → propose ,
x 1 ∉A 1 ∨ x 2 ∉A 2 ∨ x 3 ∉A 3 ∨ x 4 ∉A 4 ∨ x 5 ∉A 5 → refuse , where Ai – is the set of values of the i th characteristic of the supplier, declared by the seller at the stage of the problem announcement. 3.4
Method for analyzing supplier characteristics In this work, for the contract conclusion stage, a method has been created for analyzing the characteristics of suppliers based on the following logical-formal rules 20 ∑P (Bi ) < ε → reject _ proposal , i =6 20 ∑P (Bi ) ≥ ε → accept _ proposal , i =6 where Bi – is the set of values of the i th characteristic, declared by the supplier at the proposal stage,
ε – threshold value, is specified. 3.5
Method to evaluate suppliers based on their performance In this work, for the stage of declaring further cooperation, a method has been created for evaluating suppliers based on the results of their work based on the following logical-formal rules y 1 ∈B 1 ∧y 5 ∈B 5 →accept , y 1 ∉B 1 ∨ y 5 ∉B 5 → reject , where y i – the real value of the i th characteristic obtained by the supplier at the problem solving stage. 4. Metaheuristic method for assigning orders to product suppliers with an unequal number of suppliers and orders The fitness function (target function) in the case of a generalized assignment problem with equal weights (equal to 1) and equal budgets (equal to M ) is defined as
L M 1, x j = i F (x ) = ∑ ∑w ij [x j = i ] → max , [x j = i ] = i =1 j =1 x 0, x j ≠ i
,
M ∀i ∈ 1,L ∑v ij [x j = i ] ≤t i , v ij = 1 , t i = M , j =1
L ∀j ∈ 1,M ∑[x j = i ] = 1 ,
i =1 where w ij – income from fulfillment of the the i th supplier of the j th order, v ij – weight of fulfillment of the the i th supplier of the j th order, t i – i th supplier's budget, x j – supplier for j th order, M – number of orders, L – number of suppliers.
The genetic algorithm with dynamic parameters and natural genes consists of the following steps: 1. Initialization. 1.1. Setting the maximum number of iterations N , population size K , chromosome length (number of orders) M , number of possible chromosome gene values (number of suppliers) L , number of crossover iterations N c , number of mutation iterations N m , minimum and maximum values for probability p min ,p max . 1.2. Creation of the initial population P . 1.2.1. Chromosome number k = 1 , P = ∅ . 1.2.2. Randomly creating a chromosome
x k = (x k 1,...,x kM ) , x k = round (1 + (L − 1)U (
k * = argkm∈1a,KxF (x k ) , x * = x k * .
1.4. The initial probability is set
(
s =1 3.3. Reproduction iteration number k = 1 .
m m +1
3.4. If ∃m ∈ 1,K − 1 : ∑ p (x s ) <U (
s =1 s =1 3.5. If k < K , then k = k + 1 , go to step 3.2. 4. Crossing over natural genes to create an intermediate population P . 4.1. Crossing over iteration number m = 1 .
k = round (1 + (K − 1)U (
If U (
M min ∑[x kj = x sj ] , s ∈{1,...,K }\ {k }j =1 otherwise l = arg
M max ∑[x kj = x sj ] .
s ∈{1,...,K }\ {k }j =1 4.4. Two descendants are created
x kj
λj =U (
x lj
, x 2m ,j =
x kj
λj < 0.5
λj ≥ 0.5
, j ∈1,M .
4.5. If m < N c , then m = m + 1 , go to step 4.2.
5. Mutation over natural genes to create an intermediate population P .
5.1. Mutation iteration number s = 1 , descendant number m = 0 .
5.2. If U (
s = round (1 + (M − 1)U (
9. Determination of the global best chromosome. If F (x k * ) > F (x * ) , then x * = x k * . 10. Update probability p (n + 1) = p min + (p max − p min )1 − n .
N 10. If n < N , then n = n + 1 , go to step 3, otherwise stop.
H = P P P . x k = hk , k ∈ 1,K . k * = arg maxF (x k ) . k ∈1,K
A numerical study of the proposed optimization method was carried out using the Python package in the Google Colab environment.
In the work, the population size is K = 100 , the maximum number of iterations is N = 100 , the number of crossing over iterations is N c = 100 , the number of mutation iterations is N m = 100 , the minimum and maximum probability values are p min = 0.01,p max = 1 .
For the assignment problem, the search for a solution was carried out on the standard tai50a database (traditionally used for testing methods for solving the assignment problem).
The decreasing probability function is determined by the formula p (n + 1) = p min + (p max − p min )1 − n and is presented in Figure 3.
N
The dependence (Figure 3) of the decrease in probability on the iteration number shows that the probability decreases with increase iteration number.
For the assignment problem, the search for a solution was carried out on the standard tai50a database. The results of comparing the proposed method with the traditional genetic algorithm method are presented in Table 1. 0,9 0,8 0,7 )0,6 n ( p0,5 0,4 0,3 0,2 0,1 0
Advantages of the proposed method: 1. The proposed reproduction operator can be used at both the initial and the final stages of the genetic algorithm, since at the early stages of the genetic algorithm, equiprobable selection is used, ensuring the exploration of the entire search space (random selection of chromosomes), and at the final stages proportional selection is used, making the search directed (the current best chromosomes are saved). 2. The proposed crossover operator can be used at both the initial and the final stages of the genetic algorithm, since outbreeding (crossing the most distant chromosomes from each other) is used at the early stages of the genetic algorithm, which ensures the exploration of the entire search space (random selection of chromosomes), and in the final stages, inbreeding is used (crossing the chromosomes that are closest to each other), making the search directed (the current best chromosomes are retained). 3. The proposed mutation operator can be used at both the initial and the final stages of the genetic algorithm, since at the early stages of the genetic algorithm the probability of mutation is high, which ensures exploration of the entire search space (random selection of chromosomes), and at the final stages the probability of mutation is low, which makes the search directed (the current best chromosomes are retained). 4. The proposed method is superior to the classical method in terms of accuracy and speed (Table 1). 7. Conclusions 1. A multi-agent method for selecting product suppliers was developed, which automates the selection of suppliers and speeds up the decision-making process for the seller. The developed method includes determining the characteristics of product suppliers, creating a protocol for interaction between the seller and suppliers, developing methods for forming requirements for suppliers, analyzing the characteristics of suppliers and evaluating suppliers based on the results of their work. 2. The proposed metaheuristic method for assigning work to product suppliers through the use of dynamic parameters makes it possible to increase the accuracy and speed of this method and ensure its convergence. 3. Prospects for further research are the study of the proposed methods for a wide class of artificial intelligence problems.