A fast simulated annealing heuristic for the multi-depot two-echelon vehicle routing problem with delivery options

ABSTRACTWe studied a variant of the vehicle routing problem (VRP) arising in last-mile distribution, called the multi-depot two-echelon vehicle routing problem with delivery options (MDTEVRP-DO). The MDTEVRP-DO involves two decision levels: (i) designing routes for a fleet of vehicles located in multiple depots to transport customer demands to a set of satellites and (ii) routing a fleet of vehicles from the satellites to serve the final customers. Nowadays, a relevant feature of the problem characterizing delivery services is that customers can collect their packages at pickup stations near their homes or workplaces. We designed an effectively simulated annealing (SA) heuristic for the problem. The new algorithm was extensively tested on benchmark instances from the literature, and its results were compared with those of start-of-the-art algorithms. The results show that the proposed SA obtains 30 out of the 36 best solutions for the MDTEVRP-DO benchmark instances. Moreover, its computation performance is superior to state-of-the-art algorithms for the MDTEVRP-DO.KEYWORDS: Two-echelon vehicle routing problemdelivery optionsimulated annealing Disclosure statementNo potential conflict of interest was reported by the author(s).Additional informationFundingThe work of the first author was partially supported by the Ministry of Science and Technology of the Republic of China (Taiwan) under Grant MOST 111-2410-H-011-020-MY3 and the Center for Cyber-Physical System Innovation from the Featured Areas Research Center Program within the framework of the Higher Education Sprout Project by the Ministry of Education (MOE) of the Republic of China (Taiwan). The second author is grateful to the Ministry of Science and Technology of the Republic of China (Taiwan) for financially supporting this research under Grant MOST 109-2410-H-182-009-MY3/NSTC 112-2410-H-182-002-MY3.