Solving the k-best traveling salesman problem

E.S. van der Poort, M. Libura, G. Sierksma, J.A.A. van der Veen

    Research output: Contribution to journal › Article › Academic › peer-review

    17 Citations (Scopus)

    Abstract

    Although k-best solutions for polynomial solvable problems are extensively studied in the literature not much is known for NP-hard problems. In this paper we design algorithms for finding sets of k-best solutions to the Traveling Salesman Problem (TSP) for some positive integer k. It will be shown that a set of k-best Hamiltonian tours in a weighted graph can be determined by applying the so-called partitioning algorithms and by algorithms based on modifications of solution methods like branch-and-bound. In order to study the effectiveness of these algorithms the time for determining a set of k-best solutions is investigated for a number of instances in Reinelt's TSPLIB library. It appears that the time required to find a set of k-best tours grows rather slowly in k. Furthermore the results of numerical experiments show that the difference in length between a longest and a shortest tour in the set of k-best solutions grows only slowly in k and that also the 'structure' of the tours in the set of k-best tours is quite robust.Scope and purposeAfter having solved an optimization problem, it is often the case that one still must verify whether the optimal solution satisfies some additional restrictions that are not included in the original model. Such conditions are called ''subtle conditions''. In the case of subtle conditions, it is particularly of interest to have a set of k-best solutions in order to see which of the solutions in that set satisfy the extra conditions and how high the ''price'' is for incorporating such conditions.Algorithms for finding sets of k-best solutions have mainly been studied in the literature for polynomially solvable combinatorial optimization problems. Little is known on algorithms for finding k-best solutions for NP-hard combinatorial optimization problems. In this paper, we study algorithms for finding k-best solutions for one of the most notorious NP-hard problems, namely the Traveling Salesman Problem (TSP). Properties of the sets of k-best solutions for the TSP, such as the increase in tour length and the number of edges that the k-best solutions have in common or differ in, are discussed in detail.
    Original languageEnglish
    Pages (from-to)409-425
    JournalComputers and Operations Research
    Volume26
    Issue number4
    DOIs
    Publication statusPublished - 1999

    Fingerprint

    Traveling salesman problem
    Travelling salesman problems
    Combinatorial optimization
    Computational complexity
    NP-hard Problems
    Combinatorial Optimization Problem
    Hamiltonians
    Algorithm Design
    Branch-and-bound
    Weighted Graph
    Polynomials
    Partitioning
    NP-complete problem
    Optimal Solution
    Numerical Experiment
    Verify
    Optimization Problem
    Restriction
    NP-hard
    Optimization problem

    Cite this

    van der Poort, E. S., Libura, M., Sierksma, G., & van der Veen, J. A. A. (1999). Solving the k-best traveling salesman problem. Computers and Operations Research, 26(4), 409-425. https://doi.org/10.1016/S0305-0548(98)00070-7
    van der Poort, E.S. ; Libura, M. ; Sierksma, G. ; van der Veen, J.A.A. / Solving the k-best traveling salesman problem. In: Computers and Operations Research. 1999 ; Vol. 26, No. 4. pp. 409-425.
    @article{d5eb43e5db8e4735a4d95fae73cd6b78,
    title = "Solving the k-best traveling salesman problem",
    abstract = "Although k-best solutions for polynomial solvable problems are extensively studied in the literature not much is known for NP-hard problems. In this paper we design algorithms for finding sets of k-best solutions to the Traveling Salesman Problem (TSP) for some positive integer k. It will be shown that a set of k-best Hamiltonian tours in a weighted graph can be determined by applying the so-called partitioning algorithms and by algorithms based on modifications of solution methods like branch-and-bound. In order to study the effectiveness of these algorithms the time for determining a set of k-best solutions is investigated for a number of instances in Reinelt's TSPLIB library. It appears that the time required to find a set of k-best tours grows rather slowly in k. Furthermore the results of numerical experiments show that the difference in length between a longest and a shortest tour in the set of k-best solutions grows only slowly in k and that also the 'structure' of the tours in the set of k-best tours is quite robust.Scope and purposeAfter having solved an optimization problem, it is often the case that one still must verify whether the optimal solution satisfies some additional restrictions that are not included in the original model. Such conditions are called ''subtle conditions''. In the case of subtle conditions, it is particularly of interest to have a set of k-best solutions in order to see which of the solutions in that set satisfy the extra conditions and how high the ''price'' is for incorporating such conditions.Algorithms for finding sets of k-best solutions have mainly been studied in the literature for polynomially solvable combinatorial optimization problems. Little is known on algorithms for finding k-best solutions for NP-hard combinatorial optimization problems. In this paper, we study algorithms for finding k-best solutions for one of the most notorious NP-hard problems, namely the Traveling Salesman Problem (TSP). Properties of the sets of k-best solutions for the TSP, such as the increase in tour length and the number of edges that the k-best solutions have in common or differ in, are discussed in detail.",
    author = "{van der Poort}, E.S. and M. Libura and G. Sierksma and {van der Veen}, J.A.A.",
    year = "1999",
    doi = "10.1016/S0305-0548(98)00070-7",
    language = "English",
    volume = "26",
    pages = "409--425",
    journal = "Computers and Operations Research",
    issn = "0305-0548",
    publisher = "Elsevier",
    number = "4",

    }

    van der Poort, ES, Libura, M, Sierksma, G & van der Veen, JAA 1999, 'Solving the k-best traveling salesman problem' Computers and Operations Research, vol. 26, no. 4, pp. 409-425. https://doi.org/10.1016/S0305-0548(98)00070-7

    Solving the k-best traveling salesman problem. / van der Poort, E.S.; Libura, M.; Sierksma, G.; van der Veen, J.A.A.

    In: Computers and Operations Research, Vol. 26, No. 4, 1999, p. 409-425.

    Research output: Contribution to journal › Article › Academic › peer-review

    TY - JOUR

    T1 - Solving the k-best traveling salesman problem

    AU - van der Poort, E.S.

    AU - Libura, M.

    AU - Sierksma, G.

    AU - van der Veen, J.A.A.

    PY - 1999

    Y1 - 1999

    N2 - Although k-best solutions for polynomial solvable problems are extensively studied in the literature not much is known for NP-hard problems. In this paper we design algorithms for finding sets of k-best solutions to the Traveling Salesman Problem (TSP) for some positive integer k. It will be shown that a set of k-best Hamiltonian tours in a weighted graph can be determined by applying the so-called partitioning algorithms and by algorithms based on modifications of solution methods like branch-and-bound. In order to study the effectiveness of these algorithms the time for determining a set of k-best solutions is investigated for a number of instances in Reinelt's TSPLIB library. It appears that the time required to find a set of k-best tours grows rather slowly in k. Furthermore the results of numerical experiments show that the difference in length between a longest and a shortest tour in the set of k-best solutions grows only slowly in k and that also the 'structure' of the tours in the set of k-best tours is quite robust.Scope and purposeAfter having solved an optimization problem, it is often the case that one still must verify whether the optimal solution satisfies some additional restrictions that are not included in the original model. Such conditions are called ''subtle conditions''. In the case of subtle conditions, it is particularly of interest to have a set of k-best solutions in order to see which of the solutions in that set satisfy the extra conditions and how high the ''price'' is for incorporating such conditions.Algorithms for finding sets of k-best solutions have mainly been studied in the literature for polynomially solvable combinatorial optimization problems. Little is known on algorithms for finding k-best solutions for NP-hard combinatorial optimization problems. In this paper, we study algorithms for finding k-best solutions for one of the most notorious NP-hard problems, namely the Traveling Salesman Problem (TSP). Properties of the sets of k-best solutions for the TSP, such as the increase in tour length and the number of edges that the k-best solutions have in common or differ in, are discussed in detail.

    AB - Although k-best solutions for polynomial solvable problems are extensively studied in the literature not much is known for NP-hard problems. In this paper we design algorithms for finding sets of k-best solutions to the Traveling Salesman Problem (TSP) for some positive integer k. It will be shown that a set of k-best Hamiltonian tours in a weighted graph can be determined by applying the so-called partitioning algorithms and by algorithms based on modifications of solution methods like branch-and-bound. In order to study the effectiveness of these algorithms the time for determining a set of k-best solutions is investigated for a number of instances in Reinelt's TSPLIB library. It appears that the time required to find a set of k-best tours grows rather slowly in k. Furthermore the results of numerical experiments show that the difference in length between a longest and a shortest tour in the set of k-best solutions grows only slowly in k and that also the 'structure' of the tours in the set of k-best tours is quite robust.Scope and purposeAfter having solved an optimization problem, it is often the case that one still must verify whether the optimal solution satisfies some additional restrictions that are not included in the original model. Such conditions are called ''subtle conditions''. In the case of subtle conditions, it is particularly of interest to have a set of k-best solutions in order to see which of the solutions in that set satisfy the extra conditions and how high the ''price'' is for incorporating such conditions.Algorithms for finding sets of k-best solutions have mainly been studied in the literature for polynomially solvable combinatorial optimization problems. Little is known on algorithms for finding k-best solutions for NP-hard combinatorial optimization problems. In this paper, we study algorithms for finding k-best solutions for one of the most notorious NP-hard problems, namely the Traveling Salesman Problem (TSP). Properties of the sets of k-best solutions for the TSP, such as the increase in tour length and the number of edges that the k-best solutions have in common or differ in, are discussed in detail.

    U2 - 10.1016/S0305-0548(98)00070-7

    DO - 10.1016/S0305-0548(98)00070-7

    M3 - Article

    VL - 26

    SP - 409

    EP - 425

    JO - Computers and Operations Research

    JF - Computers and Operations Research

    SN - 0305-0548

    IS - 4

    ER -

    van der Poort ES, Libura M, Sierksma G, van der Veen JAA. Solving the k-best traveling salesman problem. Computers and Operations Research. 1999;26(4):409-425. https://doi.org/10.1016/S0305-0548(98)00070-7

    Access to Document