Modeling vehicle availability at Turo

Turo is a peer-to-peer car-sharing marketplace. Through Turo, “guests” can book cars owned by “hosts” for trips ranging anywhere in length from a day to a year. Turo supports a surprisingly wide variety of use cases; we see folks taking their dream cars for a ride around town, running errands for a weekend, and going on weeks-long road trips.

There are lots of ways guests might use a host’s car. At the same time, there are lots of different ways hosts might want to use their own cars. Some might only want to part with their car for a day or two while they’re out of town while others might want to have their car out on the road for a month while they take an extended backpacking trip across Europe.

To make sure that Turo hosts get trip requests that work for them and that Turo guests only see cars that are sure to be available for their trip times, we’ve introduced a variety of tools for hosts to describe when they’re available and what kinds of trip requests they’d like to see. Although each individual tool is easy to reason about in isolation, they can interact in complex ways. It’s easy to find out if a vehicle is available at specific times, but surprisingly difficult to figure out when a vehicle is available if not at the chosen times.

In this post, we’ll explore Turo’s vehicle availability tools, build a conceptual model for vehicle availability at Turo, and discuss some practical applications for that model.

Availability settings

To get started, lets identify all of the knobs and dials a host can adjust to manager their car’s availability.

The very first tool we built to let hosts manage their car’s availability is the ability to set times when the car simply isn’t available. We built this feature early on because hosts frequently need to reserve their cars for their own use or for maintenance.

Over time, we learned from our community of hosts that they were frequently getting requests for trips that made little sense for their use cases. Hosts whose cars were only available on the weekend were getting requests for weeks-long trips. Hosts who were going to be leaving town for a two-week vacation were getting requests for trips that only lasted a day. Based on the feedback from our host community, we introduced tools to let hosts specify minimum and maximum durations for trips in their cars. On a related note, we also added tools to express how much advance notice they need before their car can be booked.

Most recently, we observed that even though hosts were getting requests for trips of appropriate durations, the hosts themselves might not be around to hand off the keys even if the car were available. To scratch that itch, we built features to let hosts set a schedule for their own personal availability independent of their car’s availability. Those features allow hosts to set recurring “business hours” for key handoff and also to identify one-off times when they won’t be available (for example, “I can hand off keys on all day on weekends and on weekdays before noon, but I won’t be around next weekend”).

To recap, we have quite a few settings we need to consider to figure out if a car can be booked for a specific interval. They are:

1. The vehicle’s availability
2. The host’s preferences for the minimum and maximum duration of the trip
3. The host’s preferences for advance notice
4. The host’s personal availability for key handoff

We can run through each of those settings in turn to figure out if a host and their car can accommodate a request from a guest. First, we check that the car itself is available for the entire duration of the requested trip. If it is, then we check that the request matches the host’s preferences for lead time and duration. Finally, we make sure that the host is available at the pick-up and drop-off times to facilitate handoff.

It’s easy enough to run through the list to figure out if a host’s preferences allows for a trip at the guest’s chosen times. If it is, great! If not, it would be nice to be able to suggest some times to potential guests when the vehicle is available. That turns out to be surprisingly difficult.

To explain why, let’s work through an example. Let’s say we have a host who has the following preferences:

1. The car itself is available any day in March except the 10th and 11th.
2. The host requires that trips in his car be at least two days long.
3. The host needs at least a day’s notice for any upcoming trip.
4. The host is available before 09:00 and after 17:00 on weekdays and is available all day on the weekends.

Now, let’s say that it’s March 7th and a guest wants to book the car to go visit his sister for her birthday on March 9th. The guest has booked this car in the past and would love to use a familiar car for the trip. The guest finds the car in his list of favorites and chooses March 9th as the date of both the pickup and return. Turo reports that the host has a two-day minimum.

“Well, that’s fine,” thinks the guest. “I’ll just pick up the car a day early.”

The guest changes his dates to March 8th to March 9th. Turo reports that the host has a one-day minimum lead time. There are only 18 hours between the current time and the start of the trip.

“Okay. Let’s just add an extra day on the other end.”

The guest changes his dates to March 9th and March 10th. Turo reports that the vehicle is unavailable, which is true.

By now, the guest is starting to get frustrated. He could try to make small adjustments to the precise hour within each day that the trip starts and ends and try to thread the needle between all of the various timing restrictions (including the host’s business hours, which we haven’t even touched yet), but it seems like Turo should be able to just figure it out and make a recommendation.

At this point, it’s probably worth pointing out that this actually happened. I was trying to book a car that belonged to my colleague, Eric. We’re both engineers at Turo and we had literally built many of the scheduling features that we were struggling to understand. Even sitting next to each other and armed with our combined expertise, it still took us several minutes to figure out when I could actually book Eric’s car.

