Researchers Develop New Method to Optimize Paratransit Systems

(Photo by Kazuma Seki)

Paratransit systems—defined as public transportation providing individualized rides for those who have difficulty using regular transit due to mobility, cognitive, or other disabilities—not only face high levels of uncertainty from complex operations and frequent itinerary disruptions, but also cost 7–12 times more to run than fixed-route systems. 

We asked Dartmouth Engineering Professor Vikrant Vaze, co-author* of the paper published in INFORMS Journal on Computing, about how their new method works to optimize both driver itineraries and cost-effective recovery from schedule disruptions: 

Why do paratransit systems need their own optimization methods?

According to the ADA—the Americans with Disabilities Act—transit agencies are required to provide a comparable level of service to everybody, regardless of whether they have a disability status or not. So, the transit agencies often run a separate system, or a separate fleet of vehicles, to serve this population. 

In many cities, these systems are run by the transit agency directly. But they are, for a variety of reasons, extremely expensive and there's a move toward outsourcing so that private companies can run them, presumably better. 

Why are these systems so different?

These are sparse demand systems, which implies that you can't have a lot of people in the same vehicle. And there's a tremendous amount of uncertainty in terms of where the requests will come from. Although most paratransit users schedule at least a day ahead, cancellations are common. Uncertainty absolutely wreaks havoc in terms of being able to design systems in a near-optimal way.

If you know exactly who's going to cancel, then the problem is much easier to solve. You can just schedule for that. But since you don't know that ahead of time, you have to think about a lot of different scenarios for how tomorrow's cancellations will happen. And you have to make today's decisions in a way that, at least on average, can minimize the cost. 

Exactly what problem does your method try to solve?

The idea of making some decisions now, and then some uncertain things developing, and then taking some recourse action, like modifying the schedule, this is what we call two-stage stochastic optimization. 

So, let's say I'm a driver who's going to pick up five people. Essentially, I'm going to ten places—pick up the first one, drop off the first one, pick up the second one, drop off the second one, etc. I need to figure out how I'm going to do that loop. 

If none of my customers cancel, and I don't cancel anything, then I can just execute my original plan. But typically, something somewhere goes wrong. If I'm unavailable for part of the itinerary, then the planner needs to somehow take care of my customers. If some of my customers cancel, I could just say, 'All right, I have some free time,' and do nothing, but that's a bad situation in terms of cost. So, the planner will slightly overschedule, because you cannot afford to pay people to sit around. But how to do that optimally so that we balance the cost of too much versus too little overscheduling? That's the optimization problem we're talking about.

How did you approach the problem?

Two-stage stochastic optimization has been around for many decades. But the typical type of problem it solves is where the second stage decisions, after the uncertainty materializes, are represented by continuous rather than discrete variables. Discrete here means that you're working with one driver matched with one passenger. You can't assign a fraction of a driver, and that actually makes it computationally much more difficult to solve quickly.

First, what we did is come up with a new kind of mathematical model that avoids this complexity. But the problem is still incredibly complicated because of the sheer number of ways you can schedule itineraries. So, then we used a particular method called Benders' decomposition, which is a famous algorithm developed decades ago. But, for our problem and in its typical version, it takes forever to run because it's an iterative algorithm, and every iteration requires some work. 

Our main algorithmic contribution has two parts. One, we significantly reduce the amount of work needed in every iteration. And, two, we reduce the number of iterations needed to solve the overall problem. So instead of taking days or hours, we can solve it in minutes.

What does it actually look like to implement your method?

Using what we call 'activated Benders decomposition,' combined with our optimization formulation, we manage to reduce cost and improve service in three main ways. 

The first is smarter utilization of on-call drivers both to fill unexpected service gaps—which we call 'recovery outsourcing'—and to cover highly unusual service locations—which we call 'intentional outsourcing.' 

The next is flexibility of recovery actions. Fifty to seventy-five percent of itineraries are not operated exactly as planned, so you need know when to swap drivers or to outsource. Our approach allows planning for that. 

The third is called strategic slack in itineraries to facilitate insourcing. There are certain times of the day when you schedule up to twenty percent more in-house drivers than average to account for a higher level of uncertainty and avoid needing the much more expensive outsourced drivers, so that in the end, you come out ahead.

These are the kinds of knobs we turn, or levers we pull to find a balanced solution. That's what the model is able to do, and it can be applied to other complex transportation problems and reservation-based systems as well, and help to increase quality of service and reduce cost at the same time.

*Vaze's co-authors are Kayla Cummings and Professor Alexandre Jacquillat.