Математичне та програмне забезпечення для розв’язування задачі комівояжера великих розмірностей

Abstract

The Traveling Salesman Problem (TSP) is extensively applied in transportation systems, automated design, testing and manufacturing of integrated circuits, printed circuit boards, laser cutting of plastics and metals, as well as in protein structure research, continuous line drawings, X-ray crystallography and a number of other fields. A significant feature of such problems is their large-scale complexity amounting to over a million points for many of them. The TSP is viewed as an intractable combinatorial problem (discrete optimization), referred to the class of NP-hard problems due to its factorial computational complexity. The computational complexity of existing effective methods is not lower than O(N2), which makes them inappropriate for large scale and very large scale problems. Therefore there is a need for developing methods and an application software system for solving such problems. In order to achieve high computing performance, appropriate for complicated large-scale problems, this dissertation presents a set of specialized decomposition methods adapted to specific types of input data structures and an application software system that enables solving real TSPs, as well as modelling, exploring and integrating new methods. The following tasks were done: the different types of TSP such as uniform and clustered were classified, high quality heuristic methods were chosen as basic, methods of finding the initial solution as well as it’s optimization for large scale TSP with their adaptation to the structure of input data were developed. Software for solving large scale TSP was developed. Experimental investigations of the developed methods were done as well as the comparative analysis of the results and estimated their effectiveness in terms of quality and solving time. Existing methods has been improved as well as new decomposition methods for finding initial solution and solution optimization have been developed. The problem is solved in several steps: partitioning of the input set of points into smaller subsets (≈ 500-2000 points), finding partial high-quality solutions for them within small time frames, merging them into the whole initial solution, and further solution optimization. Developed methods have computational complexity very close to linear. According to the experimental results, the proposed decomposition approaches provide substantial reduction in the run time in comparison with the currently best heuristic Lin-Kernighan-Helsgaun algorithm. Quality loss is negligible. Problem instances up to 107 points were investigated. Developed mathematical methods provided the possibility to develop special software system “VRP Modeler” for large scale TSP solving and experimental research, in which with the purpose of organization of effective calculations it is computer-integrated in the unique complex known existing and developed decomposition methods. Software is developed by author independently in Microsoft Visual Studio 2008 IDE on C++ programming language with the use of methods of the object-oriented programming. Dissertation job performances were applied in the educational process of software department of the Lviv National Polytechnic University and also in the “AR-TRANS” and “SEA Electronics” companies. Developed software system "VRP Modeler" for solving large scale TSP, which is a special software that allows to solve real travelling salesman problems, model, explore and integrate new methods. The methods and tools for clustering of input data, building macroroute, finding the initial solution and its optimization can be applied to a wide range of applications, which used the TSP and those close to it: VLSI optimization, systems and networks on a crystal (SoC and NoC), optimizations of production processes, vehicle routing problems, continuous line drawings et al.В диссертационной работе рассмотрена задача коммивояжера больших размерностей, широко применяемая в транспортных системах, автоматизированном проектировании, тестировании и изготовлении интегрированных схем, производстве печатных плат и других отраслях. Развиты существующие и разработаны новые декомпозиционные методы, в которых задача решается за несколько этапов: разбиение входного множества точек на подмножества ограниченой размерности (≈ 500-2000 точек), для которых получаются высококачественные частичные решения с небольшими временными затратами; сшивания частичных решений в начальное решение, и его улучшение разработанными методами локальной оптимизации. Разработана прикладная программная система "VRP Modeler" для решения ЗК больших размерностей, которая является специальным программным обеспечением, что позволяет решать реальные задачи коммивояжера, их моделировать, исследовать и интегрировать новые методы. Разработанные методы и программные средства кластеризации входных данных, построения макромаршрута, нахождения начального решения и его оптимизации можно применять для широкого круга прикладных задач, где используется ЗК и близкие к ней.У дисертаційній роботі розглянуто задачу комівояжера великих розмірностей, яка має широке прикладне застосування в транспортних системах, автоматизованому проектуванні, тестуванні та виготовленні інтегрованих схем, виробництві друкованих плат та інших галузях. Розвинуто відомі та розроблено нові декомпозиційні методи, в яких задача розв’язується за декілька етапів: розбиття вхідної множини точок на підмножини обмеженої розмірності (≈ 500-2000 точок), для яких отримуються високоякісні часткові розв’язки з невеликими часовими затратами; зшивання часткових розв’язків у початковий розв’язок, та його покращення розробленими методами оптимізації. Розроблено прикладну програмну систему “VRP Modeler” для розв’язування ЗК великих розмірностей, яка є спеціальним програмним забезпеченням, що дає змогу розв’язувати реальні задачі комівояжера, їх моделювати, досліджувати та інтегрувати нові методи. Розроблені методи та програмні засоби кластеризації вхідних даних, побудови макромаршруту, знаходження початкового розв’язку та його оптимізації можна застосовувати для широкого кола прикладних задач, де використовується ЗК та близькі до неї.