|
View: |
Part 1: Document Description
|
|
Citation |
|
|---|---|
|
Title: |
Solutions to the symmetric traveling salesman problem for 1354 locations in the Kyiv region: Concorde solver |
|
Identification Number: |
doi:10.48788/DVUA/7P2OE6 |
|
Distributor: |
DataverseUA |
|
Date of Distribution: |
2025-12-13 |
|
Version: |
1 |
|
Bibliographic Citation: |
Anisa, Kasim; Alexandr, Palagin; Petro, Stetsyuk; Olha, Khomiak, 2025, "Solutions to the symmetric traveling salesman problem for 1354 locations in the Kyiv region: Concorde solver", https://doi.org/10.48788/DVUA/7P2OE6, DataverseUA, V1, UNF:6:LkepojHDzM92QCMow9MEvg== [fileUNF] |
|
Citation |
|
|
Title: |
Solutions to the symmetric traveling salesman problem for 1354 locations in the Kyiv region: Concorde solver |
|
Identification Number: |
doi:10.48788/DVUA/7P2OE6 |
|
Authoring Entity: |
Anisa, Kasim (V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine) |
|
Alexandr, Palagin (V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine) |
|
|
Petro, Stetsyuk (V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine) |
|
|
Olha, Khomiak (V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine) |
|
|
Distributor: |
DataverseUA |
|
Access Authority: |
Anisa, Kasim |
|
Depositor: |
Anisa, Kasim |
|
Date of Deposit: |
2025-12-11 |
|
Holdings Information: |
https://doi.org/10.48788/DVUA/7P2OE6 |
|
Study Scope |
|
|
Keywords: |
Computer and Information Science, symmetric traveling salesman problem, NEOS server, Concorde solver, Lin-Kernighan algorithm, settlements of Kyiv region |
|
Abstract: |
The dataset includes geographic and Euclidean coordinates of 1354 locations in Kyiv region (including Kyiv city) and contains both input and output data for solving the symmetric traveling salesman problem (STSP) using Euclidean (L2) and Manhattan (L1) metrics. The dataset is intended for testing, validation and comparative analysis of algorithms for solving STSP using Concorde solver with different metrics. Both exact algorithms and Lin-Kernighan heuristic approach are supported. The dataset is suitable for use in educational purposes, scientific research on combinatorial optimization, as well as in modeling transport logistics problems and integration with applied geographic information systems. |
|
Methodology and Processing |
|
|
Sources Statement |
|
|
Data Access |
|
|
Other Study Description Materials |
|
|
File Description--f524 |
|
|
File: Kyiv_region_1354.tab |
|
|
|
|
Notes: |
UNF:6:LkepojHDzM92QCMow9MEvg== |
|
List of Variables: |
|
|
Variables |
|
|
f524 Location: |
Variable Format: character Notes: UNF:6:KnUknpHcBfS+ispHM6sk1A== |
|
f524 Location: |
Summary Statistics: Valid 1354.0; Min. 49.19695; StDev 0.540763989732463; Mean 50.2555353028065; Max. 51.48571 Variable Format: numeric Notes: UNF:6:MakzhMfOBdItDa7B03db7g== |
|
f524 Location: |
Summary Statistics: StDev 0.673929013383302; Mean 30.43615229689808; Valid 1354.0; Min. 29.27393; Max. 32.15149 Variable Format: numeric Notes: UNF:6:xGnilk4YIYAuNyNGw+aQAg== |
|
f524 Location: |
Summary Statistics: Max. 112868.0; Mean -8745.031019202366; Min. -91144.0; Valid 1354.0; StDev 47779.810918501506 Variable Format: numeric Notes: UNF:6:bBt4nhtFTsj5wNW8Zs6Gng== |
|
f524 Location: |
Summary Statistics: Min. -138408.0; Valid 1354.0; StDev 60197.58175410996; Mean -20566.80945347121; Max. 116376.0; Variable Format: numeric Notes: UNF:6:x4dlDhDKrr/y/t6CiJsdsg== |
|
Label: |
kr1354_L1.tsp |
|
Text: |
File in TSPLIB format for L1 metric, structure similar to file for L2 metric, however distances are calculated using Manhattan metric (EDGE_WEIGHT_TYPE: MAN_2D). |
|
Notes: |
application/octet-stream |
|
Label: |
kr1354_L2.tsp |
|
Text: |
File in TSPLIB format for the L2 metric, containing a description of the traveling salesman problem, including location coordinates, with an indication of the norm type EDGE_WEIGHT_TYPE: EUC_2D. |
|
Notes: |
application/octet-stream |
|
Label: |
LinKernigan_tour_kr1354_L1.txt |
|
Text: |
Approximate route for L1-metric obtained by the LK algorithm. Intended for comparison with the exact solution. |
|
Notes: |
text/plain |
|
Label: |
LinKernigan_tour_kr1354_L2.txt |
|
Text: |
The result of the heuristic solution of the problem for the L2 metric using the Lin-Kernighan (LK) algorithm. The route representation format is the same as in the optimal tour file. |
|
Notes: |
text/plain |
|
Label: |
opt_tour_kr1354_L1.txt |
|
Text: |
Text file with the optimal route found by Concorde for the L1 metric. Represents the optimal tour obtained by the exact solution algorithm. |
|
Notes: |
text/plain |
|
Label: |
opt_tour_kr1354_L2.txt |
|
Text: |
Text file with the optimal route found by Concorde for the L2 metric. Each line is a pair of vertices of the traversal order and the length between them, rounded to an integer value. |
|
Notes: |
text/plain |
|
Label: |
viz_LinKernigan_tour_kr1354_L1.png |
|
Text: |
Graphical interpretation of the approximate route for the L1 metric obtained by the LK algorithm. Serves for visual analysis of deviation from the optimal route. |
|
Notes: |
image/png |
|
Label: |
viz_LinKernigan_tour_kr1354_L2.png |
|
Text: |
Visualization of the route constructed using the Lin-Kernighan algorithm for L2 metrics. Allows to visually assess the quality of the heuristic solution. |
|
Notes: |
image/png |
|
Label: |
viz_opt_tour_kr1354_L1.png |
|
Text: |
Graphical visualization of the exact route for the Manhattan metric. Displays the sequence of vertex traversal in a planar (2D) coordinate system. |
|
Notes: |
image/png |
|
Label: |
viz_opt_tour_kr1354_L2.png |
|
Text: |
Graphical visualization of the route corresponding to the optimal tour for the Euclidean metric. Constructed based on coordinates from the corresponding input file. |
|
Notes: |
image/png |
|
Label: |
xy_int_1354_L2_L1.txt |
|
Text: |
Integer (rounded to meters) Euclidean coordinates of 1354 locations. The first line in the file indicates the number of locations. The file is intended for submission to the NEOS server via the web interface of the Concorde program (L2 and L1 modes). |
|
Notes: |
text/plain |