Genetic algorithm finds routes in travelling salesman problem with profits

Travelling salesman problem with profits is a version of a classic travelling salesman problem where it is not necessary to visit all vertices. Instead of it, with each vertex a number meaning a profit is associated. The problem is to find a cycle in a graph which maximizes collected profit but does not exceed a given cost constraint. This problem is NP-hard. Additional assumptions to this problem were proposed in the paper.We assumed that a graph may not be a complete graph. Moreover, repeated visiting of a given vertex is allowed, however with an assumption that a profit is realized only during first visiting. With these additional assumptions, the problem is more real-life and could have applications in logistics and shipping. To solve the problem, a genetic algorithm with special operators was proposed. The algorithm was tested on networks of cities in some voivodeships of Poland, obtaining very good results.

Problem komiwojażera z zyskami (ang. TSP with profits) jest pewną wersją klasycznego problemu komiwojażera, w której nie jest konieczne odwiedzenie wszystkich wierzchołków grafu. Zamiast tego, z każdym wierzchołkiem związana jest pewna liczba oznaczająca zysk. Problem polega na znalezieniu cyklu w grafie, który maksymalizuje zysk, ale którego koszt nie przekracza zadanego ograniczenia. Problem ten jest problemem NPtrudnym. Do tak postawionego problemu, w pracy zaproponowano dodatkowe założenia. Przyjęto mianowicie, że graf nie musi być pełny. Ponadto dopuszczona jest możliwość powrotów, czyli ponownego odwiedzenia danego wierzchołka, przy założeniu jednak, iż zysk realizowany jest tylko podczas pierwszego odwiedzenia. Przy tych dodatkowych założeniach problem jest bardziej realny i może mieć konkretne zastosowania w logistyce i spedycji. Do rozwiązania problemu zaproponowano algorytm genetyczny, uzyskując bardzo dobre wyniki.