This problem originated from a blog post I wrote for DataCamp on graph optimization here. The algorithm I sketched out there for solving the Chinese Problem on the Sleeping Giant state park trail network has since been formalized into the postman_problems python library. I’ve also added the Rural Postman solver that is implemented here.

So the three main enhancements in this post from the original DataCamp article and my second iteration published here updating to networkx 2.0 are:

- OpenStreetMap for graph data and visualization.
- Implementing the Rural Postman algorithm to consider optional edges.
- Leveraging the postman_problems library.

This code, notebook and data for this post can be found in the postman_problems_examples repo.

The motivation and background around this problem is written up more thoroughly in the previous posts and postman_problems.

#### RPP Solution Route Animation

Here’s the full route animation. More details here. Kudos to my sister @laurabrooks for coding this up!

#### Table of Contents

- Create Graph from OSM
- Viz Sleeping Giant Trails
- Connect Edges
- Viz Connected Component
- Viz Trail Color
- Contract Edges
- Solve CPP
- Solve RPP
- Viz RPP Solution
- Create geojson solution

## Create Graph from OSM

```
<class 'networkx.classes.digraph.DiGraph'>
```

#### Adding edges that don’t exist on OSM, but should

#### Adding distance to OSM graph

Using the haversine formula to calculate distance between each edge.

#### Create graph of required trails only

A simple heuristic with a couple tweaks is all we need to create the graph with required edges:

- Keep any edge with ‘Trail’ in the name attribute.
- Manually remove the handful of trails that are not part of the required Giant Master route.

## Viz Sleeping Giant Trails

All trails required for the Giant Master:

## Connect Edges

In order to run the RPP algorithm from postman_problems, the required edges of the graph must form a single connected component. We’re almost there with the Sleeping Giant trail map as-is, so we’ll just connect a few components manually.

Here’s an example of a few floating components (southwest corner of park):

OpenStreetMap makes finding these edge (way) IDs simple. Once grabbing the `?`

cursor, you can click on any edge to retrieve IDs and attributes.

#### Define OSM edges to add and remove from graph

#### Add attributes for supplementary edges

Ensuring that we’re left with one single connected component:

```
1
```

## Viz Connected Component

The map below visualizes the required edges and nodes of interest (intersections and dead-ends where degree != 2):

## Viz Trail Color

Because we can and it’s pretty.

#### Check distance

This is strikingly close (within 0.25 miles) to what I calculated manually with some guess work from the SG trail map on the first pass at this problem here, before leveraging OSM.

```
25.56 miles of required trail.
```

## Contract Edges

We could run the RPP algorithm on the graph as-is with >5000 edges. However, we can simplify computation by contracting edges into logical trail segments first. More details on the intuition and methodology in the 50 states post.

```
Number of edges in trail graph: 5141
```

Edge contraction reduces the number of edges fed to the RPP algorithm by a factor of ~40.

```
Number of edges in contracted trail graoh: 124
```

## Solve CPP

First, let’s see how well the Chinese Postman solution works.

#### Create CPP edgelist

#### Start node

The route is designed to start at the far east end of the park on the Blue trail (node ‘735393342’). While the CPP and RPP solutions will return a Eulerian circuit (loop back to the starting node), we could truncate this last long doublebacking segment when actually running the route

#### Solve

#### CPP Stats

*(distances in meters)*

```
OrderedDict([('distance_walked', 54522.949121342645),
('distance_doublebacked', 13383.36715945256),
('distance_walked_once', 41139.581961890086),
('distance_walked_optional', 0),
('distance_walked_required', 54522.949121342645),
('edges_walked', 170),
('edges_doublebacked', 46),
('edges_walked_once', 124),
('edges_walked_optional', 0),
('edges_walked_required', 170)])
```

```
Miles in CPP solution: 33.88
```

## Solve RPP

With the CPP as benchmark, let’s see how well we do when we allow for optional edges in the route.

```
CPU times: user 1min 39s, sys: 1.08 s, total: 1min 40s
Wall time: 1min 42s
```

#### Required vs optional edge counts

(*1=required and 0=optional*)

```
Counter({0: 3034, 1: 124})
```

#### Solve RPP

```
CPU times: user 5.81 s, sys: 59.6 ms, total: 5.87 s
Wall time: 5.99 s
```

#### RPP Stats

*(distances in meters)*

```
OrderedDict([('distance_walked', 49427.7740637624),
('distance_doublebacked', 8288.19210187231),
('distance_walked_once', 41139.58196189009),
('distance_walked_optional', 5238.9032692701385),
('distance_walked_required', 44188.870794492264),
('edges_walked', 152),
('edges_doublebacked', 28),
('edges_walked_once', 124),
('edges_walked_optional', 12),
('edges_walked_required', 140)])
```

Leveraging the optional roads and trails, we’re able to shave about 3 miles off the CPP route. Total mileage checks in at 30.71, just under a 50K (30.1 miles).

```
Miles in RPP solution: 30.71
```

## Viz RPP Solution

#### Create graph from RPP solution

### Viz: RPP optional edges

The RPP algorithm picks up some logical shortcuts using the optional trails and a couple short stretches of road.

**black**: required trails**blue**: optional trails and roads

### Viz: RPP edges counts

Edge walks per color:

**black**: 1

**magenta**: 2

## Create geojson solution

Used for the D3 route animation at the beginning of the post (also here). More details here.