EXAMINATION OF THE TRAVELLING SALESMAN PROBLEM WITH GAME THEORY COST ALLOCATION METHODS

Abstract

In this study, travelling salesman problem (TSP), which is one of the Integer Programming models, is used. The purpose in TSP is to find the shortest way to return to the starting point by going to each point only once from the points to be made, in order to make the works more efficient and not create extra cost in situations such as distribution, supply and logistics. While calculating this route, the cost to be obtained as a result of the tour should be lower than all other routes. Then, cost sharing related to the problem is allocated by using cooperative game theory. In the event that players (firms) share a coalition between them, the cost of each player is obtained by two different cost allocation methods, Shapley value and nucleolus methods. Comparing the numerical results obtained, it is observed that the Shapley value has a lower cost compared to the nucleolus method and the cost reduction rates of the three players were calculated as 47.04%, 48.74%, 25.91%, respectively.

Keywords

• Integer Programming
• Cooperative Game Theory
• Travelling Salesman Problem

GEZGİN SATICI PROBLEMİNİN OYUN TEORİSİ MALİYET TAHSİS YÖNTEMLERİ İLE İNCELENMESİ

Abstract

Bu çalışmada, Tamsayılı Programlama modellerinden biri olan gezgin satıcı problemi (GSP) kullanılmıştır. GSP’de amaç; dağıtım, tedarik, lojistik vb. durumlarda işlerin daha verimli olabilmesi ve fazladan maliyet oluşturmaması için gidilecek olan noktalardan her bir noktaya yalnızca bir kez uğrayarak en kısa yoldan başlangıç noktasına geri dönülmesidir. Bu rota hesaplanırken tur sonucunda elde edilecek maliyet diğer tüm rotalardan daha düşük olmalıdır. Problemle ilgili maliyet paylaşımı işbirlikçi oyun teorisi kullanılarak tahsis edilmiştir. Çalışmadan oyuncuların (firmaların) aralarında koalisyon kurarak maliyet paylaşımı yapmaları halinde her oyuncunun maliyetleri iki farklı maliyet tahsis yöntemi olan Shapley değeri ve nükleolus yöntemleri ile elde edilmiştir. Elde edilen sayısal sonuçlar karşılaştırıldığında Shapley değerinin nükleolus yöntemine kıyasla daha düşük maliyete sahip olduğu gözlemlenmiş ve üç oyuncunun sırasıyla maliyet azalma oranları %47,04, %48,74, %25,91 olarak hesaplanmıştır.

Keywords

• İşbirlikçi Oyun Teorisi
• Tamsayılı Programlama
• Gezgin Satıcı Problemi

References

1. Ali, I.M., Essam, D., Kasmarik, K., 2020. A Novel Design of Differential Evolution for Solving Discrete Traveling Salesman Problems. Swarm and Evolutionary Computation, 52.
2. Bai, J., Jang, G.K., Chen, Y.W., Hu, L.S., Pan, C.C., 2013. A Model Induced Max-Min Ant Colony Optimization for Asymmetric Traveling Salesman Problem. Applied Soft Computing, 13, 1365–1375
3. Bakır, M.A., 2003. Tamsayılı Programlama Teori, Modeller ve Algoritmalar, Nobel Yayın Dağıtım, Ankara.
4. Baki, M.F., 2006. A New Asymmetric Pyramidally Solvable Class of the Traveling Salesman Problem. Operations Research Letters 34, 613–620.
5. Berger, S., Bierwirth, C., 2010. Solutions to the Request Reassignment Problem in Collaborative Carrier Networks. Transportation Research, Part E, 46 (5) 627–638.
6. Bläser, M., Ram, L.S., 2008. Approximately Fair Cost Allocation in Metric Traveling Salesman Games. Theory of Computing Systems, 43 (1) 19–37.
7. Branzei, R., Dimitrov, D., Tijs, S., 2005. Models in Cooperative Game Theory. Springer-Verlag Berlin Heidelberg, 556, VIII, 135.
8. Caprara, A., Letchford, A.N., 2010. New Techniques for Cost Sharing in Combinatorial Optimization Games. Mathematical Programming, 124 (1–2) 93–118.

