A three-phase heuristic for last-mile delivery with spatial-temporal consolidation and delivery options

The parcel demand in last-mile delivery increases sharply with the growth of e-commerce, which has been accelerated by the COVID-19 pandemic. The current delivery scheme follows a first-in-first-out (FIFO) rule, i.e., parcels arriving at different periods for the same customer are likely to become separate deliveries, which incurs a high transportation cost. To address this, an innovative spatial-temporal based consolidation (STC) strategy is proposed to consolidate parcels based on their delivery due dates and spatial distributions to reduce redundant delivery trips and lower the total cost. In addition to reducing the operational cost, improving customer satisfaction by offering diversified delivery preferences is key for enterprises to maintain competitiveness. This paper investigates a new variant of last-mile delivery that integrates parcel consolidation and flexible delivery options, including serving through home delivery and parcel lockers. A bi-objective model is formulated to balance the total cost and the service satisfaction. Then a three-phase heuristic is developed to solve the model. In the three-phase heuristic, the first phase determines the parcel distribution schedule, delivery option and node visiting schedule, while the second one optimizes vehicle routing by solving a series of traveling salesman problems. The third phase improves the solution by applying a general improvement routing procedure. The performance of the three-phase heuristic is demonstrated through extensive computational experiments based on a realistic parcel distribution network in the city of Melbourne, Australia. Experimental results reveal that the STC strategy has significant advantages over the FIFO scheme. Moreover, the advantage increases with the unit transportation cost, vehicle capacity and consumer distribution dispersion.