The Vehicle Routing Problem with Soft Time Windows (VRPSTW) is a critical logistics optimization challenge, balancing time flexibility and penalty costs. This paper proposes an improved parallel optimization approach, the Parallel Adaptive Local Search and Wolf Pack Algorithm (PALS-WPA), to effectively solve VRPSTW. PALS-WPA utilizes two independent threads for adaptive local search and wolf pack optimization, leveraging their complementary strengths. The local search module processes multiple initial solutions in parallel, dynamically adjusting the neighborhood search strategy to avoid local optima and explore the solution space more deeply. The wolf pack optimization enhances global search quality through foraging and besieging strategies. Experimental results demonstrate that PALS-WPA significantly outperforms mainstream algorithms on both random and benchmark datasets, showcasing its superior efficiency and solution quality.