Publication detail

Solving the Travelling Salesman Problem Using GAMS

NETUŠIL, Z.

English title

Solving the Travelling Salesman Problem Using GAMS

Type

conference paper

Language

en

Original abstract

The Travelling Salesman Problem (TSP) is well known problem consisting of designing the optimal route for a salesman originating and terminating at the depot. The salesman has to visit each customer exactly once and the total distance travelled has to be minimized. TSP is supposed to be NP-hard which roughly means that the computation time needed by an exact algorithm rises exponentially with the length of input (i.e. --- in the case of TSP --- the number of customers). This paper discusses how this NP-hard problem can be solved is optimization tool GAMS and purposes results.

English abstract

The Travelling Salesman Problem (TSP) is well known problem consisting of designing the optimal route for a salesman originating and terminating at the depot. The salesman has to visit each customer exactly once and the total distance travelled has to be minimized. TSP is supposed to be NP-hard which roughly means that the computation time needed by an exact algorithm rises exponentially with the length of input (i.e. --- in the case of TSP --- the number of customers). This paper discusses how this NP-hard problem can be solved is optimization tool GAMS and purposes results.

Keywords in English

travelling salesman problem, NP-hard, GAMS, optimization

Released

06.02.2007

Publisher

VŠB - TECHNICKÁ UNIVERZITA OSTRAVA

Location

Ostrava, ČR

ISBN

978-80-248-1649-4

Book

Sborník z 16. semináře Moderní matematické metody v inženýrství

Edition number

1

Pages from–to

216–220

Pages count

5

BIBTEX


@inproceedings{BUT27893,
  author="Zdeněk {Netušil},
  title="Solving the Travelling Salesman Problem Using GAMS",
  booktitle="Sborník z 16. semináře Moderní matematické metody v inženýrství",
  year="2007",
  month="February",
  pages="216--220",
  publisher="VŠB - TECHNICKÁ UNIVERZITA OSTRAVA",
  address="Ostrava, ČR",
  isbn="978-80-248-1649-4"
}