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"
}