TSP pertama kali diperkenalkan oleh Rand pada tahun 1948. TSP melibatkan seorang travelling salesman yang harus melakukan kunjungan ke sejumlah kota dalam menjajakan produknya. Rangkaian kota-kota yang dikunjungi harus membentuk suatu jalur sedemikian sehingga kota-kota tersebut hanya boleh dilewati tepat satu kali dan kemudian kembali lagi ke kota awal (untuk setoran ke bosnya, hehe). Maka dari itu, penyelesaian terhadap permasalahan TSP ini membutuhkan optimasi untuk dapat memperoleh jalur terpendek.
Sejarah TSP bisa ditelusur dari Euler yang mempelajari Knight Tour’s Problem (1759), Kirkman yang mempelajari grafik polihedron (1856) maupun Hamilton yang membuat game Icosian (1856) yang bertujuan mencari jalur sirkuit berbasis grafik polihedron yang memenuhi kondisi tertentu [2]. Istilah TSP sendiri diperkirakan berasal dari buku yang diterbitkan oleh seorang veteran salesman sekitar tahun 1930an di Jerman, meski dalam buku ini masalah TSP lebih dibahas dari aspek bisnis dan belum diformulasikan secara matematis.
Bentuk formulasi umum TSP sepertinya mulai dipelajari sekitar tahun 1930 oleh para matematikawan di Vienna dan Harvard, khususnya oleh Karl Menger, yang mendefinisikan problem ini sebagai berikut:
“We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.”(Schrijver, A., 2005, “On the history of combinatorial optimization (till 1960)”, in Handbook of Discrete Optimization, (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, pp. 1—68, 2005
Masalah ini pertama kali dirumuskan sebagai masalah matematika pada tahun 1930 dan merupakan salah satu masalah yang paling intensif dalam mempelajari masalah optimasi, dan digunakan sebagai patokan bagi banyak metode optimasi dalam jumlah besar dengan cara yang tepat, dan metode yang mudah untuk diketahui, sehingga beberapa kasus dengan puluhan ribu kota dapat diselesaikan dengan baik. TSP memiliki beberapa aplikasi, seperti perencanaan, logistik, dan manufaktur. Dalam aplikasi ini, TSP merupakan konsep jarak perjalanan waktu atau biaya. Dalam banyak aplikasi, dapat muncul kendala seperti keterbatasan sumber daya atau waktu.
Travelling Salesman problem (TSP) merupakan masalah kombinasi optimasi dalam operasi penelitian dan teori ilmu komputer. Dengan daftar kota-kota yang akan dikunjungi, cara ini sangat tepat untuk menemukan dengan sesingkat mungkin setiap kota yang akan dikunjungi dengan waktu, dan penggunaan biaya yang tepat, dan efisien.
Traveling Salesman Problem (TSP) adalah suatu permasalahan dimana seorang sales harus melalui semua kota yang ditunjuk dengan jarak yang paling pendek dan setiap kota hanya boleh dilalui satu kali.
Penyelesaian dalam TSP adalah jalur yang dilalui oleh salesman sesuai dengan batasan diatas. Penyelesaian terbaik adalah jalur dengan jarak terpendek. TSP adalah salah satu contoh permasalahan kombinatorial dengankemungkinan penyelesaian yang sangat banyak.
Sumber :
http://tentangpekerjaan.blogspot.com/2015/04/biaya-operasional-kendaraan.html
http://tentangpekerjaan.blogspot.com/2012/08/interaction-theory-new-paradigm-for.html
http://tentangpekerjaan.blogspot.com/2013/01/tsp-touring-united-states-115475-cities.html
http://livooz.blogspot.com/2013/04/travelling-salesman-problem-tsp.html
http://erdhs.blogspot.com/2012/07/travelling-salesman-problem.html
https://ratratr.wordpress.com/2013/02/07/travelling-salesman-problem-dengan-algoritma-clonal-selection/
