PERMAINAN TRAVELING SALESMAN DENGAN NILAI SHAPLEY SEBAGAI ALOKASI BIAYA

RIZA RAYHAN WAJDI, Prof. Dr. Salmah, M.Si.

2018 | Skripsi | S1 MATEMATIKA

Pada skripsi ini akan dibahas tentang koalisi di antara pemain (kota-kota) dalam menemukan rute perjalanan yang akan dilalui oleh suatu objek--baik seseorang atau sebuah mesin. Objek ini ditugaskan untuk mengunjungi beberapa kota tujuan dengan memperhatikan beberapa kendala. Suatu objek harus mengunjungi setiap kota tujuan dan tidak boleh kembali ke kota yang sudah dikunjungi; itu berarti setiap kota tujuan hanya dikunjungi sekali saja. Oleh karena itu, objek harus mengawali dan mengakhiri perjalanannya dari kota yang sama. Tujuan Traveling Salesman Game (TSG) adalah untuk meminimumkan biaya perjalanan suatu objek dengan mempertimbangkan beberapa kendala. Suatu koalisi sangat dimungkinkan akan memunculkan konflik. Salah satu faktor penyebab terjadinya konflik adalah biaya. Ketidakpuasan antar pemain dalam mengalokasikan biaya akan menjadi penyebab konflik yang harus diselesaikan. Pada skripsi ini, algoritma Nearest-Neighbor akan digunakan dalam mencari rute perjalanan. Kemudian masalah alokasi biaya akan diselesaikan menggunakan nilai Shapley.

In this paper, we will discuss about coalition amongst players (towns) in finding route which will be passed by an object--either a person or a machine. This object is assigned to visit diverse towns within concerning possible constrains. The object must visit each destined town and not be allowed to go back to the previous ones; that means each town must be visited only once. Therefore, the object starts and finishes the route from the same town. The aim of Traveling Salesman Game (TSG) is to minimize the travel cost spent by the object's within calculated constrains. A coalition is very likely to cause conflicts. One of the conflict causes is travel cost. A conflict cause by cost allocation must be solved to eliminate players dissatisfaction. This paper, Nearest-Neighbor algorithm will be used to find the best route. Then cost allocation will be solved by using Shapley value.

Kata Kunci : teori permainan, game theory, traveling salesman game