# Probability estimation and structured output prediction for learning preferences in last mile delivery

arXiv: https://arxiv.org/abs/2201.10269 · HTML: https://mlsanity.com/paper/2201.10269/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 25 Jan 2022.

## Builds on (most cited first, 8 of 8)

- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [RNA Secondary Structure Prediction By Learning Unrolled Algorithms](https://mlsanity.com/paper/2002.05810/) (2020)
- [Constrained Local Search for Last-Mile Routing](https://mlsanity.com/paper/2112.15192/) (2021)
- [Vehicle routing by learning from historical solutions](https://mlsanity.com/paper/1909.07893/) (2019)
- [Data Driven VRP: A Neural Network Model to Learn Hidden Preferences for VRP](https://mlsanity.com/paper/2108.04578/) (2021)

## Built on by (most cited first, 1 of 1)

- [Inverse Optimization for Routing Problems](https://mlsanity.com/paper/2307.07357/) (2023)

## Abstract (arXiv)

We study the problem of learning the preferences of drivers and planners in the context of last mile delivery. Given a data set containing historical decisions and delivery locations, the goal is to capture the implicit preferences of the decision-makers. We consider two ways to use the historical data: one is through a probability estimation method that learns transition probabilities between stops (or zones). This is a fast and accurate method, recently studied in a VRP setting. Furthermore, we explore the use of machine learning to infer how to best balance multiple objectives such as distance, probability and penalties. Specifically, we cast the learning problem as a structured output prediction problem, where training is done by repeatedly calling the TSP solver. Another important aspect we consider is that for last-mile delivery, every address is a potential client and hence the data is very sparse. Hence, we propose a two-stage approach that first learns preferences at the zone level in order to compute a zone routing; after which a penalty-based TSP computes the stop routing. Results show that the zone transition probability estimation performs well, and that the structured output prediction learning can improve the results further. We hence showcase a successful combination of both probability estimation and machine learning, all the while using standard TSP solvers, both during learning and to compute the final solution; this means the methodology is applicable to other, real-life, TSP variants, or proprietary solvers.