Engineering Insights: How we use Non-Convex Optimization to find the Best Surfer to Deliver your Kyte

Kyte EngineeringNov 17, 2020

Once booked, your Kyte will be delivered directly to your doorstep by one of our “surfers” (= Kyte delivery driving partners) saving you the hassle of the traditional rental car pickup, waiting in line and getting frustrated by filling out a ton of paperwork. In this article we want to shed some light on one of the most central challenges that our engineering team is solving for: Automatically finding the best surfer to deliver your car exactly where and when you need it.

This article is the first one as part of a series of engineering-focused posts that are giving some background on what’s happening under the hood at Kyte, what engineering culture is like at Kyte and what other exciting problems we are tackling.

Our Goal: Improving the Matching between Surfer and Kyte Trips Helps both Customers and Surfers

There are plenty of reasons why having a good automated matching algorithm is beneficial for both our customers and surfers:

• Customers get their Kytes as fast as possible: Within seconds after a booking comes into our system the algorithm can find the best surfer available that can start right away with preparing the vehicle and heading over to the delivery location.

• We can offer customers more flexibility to make changes to their booking: Using the Kyte app our customers can extend or change their drop-off location. The matching algorithm allows us to dynamically check which alternative drop-off locations and times we can offer based on how busy our surfers are during that time.

• We maximize our surfers' earnings by making their schedule more efficient: The matching algorithm optimizes the sequence of trips for each of our surfers. We minimize idle and transit times. This allows our surfers to do more trips and consequently earn more during the time they want to work.

• We can use our available Kyte fleet as efficiently as possible: With a growing number of trips we can exploit system efficiencies. For example if a vehicle is dropped off close to where a car will be picked up soon, our surfer can actually clean and prepare the vehicle in that are rather than bringing it all the way back to our depot.

Problem statement: Surfer Matching is a Hard Mathematical Problem with Temporal and Spatial Constraints

Let’s take a closer look at the structure and constraints of the mathematical problem that lies behind finding the best surfer for a Kyte trip. In its most basic form (disregarding spatial constraints and assuming a fixed delivery and return time) the problem can be seen as a classical interval scheduling problem. The only hard constraint would in this case be that a surfer can only do one trip at a time. The figure below shows an example setting where the green three trips need to be fulfilled by any of the three surfers.

Matching diagram 1.

This interval scheduling problem can be translated into a graph coloring problem. Where each trip or unavailability is a node in the graph and we draw edges between all the nodes that overlap on the time axis. Each color corresponds to a surfer. Finding a schedule that works is then equivalent to finding a graph coloring so that neighboring nodes never have the same color. While there are many efficient algorithms for coloring a completely uncolored graph, it is in general a very hard (NP-hard) problem to finish coloring a graph with pre-colored. Since surfers are not available all day we will always find pre-colored nodes in our graph (see the “Unavailable” nodes in the Figure below).

Matching diagram 2.

On top of that, the graph representation can only contain temporal hard-constraints while in reality the time needed for a delivery or return highly depends on the surfers current location. This is why we need a further analysis of all the potential solutions we can find to the graph-coloring problem. And here is where heuristics for non-convex optimization problems come into play.

In the case of the situation in the figure below we ultimately have two different options for the return trips, it could either be done by Surfer 2 or Surfer 3.

Matching diagram 3.

Which out of these options is the better one depends on multiple factors that we have not considered in our temporal hard constraints so far:

• Transit times between consecutive trips: If a surfer has a consecutive trip in a similar region it is beneficial to offer the trip to him. This will minimize the transit time.

• Possibility to do vehicle “flips”: Cars of the same category that are picked up can potentially directly be delivered to the next customer. However, we also need enough time between the trips to check, sanitize and refuel the car.

• Initial location of the Surfer: If the surfer does not have another trip before it is better for him to start with a trip close to where he currently is.

To distinguish the best option we designed a cost function that takes the aforementioned parameters into account. Unfortunately, this cost function does not fulfill the criteria for a convex function. This means that if we want to find the optimal match between trip and surfer given all of these criteria there is no algorithm that can guarantee to deliver the global optimum solution in finite time.

Fortunately, we do not need to have this guarantee but it is sufficient for us to find a sufficiently good (close to optimal) solution. There are multiple heuristics that find such a sufficiently good solution efficiently. In the next section we will talk a bit more about which of these heuristics we decided to use and how it concretely works.

Approach: We use a Heuristic that Helps us Find a Nearly Optimal Solution in Reasonable Time

We are using a popular heuristic for non-convex optimization problems.

In general it is based on two core principles:

• Exploring neighborhoods to gradually find better solutions: We start with a random solution and then evaluate how the solution performs if we change it a little bit. From this “neighborhood” around the current solution we pick the one that performs best. Then we create a new neighborhood around this solution and again pick the new best, and so on. This means that with every step we take we will gradually improve until we have a sufficiently good solution.

• Keeping a list to prevent being stuck: There are cases where strictly adhering to the principle above leads to a behavior called cycling. It means that we always go back and forth between two solutions that are okay but we never make steps far enough to actually explore a region of solutions that are even better. To prevent this we keep a list of all the solutions we already picked in the past. We will then never go back to a solution that we already visited recently. This forces the algorithm to explore sub-optimal directions from time to time which prevents being stuck in a local optimum.

We have ambitious plans! - Join us to make them reality!

While we are already using the first version of the matching algorithm in our day-to-day operations we don’t stop here. We have ambitious goals to add a plethora of features and make our algorithm even smarter. Let us give you a quick look into some things we are currently working on:

• Optimize short notice bookings in batches: As we get more and more short notice bookings in, it will be beneficial to group them in batches and then optimize for this group of new trips. This will make the overall schedule better compared to taking a greedy approach for each single trip as they come in.

• Use machine learning to better predict transit times in between trips: Since we explore hundreds of thousands of potential schedules it is infeasible to compute the exact transit estimates for each of these options. However, we can learn a heuristics that will give us a sufficiently good and fast estimate of how much gap in between trips to plan for during a certain time of the day and depending on both trip locations.

• Dynamic Pricing for customers: Sometimes it doesn't really matter to customers if they drop off their Kyte at 8 PM or 9 PM but depending on the availability of surfers it might be much easier for them to accommodate for one of these options.

As you can see we have lots of exciting projects on our agenda! If you are somebody that loves to work on real-world hard engineering challenges that combine the physical and digital world in a fast-paced environment, we would love to get in touch with you! Please don’t hesitate to shoot us a message at careers@drivekyte.com and we can give you some more insights on what we are working on!

This blog post was written by Kyte Engineering.