Modified Local Search Heuristics for the Symmetric Traveling Salesman Problem

摘要

?iame straipsnyje yra tiriamos kai kurios euristini? lokaliosios paie?kos (LP) algoritm? modifikacijos (patobulinimai), sprend?iant simetrinio tipo komivoja?ieriaus u?davin? (KU). Patobulinimai daugiausia susij? su i?pl?stini? sprendini? aplink? panaudojimu. Be to, yra nagrin?jamos naujos sprendini? per?jim? aib?s, kurios remiasi i?pl?stin?mis per?jim? formavimo taisykl?mis. Taip pat yra i?bandytas sudaryt? i?pl?stini? algoritm? veikimas, taikant vadinam?j? iteratyviosios lokaliosios paie?kos (ILP) metodik?. Kompiuterini? eksperiment?, atlikt? taikant testinius pavyzd?ius (?gair?mis“), paimtus i? vie?osios elektronin?s KU pavyzd?i? saugyklos (TSPLIB), rezultatai rodo, kad pasiūlyti i?pl?stiniai LP algoritmai, palyginti su ?prastomis LP procedūromis, leid?ia gauti geresn?s kokyb?s sprendinius nelabai padid?jus skai?iavim? laikui.DOI: http://dx.doi.org/10.5755/j01.itc.42.3.1301