Death of a [Traveling] Salesman [Problem]

Was it an easy pun? Yes, but it’s still a good one.

With programs like Concorde TSP Solver we have ways to make the Traveling Salesman Problem irrelevant to our everyday lives. Maps like Google maps can already handle multiple locations and trying to give you the best route. Not to mention you can use any number of alternative map services.

In the larger context however, TSP still lives on as a big problem for mathematicians, to the extent to have considered what it would mean to truly solve the problem in the 2012 movje Traveling Salesman.

Meanwhile, although the problem has been made much easier, truckers delivery drivers still have to deal with the problem from day to day. And given how much it can drive a person crazy we should be thankful we have modern technology to help guide us through the easier version.

That said, if you want to truly kill the TSP then answer P vs. NP and collect your million dollars, here.

 

Speeding Up the TSP by using an opposite approach?

I began my google search with the simple “traveling salesman problem”, and after reading a few articles, I found this one to be rather interesting.

In this article, the author Joshi describes solving the TSP by using the top-down approach. This is the same approach we used in class, using the largest parts of the graph to find a solution.

Then, the author mentions trying the same problem, but instead with a bottom-up approach. Joshi calls this the “bottom-up dynamic programming approach”, which begins with the smallest possible subproblems and their solutions, then progresses upward to solve the more complicated subproblem. In the end, the bottom-up approach brought Joshi to an answer sooner than the top-down method.

https://medium.com/basecs/speeding-up-the-traveling-salesman-using-dynamic-programming-b76d7552e8dd

Knight’s Tour

 

Chess and Math: A Closer Look at the Knight’s Tour

Alright, we are going to talk about the Knight’s Tour, “getting the Knight to visit all 64 squares only once.” In this article I found written by Patrick JMT for the US Chess Federation, he mentions that Euler has found a way to create his own open and closed Knight’s Tour. To clarify for those who don’t know much about chess, such as myself, a closed tour is when the Knight is able to end on the space it started and continue to follow the same sequences to recreate a new tour again and again. For an open tour, it’s when the Knight has visited all spaces but wasn’t able to end where it started. Relating this to graph theory, this would be paths and circuits. 

On the topic of graph theory, Patrick mentions how the squares can be vertices and the moves made would be edges, creating a complex map of how the Knight would move. That type of graph was shown to us in 3D printed form in class.

Also in the article there is a graph called a Bipartite graph that would represent 32 black/white tiles  and  since the “Knight always alternates the colors of the squares it visits: if the Knight stands on a black square, it can only travel to a white square and vice versa.” This makes the Bipartite graph connect to spaces of which the Knight can move from one white square to multiple black squares, in other words plots, where you can move from one space to another. 

 

How good is Disney’s touring plan?

Image result for magic kingdom touring plan

https://touringplans.com/walt-disney-world/touring-plans/how-they-work

After discussing it in class, I decided to look more into Disney’s touring plan. This is one quote i liked about the challenges “The 21 attractions in the Magic Kingdom One-day Touring Plan for Adults have a staggering 51,090,942,171,709,440,000 possible touring plans. That’s over 51 billion billion combinations, or roughly six times as many as the estimated number of grains of sand on Earth.”  This just goes to show how challenging it is to have a successful touring plan.

 

UPS Drivers Don’t Make Left Turns

https://www.travelandleisure.com/travel-tips/ground-transportation/why-ups-trucks-dont-turn-left

According to this article, UPS drivers do not take left turns (well, rarely make them. Left turns take up less than 10% of UPS drivers turns. This policy of no left turns was put into place back in 2004 and has saved the company over 10 million gallons of fuel. It has also reduced traveling time and carbon emission from the trucks.

The company used math in order to come up with this new routing tactic. It seems to be paying off. This article talked about how if all people agreed to do this then it would create many benefits for the environment, traveling, and safety (less crashes).

I personally do not think people would ever agree to it, but it is extremely interesting. It is awesome to see companies making changes that help environmental issues!

Will We Ever Solve The Traveling Salesman Problem!?

https://www.wired.com/2013/01/traveling-salesman-problem/

Before we had the computing technology, the traveling salesman problem to get around all the cities of the United States was worked on for hours on end as people could never truly find the shortest route. Now, with the use of machines and computer algorithms people are surely disappointed to find out that there is possibly no true solution, but instead produces routes guaranteed to be at most 50 percent longer than the shortest route. This method was Christofides’ algorithm. It wasn’t until a Stanford-McGill team was finally able to beat out Christofides’ algorithm by 10 percent, making thee current record 40 percent longer than the shortest route.  Mathematicians are confident that in order to come up with a route any shorter we must come up with new ideas, as we haven’t quite “hit the switch” yet.

 

The shortest traveling salesman route going through all 13,509 cities in the United States with a population of at least 500 (as of 1998).

 

Christofides’ Algorithm

https://www.wired.com/2013/01/traveling-salesman-problem/

In the past mathematicians would try and solve the traveling salesman problems for hours end . It might be easy to solve a traveling salesman problem with five stops but realistically the more stops the longer it will take. It makes more sense to create a system to have a computer solve this algorithm.   “A 49-city map in the 1950s, a 2,392-city map in the 1980s and a 85,900-city map in 2006 — no one has devised an algorithm that can efficiently solve everytraveling salesman problem. According to a landmark paper published in 1972, such a solution might not even be possible. Computer scientist Richard Karp, of the University of California at Berkeley.” The image below is the largest traveling salesman problem solved, was solved using this algorithm, 85, 900- city route was done in 2006 and is nearly impossible without the use of a computer solution. 

The Traveling Salesman and The Shortest Tree

The shortest tree is not actually that short.  “Computer scientist Richard Karp, of the University of California at Berkeley, showed that the traveling salesman problem is “NP-hard,” which means that it has no efficient algorithm.” After his article was published a number of computer scientists decided to create an algorithm to get as close to solving the Traveling Salesman Problem as they could. “A string of improved approximation algorithms have since emerged, after computer scientists began looking at the problem with fresh eyes. Although these approximations apply only to certain types of traveling salesman problems, the approach they embody holds great promise.”

The Shortest Tree is the outcome of one of these algorithms. It starts by connecting the shortest highway between two cities and that connection forms a branch. You add branches by finding more short highways to connect more cities. For example: city A and city B are connected by highway 1, then you connect city C to city B by highway 2 and so on and so forth. Until all the cities have been reached. “The resulting tree is not a possible solution to the traveling salesman problem because it does not create a round-trip route. But it can be converted into a round-trip by visualizing the branches as walls and then imagining walking along the tree, with your finger touching the wall, until you get back to where you started.”

It is kind of a cool way to look at the traveling salesman problem in a new way. “The resulting trip visits every city and returns to the starting point, but it is usually far from the shortest way to do so because it typically involves retracing steps many times — every wall in the tree is traversed twice, once on each side.” Though it may not be the fastest way to travel, it does give a person a new way of doing it. Also the idea of making the graph into a tree like figure is very interesting. The graphs we used in class with our dots and lines weren’t trees, but some of them did turn out into pretty interesting shapes.