Genetic algorithm finds routes in travelling salesman problem with profits

Travelling salesman problem with profits is a version of a cla ssic travelling salesman problem where it is not necessary to visit all verti ces. 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 c ost 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-lif e 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.