The aim of the Traveling Salesman Problem (TSP) is to find the cheapest way of visiting all elements in a given set of cities and returning to the starting point. In solutions presented in the literature costs of travel between nodes (cities) are based on Euclidean distances, the problem is symmetric and the costs are constant. In this paper a novel construction and formulation of the TSP is presented in which the requirements and features of practical application in road transportation and supply chains are taken into consideration. Computational results are presented as well. © 2009 IEEE.