Effective loading in combined vehicle routing and container loading problems. (January 2023)

• Record Type: Journal Article
• Authors: Krebs, Corinna; Ehmke, Jan Fabian; Koch, Henriette
• Is Part Of: Computers & operations research. Volume 149(2023)
• Publication Date: 2023-01
• Subjects: 90-04 -- 90-05; 3D loading -- Vehicle routing problem -- Deepest-Bottom-Left-Fill -- 3L-VRPTW; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105988
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: This paper addresses more effective loading within the 3L-VRPTW, which is a combination of the vehicle routing problem with time windows and 3D loading constraints. We use a hybrid algorithm consisting of an outer Adaptive Large Neighborhood Search tackling the routing problem in combination with an inner Deepest-Bottom-Left-Fill algorithm solving the container loading problem. We propose and compare three new variants for the Deepest-Bottom-Left-Fill algorithm which differ in the representation and storage of available possible placement positions and the shift of items. The possible placement positions can be determined either by available points so that (1) a non-overlapping check between the items is necessary, (2) by available free spaces, or (3) by using a Rectangle Tree (RTree), where items and their positions are stored in a tree. For computational studies, two well-known instance sets are used. The algorithms are evaluated and compared concerning their solution quality and performance. Hereby, the algorithm with free spaces receives the best results with the smallest runtime. Moreover, the impact of different loading constraints is analyzed showing that the LIFO and minimal supporting area constraints have significant effects on the total travel distance. Several new best solutions were found. All results are validated and published at GitHub. Highlights: Evaluation of three algorithms of Deepest-Bottom-Left-Fill algorithm (DBLF). Extensive computational studies for each algorithm (total 500'000 tests). Comparison of objective value, performance and impacts of loading constraints. DBLF with Spaces achieves superior results with best runtime.