EVOLUTIONARY POPULATION METHOD FOR SOLVING THE TRANSPORT PROBLEM

Abstract

The paper considers an evolutionary population method for solving a transport problem
based on the metaheuristics of crystallization of a placer of alternatives. We study a closed (or
balanced) model of the transport problem: the amount of cargo from suppliers is equal to the total
amount of needs at destinations. The goal of optimization is to minimize the cost (achieving a minimum
of transportation costs) or distances and the criterion of time (a minimum of time is spent on
transportation). The metaheuristics of the crystallization of a placer of alternatives is based on a
strategy based on remembering and repeating past successes. The strategy emphasizes «collective
memory», which refers to any kind of information that reflects the past history of development and
is stored independently of individuals. An ordered sequence Dk of routes is considered as a code
for solving the transport problem. The objects are routes, the alternatives are the set of positions P
in the list, where np is the number of positions in the list Dk. The set of objects Dk corresponds to
the set of all routes. The set of alternative states P of the object corresponds to the set of alternative
options for placing the object in the list Dk. The operation of the population evolutionary algorithm
for the crystallization of a placer of alternatives is based on a collective evolutionary
memory called a placer of alternatives. A scattering of solution alternatives is a data structure
used as a collective evolutionary memory that carries information about the solution, including
information about the realized alternatives of agents in this solution and about the usefulness of
the solution. A constructive algorithm for the formation of a reference plan by decoding the list Dk
has been developed. At each step t, the problem of choosing the next route in the sequence Dk and
determining the amount of cargo transported from the point of departure Ai to the point of destination
Bj along this route is solved. The developed algorithm is population-based, implementing the
strategy of random directed search. Each agent is a code for some solution of the transport problem.
At the first stage of each iteration l, a constructive algorithm based on the integral placer of
alternatives generates nk decision codes Dk. The formation of each decision code Dk is performed
sequentially in steps by sequentially selecting an object and position. For the constructed solution
code Dk, the solution estimate ξk and the utility estimate δk are calculated. An individual scattering
of alternatives Rk is formed and a transition to the construction of the next solution code is formed.
At the second stage of the iteration, the integral placer of alternatives formed at previous iterations
from l to (l-1) is summed with all individual placers of alternatives formed at iteration l.
At the third stage of iteration l, all integral utility estimates r*
αβ of the integral placer of alternatives
R*(l) are reduced by δ*. The algorithm for solving the transport problem was implemented in
C++ in the Windows environment. Comparison of the values of the criterion, on test examples,
with a known optimum showed that in 90% of the examples the solution obtained was optimal, in
2% of the examples the solutions were 5% worse, and in 8% of the examples the solutions differed
by less than 2%. The time complexity of the algorithm, obtained experimentally, lies within O(n2).