A multi-start local search heuristic for the multi-period auto-carrier loading and transportation problem in Brazil

This paper deals with a variation of the Dynamic Multi-Period Auto-Carrier Transportation Problem (DM-PACTP) applied to real-world problems in the automotive industry in Brazil. The problem consists in find-ing the set of vehicles to be loaded into auto-carriers over a planning horizon of multiple days while minimizing the total transportation cost and fulfilling the loading constraints and meeting the delivery deadlines. Our study considers that the loading sequence policy at each stop is not required, and a mini-mum cost of auto-carriers is calculated on a per trip basis. We propose a Multi-Start Local Search Heuris-tic (MSLSH) to solve large-scale instances that arise in practice. Computational experiments compare the solutions obtained by means of our heuristic with the exact solutions for four medium size instances faced by a major Brazilian 3PL as well as with the manual allocation for two larger instances compris-ing 3,865 and 3,809 vehicles that could not be solved using the exact model. The results show that the proposed heuristic is able to obtain the optimal solutions for all the tested medium-sized instances. For large-sized instances that cannot be solved to optimality, we could obtain significant total transportation cost reductions (up to 15.40%) and lower number of vehicles delivered after the promised due date com-pared to the 3PL manual allocation. The 3PL was satisfied with the results and intends to deploy it into production environment as the MSLSH is robust, does not require extensive parameter calibration and it is easy to implement.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This paper presents a study on the Dynamic Multi-Period Auto-Carrier Transportation Problem (DM-PACTP) in the automotive industry in Brazil. The goal is to find the optimal vehicle loading plan that minimizes transportation cost and meets delivery deadlines. A Multi-Start Local Search Heuristic (MSLSH) is proposed to solve large-scale instances. Experimental results demonstrate the effectiveness of the heuristic, achieving optimal solutions for medium-sized instances and significant cost reductions for large-sized instances compared to manual allocation.