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).