Skip to main content
SpringerLink
Log in

The Traveling Salesman Problem and Its Variations

  • Book
  • © 2007

Overview

Editors:
  1. Gregory Gutin

    1. Royal Holloway, University of London, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Abraham P. Punnen

    1. University of New Brunswick, Saint John, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Provides the state of the art in theory and algorithms for the traveling salesman problem (TSP)
  • Written by reputable researchers, covering all important areas of study on TSP
  • Intended for researchers, practitioners, and academicians in mathematics, computer science, and operations research
  • Appropriate as a reference work or as a main or supplemental textbook in graduate and senior undergraduate courses and projects

Part of the book series: Combinatorial Optimization (COOP, volume 12)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 259.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 329.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 329.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (16 chapters)

  1. Front Matter

    Pages i-xviii
    Download chapter PDF

  2. The Traveling Salesman Problem: Applications, Formulations and Variations

    • Abraham P. Punnen
    Pages 1-28

  3. Polyhedral Theory and Branch-and-Cut Algorithms for the Symmetric TSP

    • Denis Naddef
    Pages 29-116

  4. Polyhedral Theory for the Asymmetric Traveling Salesman Problem

    • Egon Balas, Matteo Fischetti
    Pages 117-168

  5. Exact Methods for the Asymmetric Traveling Salesman Problem

    • Matteo Fischetti, Andrea Lodi, Paolo Toth
    Pages 169-205

  6. Approximation Algorithms for Geometric TSP

    • Sanjeev Arora
    Pages 207-221

  7. Exponential Neighborhoods and Domination Analysis for the TSP

    • Gregory Gutin, Anders Yeo, Alexei Zverovitch
    Pages 223-256

  8. Probabilistic Analysis of the TSP

    • A. M. Frieze, J. E. Yukich
    Pages 257-307

  9. Local Search and Metaheuristics

    • César Rego, Fred Glover
    Pages 309-368

  10. Experimental Analysis of Heuristics for the STSP

    • David S. Johnson, Lyle A. McGeoch
    Pages 369-443

  11. Experimental Analysis of Heuristics for the ATSP

    • David S. Johnson, Gregory Gutin, Lyle A. McGeoch, Anders Yeo, Weixiong Zhang, Alexei Zverovitch
    Pages 445-487

  12. Polynomially Solvable Cases of the TSP

    • Santosh N. Kabadi
    Pages 489-583

  13. The Maximum TSP

    • Alexander Barvinok, Edward Kh. Gimadi, Anatoliy I. Serdyukov
    Pages 585-607

  14. The Generalized Traveling Salesman and Orienteering Problems

    • Matteo Fischetti, Juan-José Salazar-Gonzalez, Paolo Toth
    Pages 609-662

  15. The Prize Collecting Traveling Salesman Problem and its Applications

    • Egon Balas
    Pages 663-695

  16. The Bottleneck TSP

    • Santosh N. Kabadi, Abraham P. Punnen
    Pages 697-735

  17. TSP Software

    • Andrea Lodi, Abraham P. Punnen
    Pages 737-749

  18. Back Matter

    Pages 750-830
    Download chapter PDF
Back to top

Keywords

About this book

This volume, which contains chapters written by reputable researchers, provides the state of the art in theory and algorithms for the traveling salesman problem (TSP). The book covers all important areas of study on TSP, including polyhedral theory for symmetric and asymmetric TSP, branch and bound, and branch and cut algorithms, probabilistic aspects of TSP, thorough computational analysis of heuristic and metaheuristic algorithms, theoretical analysis of approximation algorithms, including the emerging area of domination analysis of algorithms, discussion of TSP software and variations of TSP such as bottleneck TSP, generalized TSP, prize collecting TSP, maximizing TSP, orienteering problem, etc.

Audience

This book is intended for researchers, practitioners, and academicians in mathematics, computer science, and operations research. It is appropriate as a reference work or as a main or supplemental textbook in graduate and senior undergraduate courses and projects.

Editors and Affiliations

  • Royal Holloway, University of London, UK

    Gregory Gutin

  • University of New Brunswick, Saint John, Canada

    Abraham P. Punnen

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation