A granular iterated local search for the asymmetric single truck and trailer routing problem with satellite depots at DHL Group

• DOI: 10.1002/net.22178
• Publication Date: 2023-08-19T05:44:29Z
• Authors: Rossana Cavagnini; Michael Schneider; Alina Theiß
• Keywords: Iterated local search; Robustness; Iterated function

Abstract To plan the postal deliveries of our industry partner DHL Group (DHL), single truck and trailer routing problem with satellite depots (STTRPSD) is solved to optimize mail carriers routes. In this application context, instances feature a high number customers satellites, they are based on real street networks. This motivates study asymmetric STTRPSD (ASTTRPSD). The heuristic solution methods proposed in literature for can either solve only symmetric variant, or it unclear whether also be used ASTTRPSD. We introduce an iterated local search, called ILS‐ASTTRPSD, which generates different first‐level tours perturbation phase, improves second‐level search phase. speed up granular neighborhoods used. computational results from prove capability ILS‐ASTTRPSD return high‐quality solutions. On instances, significantly decreases total travel times returns solutions structure compared ones provided by DHL. Based these differences, we give recommendations how could design more efficient carrier practices. Dedicated experiments reveal that considering parking loading when solving ASTTRPSD leads lower times, ignoring counterproductive than times. Moreover, assess robustness under time fluctuations. Finally, derive properties optimal contain multiple rooted at same spot correspond pure traveling salesman problem.