A heuristic approach to feasibility verification for truck loading

This paper introduces an industrial decision problem emerging from daily operations of a company which provides its clients in Europe and Latin America with machine rentals. The company faces several challenges in distribution of these machines using a fleet of trucks. The trucks with a non-convex loading surface are loaded with multiple machines of irregular shapes to be picked up or delivered to/from customer or depot locations. Within the algorithmic framework utilized by the company, for each route generated, one must verify whether or not it is possible to load the corresponding machines onto the truck without violating certain restrictions. The aim of this paper is to develop a competitive and automated algorithm capable of efficiently classifying load plans in a very restrictive scenario. For this purpose, we extend a well-known heuristic algorithm from the two-dimensional (2D) packing literature and compare its performance with two other methods: the original 2D packing method and the current method employed by the company in practice. The computational experiments are performed in a set of candidate load plans provided by the company. We observe that the newly introduced adaptation outperforms the other methods and correctly classifies 90% of the given load plans provided.