Flexible Slots — Helping partners to get maximum earnings through Customer flexibility
By — Kartik Verma (Engineer, Marketplace Team)
Have you ever wondered why a few e-commerce companies give us a time range for delivery, rather than an exact time? Is it because they don’t know the exact delivery time, or is there more to it? This is also true for other organizations where you schedule a delivery like groceries etc. At UC, we think there is more to it than simply our ability to promise an ETA. Let’s look at this interesting phenomenon in this blog.
One of the core value propositions of Urban Company is “convenience” — we give our customers the convenience to choose a slot at which they can avail any of our plethora of home services. It’s a delight feature — customers can choose whenever they have time during the day rather than sticking to someone else’s time. But under the hood, one person’s delight maybe someone else’s dismay. How?
Let’s say our salon specialist is available from 1:00 PM to 4:00 PM. She can do 2 jobs in this duration. Each job takes one hour, and she requires 30 minutes to travel to the next customer.
On this day, she can start one job at 1:00 PM, and the next at 2:30 PM. But what if a customer made a booking for 2:00 PM? This will result in:
- Partner is idle for the first hour (1:00–2:00 PM).
- Another customer can’t avail the same partner till 3:30 PM
- In effect, this specialist can do only one job that day, instead of two that she would love to do and take home the extra money!
What would be a win-win situation here? Can we do something to help both the Salon specialist and not disappoint the customer (Two customers, considering an extra customer being served)? We want to ensure that as an organization, we do our utmost to enable our partners to succeed.
This was our take on this problem:
- If we give customers an option to choose a time range rather than an exact time, let’s say 1:00–4:00 PM, customers can expect a partner to come anytime in between this time.
- Now, if 2 customers select this slot, we can assign the same partner to them where one customer will be served from 1:00–2:00 PM and another will be served from 2:30 -3:30 PM.
Of course, this is easier said than done: We will need to do something called “Demand shaping”, shaping the peak demand at a time to a distributed curve. In our instance, we basically shifted a customer from the 2:00 PM job [peak time] to 1:00 PM and accommodated one more customer at 2:30 PM.
Now for the technical part on how we did it:
We found there are many algorithms that can solve this problem. We finally went ahead with the two algorithms.
We wanted to optimize job packing in partners’ calendars so that more jobs could be assigned with as little packing loss as possible. This sounds like the Bin packing problem. In this case, the partner’s working hours could be the size of the bin, and the job could be an item with a duration equal to its weight. This is an NP-Hard Problem, determining the minimum number of bins takes exponential time.
What is the p50 job duration?
It is the median of all job durations for a given category.
We have a partner for a job after using the Best Fit Decreasing Algorithm, but the start time needs to be determined so that it results in the least packing loss in the partners’ day calendar. And we accomplish this with the help of the Branch and Bound Algorithm. We use p50 job duration as the Objective Function in the Branch and Bound phase, which we maximize when determining the job start time. The more p50 job slots that are available, the more demand we can take in the future.
Algorithm Steps
- Get all partners and jobs for the assignment.
- Sort the jobs in decreasing order of duration.
- For Each job, get the remaining working hours for all partners from their calendars. And sort the partners in descending order of their working hours.
- Begin with the partner having just enough working hours to accommodate the incoming new job in the calendar.
- Apply Branch and Bound on the new job and partners calendar to determine the start time of the job such that p50 job slots are maximized in the calendar.
While the basic algorithm works as above, there were a few other factors we also factored into the algorithm.
Starvation Score
The starvation score is a real-time score at the partner level that helps prioritize starved partners for jobs when other important metrics are not at stake. If the demand is sufficient, starvation score-based sorting ensures that partners are given at least minimum jobs. The distribution of jobs among the partners was skewed. We do not want to starve them. We use the starvation score for each partner and prioritize accordingly.
Travel and Packing Optimization
When distributing jobs, we try to minimize the distance traveled by the partner as well as their idle time. This takes into account previously assigned next and previous jobs for a given time period. As a result, we assign them jobs that are very close to one another.
Impact
With this small change, we are now able to give more jobs to our partners in the same time frame, this means more jobs are being delivered with the same number of partners and thus our partners’ earnings are also increasing.
Other Impacts
Fill Rate: It is also known as the partner job packing rate and it went up by 9% combined with all international geographics.
Util: It is the number of jobs partners are doing in a given time period and the average partner util has improved from 1.8 to 2.2.
Team at work
Kartik Verma (SDE), Saurabh Bora(SDE), Mohammed Hamza (SDE), Manuj Dixit (SPM), Siddharth Kumar (SEM), Rajesh Kumar (DoE)
About the author —
Kartik Verma is a part of the Marketplace vertical at Urban Company, solving complex Matchmaking problems. He loves dogs and enjoys table tennis. In his free time, you can find him watching anime and reading mangas.
Sounds like fun?
If you enjoyed this blog post, please clap 👏(as many times as you like) and follow us (@UC Blogger). Help us build a community by sharing on your favourite social networks (Twitter, LinkedIn, Facebook, etc).
You can read more about us on our publications —
https://medium.com/uc-design
https://medium.com/uc-engineering
https://medium.com/uc-culture
https://www.urbancompany.com/blog/humans-of-urban-company/
If you are interested in finding out about opportunities, visit us at http://careers.urbancompany.com
