I wrote an article titled “The Traveling Salesman Problem Using an Evolutionary Algorithm with C#” in the December 2022 edition of Microsoft Visual Studio Magazine. See https://visualstudiomagazine.com/articles/2022/12/20/traveling-salesman-problem.aspx.

The Traveling Salesman Problem (TSP) is the basic example of a combinatorial optimization problem. The goal is to visit each city once so that the total distance traveled is minimized. For example, if there are just 5 cities, one possible solution might be (2, 4, 0, 1, 3).

In my article, I describe a new algorithm that uses an evolutionary approach. In high-level pseudo-code:

create population of random solutions
loop many times
  pick two parent solutions
  create a child solution
  mutate child
  evaluate child
  replace weak solution in pop with child
end-loop
return best solution found

The difficult part is combining two existing solutions to create a new solution. Because each city can be visited only once, combining two existing solutions is quite tricky.

I spent a lot of time working on the algorithm in the article and I’m very proud of it.

To the best of my knowledge, the most common approach for combinational optimization is a technique called simulated annealing. My evolutionary algorithm appears to be a significant new approach.

When I was a young man, I loved reading the Hardy Boys juvenile fiction series. The stories took place in the fictitious town of Bayport. This map was created by a fan of the series.