A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
An Investigation of the Robustness in the Travelling Salesman Problem Routes Using Special Structured Matrices (2020)


Aziz, A. A., Mousavi Abdehgah, M., Tavana, M., & Niaki, S. T. A. (2020). An Investigation of the Robustness in the Travelling Salesman Problem Routes Using Special Structured Matrices. International Journal of Systems Science, 7 (2), 172-181. doi:10.1080/23302674.2018.1551584


JYU-tekijät tai -toimittajat


Julkaisun tiedot

Julkaisun kaikki tekijät tai toimittajat: Aziz, Azmin Azliza; Mousavi Abdehgah, Mohsen; Tavana, Madjid; Niaki, Seyed Taghi Akhavan

Lehti tai sarja: International Journal of Systems Science

ISSN: 0020-7721

eISSN: 1464-5319

Julkaisuvuosi: 2020

Volyymi: 7

Lehden numero: 2

Artikkelin sivunumerot: 172-181

Kustantaja: Taylor & Francis

Julkaisumaa: Britannia

Julkaisun kieli: englanti

DOI: http://doi.org/10.1080/23302674.2018.1551584

Avoin saatavuus: Julkaisukanava ei ole avoin

Julkaisu on rinnakkaistallennettu (JYX): https://jyx.jyu.fi/handle/123456789/70087


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.


YSO-asiasanat: lineaarinen optimointi

Vapaat asiasanat: Travelling salesman problem; robustness; special structured matrices; combinatorial; Kalmanson


Liittyvät organisaatiot


OKM-raportointi: Kyllä

Raportointivuosi: 2020

Alustava JUFO-taso: 1


Viimeisin päivitys 2020-18-10 klo 21:05