The recent issue of Westword mentioned that in June, 2010
This is a very interesting network flows or operations research problem with the following constraints:
- all 42 bicycle stations must be visited (there were 42 stations in May 2010)
- a bicycle may be exchanged at a station if a dock is available and if another bicycle is available (or can you just put it in an empty dock and take it right out?)
- there is no charge if a bicycle is returned within 30 minutes
- a station has a number of available empty docks, and a number of available bicycles
- the number of docks and bicycles changes throughout the day as people check-out and return bicycles
- the optimal solution must use the road or bicycle path network
The first thing I tried was to figure out the traveling salesman path, ignoring most of the above constraints. The map below shows this solution, calculated with Concorde. The length of this tour is 37.06 km, or 23.03 miles. This represents a lower bound on the actual solution, which would be longer when using the actual road or bike path network.
View Denver B-Cycle stations in a larger map
If you’re interested in solving this problem, the text data can be found here and the KML can be found here. This data was parsed from the source code of the Denver B-Cycle website on May 21, 2010. Coordinates are both in Web Mercator projection, and in latitude and longitude. Any optimal solver would have to download the data periodically to check if bikes or empty docks are available at the next station.