Local Search with Learned Constraints for Last Mile Routing

We describe our submission to the Amazon Last Mile Routing Research Challenge. The optimization method we employ utilizes a simple and ecient penalty-based local-search algorithm, frst developed by Helsgaun to extend the LKH traveling salesman problem code to general vehicle-routing models. We further develop his technique to handle combinations of routing constraints that are learned from an analysis of historical data. On a target set of 1,107 training instances, our submitted code achieves a mean score of 0.01989 and a median score of 0.00752. The simplicity of the method may make it suitable for applications where machine learning can discover rules that are expected (or desired) in high-quality solutions.