Index

Discrete Mathematics Project
Graph Theory Activity

Title

Designing Recycling Routes (Jim Arnow)

Goals

  1. Students will model a real-world situation, namely how to best design the route of a recycling truck which minimizes the distance traveled.
  2. Students will gain familiarity with weighted graphs and their uses.
  3. Students will explore the idea of finding a "reasonable" algorithm for finding a solution, rather that finding a method that finds the optimal solution.

Abstract

Western Disposal Services has moved to using a computer to decide what routes each of its trucks will take to pick up recyclables. The students will attempt to find an algorithm for finding a shortest route for a truck to take by experimenting with a simple, and then a more complex situation.

Problem Statement

  1. Present the students with the "Designing Recycling Routes" handout.
  2. Instruct them to read the article form the Boulder Daily Camera (July 27, 1996) titled "Recycling Program Tightens Schedules", which may be copied on to the back of the handout.
  3. After they have read the article, discuss the task presented to them -- finding the shortest route which reaches each vertex (where the recyclables will be picked up. Stress that this is a simplification of the problem modeled by Western Disposal, since it ignores many different factors.
  4. Divide the class into small groups. Allow them time to explore both problems, and come up with their own best route.

    Solutions to the two problems:

  5. The first problem has as its shortest route:
    Start--B-C-A-B-Start
    Note that the route can be reversed, and still represents a minimum solution. Also note that the segments of length 1.58 and 1.14 can be ignored, since it is always quicker to go through vertex B than to follow the route directly from the Start to either A or C. The total length of this route is 2.25 miles.
  6. The best solution found to the second problem was ??? and had a length of 11.3???

Materials Required

"Designing Recycling Routes" handout, calculators (for adding weights or various routes), scratch paper

Time

Reading article/Discussion of the task (10 min.), Group exploration (20 min.), presentation of methods (20-30 min.), discussion of topics (10 min.)

Mathematics Concepts

Discrete Mathematics Concepts

graph, edge, vertex, circuit, path, weighted graph, traveling salesperson problem, Hamiltonian circuit

Related Mathematics Concepts

optimization, minimization, algorithm, efficiency

NCTM Standards Addressed

Mathematical Problem Solving, Mathematics as Communication, Mathematics as Reasoning, Mathematical Connections, Geometry from a Synthetic Perspective, Discrete Mathematics

Colorado Model Contents Standards Addressed:

Number Sense (1), Algebraic Methods (2), Data Collection and Analysis (3), Geometric Techniques (4), Linking Concepts and Procedures (6)

Curriculum Integration

Variations/Comments

  1. This problem can be expanded by including many of the features included by Western Disposal in their model: avoiding U-turns, avoiding left turns, adding one-way streets (a digraph), etc.
  2. The more computer literate could try to program up a method for solving these problems.

In this problem, the students are looking for a circuit which must visit each vertex at least once. If the task asked them to visit each vertex once and only once, then the problem would require them to find a Hamiltonian circuit.

Note that this problem is often called the "Traveling Salesperson Problem," since it models the situation where a salesperson must travel to a number of cities and wants to minimize the distance traveled. Also note that one way to solve this problem is to list all of the possible routes and find the shortest one. This method guarantees finding the optimal solution, however, if the graph gets large, the number of routes becomes too large for even a computer to deal with in a reasonable amount of time.

To see this, consider a complete graph with n vertices. Then there are at least n!/2 possible routes since we have n choices for the first edge, (n-1) for the next, and so on, but a route is the same forwards and backwards, so we divide by two. So, if there are 30 vertices, and we check all possible routes, even if the computer can make 1,000,000 calculations per second, the calculation won't be completed for over a quintillion years!

Thus, what we are looking for is a "reasonable" algorithm which will find a short route (possibly not necessarily the shortest) in a minimum amount of time. How we balance speed versus level of optimization is not a clear question, but one that students can ponder.

One possible methods is the nearest neighbor method, where each step we move to the nearest neighbor until we have passed all of the vertices. This method is intuitively appealing, however it may encounter difficulties if the graph is not complete, and will not always find the shortest route.

Send your variations and comments to this Web page's editor

References

Crisler, N., Fisher, P., & Froelich, G. (1994). Discrete Mathematics Through Applications. New York: W. H. Freeman and Company.

Dossey, J., Otto, A., Spence, E., & Vanden Eynden, C. (1993). Discrete Mathematics. Harper Collins College.

Kenney, M. J., & Hirsch, C. R. (Eds.). (1991). Discrete mathematics across the curriculum, K-12. Reston. VA: National Council of Teachers of Mathematics.

McEliece, R., Ash, R., & Ash, C. (1989). Introduction to Discrete Mathematics. New York: Random House.

Peressini, et al. (1992). Precalculus and Discrete Mathematics. Glenview, Illinois: Scott, Foresman and Company.

Tucker, A., (1984). Applied Combinatorics. New York: John Wiley & Sons.

Boulder Daily Camera, (July 27, 1996). "Recycling Progeram Tightens Schedules". Daily Camera.

Last updated January 16, 1997