An Investigation of the Robustness in the Travelling Salesman Problem Routes Using Special Structured Matrices
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. https://doi.org/10.1080/23302674.2018.1551584
Published inInternational Journal of Systems Science
© 2018 Taylor & Francis
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.
PublisherTaylor & Francis
ISSN Search the Publication Forum0020-7721
Publication in research information system
MetadataShow full item record
Showing items with similar title or keywords.
Decision making in multiobjective optimization problems under uncertainty : balancing between robustness and quality Zhou-Kangas, Yue; Miettinen, Kaisa (Springer, 2019)As an emerging research field, multiobjective robust optimization employs minmax robustness as the most commonly used concept. Light robustness is a concept in which a parameter, tolerable degradations, can be used to ...
Application of a Knowledge Discovery Process to Study Instances of Capacitated Vehicle Routing Problems Kärkkäinen, Tommi; Rasku, Jussi (Springer, 2020)Vehicle Routing Problems (VRP) are computationally challenging, constrained optimization problems, which have central role in logistics management. Usually different solvers are being developed and applied for different ...
Työvuorojen aikataulutuksen optimointi PuLP-kirjaston avulla Hämäläinen, Iikka (2021)Työvuorojen aikatauluttaminen on käytännön ongelma, jonka tekeminen käsin on työlästä. Ongelma voidaan ratkaista kirjoittamalla aikataulujen automatisointiin ja optimointiin soveltuva tietokoneohjelma. Tässä tutkielmassa ...
Sign and rank covariance matrices with applications to multivariate analysis Ollila, Esa (University of Jyväskylä, 2002)
LR-NIMBUS : an interactive algorithm for uncertain multiobjective optimization with lightly robust efficient solutions Koushki, Javad; Miettinen, Kaisa; Soleimani-damaneh, Majid (Springer Science and Business Media LLC, 2022)In this paper, we develop an interactive algorithm to support a decision maker to find a most preferred lightly robust efficient solution when solving uncertain multiobjective optimization problems. It extends the interactive ...