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!
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).
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 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.
The search engine Google uses a method to provide ordered listings called Page Rank. Page Rank is fundamentally a concept of graph theory by using IP Addresses (your domain names address) as your vertices , and hyperlinks located on that site as edges.
In this form of graph theory, edges have weight. This means that the more weight for each edge, they are more likely to be traveled on if you think of the bridges example. In the case of search engines the higher weight accumulated for each website determines where it will be put in the order of search results.
What is interesting is that If a person knew exactly how the Page Rank algorithm worked then they could potentially have their website placed higher on google’s search results.
The article I found describes how biologists can use graph theory to find out more about DNA structure and gene mutation to more accurately determine how genes and DNA strands work. Through microscopic networks, biologists can figure out how diseases spread through infected people and how genes mutate and affect other genes using this kind of math, where the graph expresses molecular structures. I found this article to be very interesting, as it takes math I didn’t think would connect to biology at all and actually makes it into a possible mathematical solution to genetic problems and disease control!
It’s likely that you have used Google Maps before. However, it’s also likely that you don’t know how Google Maps finds these paths for you to take. Turns out they use some graph theory.
Initially, Google weighs the edges that would be part of a map, usually by either time or distance. A major part of the way they are able to find these shortest paths is by using an algorithm that actually comes up later in our book: Dijkstra’s Algorithm. That really rolls off the tongue (It’s dike-stra by the way). As given by the book, to use Dijkstra’s Algorithm:
1. Mark the ending vertex with a distance of zero. Designate this vertex as current.
2. Find all vertices leading to the current vertex. Calculate their distances to the end. Since we already know the distance the current vertex is from the end, this will just require adding the most recent edge. Don’t record this distance if it is longer than a previously recorded distance.
3. Mark the current vertex as visited. We will never look at this vertex again.
4. Mark the vertex with the smallest distance as current, and repeat from step.
Here’s an example of this algorithm being used visually:
This article talks about graph theory as a solution to Quantium physics. Although we have only applied graph theory to bridges and transportation routes, from this article you can see how this form of mathematics is found everywhere. Even when discovering more about a science we would not even think related. Since this discovery of the link of these two math subcategories, scientists are doing a lot more research on how they link together and why. Needless to say graph theory is everywhere around us, even in things we would least expect.
While doing a little research on Graph Theory I found an interesting connection that we’ve already touched upon in class. While the Bridges of Konigsberg were a simple example of Graph Theory, there are many other complicated transport systems that have been built on the foundation of this same theory. This article, in particular, brought up the use of telecommunication systems as networks that would need specific links, like cables, in this case, to connect the “nodes”. The article really strips all of the information back to the basics, so it is extremely easy to understand. It’s a pretty short read as well, so if anyone is at all interested in this kind of thing, I’d definitely recommend it!
I was curious about graph theory and what prominent topics are involved in it. Perhaps one of the most interesting and practical problem I found in the Wikipedia entry for graph theory is the art gallery problem (also see here).
To sum it up: The problem asks us to consider how many security guards we’d need to carefully monitor an art gallery. This depends on many variables such as the size and shape of the art gallery.
Marianne Freiberger for Plus Magazine, summarizes the mathematician S. Fisk’s answer to this conundrum as:
..[Y]ou never need more than n/3 guards (so that’s 9/3 = 3 guards in the example in the figure). That’s true for any simple polygon with n vertices, no matter how complicated and irregular it looks.”
Which is pretty amazing.
So next time you’re watching your favorite heist movie or thinking about starting a heist campaign in D&D, consider the art gallery problem!