Traveling Salesman Problem with Time Windows Solved with Genetic Algorithms

The Traveling Salesman Problem (TSP) is a very common problem in many applications. It appears in the transportation of goods and not only. As we know this problem is NP hard. Time Windows (TW) brings us some additional constraints to solve. In case there are many Time Windows the problem constraints determine almost the whole solution of the problem and in some cases we can solve the problem. We restrict the cardinality of Time Windows. In our work we define the following conditions without loss of generality: 1. The salesman has to visit one town each day 2. The distance between two towns can be performed in a day 3. We have maximum two Time Windows 4. We have routes between every two towns, but the cost of the routes may differ in case we go from town A to town B, or we go from town B to town A. Genetic algorithms are powerful tools for solving NP hard problems. They utilize search and optimization procedures that operate in a similar way to the evolutionary processes observed in nature. We have to code the problem data structure in a structure (chromosome), which allows us to make some genetic operations over this chromosome. Genes constitute chromosomes. A chromosome represents a possible solution in the space of solutions. We can code the problem of time windows in some chain of chromosome where the first chain segment starts with the town from where the salesman starts his journey and the end of the segment, the first constraint of time window, the town specified in the first time window. The second chain starts from the town reached from the first time window, and ends with the second town specified in the second Time Window constraint and so on. The chains connected together form the desired chromosome. None of the towns appears twice in the chromosome, the length of this chromosome equals with n, the desired cardinality of the towns to visit. Even if we reach an optimal solution, we can’t prove that it is optimal because of NP hardness