Location-routing problem for robot deliveries with customer choices and hybrid facilities

To model an innovative last-mile delivery system, we study a location-routing problem for robot deliveries with customer choices and hybrid facilities (LRP-RD-CC-HF). This system integrates two types of facilities with partial functional overlap for delivery services, namely, unattended parcel lockers and multi-functional delivery stations. Customer preferences are characterized by their service choices: home delivery within specific time windows, package pickup at designated facilities, or a flexible option that allows for either. We develop a modified variable neighborhood search heuristic for the LRP-RD-CC-HF based on problem-specific operators and several key search features. We evaluate our methodology both on LRP (Location-Routing Problem) and LoRP (Location or Routing Problem) benchmark instances. Results demonstrate that our algorithm is competitive against nine state-of-the-art algorithms on LRP benchmarks and outperforms the branch-and-price and adaptive large neighborhood search methods on LoRP benchmarks. We further validate the effectiveness of the proposed algorithm components using real-life delivery context instances. An extensive computational study also indicates the effectiveness of combining hybrid facilities. Finally, several valuable managerial insights are obtained for advancing the last-mile delivery system.