February 27, 2025 by Cyril Noirot

Optimizing the last mile: How data-driven decisions transform grocery delivery economics (part1)

The grocery delivery optimization problem deals with assigning customer orders to shoppers and determining the optimal routes for fulfillment. The goal is to minimize the total delivery time while satisfying various constraints such as store capacity, shopper availability, and customer requirements.

Sets and indices

• $S$: Set of stores, indexed by $s$
• $C$: Set of customers, indexed by $c$
• $P$: Set of shoppers (delivery personnel), indexed by $p$

Parameters

• $d_{sc}$: Distance between store $s$ and customer $c$
• $d_{ps}$: Distance between shopper $p$ and store $s$
• $t_{sc}$: Time to fulfill customer $c$’s order from store $s$ (including shopping and delivery)
• $Cap_s$: Maximum number of orders that can be fulfilled from store $s$
• $Max_p$: Maximum number of orders that shopper $p$ can handle in a batch.

Basic model:

Decision variables

Basic model

The basic model simply assigns each customer order to a shopper and a store, but it doesn’t explicitly encourage combining multiple orders into a single trip. In this model, a shopper could potentially pick up one order from a store, deliver it, then return to the same store for another order.

• $X_{scp} \in {0,1}$: Binary variable that equals 1 if customer $c$’s order is fulfilled from store $s$ by shopper $p$, and 0 otherwise.

Mathematical Formulation: Basic model.

Objective function

The objective is to minimize the total delivery time:

$$ \min \sum_{s \in S} \sum_{c \in C} \sum_{p \in P} t_{sc} \cdot X_{scp} + \sum_{p \in P} \sum_{s \in S} d_{ps} \cdot \mathbb{1}\left[ \sum_{c \in C} X_{scp} > 0 \right] $$

where $\mathbb{1}[\cdot]$ is an indicator function that equals 1 if the condition inside is true, and 0 otherwise.

Constraints

1. Each customer order must be assigned to exactly one store and one shopper: $$ \sum_{s \in S} \sum_{p \in P} X_{scp} = 1, \quad \forall c \in C $$

2. Store capacity constraint: $$ \sum_{c \in C} \sum_{p \in P} X_{scp} \leq Cap_s, \quad \forall s \in S $$

3. Shopper capacity constraint: $$ \sum_{s \in S} \sum_{c \in C} X_{scp} \leq Max_p, \quad \forall p \in P $$

4. Linking constraint for store visits: $$ \sum_{c \in C} X_{scp} \leq |C| \cdot Y_{sp}, \quad \forall s \in S, \forall p \in P $$

5. Binary variable constraints: $$ X_{scp} \in {0,1}, \quad Y_{sp} \in {0,1}, \quad \forall s \in S, \forall c \in C, \forall p \in P $$

Mathematical Formulation : Batching model.