A heuristic-attention method for location-routing problems with shared pick-up stations in green last-mile delivery

Abstract

This paper investigates the location-routing problem for a green last-mile delivery system (LRP-GLD) with shared pick-up stations (PUSs). LRP-GLD first requires determining the locations of a set of opened PUSs, followed by solving the capacitated delivery routing problem given the spatial layout of the PUSs. The overall objective is to minimize the sum of the fixed PUS opening cost, service cost, and delivery costs while satisfying the load capacity and battery capacity constraints of the electric delivery vehicles (EDVs). To effectively address the LRP-GLD with a combinatorially large solution space, we develop a two-stage method that combines simulated annealing algorithm and attention mechanism (SA-AM). At the lower operational stage, an attention model with an encoder-decoder architecture and a customized embedding strategy is trained to solve the delivery routing problem. The attention parameters are updated and optimized through a policy gradient method with an input-dependent baseline function. At the upper strategic planning stage, we employ simulated annealing (SA) to address the PUS location problem, where the performance of the location solution for the routing problem is evaluated by iteratively invoking the pre-trained attention model. Numerical experiments are conducted on randomly generated delivery networks to examine the efficiency and feasibility of the proposed solution method. A comprehensive analysis is also performed to explore the impacts of the designed delivery system and several key parameters on the system performance and provide managerial insights for decision-makers.