Do Ya Reading

You're not asking a question that's never been asked before.

Chances are, you will rarely ever ask a question that's never been studied before. Why? Well, it's 2015 and the world is much more complex than you ever imagined. People in the early 20th century thought we'd progress so fast that people simply wouldn't need to work by the year 2000.

Alas, I ask you this question: given a traveling salesman who has to visit n customers and return home by the end of the day, in what is the shortest possible route for the salesman that still visits each customer exactly once? What if each customer needs to be visited between certain 30 minute windows? What if there are multiple salesmen? Finally - how do we reschedule the salesmen if one of their cars breaks down? People in 1930 couldn't solve this; they didn't have computers. Thus, the world is much more complicated than assembly lines and the Teapot Dome.

This is basically the Data Science for Social Good Paratransit team's problem. It's a much enhanced Traveling Salesman Problem with Time Windows (TSPTW). Our problem is the following: given that King County Metro Access Operations already has a solution to the Vehicle Routing Problem with Time Windows for the next day's ADA paratransit rides, a bus breaks down or a driver doesn't show up. Access Operations can dispatch an entirely new Access bus, send taxis, or potentially reroute already existing Access bus runs to satisfy the broken bus's run. Which is the cheapest option?

Fortunately, there's an extensive body of literature on the Vehicle Routing Problem and Route Disruption Recovery. We're not asking an entirely new question. We are framing it in a new light: we need real-time vehicle rerouting with time windows that minimizes pre-optimized route disruptions (already studied) with hard constraints so that there are no stop cancellations (not studied) which is particular to paratransit context.

In the end, I guess I've misspoken. You'll never be asking an entirely new question, but you may be tweaking a previously well-understood question to the point where the prior methods for solving are now useless. Let's hope that's not the case here!