Summary

Side projects solving applications of the Rural Postman Problem using the postman_problems library. Current examples leverage OSM (Open Street Maps) for building, optimizing and visualizing graphs. Examples include:

1. 50 States Ride: Required edges are the state named avenues in DC. Optional edges are all others roads and trails. Many more details in the accompanying blog post here.

2. Sleeping Giant: Required edges are the named trails in Sleeping Giant State Park (see Giant master program). Optional edges are the non-required trails and roads. More examples in the accompanying blog post here.

1. 50 States Ride

Graph

Derived from Open Street Maps data. Edges are contracted to ease computation. There are ~400 required edges in the final edgelist.

• required state avenues: 112 miles
• connectors between required components: 12 miles

Solution

The optimal route covers 160 miles: 124 miles of required road and 36 miles of optional roads and doublebacking.

See the blog post for more visualizations and details on the approach.

Here is the route (geojson map).

Here is the solution edgelist CSV with lat and lon and street names.

Contents

• 50states/50states-blogpost.ipynb: notebook solving and visualizing the problem
• 50states/rpp_solution.csv: eulerian circuit solution solution to RPP

2. Sleeping Giant

Graph

For more details on the Sleeping Giant problem and graph, check out the blog post here.

Solution

The optimal route covers 30.7 miles: 25.6 of required trails and 5.1 miles of optional trails and doublebacking.

Project

Contents

• environment.yml: environment used to produce 50states-blogpost.ipynb.
• graph.py: module consolidating heavy lifting for blog post

Resources

• postman_problems: Python package with RPP and CPP solvers
• Blog post: 50 states RPP: solving and visualizing RPP with Leaflet using DC OSM data
• Blog post: Sleeping Giant RPP: solving and visualizing RPP with Leaflet using OSM data.
• Blog post: DataCamp: Original blog post implementing CPP from scratch using Networkx 1.11
• Blog post: Intro to Graph Optimization: Same post as above, but modified for Networkx 2.0