Module 2: Critical Thinking – Option 1, Part 2

Module 2: Critical Thinking – Option 1, Part 2

Colorado State University – Global Campus

MTH109

Traveling is a big part of everyone’s day to day life. We drive to work, drive home and maybe somewhere in between we stop for food, groceries, errands, our childs sport practice, to see a friend; the possibilities are endless. Sometimes driving from location to location is the primary function of our work. The real world optimization that I chose is the daily tasks for a courier in a large city.

Everyday the courier has to travel to 6 different suburbs in a very large city. He’s only going to one location in each suburb but he has to hit each of them everyday. There is a great deal of distance between some of his locations and in a large city it can take a long time to get from point A to point B. Similar to the original Chinese Postman scenario, the courier needs to be able to get to every location in the shortest amount of time or distance. This is how I identified that the scenario that I chose was an example of the CPP.

This example is very relevant because it applies to exactly what couriers do, and can be applied to other situations. Most people live in large cities and at times they can be nearly impossible to navigate and there is always something slowing you down. Almost everyone relies on GPS heavily to get through large cities because time is always a factor.

To create the graph, I didn’t model the nodes and edges to any particular map, but instead used the concept that is used in the planning of large cities. The idea I used is based on easing semi truck traffic by creating highways that typically lie more towards the outskirts of cities. This concepts always truckers to get through the city more efficiently, safer and helps improve drive times for everyone else.

The courier in my scenario is not a semi truck operator, but he does operate a sizable fleet vehicle to deliver items all over the city.

The graph is an Euler circuit. Part of the scenario is that the courier driver starts and ends at the same location. Knowing this and knowing “an Euler circuit is a circuit that uses every edge in a graph with no repeats” and that it “must start and end at the same vertex” indicates that this is in fact an Euler circuit (Lippman, 2013).

After drawing the graph, weighing the edges and applying the scenario to it, I needed to determine if any of the vertices were unbalanced or odd. To do this I added directional arrows on each edge to indicate which way the edge could be used. I did this at random and ended up with 2 vertices that had a negative difference, 2 with a positive difference and 2 that were balanced. Knowing this I was able to determine that I needed to find the shortest distance between the nodes to balance them out. Nodes A, B, E and F were unbalanced. This meant that I had 3 odd vertices: AE, AF and BF (Pearson Schools & FE Colleges).

My next step is to determine what path will give me the shortest total distance. Solving the first path was easy. I needed an additional path from would allow me to go from node E to node A. There was already a path between them but that path only allowed me to go from A to E. I needed to utilize Eulerization to create balance for my odd vertices (Zabrodin).

Finding the second path was not nearly as easy. I knew that I couldn’t use AF as a path as it would keep 3 of my vertices odd, so I needed to find the path from B to F. I worked backwards from F and while keeping my directions in mind compared what would happen when I added addition edges to the graph. Eventually, I was able to determine that the path would be FD, DC, CE, EA and AB.

Now that I had all of my paths that used every edge with no repeats, I just needed to use a process of elimination to determine how I would get through the graph, following the directional arrows, not repeat any edges and end up at the same node that I started with. After several attempts I was able to come up with the solution ABDEABEACEFCDFDCEA.

Another possible solution would be EACDFDCEFCEABEABDE. In this scenario the starting and ending point would be node E instead of node A.

I’m not sure that anything else could be optimized in this problem, nor do I know how my Part 1 answers would be affected by any changes.

The advantages of using a graph is that it can be a very useful visual representation. Like we learned in this lesson graph theory is excellent for traveling purposes like when we use GPS. Graphs can be used to model many types of relations and processes (Lippman, 2013). Many practical problems can be represented by graphs like the example I used in this critical thinking assignment.

It’s really interesting to think that simple and common things that we all do every day can be interpreted into a graph. I was surprised to learn about all the applications that can be applied to graph theory. In the scenario I presented I was able to provide a solution for a courier that had to travel through a large city to make deliveries in different suburbs. I was actually rather surprised that I was able to find a solution since I drew the graph and applied directionality at random to the edges. I will definitely be thinking twice about my GPS and the layout of cities the next time I use it.

REFERENCES

Lippman, D. (2013). Math in society (2.4 ed.). San Francisco, CA, USA: Creative Commons.

Pearson Schools, & FE Colleges. (n.d.). Chinese Postman Problem. Retrieved from

https://www.pearsonschoolsandfecolleges.co.uk/secondary/Mathematics/16plus/AdvancingMathsForAQA2ndEdition/Samples/SampleMaterial/Chp-03 044-064.pdf

Zabrodin, R. (n.d.). The Route of the Postman. Retrieved from

https://www-m9.ma.tum.de/graph-algorithms/directed-chinese-postman/index_en.html