It seemed like there had to be a better way, and so I set out to find it.

A conceptual model of availability

At first, the main goal of this effort was to find an easy, convenient way to hold all of the pieces of the availability puzzle together at the same time. To recap, those pieces are:

1. The availability of the car itself
2. The availability of the host to facilitate key handoff
3. The host’s preferences for minimum and maximum trip durations
4. The host’s preferences for request lead time

Let’s try to build up a model one piece at a time.

Vehicle availability

The most basic component of availability is the availability of the vehicle itself. The rule for vehicle availability is fairly straightforward: to accommodate a trip, the vehicle must be available without interruption for the entire duration of the trip. In other words, a vehicle can’t accommodate more than one trip at a time, and it can’t accommodate a trip if the owner has marked the vehicle as “unavailable” for any part of the trip (for example, if the owner needs to use the vehicle for their own purposes for a day, or if the vehicle needs to be taken to the shop during the trip).

We can represent this visually by showing an interval (or “window”) of vehicle availability as a linear “chunk” of time that has a definite start and end.

A vehicle availability interval (or “window”) has a distinct start and end time.

In this representation, a vehicle can accommodate a trip as long as that trip falls entirely within a single interval of vehicle availability.

A trip interval is valid if it fits entirely within a vehicle availability window (A). It it falls partially or entirely outside of a vehicle availability window (B) or if it starts and ends in different windows (C), it’s not valid.

So far so good. Even though this model is simple, it captures a few important ideas already. It’s easy for us to see how long a trip is relative to a vehicle’s availability “window,” for example, or how close the trip comes to the edge of one of those windows. We’re only covering one rule for the time being, but this is a solid start.

Host availability

Let’s see how our model holds up when we try to add a host’s personal availability to the picture.

Hosts can describe their availability both by providing explicit intervals in which they are unavailable (“I’ll be out of town from Friday until Monday”) and by specifying recurring “business hours” (“I’m available to hand off keys all day on weekends and before noon on weekdays”). In the end, though, both sources of information produce the same end product: a list of intervals when hosts are or are not available to facilitate a vehicle hand-off.

The rules for host availability are a bit different from the rules for vehicle availability. First, intervals of host availability must fall within an interval of vehicle availability to be meaningful (if a host is around but their vehicle isn’t, they can’t really hand that vehicle off to a guest anyhow). Second, it’s okay if a host isn’t available for the entire duration of a trip; they just need to be available when the trip starts and ends. It’s fine, for example, if a host hands off the vehicle to a guest for a week-long trip, then heads to the beach for the weekend as long as the host is back to receive the vehicle when the guest returns.

Let’s represent an interval of a host’s unavailability as a shaded span within an interval of vehicle availability.

The shaded span within a window of vehicle availability represents an interval where the vehicle is available, but the host is not.

It’s fine if a trip interval passes through a shaded span of host availability, but it must neither start nor end in that shaded span.

Trip intervals may traverse an interval of host unavailability (A), but must not start or end in an interval of host unavailability (B).

So far, our model accommodates both vehicle and host availability well. All of the rules of both systems are represented by a simple diagram, and it’s easy for us to look at a trip interval on that diagram and judge whether the host and vehicle can accommodate that trip.

Minimum and maximum duration

Let’s build on our model and try to add two new pieces: minimum and maximum trip duration preferences. It seems like minimum and maximum duration should also add a “shaded” part to our timeline in which a trip may neither start nor end. As we go to draw it, though, we quickly discover that the location of those shaded zones is dependent on when the trip starts.

We can also represent minimum duration as an “excluded zone” that starts at the beginning of a trip interval, but we can see that the position of the minimum duration zone changes as a function of the start time of the trip.

While we’re adding shaded areas of unavailability based on start time, though, this may be a good time to point out that (trivial as it sounds), a trip can’t end before it starts no matter how the host has set things up.

We can also create an “exclusion zone” for end times such to be clear that trips must end after they start (which seems obvious, but is worth trying to represent in our model all the same).

It seems that we’re looking at a situation where we have to drop a “pin” for the start time and discover what valid ending times exist after we’ve established that start time. Maybe it would be helpful to break our single time window into two: a window for valid start times and a window for valid end times.

We can try separating things into two separate timelines to clarify that the options for a valid end time are a function of where we place the start time.

This does seem to work, but it’s also not very helpful. Rather than being a tool that helps us keep everything together in our heads, it’s turning into more of a worksheet that we need to fill out following a reasonably complex set of instructions. It’s still only slightly better than guessing and checking intervals by running them through a checklist of constraints. This is probably a good time to take a step back and think about other approaches or adjustments to our model.

Expanding into new dimensions

