Traveling Salesman Problem

Problems that plague mathematicians for many years

The traveling salesman problem is a condition that a salesman is going to write some cities in a single stroke, and how to make the shortest route is possible.

The most certain thing is to try all combinations and find the shortest route out of them, but in reality this has plagued mathematicians for a long time. Because it takes a tremendous amount of time to find all combinations.

Some people think that "Do I have to leave the calculation to a computer?" However, it is said that it takes more than 10 billion years to seek all combinations, even computers, when turning around 30, and to keep it in order.

Since the universe was born, it is about 13.7 billion years ago and it will be a tremendous amount of time.

Combination explosion

So how horrible is the number of combinations

We tried using spreadsheet software, Microsoft office 365 Excel, and tried examining up to 10 cities.

Then, I think that it can be read from the graph that the number of combinations is rapidly increasing at a certain point.

As the number increased like an explosion, it is called "combination explosion".

If I try to rearrange all these combinations in turn and find the best place there, I will feel distracted.

Resolved by genetic algorithm

So how can we solve this problem?

Of course, as we mentioned earlier, since we will spend a considerable amount of time investigating each one, we will not find a solution while we are alive.

So, although we can not obtain a perfect solution, we can obtain an approximate solution by using the "genetic algorithm" defined as one type of AI.

Traveling salesman problem and logistics

So why did you pick up the "Traveling salesman problem" here?

Have you heard of such things as the recent news, such as an increase in burden on home delivery drivers, etc. in recent years?

There is also a problem of redelivery, an increase in the number of orders, and so on.

Therefore, it will be indispensable to solve these problems in order to reduce driver burden.

We noticed the shortening of the delivery route by genetic algorithm and AI.

Of course. Also in the current logistics industry, route optimization etc. are carried out based on past data etc. (Particularly recently Yamato introduced Verificationally in part)

So what we felt as doubtful was how I could do a good solution (route distance here).

Therefore, in this time we used the "genetic algorithm" in practice, I tried to examine how to improve it and ask for a good solution.

What is Genetic Algorithm (Introduction)

"Genetic algorithm" is based on the mechanism of genetics in biology as its name reads.

In other words, in a nutshell, you can select excellent data by using various methods, cross-mutate that they say on biology, take over them to the next generation, By repeating, we will make excellent data.

Also, as mentioned earlier, as for the selection method of some parent data in the above figure · how much crossover is done for the next generation · · · · "Solving for the genetic algorithm" There are various learning methods for it.

Term (selection method)

Random selection

Randomly pick out parent data for the next generation, regardless of goodness of fit, like letters

Tournament selection

Pick out the parent data for the next generation in an arbitrary number, and choose the one with the highest degree of fitness from among them. This operation is done until the number of groups is obtained.

Roulette selection

Choose parent data for the next generation at a proportion proportional to goodness of fit

Terminology (How to Make the Next Generation)

Crossover

The data of the bit string of the next generation should be replaced with a certain point. That is, data is generated based on two parent data.

Mutation

The data of the next generation is randomly changed

Term (Other)

Elite rate

What determines the proportion of goodness-of-fit data of a generation that does not cause elite selection, crossover, etc. to be passed on to the next generation.

---

BackVerificationNext