Snow Plow and Water Spider Routes

A rather simple sounding but often vexing challenge that faces lean practitioners is: What is the optimal physical route for pickups and/or deliveries? This is especially true for a fixed interval, variable quantity material replenishment system design for water spider (a.k.a., waterspider, material handler, mizusumashi, etc.) conveyance. 

Interestingly enough, the same question and logic applies when designing the best neighborhood snow plow route. 

An optimal route would be one that traverses all the desired aisles, blocks, and/or hallways without retracing any part of the route. If such a path exists, it is called an Eulerian path, and if that path begins and ends at the same place, it is called an Eulerian circuit.

Mathematicians have found that a convenient way to represent this problem is to use a graph. Graphs are simply a collection of edges and vertices where those edges cross.  For a snow plow route, the edges represent the streets that the snow plow must visit and the vertices are the intersections.  For example, for the world’s simplest city (shown on the left below) the graph consists of four edges and four vertices (as shown on the right below). waterspider1

Mathematicians have discovered that key to determining if an Eulerian path exists is the number of odd vertices. A vertex is considered even if it connects an even number of edges, and odd if it connects an odd number of vertices. The graph above has four even vertices, and the city below has four even vertices and two odd vertices.

waterspider2 With a little experimentation, you will quickly discover the following criteria that must be met in order for an Eulerian path to exist.

waterspider3Fortunately, or unfortunately, the world is not as simple as the examples above and one question that quickly arises is:  What do I do if there are more than two odd vertices? One answer is to hire more snow plows or enlist more water spiders - obviously, not always the best choice. In this case, you can take the graph and divide it into “edge-disjointed paths” which are simply paths that don’t have any common edges. For any connected set of vertices with 2n odd vertices, the graph may be covered with n edge-disjointed paths.

So for example, if our city grew a little and we added another avenue, the corresponding graph would be as shown in the figure below.

waterspider4 Note that it has 22 odd vertices, so it can be covered with 2 edge-disjointed paths as shown below.

waterspider5 Now suppose that instead of trying to find an edge-disjointed path, you want to find a path or a circuit with minimal retracing, how would you go about doing that? 

A simple strategy is to add edges that represent the retracing. If you add enough edges to reduce the number of odd vertices to two, you can find an Eulerian path, and if you reduce the number of odd vertices to zero (as in the figure below), you can find an Eulerian circuit.

waterspider6 So, if you see a plow truck drive up and down a street twice, it might not be inefficient, it might actually be very efficient. 

Note: For this entry we have assumed that each edge can be traversed in either direction, if the edges are one way streets (like many industrial aisles), then the concept of directed graphs applies, and if you are interested in visiting the vertices exactly once, then Hamiltonian paths and Hamiltonian circuits apply. But, that is for another blog post.