Districting in Last Mile Delivery: Route Creation Using SHPP-Based Algorithms

Districting can reduce the complexities of delivery problems by segmenting its dimensions while facilitating drivers’ familiarity with their work areas, fostering personal connections with customers, and enhancing satisfaction. This paper introduces and evaluates multiple heuristic approaches for route creation, to identify the most efficient method for intra and inter-districting routing. Out of 18 tested variants, the best-performing developed approach used a Lin-Khernigan-based heuristic, later converting it to a Shortest Hamiltonian Path in each district, creating inter-district connections to a hypothetical medoid in the next district to visit and utilizing asymmetric road distances. Although sub-optimal, the results obtained were satisfactory and the best components for route creation were identified. The models were developed and tested using real-world data from a parcel delivery company operating in the Porto metropolitan area of Portugal.