The Pallet-Packing Vehicle Routing Problem

This article introduces and solves a new transportation problem called the pallet-packing vehicle routing problem (PPVRP). PPVRP belongs to the category of practical routing models integrated with loading constraints, and assumes that customers raise a deterministic demand in the form of three-dimensional rectangular boxes. It is aimed at determining the optimal vehicle routes for satisfying customer demand. Regarding the packing aspects, transported boxes are not directly loaded into the vehicle-loading spaces; instead, they are feasibly stacked into pallets that are then loaded onto the vehicles before initiating their tours. Belonging to the class of combined routing and packing models, PPVRP is very hard to be optimally solved within manageable computational time; thus, we focused on heuristic approaches for both the routing and packing aspects of the problem. More specifically, PPVRP is solved via a local search metaheuristic strategy based on the regional aspiration criteria of tabu search. To determine feasible pallet-packing arrangements, we employ an efficient packing heuristic approach. The algorithm is accelerated by storing collected packing feasibility information into memory components. The proposed solution approach is tested on newly introduced benchmark instances derived from well-studied vehicle routing data sets, as well as real-world problems.