Dynamic delivery request acceptance with strict geographic fairness: a classical yield management approach

We consider the problem of dynamically accepting and rejecting last-mile delivery requests from e-retail customers given a constraint on the total route duration of a delivery vehicle. A strict geographic fairness requirement is imposed on the optimization problem: the probability of accepting an incoming customer’s request cannot depend on the customer’s location within the service region; in addition, this fairness must be mathematically guaranteed. We first consider a variant of the problem with two customer types. Leveraging recently developed near-optimal strategies for a classical dynamic yield management problem, we develop a fair and intuitive delivery request acceptance policy that rejects all customers of one type if a particular threshold is exceeded. We use the Beardwood-Halton-Hammersley Theorem to derive an asymptotic performance guarantee, then extend the policy to settings with arbitrarily many customer types. Operational simulations, including a case study on a real-world road network, suggest that the proposed threshold policy achieves higher average profits and produces less operational variability when compared to other provably fair heuristics while also maintaining transparency and managerial interpretability. We discuss practical and theoretical implications including mathematical conjectures for further analysis.