A new two-phase heuristic for a problem of food distribution with compartmentalized trucks and trailers

This paper presents a new formulation for the routing problem in which the available fleet consists of trucks and trailers divided into compartments. Solving the model for large instances is computationally expensive. Therefore, we introduce and implemented a two-phase heuristic algorithm. In the first phase, an initial solution is generated through a constructive heuristic algorithm based on concepts from the classic Clarke–Wright algorithm. In the second phase, the initial solution is improved by an iterated tabu search metaheuristic. Our algorithm was tested on 21 instances that were converted from the classic truck and trailer routing problem. The results of our computational study prove the effectiveness of our proposal; the algorithm always finds a feasible solution, which in small-sized problems it is proven to be of good quality. In addition, the algorithm outperforms previous approaches for some truck and trailer routing problem instances. Furthermore, an application of the proposed model and heuristic is demonstrated in the field of agricultural logistics by comparing the obtained resultsLaura Davila-Pena's research was funded by the Ministry of Education, Culture and Sports of Spain (contract FPU17/02126). David R. Penas' research was funded by the Xunta de Galicia (post-doctoral contract ED481B-2019-010). This work was also supported by the ERDF (MINECO/AEI grant MTM2017-87197-C3-3-P) and by the Xunta de Galicia (Competitive Reference Group ED431C 2017/38 and ED431C 2021/24)S