Advanced optimization algorithms for split delivery vehicle routing problem with three-dimensional loading constraints

Abstract

The Split Delivery Vehicle Routing Problem with Three-Dimensional Loading Constraints (3L-SDVRP) is a combination of the Split Delivery Vehicle Routing Problem (SDVRP) and the Three-Dimensional Packing Problem (3DPP), presenting significantly more challenges than the original two problems. There are two objectives: minimizing the number of vehicles used (or maximizing the average loading rate), and minimizing total travel distance. Solving the 3L-SDVRP is crucial for enhancing logistics and transportation efficiency across various industries, impacting both operational efficiency and cost-effectiveness. This thesis advances the state-of-the-art in solving the 3L-SDVRP through several key contributions. First, we introduce novel and efficient search operators, specifically the Hierarchical Neighborhood Filtering (HNF) and Adaptive Knowledge-guided Search (AKS) operators. These operators enhance solution diversity and search efficiency in our evolutionary algorithm, significantly improving overall algorithm performance. Second, we propose innovative methods to balance exploration and exploitation in meta-heuristic algorithms, achieving this balance in both global and local search-based algorithms. Third, we develop a new multi-objective algorithm, the Pareto-based Evolutionary Algorithm with Concurrent Crossover and Hierarchical Neighborhood Filtering Mutation (PEAC-HNF). This algorithm effectively addresses the 3L-SDVRP under limited computational resources by optimizing multiple objectives simultaneously, providing decision-makers with a diverse set of optimal solutions. Fourth, we propose new local search-based algorithms that enhance the state-of-the-art SDVRLH2 algorithm, significantly reducing computational resource consumption while maintaining a high solution quality. These improvements are achieved through the integration of adaptive strategies and heuristic adjustments tailored to the specific characteristics of the 3L-SDVRP. Fifth, we introduce an adaptive interactive routing-packing strategy, which combines the strengths of existing approaches to improve solution quality. This strategy adaptively adjusts packing patterns based on the vehicle's remaining space and the space requirements of different packing pattern at each node, ensuring efficient space utilization and reducing the number of vehicles required. Sixth, comprehensive experimental studies demonstrate the superior performance of our proposed algorithms across various benchmark datasets. The results indicate that our methods provide higher quality solutions and, in many cases, outperform existing methods in terms of computational efficiency, especially for large-scale problems. This thesis presents a suite of methodologies for addressing the 3L-SDVRP, each with its distinct advantages and applicability to specific industrial scenarios. For smaller-scale problems that necessitate a multi-objective approach to generate a diverse set of solutions with varying degrees of balance between the two objectives, the PEAC-HNF algorithm proposed in Chapter 3 is recommended. In contrast, for larger-scale problems where computational resources are scarce, the efficient local search algorithm presented in Chapter 4 is a more suitable choice. For larger-scale problems that require high-quality solutions, the AKS algorithm proposed in Chapter 6 is the preferred option. Furthermore, given the importance of the interaction between the packing and routing processes in solving the 3L-SDVRP, the adaptive routing-packing strategy proposed in Chapter 5 offers a flexible approach that can be broadly applied across various search algorithms, enhancing their overall effectiveness. Overall, the methods proposed in this thesis, including the HNF and AKS operators and the balance of exploration and exploitation, are flexible and applicable to other combinatorial optimization problems. This thesis contributes to the field of combinatorial optimization by providing robust, efficient, and adaptive solutions to the complex 3L-SDVRP, with significant implications for industrial applications and future research directions.