Joris Kinable, an Amazon senior research scientist, has won the 2022 Best Application Award in the operations engineering and analytics (OEA)–focused issue of IISE Transactions, the Institute of Industrial and Systems Engineers’ flagship journal.
His research paper, written while he was a post-doctoral fellow at Carnegie Mellon University (CMU), details the use of constraint programming to optimize routes for Pittsburgh’s fleet of snowplows.
“Winning this award is great,” Kinable says. “It underlines both the value and quality of our work. It was a major challenge, not only from a research perspective, but also to get alignment between the different stakeholders such as the city of Pittsburgh, its Department of Public Works, and the drivers. To actually get to the point where this is a complete project — and not just completed, but where we won this award — is a really nice accomplishment.”
Kinable joined Amazon in December 2019 and became a senior research scientist for Amazon Transportation Services’ Middle Mile team in April 2021. His research encompasses network design and operations, trailer balancing, and dispatch scheduling. More specifically, his work helps determine how to route freight through a connected network of terminals utilizing mathematical optimization, machine learning and decomposition techniques.
The paper, “Snow Plow Route Optimization: A Constraint Programming Approach,” was coauthored by Willem-Jan van Hoeve, an operations research professor at CMU, and Stephen F. Smith, a CMU robotics research professor.
The paper details a scalable model for snowplow route optimization that incorporates side constraints encountered in real-life applications.
The underlying optimization model computes a set of vehicle routes to service a street network in a pre-defined service area, while accounting for various vehicle constraints and traffic restrictions such as service time restrictions, vehicle capacity limitations, road priorities and turn restrictions.
Using data from the city of Pittsburgh, the model computes routes and sends the optimized plans to a centralized system. From there, the routes are pushed to the individual snowplows and communicated to the drivers as turn-by-turn instructions.
The snow plows are equipped with GPS trackers, which allow the centralized system to monitor the plows’ progress along the way. The turn-by-turn automated directions replace handwritten notes that drivers used to carry while they worked to clear Pittsburgh’s 4,800 streets, totaling 1,200 miles.
“We wanted to take away the hurdle of not being able to control where drivers drive and make it much easier for the drivers not to have to memorize routes,” Kinable explained. A test run with actual vehicles demonstrated that Kinable’s approach shortened snowplow routes by up to 156 percent over those generated with commercial routing software.
Kinable noted that future applications of the snowplow model will update in real time when plows need to detour to accommodate an emergency or because they encounter an obstacle in the street. Moreover, the model could integrate with the city’s website to notify people of when they can expect their streets to be plowed.
“That kind of information would really be valuable to Pittsburgh residents,” Kinable says. “It’s really rewarding to see the potential for that kind of real-life community impact.”