Sequential and parallel local search for the time-constrained traveling salesman problem

G.A.P. Kindervater, M.W.P. Savelsbergh, J.K. Lenstra

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)

    Abstract

    Local search has proven to be an effective solution approach for the traveling salesman problem. We consider variants of the TSP in which each city is to be visited within one or more given time windows. The travel times are symmetric and satisfy the triangle inequality; the objective is to minimize the tour duration. We develop efficient sequential and parallel algorithms for the verification of local optimality of a tour with respect to k-exchanges.
    Original languageEnglish
    Pages (from-to)211-225
    Number of pages15
    JournalDiscrete Applied Mathematics
    Volume42
    Issue number2-3
    DOIs
    Publication statusPublished - 1993

    Fingerprint

    Dive into the research topics of 'Sequential and parallel local search for the time-constrained traveling salesman problem'. Together they form a unique fingerprint.

    Cite this