Abstract
This paper proposes a parallel hybrid metaheuristic, named PH-SHOWOA, that integrates the Spotted Hyena Optimizer (SHO) and the Whale Optimization Algorithm (WOA) to solve the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Windows (VRPSPDTW). The proposed method leverages the strength of both algorithms: SHO primarily supports population-level diversification, while WOA focuses on best-guided intensification. An adaptive probability control mechanism dynamically regulates the interaction between these two search behaviours during the optimization process. To further enhance robustness and mitigate premature convergence, the framework incorporates simulated-annealing-based acceptance, periodic local search, and population diversification strategies. A parallel implementation enables concurrent solution updates and local refinements, improving computational efficiency on medium-scale instances. The VRPSPDTW is formulated using a hierarchical lexicographic objective that prioritizes minimizing the number of vehicles, followed by total travel distance. Extensive experiments on 65 well-known benchmark instances demonstrate that PH-SHOWOA consistently outperforms standalone SHO and WOA, achieving an average reduction in total distance of over 10%. Compared with advanced algorithms such as Co-GA, MA-FIRD, and ACO-DR, PH-SHOWOA exhibits competitive and often superior performance. Notably, it achieves the lowest total distance on several Rdp and Cdp instances and performs well in centralized-demand scenarios. Furthermore, comprehensive non-parametric statistical tests are conducted to verify the effectiveness and robustness of the proposed method.