Information Exploration for Discrete Optimization Problems such as Multiple Traveling Salesman Problems

The problem of analysis and synthesis of optimal flows like the flow of resources, information flow etc. have a vital importance for the real systems. As a rule, the mathematical models are given by different types of nets. These nets are graph structures with marked vertices and edges. They yield a number of Discrete Optimization (DO) problems most of which are NP-complete. If the information connected with a given DO problems is taken into account, then it is possible to design approximate and heuristic algorithms capable to manipulate complex large-scale data. The Multiple Traveling Salesman Problem (MTSP) and its more generalized version the Vehicle Routing Problem (VRP) are the most typical test problems. They are connected with the problems of the shortest path, Hamiltonian circuit, vertex-edge transformation, maximum cut etc. Real situations contain similar, rational, extreme statements of problems, which are important for both exact and approximate solutions. Approximate solutions are based on combinations of local heuristic algorithms. Extremal problems of analysis and synthesis on graphs should take into account knowledge, information, facts and precedents. A variety of problems is defined by the type of graphs simulating resource networks; the structure of graphs, their dimension, the possibility of decomposition; the nature of the objective functions and completeness of information concerning coefficients for the criteria; the ability to represent restrictions on the network as disjunctive normal forms. The problem is complicated by usage of additional information (knowledge) for restrictions and requires adaptation of existing algorithms.

In this work on the base of knowledge-oriented approach, we give an overview of existing results for discrete optimization problems such as TSP with restrictions, formulate new problems, and suggest algorithms to solve them. The preliminary classification is given. It is shown that the knowledge consideration about the network structure, salesmen objectives, and prohibitions leads to decomposition (cluster) algorithms. The further development is associated with the approach based on the usage of controlled intelligent agents (in particular, salesman agents). We consider the generalized multi-agent traveler salesmen problems taking into account a variety of knowledge, information, data needed for both intelligent agents control and local agent control, the algorithms of decomposition, clustering, analysis and synthesis of networks. The preliminary numerical calculations confirm a necessity in a wide range of algorithms involved in the optimal composition of met heuristics and filling control systems.

Keywords: Multiple Traveling Salesman Problem, knowledge-oriented models, approximation algorithms.

UDC: 
519.16