Traveling salesman problem (TSP) is a well known NPCompleteproblem. The objective of the problem is to findroute of the vehicle to service all the customers at aminimal cost (in term of travel distance, travel cost, etc.).Almost all TSP problems used distance between eachpoint of customer as Euclidean Distance and are notconcerned with other parameters to find minimal cost.This paper presents the new TSP that is called “TravelingSalesman Problem with Traffic conditions (TSPTC)”. Thealgorithm has been designed to employ more parameters,which results it closer to the real world condition. Thepaper also proposes the developed genetic algorithm,called “Hybrid Encoding Genetic Algorithm (HEGA)”.The concept is to combine binary encoding and integerencoding together. The successful results of HEGA ofTSPTC are shown in the paper.