An Investigation of the Robustness in the Travelling Salesman Problem Routes Using Special Structured Matrices
Julkaisuvuosi
2020
Tekijät
Aziz, Azmin Azliza; Mousavi Abdehgah, Mohsen; Tavana, Madjid; Niaki, Seyed Taghi Akhavan
Tiivistelmä
In this study, the robustness of the Travelling Salesman Problem (TSP) routes is investigated by recognising the special combinatorial structures of Kalmanson matrices. A recognition algorithm encompassing three procedures based on combinatorial and linear programming (LP) is developed and executed on several randomly generated instances. These procedures produce three lower bounds which provide guarantees on the optimality of the solutions. Computational experiments show that the proposed LP-based procedure performs efficiently well across all problem dimensions and provides the best lower bounds to the TSP. This is supported by an average deviation of less than 7% between the TSP tour lengths and the lower bounds of the Kalmanson matrices.
Näytä enemmänOrganisaatiot ja tekijät
Jyväskylän yliopisto
Mousavi Abdehgah Mohsen
Julkaisutyyppi
Julkaisumuoto
Artikkeli
Emojulkaisun tyyppi
Lehti
Artikkelin tyyppi
Alkuperäisartikkeli
Yleisö
TieteellinenVertaisarvioitu
VertaisarvioituOKM:n julkaisutyyppiluokitus
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäJulkaisukanavan tiedot
Kustantaja
Volyymi
7
Numero
2
Sivut
172-181
ISSN
Julkaisufoorumi
Julkaisufoorumitaso
1
Avoin saatavuus
Avoin saatavuus kustantajan palvelussa
Ei
Rinnakkaistallennettu
Kyllä
Muut tiedot
Tieteenalat
Matematiikka; Tietojenkäsittely ja informaatiotieteet
Avainsanat
[object Object]
Julkaisumaa
Yhdistynyt kuningaskunta
Kustantajan kansainvälisyys
Kansainvälinen
Kieli
englanti
Kansainvälinen yhteisjulkaisu
Kyllä
Yhteisjulkaisu yrityksen kanssa
Ei
DOI
10.1080/23302674.2018.1551584
Julkaisu kuuluu opetus- ja kulttuuriministeriön tiedonkeruuseen
Kyllä