Optimizing the packing strategy for parcel delivery vans

Abstract

The increasing popularity of e-commerce has led to a greater emphasis on improving parcel delivery processes. Among the various stages of the delivery process, packing parcels into delivery vans affects the delivery time. The efficiency of delivery is optimized when each parcel is conveniently accessible upon arrival, thereby minimizing the requirement for additional repacking time. Therefore, streamlining parcel packing within delivery vehicles is a crucial aspect of improving overall delivery times in e-commerce. This thesis focuses on developing a packing solution that conforms to the the Last-In-First-Out (LIFO) principle, which is defined as ensuring that a parcel can be accessed by the delivery driver as soon as they reach the destination of the parcel. This is described as the 3D-Bin Packing Problem with Loading Constraints (3L-BPP). To solve this problem, a formulation of a Mixed Integer Linear Program (MILP) has been developed. To improve the speed and accuracy of the solution, a novel placement heuristic has been created. This heuristic is derived from the established Distance to the Front-Top-Right Corner (DFTRC)-2 method and is designed to generate an initial solution.

Both the MILP and the heuristic are tested on a data set of 789 distinct rides, provided by a Dutch postal company. The results demonstrate that (a modified version of) the heuristic successfully generated an initial solution for all rides in the dataset, with 98.9% being found within 3 seconds, and for the remaining 1.1%, the inclusion of a Genetic Algorithm led to a solution being found within 90 seconds. By using the heuristic to establish an initial solution that is then refined through optimization techniques for the MILP, the findings indicate that this approach yields the best outcomes in minimizing the number of incorrectly positioned parcels.