Problem komiwojażera jako gra konkurencyjna

• Autorzy: Ewa Drabik

Warianty tytułu

A Traveling Salesman Problem as a Copmetitive Game

• Języki publikacji: PL

Abstrakty

Celem pracy jest modyfikacja klasycznego problemu komiwojażera. Tym razem w grze uczestniczą dwaj komiwojażerowie. Ich zadaniem jest sprzedaż określonego towaru w n miastach powiatu Z. Każdy z nich musi objechać wszystkie miasta niezależnie od tego czy przeciwnik już tam był, a następnie powrócić do miasta wyjściowego. Podobnie, jak to ma miejsce w klasycznym problemie komiwojażera, każdy z nich "odwiedza" poszczególne miasta tylko jeden raz. Tak więc macierz kwadratowa kosztów przejazdu stopnia n jest jednakowa dla obydwu graczy. Jednakże jeśli okaże się, że jeden z graczy zamierza udać się do określonego miasta, a jego konkurent już tam był, to jego koszt wzrasta o jednostkę, zaś przeciwnika o tyle samo maleje. Jeżeli obaj w jednakowym czasie dotrą do tego samego miasta, to dzielą się "wygraną" i w związku z tym ich koszty nie ulegają zmianie. Na swoją wędrówkę polegającą na odwiedzeniu wszystkich miast i powrocie do miasta wyjściowego potrzebują tyle samo czasu. Każdy z nich poszukuje więc zamkniętej drogi w taki sposób aby koszty, które poniosą w związku z podróżą były jak najniższe. Wygrywa ten z graczy, którego koszt okaże się niższy. W pracy podajemy propozycję rozwiązania powyższego problemu.

EN

The classical traveling salesman problem might be described as follows: a salesman starting from a given city, visiting each of cities, and returning to the original point of departure should find the shortest tour. More generally, he could consider in what order he should visit the cities to minimize the total distance traveled. For 'distance' we can substitute time, costs, or other measures of effectiveness as desired. Distance or costs between all city pair are presumed known. Our version of this problem concerns two traveling salesmen who want to sell certain goods (commodities) in n cities. Both players should visit each of cities once and only once, and return to start. Nevertheless if one of the players, goes to some city which his rival has already visited, his costs increase by a unit, whereas costs of the rival are lower by a unit. If players visit a given city at the same time, the costs of a travel do not change. In addition, it is assumed that both players cover a distance between two cities within the same time. The aim of this paper is to present an algorithm enabling to solve the two traveling salesman’s problem.

Słowa kluczowe

PL

Programowanie matematyczne; Teoria podejmowania decyzji; Algorytmy; Badania operacyjne; Teoria gier

EN

Mathematical programming; Decision making theory; Algorithms; Operations research; Game theory

• Czasopismo: Przegląd Statystyczny
• Rocznik: 2006
• Tom: 53
• Numer: z. 1
• Strony: 5--32

Twórcy

autor

Ewa Drabik

Bibliografia

• [1] Dantzig G., Fulkerson R., Johnson S., (1954), Solution of Large-Scale Traveling-Salesman Problem, "Opus. Research", 2, 393-410.
• [2] Drabik E., (2005), The modified traveling salesman problem: two traveling salesmen's problem, stuffs from conference: First Spain Italy Netherlands Meeting on Game Theory, Maastricht (Netherlands), 26-27.
• [3] Drabik E., (2005), Zmodyfikowany problem komiwojażera: komiwojażerów dwóch. Złożony do: Inowacje w Finansach i Ubezpieczeniach. Metody matematyczne, ekonometryczne i informatyczne 2005, Wydawnictwo Akademii Ekonomicznej w Katowicach.
• [4] Flood M.M., (1956), The Traveling- Salesman Problem, "Operations Research", 4, 61-75, 1956.
• [5] Grabowski W, (1980), Programowanie matematyczne, PWE, Warszawa.
• [6] Kolupa M., (1973), Elementarny wykład algebry liniowej dla ekonomistów, PWN, Warszawa.
• [7] Little J.D.C., Murty K.G., Sweeney D.W., Karel C., (1963), An Algorithm for the Traveling Salesman Problem, "Operations Research", 6, 972-989.
• [8] Naddef D., (2002), Polyhedral theory and branch- and- cut algorithms for the symmetric TSP. In: Gutin G. and Punnen A.P. (eds.), The traveling salesman problem and its variation, Kluwer Academic Publishers Dordrecht Boston London, 29-116.