Last-Mile Decomposition Heuristics with Multi-Period Embedded Optimization Models

This paper investigates last-mile delivery and explores hybrid distributed computational models for routing and scheduling delivery services and assigning delivery-points to deliverymen over multiple time periods. The objective of these models is to minimize the number of deliverymen hired for providing delivery services over multiple periods while satisfying predetermined time limits. This paper describes the development of multiple traveling deliverymen approaches, multi-period optimization models, and a multi-period distributed algorithm, to optimize routing and scheduling for last-mile deliveries. This paper utilizes a computer-aided modeling system to facilitate the proposed distributed approach, which offers an optimization model for large numbers of delivery-points and helps in performing limited computation as required to minimize the memory usage and provide efficiently solvable models within acceptable durations of execution. To illustrate the solvability of the proposed approach and scalability to large instances, 26 case problems are presented for last-mile delivery services. The key results include optimized routing and scheduling, a minimum number of deliverymen, and a significant reduction in computational effort and time.