24 Life Cycle Simulation of Machine Parts with Part Agents
347
(MD) represents the longest distance the user can travel. D is the ratio of the
actual travel distance D U to the MD of each user. L is the remaining life of the
evaluated product. a 1 to a 4 are the weighting factors for each item.
(3) Match
After all agents perform calculations on DoS, matching is performed using a
maximum weight bipartite matching problem and the paired agents perform
transactions.
The weighted maximum bipartite matching is a problem to determine a combination
in which the sum of the costs of the matched edges is maximized by matching as
many vertices as possible, assuming that the cost is set for each connecting edge in
the bipartite graph. In this study, a black vertex shown in Fig. 24.6 is a buyer and a
gray vertex is a seller. An edge is placed between the vertex of the two agents when
the distance from a certain buyer agent to a certain seller agent is within the movable
distance of one another.
As a method to solve the weighted maximum binary matching problem, the
minimum-cost flow problem (Ahuja et al. 1993) using an algorithm termed the
Bermanford method (Bellman 1958) is used.
The minimum-cost flow problem assumes that each edge of a directed network,
as shown in Fig. 24.7, is given an integer capacity and a cost resulting from an
Fig. 24.6 Weighted
maximum bipartite matching
Fig. 24.7 Minimum-cost
flow problem
347
(MD) represents the longest distance the user can travel. D is the ratio of the
actual travel distance D U to the MD of each user. L is the remaining life of the
evaluated product. a 1 to a 4 are the weighting factors for each item.
(3) Match
After all agents perform calculations on DoS, matching is performed using a
maximum weight bipartite matching problem and the paired agents perform
transactions.
The weighted maximum bipartite matching is a problem to determine a combination
in which the sum of the costs of the matched edges is maximized by matching as
many vertices as possible, assuming that the cost is set for each connecting edge in
the bipartite graph. In this study, a black vertex shown in Fig. 24.6 is a buyer and a
gray vertex is a seller. An edge is placed between the vertex of the two agents when
the distance from a certain buyer agent to a certain seller agent is within the movable
distance of one another.
As a method to solve the weighted maximum binary matching problem, the
minimum-cost flow problem (Ahuja et al. 1993) using an algorithm termed the
Bermanford method (Bellman 1958) is used.
The minimum-cost flow problem assumes that each edge of a directed network,
as shown in Fig. 24.7, is given an integer capacity and a cost resulting from an
Fig. 24.6 Weighted
maximum bipartite matching
Fig. 24.7 Minimum-cost
flow problem