So we’ve come to a place where our model is starting to show some strain and has started being more of a hindrance than a help. How can we adjust it? Could we think of the interval line as being something like a tape measure that can extend up to a certain distance? Or is it more like a telescoping antenna that can shrink down to a certain size? Is it both? Neither?

Photo by Kevin Simpson and used under CC BY-SA 2.0.

It seems like we’re trying to adjust two dials that move two points through the same space. If we take a step back, that sounds a lot like an Etch-A-Sketch. An Etch-A-Sketch is a drawing toy that has two knobs that move a point (a stylus) around a two-dimensional drawing space. Could that be a helpful model for what’s happening here?

Let’s go back to our “two timelines” model from earlier. Rather than having the two timelines running in parallel, let’s make them the axes of a two-dimensional space.

We can turn our two parallel timelines into the axes of a two-dimensional space.

Let’s see if we can add the pieces from our old model back in. We started before with basic vehicle availability. Let’s say that the space is a square, and each side is the length of a vehicle availability window. In other words, if the timeline before represented (as an example) a two-week period when a vehicle was available, the sides of this new two-dimensional “availability space” each represent a two-week duration.

What was previously represented as a two-week long “stick” of time is now represented as a two-dimensional square that is two weeks long on each side.

In a two-dimensional world, we can represent an interval as a point within this space. The point’s horizontal component tells us when the interval start, and its vertical component tells is when it ends. In other words, if we move the point to the right, we have a later start time. If we move it up, we have a later end time.

We can represent an interval as a point in our availability space. The point’s coordinates define the start time (T_s) and end time (T_e) of the interval.

Now let’s try to add host unavailability back into the model. As before, a trip can neither start nor end when the host is unavailable. In a two-dimensional world, we can express the idea of “a trip can never start in this interval” as a vertical “stripe.” To understand why this is true, think about a point in this space that represents an interval. No matter how much we move the point straight up and down, its start time never changes. That means that a vertical line in the space represents all of the possible intervals that have a specific start time. Expanding from there, a vertical stripe represents all of the possible intervals with a range of start times. We can then do the same for the “trip can never end in this interval” idea by adding a horizontal stripe.

Periods of host unavailability are now represented as intersecting stripes instead of a one-dimensional section of a timeline.

So far so good! In the old model, an interval was valid if it fit entirely within a vehicle availability window and didn’t have an endpoint within a region of host unavailability. In this new model, the same idea is at play, but in a slightly different shape: an interval is valid if its point is inside the availability space and does not fall inside a band of host unavailability.

In this model, an interval point is valid if it does not fall inside of a “band” of host unavailability.

And now we can return to the things that tripped us up before: minimum and maximum durations. Let’s start with the one basic “law of physics” we described last time: a trip can’t end before it starts. To put things in mathematical terms, we want to identify the space where end > start. Recognizing that start times are on our x-axis and end times are on our y-axis, that can also be expressed as y > x. To folks familiar with algebra, that looks a lot like the equation for a line. It turns out that’s exactly how we can represent the situation in our new model.

The requirement that a trip must end after it starts is represented as a triangular region bounded by the `y = x` diagonal line.

Similarly, we can express the minimum and maximum duration constraints as equations:

• end > start + minDuration (or y > x + minDuration)
• end ≤ start + maxDuration (or y ≤ x + maxDuration)

Both of those are equations for lines, too, and we can represent those in our two-dimensional space easily.

Our minimum duration and maximum duration rules also create diagonally-bounded regions just like our “end > start” rule.

This is a big, big improvement over our previous model. We have a number of rules that all create regions of unavailability within a two-dimensional availability space. It’s easy to see if an interval, represented by a point, falls within a region of unavailability or not.

Our model lets us see at a glance if an interval point is valid; if it falls in an un-shaded region, it’s valid because it doesn’t conflict with any of our rules.

This model already achieves most of what we set out to do. It helps us keep lots of pieces of a complex picture in our head at the same time, and has a number of really helpful and powerful properties that we’ll discuss in just a minute.

Before we start discussing the applications, though, we can make one adjustment to our axes that makes things a little easier to manage. Instead of using “start time” and “end time” as our axes, we can use “start time” and “trip duration.” That means that, instead of having everything sloping up and to the right, things flatten out into more of a square shape.

Lots of things change when we change the y-axis from “end time” to “duration,” but all of the major pieces are still there. Minimum and maximum duration regions become horizontal “stripes,” and vehicle availability windows turn into triangles. The whole space now satisfies the “end > start” requirement, and so it no longer needs to be drawn explicitly. Host unavailability changes from a “cross” into a “check mark.”

