I start off this post by providing a gentle introduction to a specific mathematical problem that has numerous practical applications. I then dive into some technical details and my thoughts on an interesting, recently published paper. You’ve been warned. I’ll try to make it interesting.
My dad showed me Charles ReVelle’s article about the Roman Legions Problem a lifetime ago, just as I was starting at Johns Hopkins. The Problem is a neat puzzle. I was hooked. I took all of Dr. ReVelle’s courses. He became my unofficial advisor.
Intro to Operations Research
The Roman Legions problem is an operations research problem, a special type of math problem where you minimize or maximize a given function known as the objective function by modifying certain variables known as decision variables. You are restricted from violating given mathematical relations known as constraints. The objective function and constraints often include constant values known as model parameters.
I find it fascinating how you formulate and then solve such a problem. You must select an objective function and constraints so that when the problem is solved the resulting decision variables provide useful information, like where to locate the Roman legions. Your constraints must force the variablesto take on values that make intuitive sense. There is no point in a formulation that tells you to place -1 Roman legion in Constantinople.
You generally strive to make all functions as simple and intuitive as possible. You also choose a formulation that allows you to find a solution relatively quickly. It can help to survey established formulations. There are well known algorithms for rapidly finding solutions to such formulations, and many of the formulations are capable of representing large numbers of seemingly unrelated practical problems.
It is magical when you are able to quickly get the solution to what initially seemed to be a tricky problem. It is interesting when you realize the problem which you need to solve is mathematically equivalent to what initially seems like a totally unrelated issue.
I am particularly interested in operations research problems related to geography and transportation. It’s remarkable how many of the world’s best operations researchers study transportation. Perhaps there is some relationship between being obsessed with maps and with math puzzles. Is there such a thing as map-math heads?
The Traveling Salesman Problem
The Traveling Salesman Problem is the most famous operations research problem. A salesman must visit a set of locations and return home. The goal is to minimize the distance traveled. The decision boils down to selecting the order in which the locations are visited.
The distances between locations are model parameters. It’s interesting to note that, at the transportation tech companies I’ve worked at, the estimation of quantities like this is a very important issue in its own right. You’ll sometimes find a disconnect between what academics study and what’s important in practice, particularly when it comes to transportation network companies.
Most formulations use one binary decision variablefor each pair of locations, representing whether or not the salesman goes directly from the first of the locations to the second. (Binary decision variables must be set to a value of 0 or 1.) If you know which of these decision variables are set to 1, you can construct the optimal path for the salesman. There are other ways to formulate the problem but these decision variables allow for a relatively compact mathematical representation of the problem. The algorithms that find the best paths for the salesman the fastest often assume a formulation that uses decision variables like these. Neat right?
A key technical challenge involves ensuring that a solution does not include a “sub-tour,” for example having the salesman go from location A to location B and from location B to location A. If your formulation isn’t quite right, such a sub-tour could trick you into thinking that both locations have been visited when neither location is linked to the rest of the salesman’s path. The end result will be a nonsensical route for the salesman.
The Vehicle and Taxi Routing Problems
The Vehicle Routing Problemis a generalization of the Traveling Salesman Problem and a well known problem in its own right. You have a set of vehicles and a (larger) set of locations to visit. You must specify routes for all the vehicles so that they collectively visit all the locations. There are numerous practical applications; for example consider how Amazon delivers all of the packages we’ve been ordering lately.
A common extension involves time windows that restrict when each location can be visited. The requirement that all locations be visited is often removed. You must then choose which locations to visit, committing to visiting those locations during specific time windows.
In the online version of the problem, all the relevant information is not available initially. Requests show up over time, as vehicles operate on their routes.
The Taxi Routing Problem is a special form of an online version of the Vehicle Routing Problem with time windows. The vehicles are referred to as drivers, and the drivers serve riders. Each rider has to be taken between pickup and dropoff locations. It’s not as different from the classic Vehicle Routing Problem as you might think, as we’ll see.
Personal History
I first came across the Vehicle Routing Problem in 2008. I was working for NASA studying aviation. I had talked them into letting me work in Germany for 2 months as an exchange researcher with the German Aerospace Center (DLR). DLR was in the middle of the CARMA project, an attempt to optimize the movement of service vehicles at Hamburg Airport. It was a dream project for a map-math head like me.
I quickly became convinced that we were working on a specific type of Vehicle Routing Problem. My German manager and I published a paper exploring this idea. The paper won an award at an aviation conference but was otherwise forgotten. I doubt that the algorithms I developed are used anywhere today. But I still remember being lost on the outskirts of a small town in the middle of northern Germany, obsessed with the Vehicle Routing Problem for 2 months.
Fast forward to today. We have started a journal club at Scoop and I am organizing the next session. I notice that 2 of the most famous operations researcher professors at MIT and their PhD student recently published a paper on the Taxi Routing Problem. The problem seems salient for transportation tech companies. The paper is remarkably well written and easy to follow. There are lots of neat little math-y tricks. My obsession with the Vehicle Routing Problem has been rekindled.
I’ll spend the rest of this article diving into technical details. The math I present is very much based on the MIT paper, although I’ve changed the notation and even the formulation slightly. I made most of the changes to simplify things. But I’ve also included a tweak to the formulation based on my own work on the CARMA project (more on this later). Hopefully this inspires some new map-math heads. At the very least, it’s helping me organize my thoughts and prepare for journal club.
Decision Variables
Let’s start with the decision variables.
The first two types of decision variables are the two most intuitive. In an optimal solution, these variables will tell us which riders we pick up and when we pick them up. To relate the two and ensure our decision variables take on values consistent with what they represent, we will need to construct paths for the drivers. We do this via the third and fourth types of decision variables.
When I studied the Vehicle Routing Problem (a dozen years ago!), formulations used decision variables with 3 indices. Does vehicle i visit location k immediately after location j? It makes intuitive sense, but if you have many vehicles and locations you end up with a huge number of decision variables.
Here, all decision variables only have 2 indices. You specify which rider, if any, each driver picks up first. You also specify which rider, if any, comes after each other rider in some (any) driver’s route. If these decision variables are set, you can construct each driver’s route. One of my first thoughts here is that it’s really neat that we have a formulation likely to involve fewer decision variables.
Another thought I have, and had a dozen years ago, is that the Vehicle Routing Problem is two problems in one. We must assign the riders to specific drivers and then solve the Traveling Salesman Problem, or something like it, for each driver. Here the c and d decision variables hint at this way of splitting (decomposing), the larger problem. The new formulation also hints at an imperfect but potentially fast strategy (a heuristic), where riders are sequentially added to a set of incomplete driver routes. These are my somewhat random first thoughts.
Model Parameters
Next, let’s examine the model parameters.
We derive some reward for serving riders. We can think of this as the profit or revenue for our taxi firm. The relevant parameters mimic the decision variables listed previously. I’ll talk more about this when introducing the objective function.
We specify the time windows during which each rider can be picked up, as mentioned previously.
We also specify how long it takes each driver to get to each rider, and to go between riders. Here again, we are mimicking our decision variables. Note that our decision variables specify pickup times so we really care about the time between pickups — including both the time a driver spends taking passenger 1 to their destination and the time it takes the driver to then travel alone to passenger 2’s trip origin. At least for me, it now becomes clear why the Taxi Routing Problem is just a special case of the Vehicle Routing Problem. Note also that we only care about the minimum of the relevant travel times. We assume that we can add any amount of delay to any driver’s schedule as needed.
The Objective Function
The objective function is just the sum total of the rewards we receive for serving riders. We want to maximize this function. We only receive a reward if we serve a rider, which is indicated by one of our decision variables being 1.
Our rewards are based not just on whether or not we serve a rider but also on what happened immediately prior to us picking up that rider. Note in particular that this formulation allows us to penalize for dead heading, for example when a driver must travel between one rider’s drop off location and the next rider’s pick up location.
Ignoring dead heading, we could have a fixed reward for serving a rider. We could even a fixed reward for serving any rider. In that case, we’d just maximize the number of riders we serve. Our formulation allows this. In these cases, we would set groups of model parameters equal to the same value. No problem. But our formulation is more general than that.
Constraint Set 1
Next let’s examine the constraints that exclusively focus on the binary decision variables.
The first constraint ensures that each driver is only assigned at most one rider to pick up first. The second constraint ensures that, for each rider j, we can only think of picking up other riders immediately after dropping off j if we have committed to serving j. Furthermore, we can only have at most 1 of these next pickups.
The third constraint ensures that our variables are consistent, that selecting to pickup rider k means we either have chosen some driver i to pickup k first or we have chosen to pickup rider k immediately after dropping off rider j. Note that this constraint together with the requirement that these decision variables be binary ensures that no solution involves picking up a rider more than once. For any rider k, at most one of the relevant c and d decision variables will be set to 1.
We have specified |I|+2*|J| mathematical relations, where |I| is the number of drivers and |J| is the number of riders. It is remarkable how efficient the formulation is with regards to the number of relations specified.
Even more importantly, the objective function together with the constraints shown above form a relatively simple sub-problem. We can remove (relax) the constraint that the decision variables be binary and let them be real valued numbers between 0 and 1. There will be an optimal solution to the resulting problem where all decision variables are 0 and 1 anyways. This allows us to use relatively fast linear programming algorithms to solve what looks like a typically harder to solve binary or integer programming problem. In particular, the problem is a type of problem called a Network Flow Problem that is relatively easy to solve, at least for small “networks.” We’ll return to this when we talk about solution strategies.
Constraint Set 2
There are additional constraints that focus on the timing of rider pickups.
The first constraint shown above ensures that each rider’s pickup time is within the relevant time window. The second constraint is more complex. Recall, from the preceding section, that for any rider k, at most one of the relevant c and d decision variables will be set to 1. All the other decision variables will be set to 0. The second constraint then specifies that if some driver i is to pickup k first, then the pickup time must be after the earliest possible time i can get to k. If k is to be picked up immediately after j, then the difference between the pickup times must be at least the fixed minimum time between these two pickups.
The second constraint shown above is my own simplified version of two separate constraints provided in the paper by the MIT authors. Those authors chose to deal with the two if statements mentioned at the end of the preceding paragraph separately. I chose to combine them. This is based on a trick I applied in the CARMA project. It worked well for me in that instance. We’ve reduced the number of constraints and, at least to me, the formulation is a little cleaner.
It’s possible I’ve missed something here as I’ve spent a few days on this and others have definitely studied this problem more intensely, for a longer period of time. The MIT authors focus on the online version of the Taxi Routing Problem, while I’ve purposefully minimized discussion of the complications that arise in this context to simplify things. Let me know if you have thoughts here.
(Starting to Talk About) Solution Strategies
In the CARMA project, I tried to get good solutions to the Vehicle Routing Problem by using an algorithm that first fixed the binary variables. We can imagine doing something like that here.
Note that if we have specified values for the c and d variables, then it becomes very easy to set the b variables. Focus first on the riders that some driver picks up first (as indicated by a c variable set to 1). Each of these rider’s pickup times will have to be greater than both the time for the relevant driver to reach them and the start of the relevant time window. Set each pickup time to the larger of the two relevant lower bounds. Then look at the riders picked up next. Each of these rider’s pickup times will have to be greater than both the prior rider’s pickup time plus the minimum time between these two specific pickups and the start of the relevant time window. Set each of these rider’s pickup times to the larger of the two relevant lower bounds. This might sound complicated in words, but it’s remarkably simple math and code.
The MIT paper turns my idea on its head. (I was so close and yet so far.) Imagine having specified values for the b variables (the pickup times) but not the a, c, and d variables. If the pickup time windows are relatively short, then this becomes a particularly useful way to think about the problem (more on this later).
The first of the constraints in what I’m calling Constraint Set 2 is irrelevant if we’ve chosen reasonable (feasible) b variables. In the authors’ algorithms, they actually choose the pickup times based on the given time windows.
The other constraint here is more interesting. Recall that for any rider at most one of the relevant c and d decision variables will be set to 1. Our choice boils down to picking one of these variables. For any rider, our constraint boils down to the rider’s pickup time being greater than either some known t parameter or some other rider’s pickup time plus some known v parameter. This will either be true or false. In a world where we know the pickup times, this constraint simply (and quickly) rules out certain choices. That’s all it does. Put another way, for any given rider and driver, either the driver can or cannot reach the rider before the (assumed specified) pickup time. For any given pair of riders, either the time between the pickup times respects or doesn’t respect the minimum time between pickups. This constraint forces certain c and d variables to 0. It is otherwise irrelevant.
The MIT paper describes an algorithm that randomly selects numerous sets of b variables (rider pickup times), removes no longer feasible c and d variables (see preceding paragraph), and then solves the relatively simple problem comprised of the objective function together with Constraint Set 1. This “maxflow” algorithm gets relatively high quality solutions to the Taxi Routing Problem relatively rapidly, particularly when time windows are short.
The paper gets more interesting as it builds off this idea, taking huge examples (instances) of the Taxi Routing Problem and using the maxflow algorithm to intelligently reduce the size of the problem before solving it. The authors develop an application capable of “dispatching in real time thousands of taxis serving more than 25,000 customers per hour.”
This blog post is already entirely too long so I’ll talk more about this in a follow-up post, assuming both you and I still have interest in it. I’m a little surprised if you made it this far. Congrats! Maybe you too are a map-math head.
Leave a Reply