← Return to Projects and Posts
The Fastest Parade Ever
Every June, homebuilders and home remodelers in the Iowa City area have a “Parade of Homes” to showcase their new homes and remodeling projects. Anyone can buy a ticket to the parade and visit the homes. The 2015 Parade of Homes is sponsored by the Greater Iowa City Area Home Builders Association and showcases 24 new homes and 10 remodeling projects.
I’m not sure if anyone actually plans to visit all 34 homes—hey, why not?! If someone did do this, I wondered: which route visiting all 34 homes minimizes total driving time?
This type of problem is known as the traveling salesman problem and has a long history in business, computer science, and mathematics. And it has many practical applications. For example, UPS and FedEx solve it every day when delivering packages. It even got some recent attention from the Washington Post.
I coded up a completely automated calculation of the fastest route using R, Google Maps, Leaflet, and the Concorde TSP solver. The Concorde code took just a split second, but the minimum drive time is 3 hours and 46 minutes. The route is depicted here (with corresponding table below):
| House | Address | Type |
|---|---|---|
| 1 | 2826 120th St, Shueyville | New Construction |
| 12 | 408 Dogwood Lane, Tiffin | New Construction |
| 14 | 1059 Camp Cardinal Rd, Iowa City | New Construction |
| 13 | 1266 Eagle Place, Iowa City | New Construction |
| 15 | 802 Ryan Ct, Iowa City | New Construction |
| 17 | 903 Tipperary Rd, Iowa City | New Construction |
| 16 | 1610 Dunley Ct, Iowa City | New Construction |
| B | 1915 Calvin Ave, Iowa City | Remodel |
| 24 | 1426 Walter Mapp Dr, Riverside | New Construction |
| 23 | 1048 Bluegrass Dr, Riverside | New Construction |
| 22 | 3070 Vine Valley Dr, Riverside | New Construction |
| J | 208 Brady St, Hills | Remodel |
| I | 4721 Chandler Ct, Iowa City | Remodel |
| 21 | 192 Lindemann Dr, Iowa City | New Construction |
| G | 631 Second Ave, Iowa City | Remodel |
| H | 1824 G St, Iowa City | Remodel |
| F | 401 Garden St, Iowa City | Remodel |
| E | 1802 Winston Dr, Iowa City | Remodel |
| 20 | 1317 Rochester Ave, Iowa City | New Construction |
| D | 1324 E Davenport St, Iowa City | Remodel |
| C | 603 River St, Iowa City | Remodel |
| 18 | 775 Barber Place, Iowa City | New Construction |
| 19 | 946 Canton St, Iowa City | New Construction |
| 9 | 3017 Woodland Ridge Dr NE, Iowa City | New Construction |
| A | 9 Chad Ct, Coralville | Remodel |
| 11 | 1981 Ollinger Dr, Coralville | New Construction |
| 10 | 2095 Dempster Dr, Coralville | New Construction |
| 2 | 395 Radcliffe Dr, North Liberty | New Construction |
| 4 | 2020 Silver Maple Trail, North Liberty | New Construction |
| 3 | 1925 Silver Maple Trail, North Liberty | New Construction |
| 8 | 1000 Wood Lily Rd, Solon | New Construction |
| 7 | 718 Raymond Dr, Solon | New Construction |
| 6 | 704 Raymond Dr, Solon | New Construction |
| 5 | Majestic Oak Ridge, Solon | New Construction |
- Download the R source code.
- I used these instructions to install Concorde on my Mac.
← Return to Projects and Posts