A heuristic algorithm for the auto-carrier transportation problem

The delivery of vehicles to dealers is one of the major tasks in the vehicle production industry. It has relied on transportation companies that use special tractor-trailer trucks called auto-carriers. One of the main problems these companies have to solve is the optimal loading and routing of the auto-carriers, referred to as the Auto-Carrier Transportation (ACT) problem. In this paper we provide an integer programming formulation of the ACT problem and show that the problem is NP-hard in the strong sense. A three-step heuristic procedure strongly based on the IP formulation, which considers loading, vehicle selection, and routing aspects, is proposed. An application to a real case study of a vehicle transportation company located in northern Italy is given, with an average deviation lower than 3 percent from an upper bound on the optimal solution value.