May 21, 2010

Traveling Bicyclist Problem

The recent issue of Westword mentioned that in June, 2010 Denver’s B-Cycle will challenge Denver velophiles to visit all 42 of the new bicycle stations. Brent Tongco from Denver Bike Sharing prepared for the challenge with a group of cyclists by visiting and switching bikes at every station. The trip took about six hours, including a coffee break, and was about 31 miles long. Naturally, this made me wonder if there is an optimal solution to this problem that minimizes time.

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.