This makes the “must not end before it starts” requirement much easier to reason about because everything in the adjusted space that has a positive duration ends after it starts. The minimum and maximum durations are now horizontal stripes instead of triangular regions. The true motivation for making this adjustment, though, is mathematical: transforming the coordinates in this way allows us to use a practical and simple distance function that obeys the rules of a metric space, which turns out to be really important for figuring out the “when can I have your car?” question. We’ll cover this in more detail shortly.

Applying the model

Now that we have a conceptual model, we can put it to work. We have lots of internal applications for a model like this, but for this post, let’s focus on the two that are most likely to have a visible effect on Turo’s guests and hosts.

Identifying restrictive settings

One really handy thing we can do for hosts is identify when a combination of settings interacts in a surprising way to make it difficult or even impossible to book a host’s car. If, for example, a host has a minimum trip duration of two weeks, but has a recurring obligation every other weekend, there will literally never be an availability window that’s at least two weeks long. As things stand, a host could easily choose those settings and then never know that their vehicle was completely unavailable.

Our conceptual model (coupled with some actual software) can help! Let’s take a look at two different example “availability spaces.”

A schedule (for Eric’s real car!) with a relatively high ratio of availability. The yellow regions are available.

A schedule for a real Turo host with a much, much lower ratio of availability (the regions in yellow). A close look at this host’s availability regions will reveal some cross-hatching within the available regions. This is the result of the host’s recurring daily business hours.

One of these spaces has lots of availability. The other has very little. We can calculate the fraction of the availability space that’s available (a completely unrestricted schedule would have an availability fraction of 1.0 and a completely unbookable schedule would have an availability fraction of 0.0) and use that as a metric to decide whether a schedule is “open” or “restrictive.” We can even calculate the availability fraction for all of the hosts and vehicles on Turo to get a clearer sense for what’s “normal” and what’s an outlier.

Features that help hosts understand how their settings affect their vehicles’ availability will give them insight into their own performance as a host, keep surprises to a minimum, and help guests find the perfect car.

When CAN I have your car?

Our new model of availability also — finally! — lets us answer the question that started this whole effort: “if I can’t book your car at these specific times, when can I book it?”

To answer that question, we generally want to find an available interval that is as similar to the desired interval as possible, and to do that, we need to have some way of measuring how similar two intervals are. Our first step is to define a “distance function” or “metric.” While coming up with a distance function is something of a judgment call, we want to make sure it does two things:

1. It should make sense for the use case. If we decide that two intervals are “similar” from a computational perspective, our guests should agree that the interval we’re suggesting as an alternative is a reasonable substitute for what they originally had in mind.
2. It should conform to the rules of a metric space so we can reliably calculate the distance between points. The details of the math are, unfortunately, a little beyond the scope of this post.

With those rules in mind, we selected a distance function with two rules:

1. For every half hour “tick” (the minimum unit of adjustment for a reservation time) of difference between the start times of the two intervals, we add one “tick” to the distance.
2. For every half hour “tick” of difference between the duration of the intervals, we add one “tick” to the distance.

That means that two intervals that start at the same time but have durations that are different by two hours would have a distance of 4. Two intervals with the same duration but a 90-minute difference in start time would have a distance of 3. Two intervals that start an hour apart and have durations that differ by three hours would have a distance of 8 (2 for the start time, 6 for the duration).

From a guest’s perspective, we think (hope!) this meets the requirement that computationally-similar intervals “feel” similar. Small adjustments (“could you just pick up the car an hour earlier?”) will have small distances, while big adjustments (“I know you said you wanted the car for a week next month, but how about three hours tomorrow?”) will have large distances.

It turns out that, in our two-dimensional space, our distance function is just the Manhattan distance between two points. We mentioned earlier that we had to transform the coordinates of our availability space to make the math work out, and this is why! Prior to the transformation, our distance function created something we called the “time peanut” (or I did, anyhow) that most definitely did not obey the rules of a metric space.

Now that we have a metric space and a distance function, finding the next-best interval is just a matter of finding the closest point that falls within a region of availability.

If a guest wants to book a car at a time when it’s not available, we can find the nearest point that IS available and recommend that as a substitute.

We’ll skip the details of the algorithm for finding the nearest available interval for now, but suffice it to say that it’s very computationally-efficient. For the engineers in the audience, we can find a nearest neighbor with O(log(V + H)) time complexity and O(V + H) space complexity, where V is the number of discrete windows of vehicle availability and H is the number of discrete windows of host availability.

Wrapping it up

It took some doing, but we managed to wrangle a deceptively complicated set of rules governing vehicle availability into a single, coherent model. That model gives us some really powerful analytical capabilities that we can use to make life better for Turo’s guests and hosts both directly in our main product and quietly behind the scenes.

And, of course, all this work should make it easier for me to visit my sister for her birthday this year.