SOLVING ROUTING AND THREE-DIMENSIONAL PACKING PROBLEMS: A HYBRID APPROACH

This research addresses the integration of the vehicle routing problem with the three-dimensional packing problem, focusing on developing an efficient approach to verify the feasibility of packing all the boxes demanded by the customers visited on each route generated by the routing problem. For the packing, in addition to the classical constraints on container size and non-overlapping boxes, constraints on delivery order, stability, and cargo fragility are considered. The feasibility analysis of the packing is performed in steps, starting with lower bounds established in the scientific literature to identify invalid routes quickly. If infeasibility is not proven, other strategies are applied, including packing heuristics and an integer programming mathematical model. Data adapted from instances of the literature are used to analyze the efficiency of the proposed approach in computational experiments. The authors would like to thank FAPESP (Proc. Nº. 2023/16405-1) for the financial support.