9. Ceran, Y., Alagöz, A., 2007. Lojistik Maliyet Yönetimi: Lojistik Maliyetler Ve Lojistik Maliyet Muhasebesi. Yönetim Bilimleri Dergisi (Journal of Administrative Sciences), 5 (2).
10. Derks, J., Kuipers, J., 1997. On the Core of Routing Games. International Journal of Game Theory, 26 (2) 193–205.
11. Dror, M., 1990. Cost allocation: The Traveling Salesman, Binpacking, and the Knapsack. Applied Mathematics and Computation, 35 (2) 191–207.
12. Engevall, S., Göthe-Lundgren, M., Värbrand, P., 2004. The Heterogeneous Vehicle Routing Game. Transportation Science, 38 (1) 71–85.
13. Estévez-Fernández, A., Borm, P., Meertens, M., Reijnierse, H., 2009. On the Core of Routing Games With Revenues. International Journal of Game Theory, 38 (2) 291–304.
14. Faigle, U., Fekete, S.P., Hochstättler, W., Kern, W., 1998. On Approximately Fair Cost Allocation in Euclidean TSP Games. OR Spektrum, 20 (1) 29–37.
15. Fishburn, P., Pollak, H., 1983. Fixed-Route Cost Allocation. American Mathematical Monthly, 90 (6) 366–378.
16. Guajardo, M., Jörnsten, K., 2015. Common Mistakes in Computing the Nucleolus. European Journal of Operational Research, 241, 931–935.
17. Guajardo, M., Rönnkvist, M., 2016. A Review on Cost Allocation Methods in Collaborative Transportation. International Transactions in Operational Research, 23 (3), 371-392.
18. Ha, K.M., Deville, Y., Pham, Q.D., Ha, M.H., 2018. On the Min-Cost Traveling Salesman Problem with Drone. Transportation Research, Part C, 86, 597–621.
19. Hausken, K., Mohr, M., 2001. The Value of a Player in n-Person Games. Social Choice and Welfare, 18 (3), 465-483.
20. Kendal, G., Li, J., 2013. Competitive Gravelling Salesmen Problem: A Hyper-Heuristic Approach. Journal of the Operational Research Society, 64 (2), 208-216.
21. Kimms, A., Kozeletskyi, I., 2016a. Core Based Cost Allocation in the Cooperative Traveling Salesman Problem. European Journal of Operational Research, 248(3), 910–916.
22. Kimms, A., Kozeletskyi, I., 2016b. Shapley Value Based Cost Allocation in the Cooperative Traveling Salesman Problem Under Rolling Horizon Planning. Working paper. University of Duisburg-Essen.
23. Laporte, G., 1992. The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, 59 (2) 231–247.
24. Marinakis Y., Migdalas A., Pardalos P.M., 2008. Cost Allocation in Combinatorial Optimization Games. In: Chinchuluun A., Pardalos P.M., Migdalas A., Pitsoulis L. (eds) Pareto Optimality, Game Theory And Equilibria. Springer Optimization and Its Applications, 17. Springer, New York, NY.
25. Nowak, A. S., & Radzik, T., 1994. The Shapley Value for n-Person Games in Generalized Characteristic Function Form. Games and Economic Behavior, 6(1), 150–161.
26. Platz, T. T., 2019. On the Submodularity of Multi-Depot Traveling Salesman Games. Discrete Applied Mathematics, 255, 75-8.
27. Potters, J.A., Curiel, I.J., Tijs, S.H., 1992. Traveling Salesman Games. Mathematical Programming, 53 (1–3) 199–211.
28. Quant, M., Borm, P., Reijnierse, H., 2006. Congestion Network Problems And Related Games. European Journal of Operational Research, 172 (3) 919–930.
29. Rodriguez, A., Ruiz, R., 2012. The Effect of the Asymmetry of Road Transportation Networks on the Traveling Salesman Problem. Computers & Operations Research, 39 (7), 1566-1576.
30. Shapley, L.S., 1953. A Value for n-PersonGames. Contributions to the Theory of Games, II (Annals of Mathematics Studies 28), H. W. Kuhn and A. W. Tucker (eds.), Princeton University Press, Princeton, 307-17.
31. Sun, L., Rangarajan, A., Karwan, M.H., Pinto, J.M., 2015. Transportation Cost Allocation on a Fixed Route. Computers & Industrial Engineering, 83, 61–73.
32. Tamir, A., 1989. On the Core of a Traveling Salesman Cost Allocation Game. Operations Research Letters, 8 (1), 31–34.
33. Thomson, W., Roth, A. E., 1991. The Shapley Value: Essays in Honor of Lloyd S. Shapley. Economica, 58(229), 123.
34. Tijs, S., 2003. Introduction to Game Theory, Hindustan Book Agency.
35. Toriello, A., Haskell, W.B., Poremba, M., 2014. A Dynamic Traveling Salesman Problem with
36. Stochastic Arc Costs. Operation Research, 62 (5), 1107-1125.
37. Toriello, A., Uhan, N.A., 2013. Technical Note: On Traveling Salesman Games with Asymmetric Costs. Operations Research, 61 (6), 1429–1434.
38. Veenstra, M., Roodbergen, K.J., Vis, I.F.A., Coelho, L.C., 2017. The Pickup and Delivery Traveling Salesman Problem with Handling Costs. European Journal of Operational Research, 257, 118–132.
39. Yengin, D., 2012. Characterizing the Shapley Value in Fixed-Route Traveling Salesman Problems with Appointments. International Journal of Game Theory 41 (2), 271–299.