Winter road maintenance activities include removal of snow and ice from roadways and spreading materials to provide safe and efficient service for road users. Iowa DOT District 3 is responsible for servicing about 4,000 lane miles from 20 depots for winter road maintenance. Two types of maintenance trucks with different capacities (12,000 or 16,000 pounds of solid material) are primarily used in Iowa. The current routes for District 3 are designed based on staff knowledge and past experience. To minimize the deadhead distance (travel while not actively treating roadway) and meet service expectations, two optimization problems were identified and solved. The first problem was to design the optimal truck routes for winter maintenance for single depots under the district’s current responsibility maps. The second problem was to design routes for multiple depots with intermediate facilities. The study used data from two winter seasons, from October 1, 2016, to April 1, 2017, and from October 1, 2017, to April 1, 2018.