Nilai Shapley sebagai Alokasi Biaya pada Permainan Traveling Salesman Kooperatif dengan Rolling Horizon
Sintia Aurida, Prof. Dr. Salmah, M.Si.
2023 | Skripsi | MATEMATIKA
Permasalahan TSP (Traveling Salesman Problem) merupakan suatu masalah di mana seorang salesman akan mengunjungi beberapa tempat sekaligus dan setiap tempatnya akan dikunjungi tepat satu kali. Permasalahan TSP memiliki tujuan untuk menentukan rute terpendek agar biaya yang dikeluarkan minimum. Pada skripsi ini, dikembangkan permasalahan TSP dengan menambahkan variabel jumlah pesanan sehingga biaya minimumnya akan dipengaruhi panjang rute dan jumlah pesanan yang dibawa oleh salesman. Selanjutnya, permasalahan utama yang akan dibahas adalah mengenai TSG (Traveling Salesman Game) kooperatif yaitu TSP dengan pendekatan teori permainan yang terdiri dari n salesman yang saling bekerjasama untuk melayani semua pesanan dari customer. Anggota koalisi dari salesman yang menjalin kerjasama akan membagi rute perjalanan untuk melayani semua pesanan agar tercipta solusi yang paling optimal. Kemudian, akan ditunjukkan bahwa salesman akan mendapatkan solusi yang lebih optimal saat menjalin kerjasama dibandingkan saat salesman bekerja secara individu. Pada permasalahan TSP klasik, diasumsikan bahwa permintaan pelanggan diketahui sebelum perencanaan. Namun, hal tersebut tidak sesuai dengan situasi nyata karena permintaan pelanggan bisa bertambah saat periode pelayanan. Oleh karena itu, pada skripsi ini masalah TSP kooperatif dimodelkan pada kasus rolling horizon untuk mengatasi permasalahan tersebut. Selain itu, akan dibahas cara membagi nilai solusi optimal kerjasama menggunakan nilai Shapley sehingga didapatkan pembagian biaya secara adil dengan besar penghematan biaya pengeluaran saat kooperatif adalah sama untuk masing-masing salesman.
The Traveling Salesman Problem (TSP) is a problem where a salesman
needs to visit multiple locations, and each location visited exactly once. The goal of
the TSP is to determine the shortest route to minimize the required cost. In this undergraduate thesis, the TSP problem is extended by adding a variable, the number
of orders, which will influence the minimum cost, considering both the length of
the route and the quantity of orders carried by the salesman. Furthermore, the main
problem discussed is the Cooperative Traveling Salesman Game (TSG), which is
a cooperative version of the TSP in game theory that involving n salesmen collaborating to serve all customer orders. Members of the salesmen coalition cooperate
by dividing the travel routes to serve all orders to create the most optimal solution.
Then, it will be shown that salesmen will get more optimal solutions when collaborating compared to when salesmen work individually. In the classic TSP, it is
assumed that customer demands are known before planning. However, this assumption does not align with real-life situations, as customer demands can change during
the service period. Therefore, this thesis models the cooperative TSP problem in the
context of a rolling horizon case to address this issue. Additionally, it discusses how
to distribute the value of the optimal cooperative solution using Shapley values to
ensure a fair cost allocation, with equal cost savings for each salesman when working together.
Kata Kunci : Nilai Shapley, Teori Permainan, Permainan Kooperatif, Traveling Salesman Problem.
