Learn global and optimize local: a data-driven methodology for last-mile routing

DOI10.1016/J.COR.2023.106312MaRDI QIDQ6047849zbMATH OpenOpenAlexFDO

Authors Mayukh Ghosh, Alex Kuiper, Roshan Mahes, Donato Maragno

Publication date 13 September 2023

Published in Computers \& Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2112.01937

zbMATH Keywords

data-driven optimizationlast-mile logisticsnavigationroute predictiontraveling salesman problem

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Abstract: In last-mile routing, the task of finding a route is often framed as a Traveling Salesman Problem to minimize travel time and associated cost. However, solutions stemming from this approach do not match the realized paths as drivers deviate due to navigational considerations and preferences. To prescribe routes that incorporate this tacit knowledge, a data-driven model is proposed that aligns well with the hierarchical structure of delivery data wherein each stop belongs to a zone - a geographical area. First, on the global level, a zone sequence is established as a result of a minimization over a cost matrix which is a weighted combination of historical information and distances (travel times) between zones. Subsequently, within zones, sequences of stops are determined, such that, integrated with the predetermined zone sequence, a full solution is obtained. The methodology is particularly promising as it propels itself within the top-tier of submissions to the Last-Mile Routing Research Challenge, while it maintains an elegant decomposition that ensures a feasible implementation into practice. The concurrence between prescribed and realized routes underpins the adequateness of a hierarchical breakdown of the problem and the fact that drivers make a series of locally optimal decisions when navigating. Furthermore, experimenting with the balance between historical information and distance exposes that historic information is pivotal in deciding a starting zone of a route. The experiments also reveal that at the end of a route, historical information can best be discarded, making the time it takes to return to the station the primary concern.

Recommendations

• Model and algorithm for bilevel multisized terminal location‐routing problem for the last mile delivery
• Last-mile shared delivery: a discrete sequential packing approach
• Exact Approach for Integrated Delivery Optimization of E-Commerce and Online-to-Offline Parcels
• A tailored Benders decomposition approach for last-mile delivery with autonomous robots
• A two-echelon location routing problem with mobile satellites for last-mile delivery: mathematical formulation and clustering-based heuristic method

Cites work

• A generalized insertion heuristic for the travelling salesman problem with time windows
• A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• A survey on matheuristics for routing problems
• Divide and conquer strategies for parallel TSP heuristics
• Heuristics for the traveling salesman problem with pickup and delivery
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Integer Programming Formulation of Traveling Salesman Problems
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• The Covering Salesman Problem
• The Euclidean traveling salesman problem is NP-complete
• The traveling-salesman problem
• The truck dispatching problem

Cited in

(1)

• Adaptive appointment scheduling with periodic updates

This page was built for publication: Learn global and optimize local: a data-driven methodology for last-mile routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6047849)