This paper introduces a novel type of a problem in which two travelling salespersons are competing, where each of them has two conflicting objectives. This problem is categorized as a Multi-Objective Game (MOG). It is solved by a non-utility approach, which has recently been introduced. According to this method all rationalizable strategies are initially found, to support posteriori decision on a strategy. An evolutionary algorithm is proposed to search for the set of rationalizable strategies. The applicability of the suggested algorithm is successfully demonstrated on the presented new type of problem.