<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Mathieu Ripert on Medium]]></title>
        <description><![CDATA[Stories by Mathieu Ripert on Medium]]></description>
        <link>https://medium.com/@mathieu_52058?source=rss-da2cc1147060------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*qH80C9IpWVkTqW4waHRRHQ.jpeg</url>
            <title>Stories by Mathieu Ripert on Medium</title>
            <link>https://medium.com/@mathieu_52058?source=rss-da2cc1147060------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 11:01:00 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mathieu_52058/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[How Instacart delivers on time (using quantile regression)]]></title>
            <link>https://tech.instacart.com/how-instacart-delivers-on-time-using-quantile-regression-2383e2e03edb?source=rss-da2cc1147060------2</link>
            <guid isPermaLink="false">https://medium.com/p/2383e2e03edb</guid>
            <category><![CDATA[on-demand]]></category>
            <category><![CDATA[logistics]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[statistics]]></category>
            <dc:creator><![CDATA[Mathieu Ripert]]></dc:creator>
            <pubDate>Tue, 06 Mar 2018 18:39:33 GMT</pubDate>
            <atom:updated>2018-03-06T18:39:52.841Z</atom:updated>
            <content:encoded><![CDATA[<p><em>How quantile regression is used to manage variance and ensure on-time deliveries.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/450/1*nuMqz0Ijg3OAxgiA27iZPQ.png" /><figcaption>Instacart delivery email reminder.</figcaption></figure><p>At <strong>Instacart, we deliver a lot of groceries</strong>. Very soon, <a href="https://news.instacart.com/instacart-announces-nationwide-expansion-one-year-of-free-grocery-delivery-in-texas-and-the-dbc6313ae822">80% of American households</a> will be able to use Instacart. In a previous blog post <a href="https://tech.instacart.com/space-time-and-groceries-a315925acf3a"><em>Space, Time and Groceries</em></a><em> by </em><a href="https://medium.com/u/eac4abbe4148"><em>Jeremy Stanley</em></a>, we talked about how complex our logistics problem can be. In particular, we need to solve a <em>Dynamic Capacitated Vehicle Routing Problem with Time Windows (DCVRPTW)</em>. The goal is to ensure orders are delivered on time and in the most efficient way.</p><p>Our fulfillment algorithm decides in real time how to route our shoppers to grocery store locations to pick groceries and deliver them to customers’ door-steps in as little as one hour.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/560/1*k7UXR6q0JhMbN52W6xzvsQ.png" /><figcaption>To fulfill an order, a shopper needs to drive to the store, picks groceries and drives to the customer location to make the delivery.</figcaption></figure><p>In order to optimize shopper routes, we need to know how much time a shopper will take to deliver a given order. <strong>This is why we built a model to predict delivery times</strong>. The exact features that go into this predictive model and the way the model is built is not the purpose of this blog post. Rather we will deep dive into how this model is used by our fulfillment engine.</p><p>Let’s suppose a customer placed an order for 1pm–2pm. It means we need to plan a trip such that the estimated time arrival (ETA) is between 1pmand2pm. Before 1pm the order is early<em>, </em>after 2pm the order is<em> </em>late<em>.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/765/1*L8zuasrPHKQXL5bnyrjEng.png" /><figcaption>Example of trip planned to be delivered on time, i.e ETA is before the due time.</figcaption></figure><p>But to make sure the order is delivered on time, it is not enough to have the ETA before the due time (2pm). We want the shopper to <strong>actually</strong> deliver the order before the due time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/765/1*EAcN-nHOT3JfbdI57cDbrw.png" /><figcaption>Example of a trip actually delivered on time, i.e the actual arrival time is before the due time.</figcaption></figure><p>In other words, to make sure the order is actually delivered on time, we need:</p><blockquote><strong>Actual Arrival Time = ETA + Prediction Error &lt; Due Time</strong></blockquote><p>Obviously, we do not know the prediction error until the order is delivered, so we need a way to account for how big the predicted error can be. Even if our predictive model is unbiased, we are only correct on average, which means the distribution of errors can be wide. Below is the distribution of the prediction errors in different cities:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/794/1*zRjXuXNeZtt2GpTd8JNmig.png" /><figcaption>Distribution of model errors. Error = Actual-Predicted</figcaption></figure><p>So to account for this, let’s introduce the notion of a Buffer which will be used to cover the model prediction error. Therefore, when planning a trip to a shopper, we need to use a Buffer such that:</p><blockquote><strong>ETA + Buffer &lt; Due Time</strong></blockquote><p>Now the question is: <strong><em>What value do we choose for this buffer?</em></strong></p><p>The buffer needs to be high enough to cover the risk of lateness in most of the cases. But if the buffer is too high, we might lose efficiency by reducing the size of the feasible space of the optimization problem, as fewer shoppers might be considered for a given order.</p><h4>Simple Approach</h4><p>As a first and simple solution, we looked at the percentage of late deliveries we had depending on how close to the due time we planned the delivery to be delivered.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*uvniEjG9-Pe9NtCL2e3LRQ.png" /><figcaption>Percentage of lateness depending on close to the due time we plan the delivery to be delivered.</figcaption></figure><p>For example, in San Francisco, if we plan all deliveries to be delivered 10 minutes before the end of the window, we find that about 18% of deliveries are late.</p><p>We chose a fixed buffer based on the maximum percentage of lateness we were willing to have. We looked the graph above and chose a buffer such that we get 10% of late deliveries in the worst case. Using this approach, we chose 13 minutes for Chicago North, 15 minutes for Manhattan, and 18 minutes for San Francisco and Miami.</p><p>However, this approach was obviously suboptimal. There are some cases where the risk is higher and some cases where the risk is lower. Hence, a fixed buffer may be sometimes too conservative (higher risk of lateness), and sometimes too aggressive (loss of efficiency).</p><p>A better approach would be to compute a prediction interval for the delivery time and use the upper bound of the interval. This is where quantile regression comes into play.</p><h4>Quantile regression</h4><p>First of all, let’s take a moment to explain what a quantile regression is.</p><p>A typical regression aims to fit the mean of the distribution. We try to approximate the conditional mean of the response variable <strong>y</strong> given certain values of the predictor variables <strong>X</strong>. In this context the objective is to minimize is the sum of the squared errors.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O8ug6DyyTnqh3I21t-sQEw.png" /><figcaption><em>y_i</em> is the <em>i</em>th value of the variable to be predicted, yhat_i is the predicted value of y_i.</figcaption></figure><p>In quantile regression, we want to make a set of predictions <strong>Q </strong>so that, for a given quantile <strong>q,</strong> <strong>q</strong>% of the true values are less than <strong>Q</strong>. In this case, we try to minimize the following loss function:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Q-p8EzHLWoY2G54o6-74MA.png" /><figcaption>The special case q=0.5 corresponds to the median regression where the cost function is the absolute deviation.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/739/1*mF9Pv4NNnzZhT1ocEPOgvQ.png" /><figcaption>Cost function for linear regression and quantile regression for different values of q.</figcaption></figure><p>Now let’s suppose that we want to build a simple linear model to predict the delivery time, as a function of the distance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/705/1*GredPjFgA36j_yeRAX4QJg.png" /><figcaption>Linear Regression to predict delivery time as a function of distance</figcaption></figure><p>With quantile regression, we can obtain a prediction interval for the delivery time. Let’s choose q=0.1 for the lower bound and q=0.9 for the upper bound.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/705/1*r6rNyF8bm6TB68A_kx2IIw.png" /><figcaption>Quantile regressions q=0.1 and q=0.9 for the delivery time, used as prediction interval.</figcaption></figure><p>We immediately see that the quantile regressions give us a prediction interval for the delivery time. We notice that the prediction interval increases as the delivery distance increases, which makes sense as it becomes harder to predict accurately for long distances (more variance, less data). Therefore, we see that this prediction interval is much better than adding a global constant to the mean predicted value (c.f. fixed buffer of the simple approach).</p><h4>Back to our problem</h4><p>In our case, we built a second model, a q=0.9 quantile regression for the delivery time. This model will give us an upper bound of the delivery time, that will be used to make sure the delivery will not be late 90% of the time. When dispatching a delivery to a shopper we need to have:</p><blockquote><strong>Prediction from 90th quantile &lt; Due time</strong></blockquote><h4>Multi-deliveries trips</h4><p>In reality, our fulfillment engine tries to generate trips containing up to 5 deliveries, in order to save shopper minutes and increase system efficiency.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/573/1*3vdQcWKwP6IzNklLCseGgA.png" /></figure><p>When planning this kind of trip, we need to make sure that all orders will be delivered on time and we need to manage the risk of lateness. This risk is cumulative. For example, if the shopper takes more time than expected for a given order, this will impact the remaining deliveries in the trip.</p><p>To account for this cumulative risk, the buffer that we need to use for a given delivery needs to be a function of the buffers of the previous deliveries in the trip. Let’s first take the example of a double trip, i.e, a trip containing 2 deliveries D1 and D2.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/484/1*A0-LCabRQ3LcqDGSfpHeuA.png" /><figcaption>Example of trip containing 2 deliveries</figcaption></figure><pre><strong>Dt0-&gt;1</strong> = <em>Predicted delivery time from store to D1.</em><br><strong>Dt1-&gt;2</strong> = <em>Predicted delivery time from D1 to D2.<br></em><strong>Qt0-&gt;1</strong> = <em>90th percentile prediction from store to D1.</em><br><strong>Qt1-&gt;2</strong> = <em>90th percentile prediction from D1 to D2.<br></em><strong>B0-&gt;1</strong> = <em>Qt0-&gt;1 - Dt0-&gt;1 = Delivery Time Buffer from store to D1.<br></em><strong>B1-&gt;2</strong> = <em>Qt1-&gt;2 - Dt1-&gt;2 = Delivery Time Buffer from D1 to D2.<br></em><strong>B0-&gt;2</strong> = <em>Buffer that we need to use to make sure D2 will not be late.</em></pre><p>Now, we need to compute the buffer B0-&gt;2 we need in order to make sure D2 will be delivered before its due time.</p><blockquote><strong>Dt0-&gt;1 + Dt1-&gt;2 + B0-&gt;2 &lt; Due Time of D2</strong></blockquote><p>To approximate this buffer, let’s assume that delivery times follow a normal distribution, and that they are independent.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kqTb-noVQncm9o474CScOQ.png" /><figcaption>Delivery times as independent normal random variables.</figcaption></figure><p>The sum of two independent normal random variables still follows a normal distribution:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*o6WZI61cR8l7MWO7u7M3Hw.png" /><figcaption>Sum of two normal independent random variables.</figcaption></figure><p>We know that for a normal distribution, prediction intervals can be easily computed as <em>[mu — z * sigma, mu + z * sigma] </em>(z=1.67 for 90% prediction interval). So it means:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZSr5gC0aAlk9AznhVWZv-Q.png" /><figcaption>Formula to compute total cumulative buffer for D2 from individual buffers of D1 and D2.</figcaption></figure><p>And finally, the following formula can be used to generalize to a N deliveries trip:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2aCsOgta5NkfIGRUppMjCQ.png" /><figcaption>Generalization of cumulative buffer for the Nth delivery of a trip.</figcaption></figure><h4>Results</h4><p>We performed an A/B test to measure the impact on the efficiency/lateness tradeoff when using quantile regression vs a fixed buffer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XWW4nDqOoRaWHnOiJ_hxyQ.png" /><figcaption>With quantile regression, we are able to plan closer to the due time without increasing late percentage.</figcaption></figure><p>As seen from the graph above, we found out that with quantile regression we were able to plan deliveries closer to their due time without increasing late percentage. This effect allowed us to explore more trip combinations in our fulfillment engine and therefore increase efficiency (one of our most important metric) by 4%.</p><h4>Conclusion</h4><p>In many prediction problems, <strong>you might need to think beyond the mean. </strong>Quantile regression is a very powerful tool for that, as it allows you to approximate any percentile of the distribution, and therefore provides you a more comprehensive analysis of the relationship between variables. At Instacart, quantile regression has been used to better understand and manage the risk of late deliveries.</p><p>🥕 Interested in joining us? <a href="https://careers.instacart.com/">Apply here</a>.</p><p>Want to learn more about how Instacart works? Read <a href="https://www.instacart.com/help/section/200758544#115005491906"><em>here</em></a>.</p><h4>Resources</h4><ul><li><a href="http://www.statsmodels.org/dev/examples/notebooks/generated/quantile_regression.html">Quantile regression implementation in python for linear models</a></li><li><a href="http://scikit-learn.org/stable/auto_examples/ensemble/plot_gradient_boosting_quantile.html">Quantile regression implementation in python for random forests</a></li><li><a href="https://en.wikipedia.org/wiki/Quantile_regression">Quantile regression on Wikipedia</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2383e2e03edb" width="1" height="1" alt=""><hr><p><a href="https://tech.instacart.com/how-instacart-delivers-on-time-using-quantile-regression-2383e2e03edb">How Instacart delivers on time (using quantile regression)</a> was originally published in <a href="https://tech.instacart.com/">tech-at-instacart</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>